Minimizing Makespan with Start Time Dependent Jobs in a Two Machine Flow Shop
(ندگان)پدیدآور
Tavakkoli-Moghaddam, RezaLotfi, Mohammad MehdiKhademi Zare, HasanJafari, Abbasa-Aliنوع مدرک
Textزبان مدرک
Englishچکیده
[if gte mso 9]> The purpose of this paper is to consider the problem of scheduling a set of start time-dependent jobs in a two-machine flow shop, in which the actual processing times of jobs increase linearly according to their starting time. The objective of this problem is to minimize the makespan. The problem is known to be NP-hardness[ah1] ; therefore, there is no polynomial-time algorithm to solve it optimally in a reasonable time. So, a branch-and-bound algorithm is proposed to find the optimal solution by means of dominance rules, upper and lower bounds. Several easy heuristic procedures are also proposed to derive near-optimal solutions. To evaluate the performance of the proposed algorithms, the computational experiments are extracted based on the recent literature. Deteriorating jobs lead to an increase in the makespan of the problems; therefore, it is important to obtain the optimal or near-optimal solution. Considering the complexity of the problem, the branch-and-bound algorithm is capable of solving problems of up to 26 jobs. Additionally, the average error percentage of heuristic algorithms is less than 1.37%; therefore, the best one is recommended to obtain a near-optimal solution for large-scale problems.
کلید واژگان
Linear deteriorating jobsStart time dependent
Flow shop
makespan
Branch and bound
heuristic
شماره نشریه
6تاریخ نشر
2016-06-011395-03-12
ناشر
Materials and Energy Research Centerسازمان پدید آورنده
, University of TehranIndustrial Engineering, Yazd University
IE yazd, Yazd University
, Yazd University
شاپا
1025-24951735-9244