Maximizing the number of jobs scheduled at their baseline starting times in case of machine failures

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

Journal of Scheduling, 2020, vol. 23, issue 1, No 7, 135-143

Abstract: Abstract We investigate the problem of keeping the maximum number of starting times of a baseline schedule if some machines happen to be out of order when the baseline schedule is to be implemented. If the machines are identical, we show that the problem is polynomially solved when no deadline is imposed on the reactive schedule and is strongly NP-hard otherwise. If the number of unrelated machines is fixed and if no deadline is imposed on the reactive schedule, a polynomial algorithm, based on a state graph, has been developed. We conclude with an open complexity question and some further research directions for this class of problems.

Keywords: Scheduling; Complexity; Algorithms; State graph (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-019-00621-x 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:jsched:v:23:y:2020:i:1:d:10.1007_s10951-019-00621-x

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

DOI: 10.1007/s10951-019-00621-x

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

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