Article ID Journal Published Year Pages File Type
427625 Information Processing Letters 2010 7 Pages PDF
Abstract

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 . 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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics