Single machine batch scheduling with release times

Motivated by a high-throughput logging system, we investigate the single machine scheduling problem with batching, where jobs have release times and processing times, and batches require a setup time. Our objective is to minimize the total flow time, in the online setting. For the online problem where all jobs have identical processing times, we propose a 2-competitive algorithm and we prove a corresponding lower bound. Moreover, we show that if jobs with arbitrary processing times can be processed in any order, any online algorithm has a linear competitive ratio in the worst case. A preliminary version of a part of this paper was presented at the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006). We gratefully acknowledge reviewers’ comments that helped to improve the presentation of this work. Supported by the Swiss SBF under contract no. C05.0047 within COST-295 (DYNAMO) of the European Union. Research carried out while B. Weber was affiliated with the Institute of Theoretical Computer Science, ETH Zurich.