A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan

摘要

We consider online scheduling with restarts in an unbounded parallel-batch processing system to minimize the makespan. By online we mean that jobs arrive over time and all the information on a job is unknown before its arrival time (release date) and restart means that a running batch may be interrupted, losing all the work done on it, and the jobs in the interrupted batch are released and become independently unscheduled jobs. It is known in the literature that the considered problem has no online algorithm with a competitive ratio less than (5-√5)/2.We give an online algorithm for the considered problem with a competitive ratio (5 -√5)/2 ≈ 1.382.