Properties of optimal schedules in preemptive shop scheduling

Philippe Baptiste, Jacques Carlier, Alexander V. Kononov, Maurice Queyranne, Sergey Sevastyanov, Maxim SviridenkoDiscret. Appl. Math 2011 · OpenReview

Abstract

In this work we show that certain classical preemptive shop scheduling problems with integral data satisfy the following integer preemption property: there exists an optimal preemptive schedule where all interruptions and all starting and completion times occur at integral dates. We also give new upper bounds on the minimal number of interruptions for various shop scheduling problems.
BibTeX
@inproceedings{baptiste2011properties,
  author = {Philippe Baptiste and Jacques Carlier and Alexander V. Kononov and Maurice Queyranne and Sergey Sevastyanov and Maxim Sviridenko},
  title = {{Properties of optimal schedules in preemptive shop scheduling}},
  booktitle = {Discret. Appl. Math},
  year = {2011},
  url = {https://openreview.net/forum?id=BIBNwuPO-Xr},
}

Loading related content...

Figure