Cyclic routing algorithms in graphs: Performance analysis and applications to robot scheduling

Cyclic routing algorithms in graphs: Performance analysis and applications to robot scheduling

0.00 Avg rating0 Votes
Article ID: iaor20119104
Volume: 61
Issue: 2
Start Page Number: 279
End Page Number: 288
Publication Date: Sep 2011
Journal: Computers & Industrial Engineering
Authors: ,
Keywords: graphs
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.