Two-machine no-wait flow shop scheduling with missing operations
成果类型：
Article
署名作者：
Glass, CA; Gupta, JND; Potts, CN
署名单位：
University of Southampton; Ball State University
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.24.4.911
发表日期：
1999
页码：
911-924
关键词：
摘要：
This paper considers the no-wait scheduling of n jobs in a two-machine flow shop, where some jobs require processing on the first machine only. The objective is to minimize the maximum completion time, or makespan. In view of its NP-hardness, we propose and analyze heuristic algorithms. Our main result is an O(n log n)-time heuristic which generates a schedule with makespan no more than 4/3 times that of an optimal schedule. This heuristic solves optimally the subproblem involving the jobs with no missing operations, using, for example, the well-known algorithm of Gilmore and Gomory, and then uses a list scheduling procedure to insert the remaining jobs in the schedule. A new proof technique is employed in the worst-case analysis, which has potential application in a variety of bin packing and scheduling problems.
来源URL：