New Challenges in Scheduling Theory

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

High-multiplicity scheduling on one machine with forbidden start and completion times

SpeakerNadia Brauner

Co-authorChristophe Rapine

For an industrial application in the chemical industry, we were confronted with the planning of experiments, where human intervention of a chemist is required to handle the starting and termination of each of the experiments. This gives rise to a new type of scheduling problems, namely problems of finding schedules with instants when the tasks can neither start nor finish. We show that a schedule without idle time always exists if the number of forbidden instants is less than the number of distinct processing times appearing in the instance. We derive a quite fast algorithm to find such a schedule, based on an hybridization between list algorithm and local exchange. We then improve our approach to propose a polynomial time algorithm under a High Multiplicity encoding. As a corollary minimizing the makespan for a constant number of forbidden instants is polynomial.