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 online algorithm can have a competitive ratio of less than 1 + (√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.