Reactive and proactive single-machine scheduling to maintain a maximum number of starting times

Philippe Chrétienne ()
Additional contact information
Philippe Chrétienne: Sorbonne Universités, Université Pierre et Marie Curie

Annals of Operations Research, 2021, vol. 298, issue 1, No 7, 124 pages

Abstract: Abstract This paper considers, in the single-machine scheduling context, the reactive and proactive problems arising when, due to unpredictable events between the time a baseline scheduled has been planned and the time the schedule must be implemented, the job durations may have increased so that the baseline schedule is no longer feasible. In the reactive case, the baseline schedule is known, the real job durations are known and we search for a schedule of the real instance that maximizes the number of jobs started at the same date in both schedules, this maximum being called the reactive gain. We show that, in the non-preemptive case, the corresponding decision problem is NP-complete in the strong sense while in the discrete preemptive case, it can be polynomially solved. In the proactive case, the real job durations are only known to belong to an uncertainty domain and we search for a baseline schedule that maximizes the worst reactive gain over the uncertainty domain. We show that the corresponding decision problem is NP-complete in the non-preemptive case while it is quite easy in the discrete preemptive case.

Keywords: Scheduling; Complexity; Dynamic programming (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-018-2763-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:298:y:2021:i:1:d:10.1007_s10479-018-2763-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-018-2763-9

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().