Scheduling on same-speed processors with at most one downtime on each machine

摘要

We consider the problem of scheduling a set of independent tasks on multiple same-speed processors with planned shutdown times with the aim of minimizing the makespan. We give an LPT-based algorithm, LPTX, which yields a maximum completion time that is less than or equal to 3/2 the optimal maximum completion time or 3/2 the time that passes from the start of the schedule until the latest end of a downtime. For problems where the optimal schedule ends after the last downtime, and when the downtimes represent fixed jobs, the LPTX maximum completion time is within 3/2 of the optimal maximum completion time. In addition, we show that this result is asymptotically tight for the class of polynomial algorithms assuming that P≠NP. We also show that the bound obtained previously for a similar problem, when no more than half of the machines are shut down at the same time, for the LPT algorithm is asymptotically tight in the class of polynomial algorithms if P≠NP.