Single-Machine Scheduling Problems with Generalized Preemption
Alessandro Agnetis, Arianna Alfieri, Gaia Nicosia
INFORMS Journal on Computing · 2009 · Volume 21 · Issue 1
Abstract
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.
Keywords
production scheduling, sequencing, production scheduling, single machine, preemptive scheduling, packing, column generation
Enable JavaScript for citation tools and additional paper interactions.