High-multiplicity scheduling on one machine with forbidden start and completion times
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.