New Challenges in Scheduling Theory

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

Some advances in solving non-idling m-machine scheduling problems

SpeakerPhilippe Chretienne

The basic principles and main motivations of non-idling scheduling are first presented. We first briefly recall the main single-machine results and then consider the m-machine case. Some general properties are proposed that give some insights on the difficulty to handle precedence constraints and to get efficient heuristics. Polynomial algorithms are proposed for some specific problems. However it happens that the complexity of the very basic problem Pm,NI/r(i),d(i),p(i)=1/- remains open while its more restricted variant, when the union of the busy intervals of any subset of machines must make an interval, is shown to be polynomial