On‐line algorithms for minimizing makespan on batch processing machines

• DOI: 10.1002/nav.5
• Publication Date: 2004-10-29T10:55:38Z
• Authors: Gouchuan Zhang; Xiaoqiang Cai; C.K. Wong
• Keywords: Batch processing; Competitive Analysis

Abstract We consider problem of scheduling jobs on‐line on batch processing machines with dynamic job arrivals to minimize makespan. A machine can handle up B simultaneously. The that are processed together from a batch, and all in start complete at the same time. time is given by longest any batch. Each becomes available its arrival time, which unknown advance, known upon arrival. In first part this paper, we address single problem. First deal two variants: unbounded model where sufficiently large bounded have distinct times. For both variants, provide algorithms worst‐case ratio $(\sqrt{5}+1)/2$ (the inverse Golden ratio) prove these results best possible. Furthermore, generalize our general case show 2. then for parallel scheduling. Lower bound given, presented. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 241–258,