Parallel Machine Scheduling With Periodic Availability Constraints to Minimize Makespan

ABSTRACT We investigate the scheduling problem on parallel and identical machines under periodic availability constraints. Availability periods and unavailability periods appear alternately on each machine. We propose an algorithm, PFFD, and demonstrate that its worst‐case ratio is at most for , where represents the ratio of the duration of an unavailability period to an availability period. Furthermore, we develop the PPTAS algorithm, which can achieve a worst‐case ratio arbitrarily close to and runs in polynomial time when is a constant. When is part of the input, we show that there does not exist a polynomial time algorithm with worst‐case ratio better than unless .