Single machine scheduling problems with generalized preemption

We address a class of single-machine, hard scheduling problems with the objective of minimizing the maximum tardiness. The jobs can be preempted, but whenever a job is started or resumed, there is a recovery interval affecting its progress. Such a feature is motivated by certain application environments and generalizes the usual preemption concept. For three different cases of this problem, we propose a heuristic algorithm, based on the partial enumeration of feasible schedules. A packing formulation solved by means of a column generation approach is used to certify the quality of the heuristic solution. An extensive computational experience shows the effectiveness of the approach on different classes of instances and shows that real-size problems can be solved to optimality in an acceptable amount of time. © 2009 INFORMS.