期刊
COMPUTERS & OPERATIONS RESEARCH
卷 37, 期 5, 页码 960-969出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2009.08.001
关键词
Scheduling; Batching machine; Blocking; Setup time
类别
资金
- National Natural Science Foundation for Distinguished Young Scholars of China [70425003]
- National 863 High-Tech Research and Development Program of China [2006AA04ZI74]
- National Natural Science Foundation of China [60674084]
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. (C) 2009 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据