General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Diskretn. Anal. Issled. Oper.:

Personal entry:
Save password
Forgotten password?

Diskretn. Anal. Issled. Oper., 2009, Volume 16, Number 1, Pages 3–36 (Mi da559)  

This article is cited in 8 scientific papers (total in 8 papers)

Structural properties of optimal schedules with preemption

Ph. Baptistea, J. Carliera, A. V. Kononovb, M. Queyrannec, S. V. Sevast'yanovbd, M. Sviridenkoe

a Université de Technologie de Compiégne
b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
c Faculty of Commerce and Business Administration, University of British Columbia
d Novosibirsk State University
e IBM T. J. Watson Research Center

Abstract: 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.

Full text: PDF file (383 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2010, 4:4, 455–474

Bibliographic databases:

UDC: 519.854.2
Received: 13.10.2008
Revised: 12.12.2008

Citation: Ph. Baptiste, J. Carlier, A. V. Kononov, M. Queyranne, S. V. Sevast'yanov, M. Sviridenko, “Structural properties of optimal schedules with preemption”, Diskretn. Anal. Issled. Oper., 16:1 (2009), 3–36; J. Appl. Industr. Math., 4:4 (2010), 455–474

Citation in format AMSBIB
\by Ph.~Baptiste, J.~Carlier, A.~V.~Kononov, M.~Queyranne, S.~V.~Sevast'yanov, M.~Sviridenko
\paper Structural properties of optimal schedules with preemption
\jour Diskretn. Anal. Issled. Oper.
\yr 2009
\vol 16
\issue 1
\pages 3--36
\jour J. Appl. Industr. Math.
\yr 2010
\vol 4
\issue 4
\pages 455--474

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. D. A. Chemisova, “O svoistvakh optimalnykh raspisanii v zadache flow shop s preryvaniyami i proizvolnym regulyarnym kriteriem”, Diskretn. analiz i issled. oper., 16:3 (2009), 74–98  mathnet  mathscinet  zmath
    2. Baptiste Ph., Cartier J., Kononov A., Queyranne M., Sevastyanov S., Sviridenko M., “Properties of optimal schedules in preemptive shop scheduling”, Discrete Appl. Math., 159:5 (2011), 272–280  crossref  mathscinet  zmath  isi  elib  scopus
    3. Cheng T.C.E., Lin B.M.T., Huang H.L., “Resource-constrained flowshop scheduling with separate resource recycling operations”, Comput. Oper. Res., 39:6 (2012), 1206–1212  crossref  mathscinet  zmath  isi  elib  scopus
    4. Baptiste Ph., Carlier J., Kononov A., Queyranne M., Sevastyanov S., Sviridenko M., “Integer Preemptive Scheduling on Parallel Machines”, Oper. Res. Lett., 40:6 (2012), 440–444  crossref  mathscinet  zmath  isi  elib  scopus
    5. R. Yu. Simanchev, N. Yu. Shereshik, “Tselochislennye modeli obsluzhivaniya trebovanii odnim priborom s preryvaniyami”, Diskretn. analiz i issled. oper., 21:4 (2014), 89–101  mathnet  mathscinet
    6. Gawiejnowicz S., Kononov A., “Isomorphic Scheduling Problems”, Ann. Oper. Res., 213:1 (2014), 131–145  crossref  mathscinet  zmath  isi  elib  scopus
    7. N. Yu. Shereshik, “Relaksatsii mnogogrannika optimalnykh raspisanii obsluzhivaniya trebovanii odnim priborom s preryvaniyami”, Diskretn. analiz i issled. oper., 22:6 (2015), 78–90  mathnet  crossref  mathscinet  elib
    8. Coffman Jr. E. G., Ng C.T., Timkovsky V.G., “How Small Are Shifts Required in Optimal Preemptive Schedules?”, J. Sched., 18:2 (2015), 155–163  crossref  mathscinet  zmath  isi  elib  scopus
  • Дискретный анализ и исследование операций
    Number of views:
    This page:689
    Full text:142
    First page:22

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020