Treffer: Parallel Machine Scheduling With Periodic Availability Constraints to Minimize Makespan.

ABSTRACT We investigate the scheduling problem on m$$ 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 most m3m+1(5+4β)$$ \frac{m}{3m+1}\left(5+4\beta \right) $$ for m≥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 to 1+β$$ 1+\beta $$ and runs in polynomial time when m$$ m $$ is a constant. When m$$ m $$ is part of the input, we show that there does not exist a polynomial time algorithm with worst‐case ratio better than 5+4β4$$ \frac{5+4\beta }{4} $$ unless P=NP$$ P= NP $$. [ABSTRACT FROM AUTHOR]

Copyright of Naval Research Logistics is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)