Anchored Rescheduling Problems Under Generalized Precedence Constraints
| Autor: | Philippe Chrétienne, Pascale Bendotti, Adèle Pass-Lanneau, Pierre Fouilhoux |
|---|---|
| Přispěvatelé: | Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Optimisation, Simulation, Risque et Statistiques pour les Marchés de l’Energie (EDF R&D OSIRIS), EDF R&D (EDF R&D), EDF (EDF)-EDF (EDF) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Polynomial
Mathematical optimization Schedule Machine scheduling 021103 operations research Computer science Generalized precedence graph 0211 other engineering and technologies 02 engineering and technology Rescheduling 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Anchored jobs [INFO]Computer Science [cs] Sensitivity (control systems) [MATH]Mathematics [math] Deadline constraints |
| Zdroj: | Combinatorial Optimization, 6th International Symposium, ISCO 2020, Montreal, QC, Canada, May 4–6, 2020 ISCO: International Symposium on Combinatorial Optimization ISCO: International Symposium on Combinatorial Optimization, May 2020, Montreal, QC, Canada. pp.156-166, ⟨10.1007/978-3-030-53262-8_13⟩ Lecture Notes in Computer Science ISBN: 9783030532611 ISCO |
| DOI: | 10.1007/978-3-030-53262-8_13⟩ |
| Popis: | International audience; The anchored rescheduling problem, recently introduced in the literature, is to find a schedule under precedence constraints with a maximum number of prescribed starting times. Namely, prescribed starting times may correspond to a former schedule that must be modified while maintaining a maximum number of starting times unchanged. In the present work two extensions are investigated. First we introduce a new tolerance feature, so that starting times can be considered as unchanged when modified less than a tolerance threshold. The sensitivity of the anchored rescheduling problem to tolerance is studied. Second we consider generalized precedence constraints, which include, e.g., deadline constraints. Altogether this leads to a more realistic rescheduling problem. The main result is to show that the problem is polynomial. We discuss how to benefit from the polynomiality result in a machine scheduling environment. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|