On-line algorithms for minimizing makespan on batch processing machines

We consider the problem of scheduling jobs on-line on batch processing mach ines with dynamic job arrivals to minimize makespan. A batch processing mac hine can handle up to B jobs simultaneously. The jobs that are processed to gether form a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing ti me of any job in the batch. Each job becomes available at its arrival time, which is unknown in advance, and its processing time becomes known upon it s arrival. In the first part of this paper, we address the single batch pro cessing machine scheduling problem. First we deal with two variants: the un bounded model where B is sufficiently large and the bounded model where job s have two distinct arrival times. For both variants, we provide on-line al gorithms with worst-case ratio (root5 + 1)/2 (the inverse of the Golden rat io) and prove that these results are the best possible. Furthermore, we gen eralize our algorithms to the general case and show a worst-case ratio of 2 . We then consider the unbounded case for parallel batch processing machine scheduling. Lower bounds are given, and two on-line algorithms are present ed. (C) 2001 John Wiley B Sons, Inc. Naval Research Logistics 48: 241-258, 2001.