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

Christian Artigues (), Emmanuel Hébrard (), Alain Quilliot () and Hélène Toussaint ()
Additional contact information
Christian Artigues: Laboratoire d’Analyse et d’Architecture des Systèmes du Centre National de la Recherche Scientifique, Université de Toulouse, Centre National de la Recherche Scientifique, 31031 Toulouse, France
Emmanuel Hébrard: Laboratoire d’Analyse et d’Architecture des Systèmes du Centre National de la Recherche Scientifique, Université de Toulouse, Centre National de la Recherche Scientifique, 31031 Toulouse, France
Alain Quilliot: Laboratoire d’Informatique, de Modélisation et d’Optimisation des Systèmes du Centre National de la Recherche Scientifique et de l’Universitè Clermont-Auvergne, 63178 Clermont-Ferrand, France
Hélène Toussaint: Laboratoire d’Informatique, de Modélisation et d’Optimisation des Systèmes du Centre National de la Recherche Scientifique et de l’Universitè Clermont-Auvergne, 63178 Clermont-Ferrand, France

INFORMS Journal on Computing, 2024, vol. 36, issue 6, 1676-1695

Abstract: 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.

Keywords: continuous time-resource trade-off scheduling; time windows; complexity; mixed-integer linear programming; branch and cut; insertion heuristic; evacuation planning (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0142 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:6:p:1676-1695

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().