Parallel Machine Scheduling With Periodic Availability Constraints to Minimize Makespan

ABSTRACT We investigate the scheduling problem onm $$ m $$ 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 mostm 3 m + 1 ( 5 + 4 β 5+4\beta $$ form ≥ 3 $$ m\ge 3 $$ , whereβ $$ \beta $$ 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 to1 + β $$ 1+\beta $$ and runs in polynomial time whenm $$ m $$ is a constant. Whenm $$ m $$ is part of the input, we show that there does not exist a polynomial time algorithm with worst‐case ratio better than5 + 4 β 4 unlessP = N P $$ P= NP $$ .