Minimizing Makespan with Start Time-Dependent Jobs in a Two-Machine Flow Shop
محل انتشار: ماهنامه بین المللی مهندسی، دوره: 29، شماره: 6
سال انتشار: 1395
نوع سند: مقاله ژورنالی
زبان: انگلیسی
مشاهده: 473
فایل این مقاله در 10 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_IJE-29-6_007
تاریخ نمایه سازی: 12 دی 1395
چکیده مقاله:
The purpose of this paper is to consider the problem of scheduling a set of start time-dependent jobs ina two-machine flow shop, in which the actual processing times of jobs increase linearly according totheir starting time. The objective of this problem is to minimize the makespan. The problem is knownto be NP-hardness; therefore, there is no polynomial-time algorithm to solve it optimally in areasonable time. So, a branch-and-bound algorithm is proposed to find the optimal solution by meansof dominance rules, upper and lower bounds. Several easy heuristic procedures are also proposed toderive near-optimal solutions. To evaluate the performance of the proposed algorithms, thecomputational experiments are extracted based on the recent literature. Deteriorating jobs lead to anincrease in the makespan of the problems; therefore, it is important to obtain the optimal or near-optimalsolution. Considering the complexity of the problem, the branch-and-bound algorithm is capable of solvingproblems of up to 26 jobs. Additionally, the average error percentage of heuristic algorithms is less than1.37%; therefore, the best one is recommended to obtain a near-optimal solution for large-scale problems.
کلیدواژه ها:
Linear Deteriorating JobsStart Time-DependentFlow ShopMakespanBranch and BoundHeuristics
نویسندگان
A.A Jafari
Department of Industrial Engineering, Faculty of Engineering, Yazd University, Yazd, Iran
H Khademi Zare
Department of Industrial Engineering, Faculty of Engineering, Yazd University, Yazd, Iran
M.M Ltfi
Department of Industrial Engineering, Faculty of Engineering, Yazd University, Yazd, Iran
R Tavakkoli-Moghaddam
School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran