A two-stage flow shop scheduling problem on a batching machine and a discrete machine with blocking and shared setup times

作者：Gong Hua; Tang Lixin^*; Duin C W

来源：Computers & Operations Research, 2010, 37(5): 960-969.

DOI：10.1016/j.cor.2009.08.001

• Scheduling
• Batching machine
• Blocking
• Setup time

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.

• 出版日期2010-5
• 单位东北大学