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.
Single-Machine Scheduling Problems with Generalized Preemption / AGNETIS A; ALFIERI A.; NICOSIA G. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - STAMPA. - 21:1(2009), pp. 1-12. [10.1287/ijoc.1080.0273]
|Titolo:||Single-Machine Scheduling Problems with Generalized Preemption|
|Data di pubblicazione:||2009|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1287/ijoc.1080.0273|
|Appare nelle tipologie:||1.1 Articolo in rivista|