Geodesic
Structural properties of optimal schedules with preemption
Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 1, pp. 3-36

Voir la notice de l'article provenant de la source Math-Net.Ru

Scheduling problems with preemption are considered, where each operation can be interrupted and resumed later without any penalty. We investigate some basic properties of their optimal solutions, such as the existence of an optimal schedule (provided that the set of feasible solutions is nonempty), the existence of such a solution with a finite/polynomial number of interruptions or with interruptions at integral points only. Such theoretical questions are also of practical interest, since structural properties can be used to reduce the search space in a practical scheduling application. In this paper we provide answers to these basic questions for a rather general scheduling model (including, as its special cases, such classical models as parallel machine scheduling, shop scheduling, and resource constrained project scheduling) and for a large variety of objective functions, including nearly all known. For two special cases of objective functions (including, however, all classical functions) we prove the existence of an optimal solution with a special “rational structure”. An important consequence of this property is that the decision versions of these optimization scheduling problems belong to class NP. Bibl. 13.
Keywords: scheduling theory, preemption, optimal schedule. 
@article{DA_2009_16_1_a0,
     author = {Ph. Baptiste and J. Carlier and A. V. Kononov and M. Queyranne and S. V. Sevast'yanov and M. Sviridenko},
     title = {Structural properties of optimal schedules with preemption},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--36},
     publisher = {mathdoc},
     volume = {16},
     number = {1},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2009_16_1_a0/}
}
TY  - JOUR
AU  - Ph. Baptiste
AU  - J. Carlier
AU  - A. V. Kononov
AU  - M. Queyranne
AU  - S. V. Sevast'yanov
AU  - M. Sviridenko
TI  - Structural properties of optimal schedules with preemption
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2009
SP  - 3
EP  - 36
VL  - 16
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2009_16_1_a0/
LA  - ru
ID  - DA_2009_16_1_a0
ER  - 
%0 Journal Article
%A Ph. Baptiste
%A J. Carlier
%A A. V. Kononov
%A M. Queyranne
%A S. V. Sevast'yanov
%A M. Sviridenko
%T Structural properties of optimal schedules with preemption
%J Diskretnyj analiz i issledovanie operacij
%D 2009
%P 3-36
%V 16
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2009_16_1_a0/
%G ru
%F DA_2009_16_1_a0
Ph. Baptiste; J. Carlier; A. V. Kononov; M. Queyranne; S. V. Sevast'yanov; M. Sviridenko. Structural properties of optimal schedules with preemption. Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 1, pp. 3-36. http://geodesic.mathdoc.fr/item/DA_2009_16_1_a0/