Article ID: | iaor20119104 |
Volume: | 61 |
Issue: | 2 |
Start Page Number: | 279 |
End Page Number: | 288 |
Publication Date: | Sep 2011 |
Journal: | Computers & Industrial Engineering |
Authors: | Levner Eugene, Kats Vladimir |
Keywords: | graphs |
In this paper we revisit and extend the algorithm for the cyclic project scheduling problem which was originally proposed by Romanovskii (1967). While the algorithm has been derived for fixed numerical data, we show how it can be extended to handle the problems with interval data. We also propose a new algorithm for the cyclic scheduling problem with interval data that extends the parametric method developed by Megiddo (1979) and runs in strongly polynomial time.