The Continuous Time-Resource Trade-off Scheduling Problem with Time Windows - LAAS-Décision et Optimisation
Article Dans Une Revue INFORMS Journal on Computing Année : 2024

The Continuous Time-Resource Trade-off Scheduling Problem with Time Windows

Résumé

We introduce a variant of the cumulative scheduling problem (CuSP) characterized by continuous modes, time windows, and a criterion that involves safety margin maximization. The study of this variant is motivated by the Geospatial based Environment for Optimisation Systems Addressing Fire Emergencies Horizon 2020 Project, which is devoted to the design of evacuation plans in the face of natural disasters and more specifically, wildfire. People and goods have to be transferred from endangered places to safe places, and evacuation planning consists of scheduling evacuee moves along precomputed paths under arc capacities and deadlines. The resulting model is relevant in other contexts, such as project or industrial process scheduling. We consider here several formulations of the continuous time-resource trade-off scheduling problem (CTRTP-TW) with a safety maximization objective. We establish a complete complexity characterization distinguishing polynomial and NP-hard special cases depending on key parameters. We show that the problem with fixed sequencing (i.e., with predetermined overlap or precedence relations between activities) is convex. We then show that the preemptive variant is polynomial, and we propose lower and upper bounds based on this relaxation. A flow-based mixed-integer linear programming formulation is presented, from which a branch-and-cut exact method and an insertion heuristic are derived. An exact dedicated branch-and-bound algorithm is also designed. Extensive computational experiments are carried out to compare the different approaches on evacuation planning instances and on general CTRTP-TW instances. The experiments also show the interest of the continuous model compared with a previously proposed discrete approximation.
Fichier principal
Vignette du fichier
Article_GEO_SAFE-2.pdf (926.1 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04610399 , version 1 (10-10-2024)

Identifiants

Citer

Christian Artigues, Emmanuel Hébrard, Alain Quilliot, Hélène Toussaint. The Continuous Time-Resource Trade-off Scheduling Problem with Time Windows. INFORMS Journal on Computing, 2024, 36 (6), pp.1359-1756. ⟨10.1287/ijoc.2022.0142⟩. ⟨hal-04610399⟩
163 Consultations
18 Téléchargements

Altmetric

Partager

More