Online scheduling on an unbounded parallel-batch machine to minimize the weighted makespan

Abstract

In this paper we study the online over-time scheduling on an unbounded parallel-batch machine to minimize the weighted makespan. First, we show that the general problem has a low bound 2 and then design a 4-competitive online algorithm. Furthermore, we consider a special case in which the jobs have agreeable processing times and weights. When all jobs have the same weights (the task is to minimize the makespan), an online algorithm with the best possible competitive ratio $\frac{\sqrt{5}+1}{2}\approx 1.618$ has been established in the literature. We show that, after a slightly modification, this known online algorithm also has the best possible competitive ratio $\frac{\sqrt{5}+1}{2}\approx 1.618$ for our problem. Finally, we introduce limited restarts into the above special case and present an online algorithm with a better competitive ratio $\frac{11}{7}\approx 1.571$.