SCHEDULING BY POSITIONAL COMPLETION TIMES - ANALYSIS OF A 2-STAGE FLOW-SHOP PROBLEM WITH A BATCHING MACHINE

We consider a scheduling problem introduced by Ahmadi et al., Batching and scheduling jobs on batch and discrete processors, Operation Resea rch 40 (1992) 750-763, in which each job has to be prepared before it can be processed. The preparation is performed by a batching machine; it can prepare at most c jobs in each run; which takes an amount of ti me that is independent of the number and identity of the jobs ui?der p reparation. We present a very strong Lagrangian lower bound by using t he new concept of positional completion times. This bound can be compu ted in O(n log n) time only, where n is the number of jobs. We further present two classes of O(n log n) heuristics that transform an optima l schedule for the Lagrangian dual problem into a feasible schedule. A ny heuristic in one class has performance guarantee of 3/2. We further show that even the most naive heuristic in this class has a compellin g empirical performance. (C) 1998 The Mathematical Programming Society , Inc. Published by Elsevier Science B. V.