Optimal on‐line algorithms for one batch machine with grouped processing times

In this paper, we study on‐line scheduling problems on a batch machine with the assumption that all jobs have their processing times in [p, (1+φ)p], where p>0 and $\phi =(\sqrt{5}‐1)/2$ . Jobs arrive over time. First, we deal with the on‐line problem on a bounded batch machine with the objective to minimize makespan. A class of algorithms with competitive ratio $(\sqrt{5}+1)/2$ are given. Then we consider the scheduling on an unbounded batch machine to minimize the time by which all jobs have been delivered, and provide a class of on‐line algorithms with competitive ratio $(\sqrt{5}+1)/2$ . The two class of algorithms are optimal for the problems studied here.