Portal de Periódicos da CAPES

Two-Machine No-Wait Flow Shop Scheduling with Missing Operations

1999; Institute for Operations Research and the Management Sciences; Volume: 24; Issue: 4 Linguagem: Inglês

10.1287/moor.24.4.911

1526-5471

Celia A. Glass, Jatinder N.D. Gupta, Chris N. Potts,

Assembly Line Balancing Optimization

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.