The Anchor-Robust Project Scheduling Problem
| Autor: | Pascale Bendotti, Philippe Chrétienne, Pierre Fouilhoux, Adèle Pass-Lanneau |
|---|---|
| Přispěvatelé: | 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), 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), Pass-Lanneau, Adèle |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
anchored decisions [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO] rescheduling robust optimization [INFO]Computer Science [cs] Project scheduling [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] [INFO] Computer Science [cs] Management Science and Operations Research [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ComputingMilieux_MISCELLANEOUS Computer Science Applications |
| Zdroj: | 14th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP) 14th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), Jun 2019, Renesse, Netherlands HAL |
| Popis: | A project scheduling framework is considered where processing times of jobs lie in some uncertainty set. The decision maker needs to compute a baseline schedule in advance, while guaranteeing that some jobs may not be rescheduled later. A subset of jobs is said to be anchored with respect to a baseline schedule if for any realization of processing times in the uncertainty set, the baseline schedule can be repaired in a second stage without changing the starting times of anchored jobs. Each job has an anchoring weight. The Anchor-Robust Project Scheduling Problem (AnchRobPSP) is to find in a first stage a baseline schedule satisfying a given deadline, and a subset of anchored jobs with maximum total weight. AnchRobPSP is considered for several uncertainty sets, such as box or budgeted uncertainty set, and dedicated graph models are presented. AnchRobPSP is shown to be NP-hard even for budgeted uncertainty. Polynomial or pseudo-polynomial algorithms are devised for box uncertainty and special cases of budgeted uncertainty. Numerical experiments for AnchRobPSP under budgeted uncertainty are presented. AnchRobPSP solutions are compared to those of state-of-the-art robust techniques. Finally it is shown how to achieve a trade-off between the number of anchored jobs and the makespan of the baseline schedule. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|