Minimizing Makespan with Start Time-Dependent Jobs in a Two-Machine Flow Shop

سال انتشار: 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