Single machine scheduling with small operator-non-availability periods
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 problem, namely problems of finding schedules with time periods when the tasks can neither start nor finish. We consider in this paper the natural case of small periods where the duration of the periods is smaller than any processing time. This assumption corresponds to our chemical experiments lasting several days, whereas the operator unavailability periods are typically single days or week-ends. These problems are analyzed on a single machine with the makespan as criterion.
single machine scheduling unavailability constraints forbidden start and end approximation algorithm