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/

[1] Baptiste Ph., Timkovsky V., “On preemption redundancy in scheduling unit processing time jobs on two parallel machines”, Oper. Research Lett., 28 (2001), 205–212 | DOI | MR | Zbl

[2] Brucker P., Heitmann S., Hurink J., “How useful are preemptive schedules?”, Oper. Res. Lett., 31:2 (2003), 129–136 | DOI | MR | Zbl

[3] Du J., Leung J. Y. T., “Minimizing mean flow time in two-machine open shops and flow shops”, J. Algorithms, 14 (1993), 24–44 | DOI | MR | Zbl

[4] Gonzalez T., Sahni S., “Open shop scheduling to minimize finish time”, J. ACM, 23 (1976), 665–679 | DOI | MR | Zbl

[5] Gonzalez T., Sahni S., “Preemptive scheduling of uniform processor systems”, J. ACM, 25 (1978), 92–101 | DOI | MR | Zbl

[6] Labetoulle J., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., “Preemptive scheduling of uniform machines subject to release dates”, Progress in Combinatorial Optimization, Academic Press, New York, 1984, 245–261 | MR

[7] Lawler E. L., Labetoulle J., “On preemptive scheduling of unrelated parallel processors by linear programming”, J. ACM, 25 (1978), 612–619 | DOI | MR | Zbl

[8] Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B., “Sequencing and scheduling: algorithms and complexity”, Logistics of Production and Inventory, Handbooks in Operations Research and Management Science. Vol. 4, North-Holland, Elsevier, Amsterdam, 1993, 445–522

[9] McNaughton R., “Scheduling with deadlines and loss functions”, Management Science, 6 (1959), 1–12 | DOI | MR | Zbl

[10] Sauer Stone M., “Preemptive scheduling”, Algorithms and order (Ottawa, ON, 1987), Kluwer Acad. Publ., Dordrecht, 1989, 307–323 | MR

[11] Sauer N., Stone M., “Rational preemptive scheduling”, Order, 4:2 (1987), 195–206 | DOI | MR | Zbl

[12] Schrijver A., Theory of linear and integer programming, Wiley, Chichester, 1986, 470 pp. | MR | Zbl

[13] Tanaev V. S., Gordon V. S., Shafransky Y. M., Scheduling theory. Single-stage systems, Kluwer Acad. Publ., Dordrecht– Boston–London, 1994, 380 pp. | MR | Zbl