Maximizing the number of jobs scheduled at their baseline starting times in case of machine failures
| Autor: | Philippe Chrétienne |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Mathematical optimization
021103 operations research Out-of-order execution Computer science 0211 other engineering and technologies General Engineering 0102 computer and information sciences 02 engineering and technology Management Science and Operations Research 01 natural sciences Polynomial algorithm Scheduling (computing) 010201 computation theory & mathematics Artificial Intelligence Computer Science::Operating Systems Software State graph |
| Zdroj: | Journal of Scheduling. 23:135-143 |
| ISSN: | 1099-1425 1094-6136 |
| DOI: | 10.1007/s10951-019-00621-x |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink