Anchored reactive and proactive solutions to the CPM-scheduling problem
| Autor: | Philippe Chrétienne, Pascale Bendotti, Alain Quilliot, Pierre Fouilhoux |
|---|---|
| Přispěvatelé: | EDF R&D (EDF R&D), EDF (EDF), Recherche Opérationnelle (RO), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
Mathematical optimization
021103 operations research Information Systems and Management General Computer Science Job shop scheduling Maximum level Scheduling Uncertainty interval 0211 other engineering and technologies Combinatorial optimization problem Robust optimization 02 engineering and technology [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] 010501 environmental sciences Management Science and Operations Research 01 natural sciences Industrial and Manufacturing Engineering Scheduling (computing) Time windows Modeling and Simulation [INFO]Computer Science [cs] 0105 earth and related environmental sciences Mathematics Anchored solutions |
| Zdroj: | European Journal of Operational Research European Journal of Operational Research, Elsevier, 2017, 261 (1), pp.67-74. ⟨10.1016/j.ejor.2017.02.007⟩ European Journal of Operational Research, 2017, 261 (1), pp.67-74. ⟨10.1016/j.ejor.2017.02.007⟩ |
| ISSN: | 0377-2217 1872-6860 |
| DOI: | 10.1016/j.ejor.2017.02.007⟩ |
| Popis: | International audience; In a combinatorial optimization problem under uncertainty, it is never the case that the real instance is exactly the baseline instance that has been solved earlier. The anchorage level is the number of individual decisions with the same value in the solutions of the baseline and the real instances. We consider the case of CPM-scheduling with simple precedence constraints when the job durations of the real instance may be different than those of the baseline instance. We show that, given a solution of the baseline instance, computing a reactive solution of the real instance with a maximum anchorage level is a polynomial problem. This maximum level is called the anchorage strength of the baseline solution with respect to the real instance. We also prove that this latter problem becomes NP-hard when the real schedule must satisfy time windows constraints. We finally consider the problem of finding a proactive solution of the baseline instance whose guaranteed anchorage strength is maximum with respect to a subset of real instances. When each real duration belongs to a known uncertainty interval, we show that such a proactive solution (possibly with a deadline constraint) can be polynomially computed. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect