Single machine scheduling problems with generalized preemption

We address a class of single-machine, hard scheduling problemswith the objective of minimizing the maximum tardiness. The jobscan be preempted, but whenever a job is started or resumed, thereis a recovery interval affecting its progress. Such a feature ismotivated by certain application environments and generalizes theusual preemption concept. For three different cases of thisproblem, we propose a heuristic, a packing formulation and acolumn generation approach to its solution. An extensivecomputational experience shows that suitably combining the aboveapproaches, real-size problems can be solved to optimality in anacceptable amount of time.