Two-machine no-wait flow shop scheduling with missing operations

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 ob jective is to minimize the maximum completion time, or makespan. In view of its NP-hardness, we propose and analyze heuristic algorithms. Our main res ult is an O(n log n)-time heuristic which generates a schedule with makespa n no more than 4/3 times that of an optimal schedule. This heuristic solves optimally the subproblem involving the jobs with no missing operations, us ing, for example, the well-known algorithm of Gilmore and Gomory, and then uses a list scheduling procedure to insert the remaining jobs in the schedu le. A new proof technique is employed in the worst-case analysis, which has potential application in a variety of bin packing and scheduling problems.