Online batch scheduling on parallel machines with delivery times

摘要

We study the online batch scheduling problem on parallel machines with delivery times. Online algorithms are designed on m parallel batch machines to minimize the time by which all jobs have been delivered. When all jobs have identical processing times, we provide the optimal online algorithms for both bounded and unbounded versions of this problem. For the general case of processing time on unbounded batch machines, an online algorithm with a competitive ratio of 2 is given when the number of machines m = 2 or m = 3, respectively. When m ≥ 4, we present an online algorithm with a competitive ratio of 1.5 + o(1).