A best possible deterministic on‐line algorithm for minimizing makespan on parallel batch machines

We study on‐line scheduling on parallel batch machines. Jobs arrive over time. A batch processing machine can handle up to B jobs simultaneously. The jobs that are processed together form a batch and all jobs in a batch start and are completed at the same time. The processing time of a batch is given by the processing time of the longest job in the batch. The objective is to minimize the makespan. We deal with the unbounded model, where B is sufficiently large. We first show that no deterministic on‐line algorithm can have a competitive ratio of less than $1+(\sqrt{m^2+4}‐m)/2$ , where m is the number of parallel batch machines. We then present an on‐line algorithm which is the one best possible for any specific values of m.