New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

A Fully Polynomial Algorithm for a Cyclic Scheduling Problem with Interval Data

SpeakerEugene Levner

Co-authorVladimir Kats

In 1979, Nimrod Megiddo proposed a strongly polynomial method for finding a cycle of the minimum length-to-height ratio in a graph if all the cycle heights are positive. This method can be directly applied for solving cyclic PERT-type scheduling problems with positive data but cannot handle the cyclic problems with interval data, as in the latter case the cycle heights may be either positive or negative. A new algorithm is proposed for the case when the input data are of any sign. The algorithm combines the idea of Megiddo with Levner-Kats's (1998) parametric critical-path algorithm. It runs in O(mn^2 log n) time, where n is the number of nodes and m the number of arcs in the underlying graph. To our knowledge, no strongly polynomial algorithm for this scheduling problem has been known before.