Parametric Algorithms for Cyclic Scheduling Problems with Applications to Robotics

摘要

The paper considers cyclic scheduling problems arising in planning of robotic flowlines and logistics. The problems are reduced to finding the minimum (or maximum) cost-to-time ratio in doubly weighted graphs. New combinatorial algorithms are developed extending the cyclic project scheduling algorithm by Romanovskii (1967) and the minimum-cost-to-time-ratio algorithm by Dantzig, Blattner and Rao (1967). Whereas Romanovskii's and Dantzig-Blattner-Rao's algorithms are restricted to solving problems with fixed numerical data, the new algorithms can treat input data that are varied at prescribed intervals. Several special cases are solved in strongly polynomial time.