Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan

摘要

We study online scheduling on two unbounded parallel-batching machines with limited restarts to minimize the makespan. In this system jobs arrive over time and a batch can be restarted if and only if all the jobs in it have never been restarted. To tackle this difficult problem, we make the second-restart assumption whereby we can only interrupt a running batch B at time t if both machines are busy at time t and batch B has a later starting time than the other running batch. For this case, we provide a best online algorithm with a competitive ratio ?3+12 ≈ 1.366. For the general problem, we show that no online algorithms can have a competitive ratio less than 1.298, leaving a gap from 1.298 to 1.366.