کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
475847 | 699383 | 2010 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A two-stage flow shop scheduling problem on a batching machine and a discrete machine with blocking and shared setup times A two-stage flow shop scheduling problem on a batching machine and a discrete machine with blocking and shared setup times](/preview/png/475847.png)
Motivated by applications in iron and steel industry, we consider a two-stage flow shop scheduling problem where the first machine is a batching machine subject to the blocking constraint and the second machine is a discrete machine with shared setup times. We show that the problem is strongly NP-hard when the objective is to minimize the makespan. When solved with a heuristic priority rule, the worst case ratio with the minimum makespan is 2. For a more general objective, the minimization of a linear combination of the makespan and the total blocking time, a quadratic mixed integer program is presented first. Then we pinpoint two cases with polynomial time algorithms: the case without blocking constraint and the case with a given job sequence. Also for the general objective, we analyze an approximation algorithm. Finally, we evaluate the algorithms, giving experimental results on randomly generated test problems.
Journal: Computers & Operations Research - Volume 37, Issue 5, May 2010, Pages 960–969