A best online algorithm for scheduling on two parallel batch machines

AbstractWe consider the online scheduling on two parallel batch machines with infinite batch size to minimize makespan, where jobs arrive over time. That is, all information of a job is not available until it is released. For this online scheduling problem, Nong et al. [Q.Q. Nong, T.C.E. Cheng, C.T. Ng, An improved online algorithm for scheduling on two unrestrictive parallel batch processing machines, Operations Research Letters, 36 (2008) 584–588] have provided an online algorithm with competitive ratio no greater than 2. We show that this bound is tight for the problem. Furthermore we give a new best possible online algorithm with a tighter structure