Parallel Machine Scheduling With Periodic Availability Constraints to Minimize Makespan
研究了在周期性可用性约束下，并行同速机调度问题以最小化最大完工时间，提出了PFFD和PPTAS两种算法，并分析了其最坏情况比。
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 .