# The resource-constrained project scheduling problem for risk reduction after industrial disasters involving dangerous substances

Thiago Jobson Barbalho, Juan Luis Jiménez Laredo, Andréa Cynthia Santos

► To cite this version:

Thiago Jobson Barbalho, Juan Luis Jiménez Laredo, Andréa Cynthia Santos. The resource-constrained project scheduling problem for risk reduction after industrial disasters involving dangerous substances. OR Spectrum, inPress, 10.1007/s00291-025-00822-1. hal-05017178

HAL Id: hal-05017178

https://hal.science/hal-05017178v1

Submitted on 15 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

# The resource-constrained project scheduling problem for risk reduction after industrial disasters involving dangerous substances

Thiago J. Barbalho¹ · Juan Luis Jiménez Laredo¹,² · Andréa Cynthia Santos¹

<figure><img src="image_3.png" /></figure>

Received: 18 December 2023 / Accepted: 2 April 2025
© The Author(s) 2025

## Abstract

The accidental release of dangerous substances from industrial sources into the environment is a recurring problem. Despite the regulations implemented to prevent these accidents and mitigate their consequences, managing operations in the aftermath of industrial disasters remains a complex challenge. This paper investigates post-catastrophe operations in the event of industrial disasters, where a group of specialized teams are deployed to clean up areas contaminated by dangerous substances, with the objective of minimizing the overall risk of the operation. To this end, we propose a new optimization problem named Resource Constrained Project Scheduling Problem with Risk and Priorities (RCPSP-RP), which is composed of an integrated scheduling-routing model with different schemes of task prioritization. Two integer linear models and an Iterated Local Search (ILS) metaheuristic are proposed and applied to solve several theoretical instances. A first contribution of this study is the introduction of a new problem that is highly relevant in the context of industrial disasters. In addition, several experiments have been conducted that reveal that relaxation of priority constraints generally leads to solutions with a lower overall risk. Furthermore, the results highlight the limitations of the mathematical formulation, which can only solve instances with up to 16 tasks. In contrast, the ILS approach consistently provides solutions in seconds for all instances.

**Keywords** Industrial disasters · Logistics · Emergency response · Hazardous materials · Optimization

## 1 Introduction

In September 2019, a chemical plant in Rouen (France) caught fire, releasing a plume of smoke containing toxic particles that reached the city center and the north of France (eMARS 2019). According to Reuters (2019), in the following days “people were told not to eat produce from their gardens,” and farmers were “not allowed

<footnote>Extended author information available on the last page of the article</footnote>
*to sell milk, vegetables and other products harvested in the area.*" It was later confirmed that approximately 5253 tons of multi-purpose additives, oil, detergent and other chemicals were burned in the fire, raising a generalized concern about the impact of the released substances on human health, the environment and the local economy (Seine-Maritime 2019).

Unfortunately, accidents of this type are not isolated cases. In Europe, on average, around 24 major accidents involving dangerous substances are reported annually (European Commission 2021). These incidents highlight the urgent needs for robust post-catastrophe operations to manage and mitigate the aftermath of such disasters. Effective decision-making models are crucial to minimize the impact on human health, the environment, and the local economy.

Despite the regulations in place to prevent such accidents and minimize their impact once they occur (see, e.g., the Seveso-III Directive (2018)), operations after industrial disasters remain a challenging task. Each disaster has unique characteristics, requiring tailored operational decisions based on the hazardous nature of the substances released and the extent of the affected area. For example, pollutants can be absorbed by plants and soil, infiltrate groundwater, or metabolize into more harmful byproducts (Görlitz et al. 2011). The proximity of industrial areas to urban centers further exacerbates the risks to human health, which requires specialized teams and equipment for cleanup operations.

Some studies in the literature have tackled related problems from the Operational Research (OR) perspective. For instance, scheduling or integrated scheduling-routing applications have been developed to provide decision-making support for emergency response to natural incidents (Wex et al. 2014; Tirkolaee et al. 2020), forest fires (Ren and Tian 2016; Wu et al. 2019; Wang et al. 2020; Bodaghi et al. 2020), and provide strategical (Maya Duque and Sörensen 2011; Maya Duque et al. 2016; Sakuraba et al. 2016; Barbalho et al. 2023) and operational (Pena et al. 2022) support after natural disasters. However, to the extent of our knowledge, limited work has been dedicated to industrial disasters involving dangerous substances that can cause harmful effects to the environment or community at large from the OR point of view.

This paper investigates the post-catastrophe operations in the event of industrial disasters application, which is modeled as the Resource Constrained Project Scheduling Problem with Risk and Priorities (RCPSP-RP). In this context, a set of specialized teams is required for the cleanup of contaminated areas. Each polluted area is depicted as a node within a connected graph, with an associated risk contingent upon the hazardous nature of pollutants. Teams are deployed to traverse the edges of the graph, conducting cleaning operations to neutralize the risk associated with each node. The primary objective is to minimize the overall risk of the operation, quantified as the weighted sum of task completion times.

The RCPSP-RP is a new integrated scheduling-routing optimization problem with different schemes of task prioritization. The polluted nodes in the graph are mapped as tasks with associated risk and processing time attributes. Resources represent the specialized teams that are deployed from a specific node in the graph (called the depot) to perform the cleaning operation and mitigate risk by processing all mapped tasks. Travel times when traversing the edges are implied based on their traveling
distance. More specifically, these travel times are treated as Sequence-Dependent Setup Times (SDST) (see, e.g., Allahverdi et al. (2008)) by taking into account the shortest travel time between every pair of nodes in the graph. The RCPSP-RP performs task prioritization by employing precedence constraints between tasks based on their risk attribute. As a consequence, tasks with higher risk take precedence over lower risk ones. This behavior is defined as a strict priority policy. In order to gain insights on the impact that task prioritization may have on the quality of solutions, we follow a relaxation schema inspired by Panchamgam et al. (2013) by introducing a relaxation threshold that partially or completely relaxes precedence constraints according to the stated level of strictness. Thus, providing a moderate or no priority policy, respectively.

To conduct an experimental analysis on the RCPSP-RP, we propose mathematical formulations inspired by an exact formulation for the classical Resource Constrained Project Scheduling Problem (RCPSP) from Christofides et al. (1987). In addition, an Iterated Local Search (ILS) metaheuristic is also developed to cope with large problem instances, when optimal—or even integer—solutions cannot be computed by the exact methods in reasonable time. Experiments are conducted on a set of theoretical instances to investigate different problem scenarios and the three types of priority schemes, namely strict, moderate and no priority policies. Overall, results show that less strict priority policies can improve the quality of the solutions, although longer running times are required due to the exploration of a larger solution space. Likewise, in certain instances, a full relaxation of travel times yields up to 40% improvement in solutions. This particular scenario can arise in the context of industrial disasters contained within enclosed areas, where traveling times are significantly smaller than processing times and, therefore, they can be neglected from a practical perspective.

The remainder of this paper is organized as follows: related works in classical RCPSP and applications in the context of disaster relief are presented in Sect. 2. Section 3 introduces the mathematical formulations of the problem, including the modeling of task prioritization as precedence constraints in Sect. 3.1 and integer programming models in Sect. 3.2. Section 4 is dedicated to the proposed ILS metaheuristic. Afterwards, a description of the computational experiments including the experimental setup, data generation and automated calibration of ILS' parameters using the Iterated racing for automatic algorithm configuration (IRACE) package are presented in Sect. 5. In this section, the analysis of results is presented, including a comparison between the results obtained using CPLEX and ILS for the different experimental scenarios. Finally, concluding remarks and perspectives for future works are discussed in Sect. 6.

## 2 Related works

The classical Resource-Constrained Project Scheduling Problem (RCPSP), described in Brucker et al. (1999), considers a project with *J* tasks labeled *j* = 1, ..., *J* that should be scheduled on limited renewable resources such that the makespan is minimized. Each task requires a certain number of resources to be performed and
takes $p_j$ consecutive periods of time to complete (preemption is not allowed). Due to technological requirements, there are acyclic precedence relations between some of the tasks given by sets of immediate predecessors $P_j$ stating that a task $j$ may only start after all its predecessors $i \in P_j$ are completed. Usually, two dummy tasks $j=0$ and $j=J+1$ with instant duration and no demand of resources represent the start and the completion of the project, respectively.

The RCPSP was proved NP-hard in Blazewicz et al. (1983) as a generalization of the well-known Job Shop Scheduling Problem (Graham et al. 1979) and its variants were surveyed in Kolisch (1995); Demeulemeester and Herroelen (2002); Hartmann and Briskorn (2010) and more recently, Hartmann and Briskorn (2022). Generally, methods for solving the RCPSP involve exact algorithms such as Brucker et al. (1999); Demeulemeester and Herroelen (1992, 1997); Mingozzi et al. (1998) and Sprecher (2000); as well as heuristics and metaheuristics such as Kochetov and Stolyar (2003); Kolisch and Hartmann (2006); Mendes et al. (2009); Palpant et al. (2004) and Tormos and Lova (2001). In addition, a benchmark set with 480 instances was introduced by Kolisch (1995) and used by methods such as evolutionary (Kochetov and Stolyar (2003); Mendes et al. (2009)) and branch-and-bound (Demeulemeester and Herroelen (1997); Sprecher (2000)) algorithms.

The application treated in this paper is a particular case of the RCPSP, with a single type of renewable resource, with or without SDST (according to the problem scenario) and precedence constraints determined by the value of the relaxation threshold. An important difference is that, in our case, precedence constraints refer to task prioritization, which allows successor tasks to be started as early as their predecessors if there are enough available resources. This behavior is referred in the literature as precedence constraints with zero time lags (Hartmann and Briskorn 2022). In this paper, these constraints are referred as priority constraints (see Sect. 3.1).

## 2.1 Related applications in disaster relief

In the scientific literature, the RCPSP has been applied to several disaster relief scenarios such as debris removal, humanitarian logistics, risk mitigation and emergency response to forest fires. Some relevant reviews can be found in Farahani et al. (2020); Santos (2019) and Hu et al. (2019).

In general, these works follow a scheduling or integrated scheduling-routing approach aiming at minimizing operational cost, or at maximizing some satisfaction measure such as road accessibility, number of lives saved, etc. Another characteristic is that decisions may be restricted by financial or time budgets, thus, not all demands may be fulfilled (Maya Duque and Sörensen 2011; Maya Duque et al. 2016). We describe below in detail some of these approaches proposed in the literature.

The Rescue Unit Assignment and Scheduling Problem (RUASP), presented in Wex et al. (2014), concerns the allocation and scheduling of heterogeneous rescue units located in operation centers, to emerging incidents with the objective of minimizing the sum of completion times of incidents weighted by their severity. The problem was modeled as a binary quadratic optimization model where each incident may require a specific type of rescue unit. The authors developed
a Greedy Randomized Adaptive Procedure (GRASP) metaheuristic, a Monte Carlo-based heuristic and a conjoint of 8 construction heuristics coupled with 5 improvement heuristics. The methods were tested against small and medium sized instances with up to 40 incidents and 40 rescue units, designed in contact with rescue teams active in the major 2011 Japan earthquake. Subsequently, Tirkolaee et al. (2020) also extended the above problem by adding a second objective function and parameter uncertainty such as travel times, incident severity and processing times to minimize also the total delay time. The authors applied the robust optimization technique to solve the model using several theoretical instances with up to 20 incidents and 15 rescue units.

Another integrated scheduling-routing application can be found in the Scheduling vehicle Routing Problem to Clean Debris (SRP-CD) presented in Pena et al. (2022), concerning strategic (scheduling) and operational (routing) decisions to remove debris in urban areas after major disasters. The objective is simultaneously to minimize the operation duration, at the strategic level, and the total costs of vehicles routes, at the operational one. The authors proposed a new mathematical model based on a dynamic multi-flow formulation, several constructive heuristics and a Large Neighborhood Search (LNS)-based metaheuristics. These methods were applied to theoretical instances with 10–500 demand nodes and 2–7 homogeneous vehicles.

A similar application where only the strategical level is considered is found in the Work-troops Scheduling Problem described in Sakuraba et al. (2016), concerning the scheduling of a homogeneous fleet of work-troops to unblock blocked roads in urban networks affected by natural disasters, such as earthquakes. Implicit precedence relations are considered due to roads' physical accessibility in the network. The authors developed three greedy heuristics to solve a theoretical benchmark of small instances with up to 20 blocked roads and a large-scale realistic instance of the 2010 Haiti earthquake with 16,660 nodes, 19,866 roads and 536 blocked roads. An extension of this work is subsequently found in Barbalho et al. (2023), where the authors developed a GRASP and an ILS metaheuristic coupled with a dedicated local search to solve the set of theoretical and realistic instances from Sakuraba et al. (2016).

The Multivehicle Synchronized Arc Routing Problem to Restore Network Connectivity (K-ARCP) presented in Akbari and Salman (2017) (see also Akbari et al. (2021)) is an open vehicle routing problem to restore blocked arcs in an urban network. A mathematical formulation and a matheuristic based on the linear relaxation of the problem are proposed. Three data sets based on Istanbul city were generated including up to six vehicles: the first one corresponds to the highways network, with 74 nodes and 179 edges, the second data set has 389 nodes and 689 edges, and the third one is based on the southwestern region of Istanbul city with 250 nodes and 539 edges. Route damage is taken as a probability of being impassable after a earthquake, high, medium and low-risk edges, respectively 0.3, 0.2 and 0.1 of probability. In another study by Vodák et al. (2018), a Vehicle Routing Problem (VRP) to minimize the time of repairing blocked road segments is solved with an ant colony algorithm. The authors have produced
a realistic instance based on the road network of the Zlín region in the Czech Republic, composed of 723 nodes, 974 links and 46 blocked roads.

The Disruption Scheduling problem on Urban Networks (DSUN), introduced by Coco et al. (2020), in the context of rapid and unplanned urban growth. The authors address critical issues that raise from various social, economic, and ecological challenges in urban mobility. The DSUN involves scheduling planned disruptions in an urban road network while ensuring strong connectivity. Disruptions can break network connections, requiring route direction modifications (arc reversals) and potentially disturbing users habits. The objective is to minimize the number of arc reversals and the sum of starting times for all disruptions simultaneously. The study formulates DSUN mathematically and presents an exact algorithm based on the $ε$-constraint method to handle its bi-objective nature. Computational experiments were conducted on theoretical and realistic instances, demonstrating the algorithm's ability to prove optimality for instances with up to 100 vertices and 20 disruptions.

The Early Stage Response Problem (ESRP), presented in Kim et al. (2018), provides an emergency response composed of routing and scheduling of teams with the objective of maximizing risk prevention to buildings under imminent threat such as fire spread, gas leak and explosions, neutralizing further hazards to material and human lives. Thus, the model reflects dynamic changes in emergency situations, such as changes in hazard intensity and time required to neutralize dangerous targets. In addition, the authors developed a Mixed Integer Linear Program (MILP) and two greedy algorithms to solve theoretical instances based on data from the central city building in Seoul, Korea, with up to 5 dangerous targets.

In addition to previous publications, in recent years, works in the actual context of emergency response to forest fires have been proposed as integrated scheduling-routing problems with static, dynamic or stochastic characteristics. The Resource-Constrained Emergency Scheduling Problem for Forest Fires with Priority Areas (RCESP) presented in Ren and Tian (2016) provides a disaster relief model to extinguish forest fires, where a homogeneous fleet of firefighting teams is dispatched to multiple areas according to their priorities following a strict policy, with the objective of minimizing teams' total travel distance constrained by a maximum operational autonomy. The authors developed a genetic algorithm coupled with a particle swarm metaheuristic to solve a case study based on realistic data from Heilongjiang, China, with 7 fire points and 3 teams. A dynamic version of the RCESP was later presented in Wu et al. (2019), where fire spreading and fire extinguishing speed of teams were considered. The problem was solved as a MILP with total rescue time minimization. Furthermore, Wang et al. (2020) extended the two previous works with a bi-objective MILP to simultaneously minimize the total travel distance and the total fire extinguishing rescue time. Fuzzy logic decision-making based on an $ε$-constraint method was also designed to obtain schedule schemes and produce Pareto fronts. The MILP and the $ε$-constraint method were tested against the benchmark instances of Ren and Tian (2016) and several randomly generated instances with up to 16 fire points and 6 rescue teams.

The Multi-Resource Scheduling Model under Uncertainty (MRSU), introduced in Bodaghi et al. (2020), presents a MILP framework for scheduling and sequencing heterogeneous resources under uncertain parameters, where the deterministic MILP
is solved many times with multiple stochastic scenarios to identify the most persistent optimal solution. The authors applied the MRSU framework to a 2009 bushfire case study in Australia with 25 bushfires with stochastic severity and propagation and 16 vehicles, where a total of 1000 scenarios were solved to identify the most probable one.

Despite the relevance of the contributions that the previous works represent in the field of operational research for catastrophe relief, none of them addresses the particularities of industrial catastrophe scenarios where the toxicity of the released substances must be considered. Knowledge about the long-term consequences of these substances to the environment and human health are often unknown or limited (Keim 2011), which motivates further study of industrial catastrophe events from the perspective of operational research so as to minimize their impacts once they occur. The main contributions of this work are both proposing and modeling the RCPSP-RP as an optimization problem in the context of industrial disasters, as well as the proposing methods that, in conjunction with existing risk management plans, can help support decision making in the occurrence of such situations.

In this study, we propose the RCPSP-RP with applications in industrial disasters, which, to our knowledge, has not been addressed in the scientific literature. It incorporates a risk assessment mechanism that quantifies the hazards associated with each task based on the nature of the toxic materials involved. Furthermore, while many existing models use static priority rules, this research introduces a flexible priority constraint mechanism that adapts to dynamic risk levels, ensuring more effective task prioritization. The novel mathematical formulation integrates scheduling with risk management strategies, and the development of a specialized metaheuristic approach represents a significant advancement in methodologies for disaster response. Ultimately, this research not only enhances theoretical understanding but also provides practical tools that emergency response teams can implement to improve decision-making and outcomes during industrial disasters, thereby filling a critical gap in the literature and laying the groundwork for future studies

## 3 Problem definition

This section provides a formal definition for the RCPSP-RP optimization problem. Let $G = (V, E)$ be a connected graph, where $V$ is the set of nodes and $E$ is the set of edges. Let $V_o \subset V$ be defined as a subset containing a single depot node where $K$ homogeneous teams are located at the start of the operation. Moreover, a subset $V_d \subset V$ ($V_o \cap V_d = \emptyset$ & $V_o \cup V_d = V$) contains all tasks that need to be performed by the teams, where each task $i \in V_d$ has a risk $r_i \in (0, 1]$ and a processing time $p_i \in \mathbb{Z}^+$ attribute.

The $r_i$ is determined by the hazardous materials present at $i$ in a scale of low- ($r_i \le 0.3$), medium- ($0.3 < r_i \le 0.5$), high- ($0.5 < r_i < 0.9$) or critical- ($r_i \ge 0.9$) risk, while $p_i$ is an estimate of the time required to neutralize the hazardous substances in the node. Every task is processed by a single team and after being started it cannot be interrupted (preemption is not allowed).
The set of edges E represents the secured paths that teams can use to move from one node to another with reduced exposition to dangerous products. Each path has a $w_{ij} \in \mathbb{N}$ associated value that represents the SDST between i and j with $(i, j) \in V^2$.

Taking into account previous definitions, the RCPSP-RP consists in defining a schedule for tasks/nodes assigned to teams over a time horizon H that minimizes the sum of weighted completion times:

$$f = \sum_{i \in V_d} r_i c_i \qquad (1)$$

where $c_i$ is the completion time of task i (see Sect. 3.2 for the complete mathematical formulations). In this context, the function f represents the accumulated risk ($r_i$) of unfinished tasks at each time unit $t \in H$, from which we can generate a graph that represents the risk mitigation process over the time horizon (see Fig. 1). Naturally, optimal solutions yield the smallest possible area.

## 3.1 Priority constraints

Similar to the d-relaxed priority rule presented in Panchamgam et al. (2013) (see also Doan et al. (2021)), priority constraints are added to perform task prioritization based on the $r_i$.

Priority constraints are represented by a Direct Acyclic Graph (DAG) defined as $D = (V_d, P)$, where we define P as the set of ordered pairs $P = \{(i, j) \in V_d^2 | r_i > r_j + d\}$ representing the priority relations. The relaxation threshold $d \in [0, 1]$ is used to adjust the priority policy strictness. We define the cases $d = 0$, $d = 0.5$ and $d = 1$ as, respectively, strict, moderate and zero priority policy. The strict policy ($d = 0$) imposes tasks to be processed in a decreasing order of risk; the moderate policy ($d = 0.5$) provides relative task prioritization; and the zero priority policy ($d = 1$) completely disables task prioritization.

As an illustration, Fig. 2 shows the priority relations generated for the strict and moderate priority policies using some example data.

* Fig. 2a displays the complete set of priority relations. It is worth noting that the priority relation (1, 3) is included for illustrative purposes but does not need to be a part of the set P since it is redundant. Redundant arcs can be eliminated

<figure><img src="image_4.png" /><figcaption>**Fig. 1** Overall risk of a solution with a total area (objective function) of 220.3. At $t = 0$, the accumulated risk is at its maximum and decreases over time as tasks are processed</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Fig. 2 Priority relations for the (2a) strict and (2b) moderate priority policies</figcaption></figure>

through a process known as transitive reduction of acyclic graphs (see, e. g., Gries et al. (1989)).

* In Fig. 2b, the priorities (1, 2) and (1, 4) have been relaxed because the conditions $r_1 > r_2 + d$ and $r_1 > r_4 + d$ are not met. Moreover, the priority relation (1, 3) emerges as it is no longer redundant.

It is clear that $P = \emptyset$ for the zero priority policy.

Given that priority constraints aim at modeling task prioritization and not opera-
tional relations, tasks are allowed to start at the same time as their predecessors as
long as there are enough available resources. For instance, $(i,j) \in P$ indicates that $i$
has priority over $j$ and $j$ may start at the same time or after $i$, but never before.

3.2 Mathematical formulations for the RCPSP-RP

In this section, the mathematical models for both problem scenarios under study
(with and without SDST) are provided as time-indexed integer formulations inspired
in Christofides et al. (1987)'s formulation for the RCPSP (see also Artigues (2017)).
The problem's input data is detailed in Table 1.

3.2.1 Scenario without sequence-dependent setup times

The model for the problem without SDST uses the following decision variables: the
binary variables $x_i^t, i \in V_d, \forall t \in H$, such that $x_i^t = 1$ if task $i$ starts at time $t$, $x_i^t = 0$ otherwise. The integer variables $c_i$ and $s_i$ correspond, respectively, to the start and completion times of task $i$.

$$
\text{Minimize } f = \sum_{i \in V_d} r_i c_i \quad \text{s.t.} \tag{2}
$$
<table><caption>**Table 1** Table of problem input data</caption><thead><tr><th>Input parameter</th><th>Description</th></tr></thead><tbody><tr><td>V</td><td>Set of nodes</td></tr><tr><td>E</td><td>Set of secured paths</td></tr><tr><td>V<sub>d</sub></td><td>Set of tasks</td></tr><tr><td>V<sub>o</sub></td><td>Singleton set containing the depot node</td></tr><tr><td>P</td><td>Set of precedence relations</td></tr><tr><td>H</td><td>Set of time units</td></tr><tr><td>K</td><td>Number of available teams at the depot</td></tr><tr><td>r<sub>i</sub> ∈ (0, 1]</td><td>Risk attribute of i ∈ V<sub>d</sub></td></tr><tr><td>p<sub>i</sub> ∈ Z<sup>+</sup></td><td>Processing time attribute of task i ∈ V<sub>d</sub></td></tr><tr><td>w<sub>ij</sub> ∈ N</td><td>Sequence-dependent setup times (travel times) between i and j, (i, j) ∈ V × V</td></tr></tbody></table>

$$ \sum_{i \in V_d} \sum_{\tau=t-p_i+1}^{t} x_i^\tau \leq K \quad \forall t \in H \quad (3) $$

$$ \sum_{i \in H} x_i^t = 1 \quad \forall i \in V_d \quad (4) $$

$$ s_i = \sum_{t \in H} tx_i^t \quad \forall i \in V_d \quad (5) $$

$$ c_i = \sum_{t \in H} (t + p_i)x_i^t \quad \forall i \in V_d \quad (6) $$

$$ s_i \leq s_j \quad \forall (i, j) \in P \quad (7) $$

$$ s_i \geq 0 \quad \forall i \in V_d \quad (8) $$

$$ c_i \geq 0 \quad \forall i \in V_d \quad (9) $$

$$ x_i^t \in \{0, 1\} \quad \forall i \in V_d, \forall t \in H \quad (10) $$

The objective function (2) minimizes the sum of completion times weighted by task risk. Constraints (3) define the resource constraints. Constraints (4) state that every task starts exactly once in the scheduling horizon. Constraints (5) and (6) calculate, respectively, the start and completion times of tasks. Constraints (7) refer to the priority constraints generated by the priority policy used. The model variables are defined in (8) – (10).
### 3.2.2 Scenario with sequence-dependent setup times

The model for the problem with SDST constraints uses binary variables $y_{ij}^t$ representing the flow of teams between $i$ and $j$ in period $t$, $i, j \in V$, $t \in H$, such that $y_{ij}^t = 1$ if task $j$ starts after task $i$ at period $t$, $y_{ij}^t = 0$ otherwise.

$$ \text{Minimize } f = \sum_{i \in V_d} r_i c_i \quad \text{s.t.} \tag{11} $$

$$ \sum_{i \in H} \sum_{j \in V_d} y_{ij}^t \le K \quad \forall i \in V_o \tag{12} $$

$$ \sum_{i \in H} \sum_{i \in V \setminus \{j\}} y_{ij}^t = 1 \quad \forall j \in V_d \tag{13} $$

$$ \sum_{i \in H} \sum_{i \in V \setminus \{j\}} y_{ji}^t = 1 \quad \forall j \in V_d \tag{14} $$

$$ \sum_{t \in H} \sum_{i \in V \setminus \{j\}} ty_{ji}^t \ge c_j \quad \forall j \in V_d \tag{15} $$

$$ s_j = \sum_{t \in H} \sum_{i \in V \setminus \{j\}} ty_{ij}^t \quad \forall j \in V_d \tag{16} $$

$$ c_j = \sum_{i \in H} \sum_{i \in V \setminus \{j\}} (t + w_{ij} + p_j)y_{ij}^t \quad \forall j \in V_d \tag{17} $$

$$ \text{Constraints(7) - (9)} \\ y_{ij}^t \in \{0, 1\} \quad \forall i, j \in V, \forall t \in H \tag{18} $$

The objective function (2) and the priority constraints (7) are previously defined. Constraints (12) represent the teams' departure from the depot node and their flow conservation across the graph is ensured by the constraints (13) – (15). Constraints (16) and (17) calculate, respectively, the start and completion times of tasks. The model variables are defined by (8) – (9) and (18). One may note that the model (2) – (10) can be emulated by switching off SDST, i.e., setting $w_{ij} = 0 \forall (i, j) \in V^2$, but with a considerably less efficient formulation.
# 4 Iterated local search for the RCPSP-RP

The Iterated Local Search (ILS), from the stand point of a metaheuristic classification, may be viewed as an iterative single-chain of solutions generated by an embedded heuristic, that usually leads to better solutions than repeating random trials of that heuristic (Lourenço et al. 2003). The concept of ILS leaves many implementation choices to developers. Thus, one can apply problem-specific knowledge to the optimization process (see, e. g. Huang et al. (2020)) and is known to have achieved numerous state-of-the-art results in the past (Lourenço et al. 2003).

The ILS implementation proposed in this paper is based on Lourenço et al. (2010). The following components describe our implementation choices for ILS applied to the RCPSP-RP.

Solutions are represented by a sequence $s = (j_1, ..., j_{|V_d|})$ of length $|V_d|$ containing tasks in a particular scheduling order. A sequence of tasks is feasible (does not violate the priority constraints) if $r_u \ge r_v - d$ holds for every u-th and v-th elements, with $u < v$. Thus, if $d = 0$ (strict priority policy), $s$ must sequence tasks in a non-increasing order of risk; if $d = 1$ (no priority policy), tasks can be sequenced in any order.

The construction of the initial solution is performed by a greedy heuristic that sequences tasks in a non-increasing order of risk. That is, the tasks with the highest risk attributes are queued before the tasks with lower risk ones. This is a computationally efficient greedy method that always generates a feasible solution and can be performed by a sorting algorithm with a $O(|V_d|\log|V_d|)$ computational complexity.

The evaluation procedure is a deterministic function that takes a feasible sequence of tasks $s$ and calculates the weighted sum of the completion times by assigning teams to tasks in the order the tasks appear in $s$. In the case that more than one team can be assigned to a same task, the team that provides the earliest completion time is chosen.

The local search is a first-improving heuristic (see, e. g. Anderson (1996)) that searches for local optima in the neighborhood $N$ of $s$ defined by the swap move: a procedure that changes the scheduling order of two tasks in a solution $s$. Such a procedure must always produce a feasible solution according to the given priority policy under consideration. For instance, when the strict policy is considered, it is only feasible to swap tasks of the same risk. On the other hand, when the no priority policy is applied, swapping is always allowed because there are no priority constraints. Thus, the neighborhood $N(s)$ may contain up to $O(|V_d|^2)$ solutions. The local search begins with a given solution $s$ and iteratively searches for a solution $s' \in N(s)$ that has a better objective function than $s$. If $s'$ exists, the local search will continue by assigning $s \leftarrow s'$ and repeating the process until no neighbor $s'$ outperforms $s$, which means that a local optimum has been found.

The perturbation procedure is used to introduce diversity in the optimization process by applying multiple random swaps to a local optimum $s$. It is controlled by a strength parameter ($\rho$) that ranges over the interval $[0, 1]$ and states how
many random moves are introduced in the solution, calculated by the formula $||V_d| \times \rho \div 2|$. A random swap is only introduced if the solution remains feasible. The higher the value of the strength parameter, the more diversified the resulting solution is.

The acceptance criterion is a memory less function that prioritizes solutions with better objective function values, defined as:

$$ Better(s^*, s'^{\prime}) = \begin{cases} s^{*\prime}, & \text{if } \mathcal{E}(s^{*\prime}) < \mathcal{E}(s^*) \\ s^*, & \text{otherwise} \end{cases} \qquad (19) $$

Where $\mathcal{E}$ represents the evaluation procedure. In particular, $s^{*\prime}$ is only accepted if it improves upon $s^*$. This criterion emphasizes intensification over diversification, compelling the search to move toward a solution with a lower objective function value, effectively following a first-improvement descent strategy.

Overall, ILS starts by generating a feasible initial solution by sorting tasks in a decreasing order of risk (this always guarantees a feasible solution) followed by a local search. Afterwards, in the optimization loop, consecutive calls to the perturbation and local search procedures are applied, updating the current solution whenever a better one is found. The stopping criterion is defined as a maximum number of calls to the evaluation procedure. This number is named the solution budget and it is a configurable parameter that can vary from 1 to any large integer. Each time a solution is evaluated, the solution budget decreases by 1. Once the solution budget reaches 0, the optimization process will stop and return the current local optima solution $s^*$. This strategy is used to limit ILS complexity to a certain polynomial in the worst-case, defined by the solution budget value. It is also particularly interesting for ensuring repeatability of results and fair comparison across methods of different nature (Wang et al. 2015). The best solution found during the optimization process is returned at the end of the run. Since ILS is a stochastic method, multiple runs should be performed for a given problem instance.

# 5 Computational experiments

Computational experiments were conducted in order to assess the performance of the proposed methods.

These experiments were conceived to obtain insights into the nature of the problem by measuring the impact of different experimental settings on the quality of the solutions and the algorithmic performance. These settings include: (a) different problem instances of increasing order of complexity such as to analyze the scalability of the problem; (b) the impact of travel times, that may or may not be considered depending on whether we assume large or confined areas where travel times can be neglected, and (c) the effects of priority constraints under three different relaxation schemes in use, namely strict, moderate and no priority policies.

This section also describes the procedure for generating the benchmark instances, the algorithm implementation details, the parameter settings and the system configuration in which the experiments were conducted. The source code for the
<figure><img src="image_6.png" /><figcaption>**Fig. 3** Example of a hexagonal grid instance</figcaption></figure>

<table><caption>**Table 2** Summary of the benchmark instances</caption><thead><tr><th>Parameter</th><th>Value</th></tr></thead><tbody><tr><td>Graph topology</td><td>Hexagonal grid</td></tr><tr><td>Number of tasks (|V<sub>d</sub>|)</td><td>8, 16, 32, 64</td></tr><tr><td>Number of teams (K)</td><td>from 1 to |V<sub>d</sub>|, in powers of 2</td></tr><tr><td>Distribution of task risk (r<sub>i</sub>)</td><td>U(0, 1]</td></tr><tr><td>Distribution of task duration (p<sub>i</sub>)</td><td>U[1, 10]</td></tr></tbody></table>

experiments has been made publicly available under MIT license at Barbalho (2022).

## 5.1 Benchmark design

Following an analogous approach to the one presented in Pena et al. (2022), a theoretical instance benchmark is proposed. The benchmark is designed to investigate the scalability of the RCPSP-RP on instances with an increasing number of tasks and with a variable number of teams, in order to determine which features render the problem more intractable.

Each of these instances is defined on a hexagonal grid layout as depicted in Fig. 3: hexagonal grids provide more accuracy than other 2-dimensional graph topologies when mapping Euclidean to grid distances (Birch et al. 2007; Mora et al. 2007), thus, one can map terrains with more accurate distance measures.

The procedure to generate the instances can be described as follows (see Table 2 for the different parameters values that were used for the generation of such instances): it starts by generating a hexagonal grid lattice with a depot located at the top-left node for each number of tasks $|V_d| \in \{8, 16, 32, 64\}$, each with $r_i$ and $p_i$ attributes drawn over the discrete uniform distributions $U(0, 1)$ and $U[1, 10]$, respectively. The hexagonal grid is consistently generated in a square-like shape, with equal width and height whenever feasible. However, in certain instances, there may be slight variations in the width and height. Afterwards, for each generated graph, $log_2|V_d|$ instances are created with $\{2^0, 2^1, 2^2, ..., 2^{log_2|V_d|}\}$ teams placed at the depot
node. Subsequently, SDST are obtained by calculating the shortest path between each pair of nodes in the graph with each edge weighted by 1. Following this procedure, the benchmark contains 22 unique instances, although it could be easily parameterized to generate other instances at will.

## 5.2 Implementation details and tuning of parameters

The integer models [(2) – (10)] and [(11) – (18), (7) – (9)] for the two problem scenarios were implemented in PuP (version 2.4) and linked to IBM ILOG CPLEX (version 20.1) with default parameters and time limit of 4 h for every instance. The experiments were carried out on a Ubuntu (version 18.04.1) machine with a 26 core Intel Xeon Processor (Skylake) CPU @ 2.1Ghz and 288GB available RAM, at the computing facilities of the Laboratoire d'Informatique, du Traitement de l'Information et des Systèmes (LITIS).

The ILS was implemented in Python with the perturbation parameter tuned by the IRACE package (López-Ibáñez et al. 2016). The IRACE package is a software that implements the iterated F-race algorithm to automatically find the best parameter settings of an optimizer. The package performs an elitist racing procedure to ensure that the best configurations returned are evaluated in the highest number of training instances. For this purpose, 5 training instances of different sizes in which optimal values were known were used to tune the ILS perturbation parameter under the two problem scenarios and the three priority policies. These instances are part of the benchmark set and therefore utilize the same distributions. The configurations returned by IRACE are shown in Table 3 and they represent the respective parameterization employed for the different scenarios. The maximum number of calls to the evaluation procedure is used as the stopping criterion. We refer to this maximum number of calls as the *solution budget* and it is determined by the formula $|V_d| \times 10,000$. A total of 35 repetitions with different random seeds were performed for every instance.

## 5.3 Analysis of results

Experimental results were compiled and summarized in Tables 4 and 5. They both present the numerical results obtained by CPLEX and ILS for the different benchmark instances under study, each instance being identified by a tuple $(|V_d|, K)$.

In the case of CPLEX, results show either the optimal or the best integer solutions found, if any exist. Otherwise, lower bounds are provided. As for ILS, the best solution found out of all independent runs is given as well as the mean solution

<table><caption>**Table 3** Best configuration returned by IRACE for ILS' perturbation strength parameter by problem scenario × priority policy</caption><thead><tr><th rowspan="2">Travel times?</th><th colspan="3">Priority policy</th></tr><tr><th>Strict</th><th>Moderate</th><th>None</th></tr></thead><tbody><tr><td>Yes</td><td>0.61</td><td>0.19</td><td>0.86</td></tr><tr><td>No</td><td>0.50</td><td>0.56</td><td>0.24</td></tr></tbody></table>
values in all the runs. Solutions known to be optimal are shown in bold font in both cases, CPLEX and ILS. A preliminary analysis of these results suggests that:

* In general terms, and not surprisingly, the larger the number of tasks ($|V_d|$) is, the harder the problem instance gets.

* In contrast, the larger the number of teams (K) is, the easier the problem instance gets. The specific case $K = |V_d|$ can be trivially solved.

* The tractability of the problem in scenarios that take into account travel times is harder, i.e. optimizing the routing aspect adds additional complexity to the scheduling problem.

* The relaxation of priority constraints can have different effects on the computational performance depending on the chosen algorithmic approach:

* the first integer model gets harder to solve the more priority constraints there are.

* both the second integer model and ILS' complexity increases as the number of priority constraints decreases. A possible explanation is that relaxing these constraints implies exploring a larger solution space.

* Despite the fact that the problem's complexity is hardened when relaxing priority constraints, it usually pays off in terms of objective function value.

* In all of the instances under study in which CPLEX is capable of computing the optimum, ILS is able to yield either the optimal or a near-optimal value with a small percentage gap. This fact, together with CPLEX's incapability to find solutions for the hardest instances, points to the proposed ILS implementation as a good alternative to solve the RCPSP-RP efficiently both in computational and algorithmic terms.

Given the impact that travel times and priority policies have on the numerical results, the following sections provide a more detailed analysis of such experimental scenarios.

### 5.3.1 Scenario without sequence-dependent setup times

The first experimental scenario aims at analyzing the results of the benchmark instances with disabled SDST. In practice, this scenario can arise, for instance, in the context of industrial disasters contained in self-enclosed spaces, where travel times can be neglected from a practical perspective since processing times are considerable longer. The complete numerical results are compiled in Table 4.

In the experiments carried out using CPLEX, out of the 22 instances, the number of obtained optimal solutions was 20, 22 and 22 for the strict, moderate and no priority policy, respectively. For the strict policy, the integer solutions found for the instances (64, 1) and (64, 2) are the only ones not guaranteed to be optimal, with gaps of 0.42% and 0.26% to their best lower bounds, respectively.

The number of optimal solutions obtained by ILS was 20 out of 22 for every different priority policy under study:
* For the strict policy, all the solutions are identical to the ones obtained by CPLEX.

* For the moderate policy, the best solutions found for the instances (64, 1) and (64, 2) are non-optimal with percentage gaps of 0.011% and 0.017% to the optimal solutions, respectively.

* For the no priority policy, the best solutions found for the instances (64, 2) and (64, 4) are also non-optimal with percentage gaps of 0.021% and 0.005%, respectively.

Even though ILS fails to compute the optimal solutions in 4 cases, the solutions can be considered near-optimal since the percentage gaps to the optimal solutions are in the order of hundredths or even thousandths.

Another aspect to analyze from the obtained results is the effect that the priority policy strictness has on the computed overall risk. The strict priority policy is, in general, the one that yields the worst objective function values. As a conclusion, results indicate that using such policy is not the best operational strategy if one wants to obtain the best solution possible. Nonetheless, it can be argued that decision makers may impose task prioritization in certain emergency situations. In such cases, the moderate policy seems to be a good alternative to the strict one.

While imposing certain constraints in the order that tasks are processed, the moderate priority policy is capable of generating solutions that are, on average 8.74% (and up to 20.87% in the best case) better than the strict policy. If task prioritization is not required, the no priority policy can yield solutions that are, on average, 8.79% (and also up to 20.87% in the best case) better than the strict policy. The no priority policy is also slightly better than the moderate by 0.06%, on average, and up to 0.43% in the best case. For visualization purposes, Fig. 4 shows the strict vs. no priority policies comparison for two representative instances. Naturally, the no priority policy yields smaller graph areas, mostly due to a stronger decrease of the overall risk at early periods.

Last but not least, another important aspect to consider is the running times of the different algorithmic approaches. Typically, when comparing different

<figure><img src="image_7.png" /><figcaption>**Fig. 4** Comparison of optimal solutions for the strict and no priority policies. Purple regions are the overlapping of the solutions in orange and blue. The respective objective functions are a 40.1 and 33.8; and b 183.3 and 172.5</figcaption></figure>
optimization techniques, the preference is to select the one that, given the same results, takes the shorter time. Moreover, in many cases, a small loss in the quality of the solutions provided by a method can be justified if the running time is substantially shorter than that of another method. This may be the case, for instance, in disaster relief operations where a rapid post-disaster response is usually expected.

In order to compare CPLEX and ILS in terms of their computational performance, Fig. 5 shows the running times of both algorithmic approaches for the benchmark instances. The plots were obtained by retrieving, for each instance, the time to solution for CPLEX and the average execution time to the best solution found out of the 35 independent runs for ILS. In general, instances towards the bottom right corner are harder to solve.

<figure><img src="image_8.png" /><figcaption>**Fig. 5** Color maps representing CPLEX and ILS running times for the scenario without SDST. The gray-scale, ranging from light to dark, represents the base-10 exponents (log scale) corresponding to the number of seconds required to find the best solution. Each gray square represents an instance ($|V_d|$, $K$)</figcaption></figure>
For CPLEX, instances under the strict policy usually have longer running times than their moderate or none counterparts. In particular, the instances (64, 1) and (64, 2) are the hardest ones for CPLEX. Under strict priorities, they reached 4 h time limit while their moderate and none equivalent required respectively 12.45s and 3.36s to complete. These two specific instances required between 0.20s and 1.5s to be solved in ILS, with the shortest running time for the instance (64, 1) under strict priorities and the longest running time for the instance (64, 2) under moderate policy. This signals that the problem scenario becomes easier to solve in CPLEX as the number of priority constraints decreases. For ILS, contrary to CPLEX, the relaxation of priority constraints slightly increases the running times due to the exploration of a larger solution space.

In the experiments carried out with the moderate and no priority policies, CPLEX and ILS can be considered equivalent in terms of solution quality and computational complexity, since both methods can calculate optimal solutions with short running times in the order of seconds. The only notable difference is for the strict policy, where ILS can provide the same optimal solutions as CPLEX in substantially less time. For more complex scenarios as the one presented in the next section, CPLEX starts to fail to obtain optimal, or even integer, results while ILS continues to scale polynomially.

### 5.3.2 Scenario with sequence-dependent setup times

This second experimental scenario aims at analyzing the results of the benchmark instances with enabled SDST. In practice, this scenario can arise, for instance, in the context of industrial disasters affecting large areas, where travel times cannot be neglected and must be taken into consideration in the optimization process. The complete numerical results are compiled in Table 5.

In the experiments carried out using CPLEX, out of the 22 instances, the number of obtained optimal solutions was 14, 13 and 13 for the strict, moderate and no priority policies, respectively. CPLEX failed to compute 8, 9 and 7 integer solutions for each priority policy, which shows that this scenario is harder to solve than its counterpart without SDST. Additionally, for the no priority policy, the solutions found for the instances (16, 1) and (32, 4) are not guaranteed to be optimal, with gaps of 55.02% and 27.24% to their respective best lower bounds.

Since CPLEX failed to yield an integer solution in some of the instances and obtained non-optimal results in another two of them, it was not possible to determine optimality for the strict, moderate and no priority policies in 8, 9, and 9 of the instances, respectively. Overall, results show the adequacy of ILS to address the case scenario with enabled SDST while CPLEX does not. Clearly, by adding SDST, a large portion of the instances becomes unsolvable by CPLEX within the given time limit of 4 h and most of the solution from 32 tasks ahead are left without integer solutions. Meanwhile, ILS presents the same polynomial complexity growth shown in the first problem scenario.

ILS obtains both optimal and near-optimal results in instances with known optimal values and is capable of obtaining competitive results in instances where CPLEX fails to obtain any integer solution. ILS, in the other hand, was able to
provide a solution in all of these cases and to outperform the non-optimal integer solutions provided by CPLEX. Additionally, ILS also obtained 11, 11 and 12 optimal solutions for the strict, moderate and no priority policies, respectively. Below we detail the cases in which ILS was not able to attain known optimal solutions:

* For the strict policy, the solutions calculated for the instances (16, 4), (32, 16) and (64, 32) are non-optimal with percentage gaps to the optimum of 0.33%, 0.19% and 0.66%, respectively.

* For the moderate policy, the solutions calculated for the instances (16, 2) and (64, 32) are also non-optimal with percentage gaps of 0.06% and 0.16%, respectively.

* For the no priority policy, the solution for the instance (64, 32) is non-optimal with a percentage gap of 0.18%. Nevertheless, the solutions obtained for the

<figure><img src="image_9.png" /><figcaption>**Fig. 6** Color maps representing CPLEX and ILS running times for the scenario with SDST. The gray-scale, ranging from light to dark, represents the base-10 exponents (log scale) corresponding to the number of seconds required to find the best solution. Each gray square represents an instance ($|V_d|$, $K$)</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>**Fig. 7** Comparison of optimal solutions for the strict and no priority policies. Purple regions are the overlapping of the solutions in orange and blue. The respective objective functions are **a** 77.5 and 63.4; and **b** 300.6 and 272.1</figcaption></figure>

instances (64, 2) and (64, 4) are, respectively, 3.19% and 10.81% better than those obtained by CPLEX.

In order to compare CPLEX and ILS in terms of their computational performance, Fig. 6 shows the running times of both algorithmic approaches for the different benchmark instances. Instances towards the right bottom corner are harder to solve. This comparison reinforces the previous conclusion that by enabling SDST in the optimization process, the problem becomes considerably less tractable for exact solvers such as CPLEX, while the computational performance of ILS scales polynomially.

Similarly to the first experimental scenario, the regime of task prioritization has a great effect in the overall risk as exemplified in Fig. 7. The no priority policy, in general, yields the smallest objective function values, although it can be considered virtually equivalent in terms of solution quality and running times to the moderate priority policy:

* The no priority policy can yield solutions that are, on average, 6.56% (and up to 20.02% in the best case) better than the strict policy.

* The moderate policy is capable of generating solutions that are, on average 5.51% (and up to 19.70% in the best case) better than the strict policy.

## 5.4 Theoretical and practical implications

The computational experiments conducted in this study provide several valuable theoretical and practical insights into the RCPSP-RP. This section aims to discuss and explain these implications while suggesting how the findings can be applied to more realistic, real-life scenarios. Some theoretical implications include, but not limited to:
<figure><img src="image_11.png" /></figure>

<table><caption>Table 4 Results for the problem scenario without sequence-dependent setup times</caption><thead><tr><th rowspan="3">Instance<br>|V<sub>d</sub>|</th><th rowspan="3">K</th><th colspan="6">Priority policy</th><th colspan="6">none</th></tr><tr><th colspan="3">strict</th><th colspan="3">moderate</th><th colspan="3">none</th><th colspan="3">none</th></tr><tr><th>CPLEX<br>best</th><th>ILS<br>best</th><th>mean</th><th>CPLEX<br>best</th><th>ILS<br>best</th><th>mean</th><th>CPLEX<br>best</th><th>ILS<br>best</th><th>mean</th><th>CPLEX<br>best</th><th>ILS<br>best</th><th>mean</th></tr></thead><tbody><tr><td>8</td><td>1</td><td><strong>40.1</strong></td><td>-</td><td>40.1</td><td>33.8</td><td>-</td><td>33.8</td><td>33.8</td><td>-</td><td><strong>33.8</strong></td><td>-</td><td>33.8</td><td>33.8</td></tr><tr><td>2</td><td>2</td><td><strong>23.2</strong></td><td>-</td><td>23.2</td><td>21.4</td><td>-</td><td>21.4</td><td>21.4</td><td>-</td><td><strong>21.4</strong></td><td>-</td><td>21.4</td><td>21.4</td></tr><tr><td>4</td><td>4</td><td><strong>16.3</strong></td><td>-</td><td>16.3</td><td>16.3</td><td>-</td><td>16.3</td><td>16.3</td><td>-</td><td><strong>16.3</strong></td><td>-</td><td>16.3</td><td>16.3</td></tr><tr><td>8</td><td>8</td><td><strong>14.8</strong></td><td>-</td><td>14.8</td><td>14.8</td><td>-</td><td>14.8</td><td>14.8</td><td>-</td><td><strong>14.8</strong></td><td>-</td><td>14.8</td><td>14.8</td></tr><tr><td>16</td><td>1</td><td><strong>264.5</strong></td><td>-</td><td>264.5</td><td>209.3</td><td>-</td><td>209.3</td><td>209.3</td><td>-</td><td><strong>209.3</strong></td><td>-</td><td><strong>209.3</strong></td><td>209.3</td></tr><tr><td></td><td>2</td><td><strong>141.2</strong></td><td>-</td><td>141.2</td><td>117.3</td><td>-</td><td>117.3</td><td>117.3</td><td>-</td><td><strong>117.3</strong></td><td>-</td><td><strong>117.3</strong></td><td>117.4</td></tr><tr><td></td><td>4</td><td><strong>79.6</strong></td><td>-</td><td>79.6</td><td>72.5</td><td>-</td><td>75.5</td><td>72.5</td><td>-</td><td><strong>72.5</strong></td><td>-</td><td><strong>72.5</strong></td><td>72.5</td></tr><tr><td></td><td>8</td><td><strong>52.3</strong></td><td>-</td><td>52.3</td><td>52.0</td><td>-</td><td>52.0</td><td>52.0</td><td>-</td><td><strong>52.0</strong></td><td>-</td><td><strong>52.0</strong></td><td>52.0</td></tr><tr><td></td><td>16</td><td><strong>47.2</strong></td><td>-</td><td>47.2</td><td>47.2</td><td>-</td><td>47.2</td><td>47.2</td><td>-</td><td><strong>47.2</strong></td><td>-</td><td><strong>47.2</strong></td><td>47.2</td></tr><tr><td>32</td><td>1</td><td><strong>1167.1</strong></td><td>-</td><td>1167.1</td><td>977.9</td><td>-</td><td>977.9</td><td>977.9</td><td>-</td><td><strong>977.9</strong></td><td>-</td><td><strong>977.9</strong></td><td>977.9</td></tr><tr><td></td><td>2</td><td><strong>601.8</strong></td><td>-</td><td>601.8</td><td>516.0</td><td>-</td><td>516.0</td><td>516.0</td><td>-</td><td><strong>516.0</strong></td><td>-</td><td><strong>516.0</strong></td><td>516.0</td></tr><tr><td></td><td>4</td><td><strong>324.3</strong></td><td>-</td><td>324.3</td><td>285.5</td><td>-</td><td>285.5</td><td>285.5</td><td>-</td><td><strong>285.5</strong></td><td>-</td><td><strong>285.5</strong></td><td>285.6</td></tr><tr><td></td><td>8</td><td><strong>183.3</strong></td><td>-</td><td>183.3</td><td>172.5</td><td>-</td><td>172.5</td><td>172.5</td><td>-</td><td><strong>172.5</strong></td><td>-</td><td><strong>172.5</strong></td><td>172.5</td></tr><tr><td></td><td>16</td><td><strong>120.1</strong></td><td>-</td><td>120.1</td><td>118.7</td><td>-</td><td>118.7</td><td>118.7</td><td>-</td><td><strong>118.7</strong></td><td>-</td><td><strong>118.7</strong></td><td>118.7</td></tr><tr><td></td><td>32</td><td><strong>104.1</strong></td><td>-</td><td>104.1</td><td>104.1</td><td>-</td><td>104.1</td><td>104.1</td><td>-</td><td><strong>104.1</strong></td><td>-</td><td><strong>104.1</strong></td><td>104.1</td></tr></tbody></table>
<table><caption>Table 4 (continued)</caption><thead><tr><th rowspan="3">Instance<br>|V<sub>d</sub>|</th><th rowspan="3">K</th><th colspan="6">Priority policy</th><th colspan="6">none</th></tr><tr><th colspan="3">strict</th><th colspan="3">moderate</th><th colspan="3">none</th><th colspan="3">none</th></tr><tr><th>CPLEX<br>best</th><th>ILS<br>best</th><th>mean</th><th>CPLEX<br>best</th><th>ILS<br>best</th><th>mean</th><th>CPLEX<br>best</th><th>ILS<br>best</th><th>mean</th><th>CPLEX<br>best</th><th>ILS<br>best</th><th>mean</th></tr></thead><tbody><tr><td>64</td><td>1</td><td>4258.2</td><td>4240.2</td><td>4258.2</td><td>3501.6</td><td>-</td><td>3502.2</td><td>3504.5</td><td>3486.6</td><td>-</td><td>3486.6</td><td>-</td><td>3486.6</td></tr><tr><td>2</td><td>2</td><td>2161.2</td><td>2155.5</td><td>2161.2</td><td>1797.5</td><td>-</td><td>1797.7</td><td>1798.4</td><td>1791.4</td><td>-</td><td>1791.5</td><td>-</td><td>1791.5</td></tr><tr><td>4</td><td>4</td><td>1115.8</td><td>-</td><td>1115.8</td><td>947.2</td><td>-</td><td>947.2</td><td>947.3</td><td>944.6</td><td>-</td><td>944.8</td><td>-</td><td>944.9</td></tr><tr><td>8</td><td>8</td><td>600.1</td><td>-</td><td>600.1</td><td>523.7</td><td>-</td><td>523.7</td><td>523.8</td><td>522.8</td><td>-</td><td>522.8</td><td>-</td><td>522.8</td></tr><tr><td>16</td><td>16</td><td>345.0</td><td>-</td><td>345.0</td><td>315.7</td><td>-</td><td>315.7</td><td>315.7</td><td>315.3</td><td>-</td><td>315.3</td><td>-</td><td>315.3</td></tr><tr><td>32</td><td>32</td><td>220.3</td><td>-</td><td>220.3</td><td>217.9</td><td>-</td><td>217.9</td><td>217.9</td><td>217.9</td><td>-</td><td>217.9</td><td>-</td><td>217.9</td></tr><tr><td>64</td><td>64</td><td>189.4</td><td>-</td><td>189.4</td><td>189.4</td><td>-</td><td>189.4</td><td>189.4</td><td>189.4</td><td>-</td><td>189.4</td><td>-</td><td>189.4</td></tr></tbody></table>
<figure><img src="image_12.png" /><figcaption>**Table 5** Results for the problem scenario with sequence-dependent setup times</figcaption></figure>

<table><thead><tr><th rowspan="3">Instance<br>|V<sub>d</sub>|</th><th rowspan="3">K</th><th colspan="6">Priority policy</th><th colspan="6">none</th></tr><tr><th colspan="2">strict</th><th colspan="4">moderate</th><th colspan="2">CPLEX</th><th colspan="2">ILS</th><th colspan="2">ILS</th></tr><tr><th>CPLEX<br>best</th><th>LB</th><th>ILS<br>best</th><th>ILS<br>best</th><th>ILS<br>best</th><th>ILS<br>mean</th><th>best</th><th>LB</th><th>best</th><th>best</th><th>mean</th></tr></thead><tbody><tr><td>8</td><td>1</td><td>77.5</td><td>-</td><td>77.5</td><td>77.5</td><td>-</td><td>63.4</td><td>-</td><td>63.4</td><td>63.4</td><td>63.4</td><td>63.4</td></tr><tr><td>2</td><td>2</td><td>45.1</td><td>-</td><td>45.1</td><td>45.1</td><td>-</td><td>43.4</td><td>-</td><td>43.4</td><td>43.4</td><td>43.4</td><td>43.4</td></tr><tr><td>4</td><td>4</td><td>33.7</td><td>-</td><td>33.7</td><td>33.7</td><td>-</td><td>32.9</td><td>-</td><td>32.9</td><td>32.9</td><td>32.9</td><td>32.9</td></tr><tr><td>8</td><td>8</td><td>28.6</td><td>-</td><td>28.6</td><td>28.6</td><td>-</td><td>28.6</td><td>-</td><td>28.6</td><td>28.6</td><td>28.6</td><td>28.6</td></tr><tr><td>16</td><td>1</td><td>376.6</td><td>-</td><td>376.6</td><td>376.6</td><td>-</td><td>190.8</td><td>-</td><td>291.6</td><td>291.6</td><td>301.2</td><td>194.3</td></tr><tr><td>2</td><td>2</td><td>202.5</td><td>-</td><td>202.5</td><td>202.5</td><td>-</td><td>162.6</td><td>-</td><td>162.7</td><td>165.53</td><td>162.6</td><td>162.6</td></tr><tr><td>4</td><td>4</td><td>121.2</td><td>-</td><td>121.6</td><td>121.6</td><td>-</td><td>106.6</td><td>-</td><td>106.6</td><td>107.4</td><td>106.6</td><td>106.6</td></tr><tr><td>8</td><td>8</td><td>81.2</td><td>-</td><td>81.2</td><td>82.2</td><td>-</td><td>81.1</td><td>-</td><td>81.1</td><td>81.1</td><td>81.1</td><td>81.1</td></tr><tr><td>16</td><td>16</td><td>75.3</td><td>-</td><td>75.3</td><td>75.3</td><td>-</td><td>75.3</td><td>-</td><td>75.3</td><td>75.3</td><td>75.3</td><td>75.3</td></tr><tr><td>32</td><td>1</td><td>-</td><td>349.5</td><td>1667.0</td><td>1669.4</td><td>-</td><td>331.0</td><td>1402.0</td><td>1410.5</td><td>-</td><td>381.9</td><td>1402.3</td></tr><tr><td>2</td><td>2</td><td>-</td><td>430.7</td><td>900.6</td><td>903.5</td><td>-</td><td>364.4</td><td>735.5</td><td>739.7</td><td>-</td><td>297.9</td><td>735.4</td></tr><tr><td>4</td><td>4</td><td>-</td><td>433.1</td><td>500.4</td><td>502.9</td><td>-</td><td>368.0</td><td>420.9</td><td>426.4</td><td>471.8</td><td>370.8</td><td>420.8</td></tr><tr><td>8</td><td>8</td><td>300.6</td><td>-</td><td>300.6</td><td>301.4</td><td>-</td><td>272.1</td><td>-</td><td>272.1</td><td>274.4</td><td>272.1</td><td>272.1</td></tr><tr><td>16</td><td>16</td><td>214.7</td><td>-</td><td>215.1</td><td>215.1</td><td>-</td><td>205.9</td><td>-</td><td>205.9</td><td>205.9</td><td>205.9</td><td>205.9</td></tr><tr><td>32</td><td>32</td><td>185.6</td><td>-</td><td>185.6</td><td>185.6</td><td>-</td><td>185.6</td><td>-</td><td>185.6</td><td>185.6</td><td>185.6</td><td>185.6</td></tr></tbody></table>
<table><caption>Table 5 (continued)</caption><thead><tr><th rowspan="3">Instance<br>|V<sub>d</sub>|</th><th rowspan="3">K</th><th colspan="6">Priority policy</th><th colspan="6">none</th></tr><tr><th colspan="3">strict</th><th colspan="3">moderate</th><th colspan="3">none</th><th colspan="3">none</th></tr><tr><th>CPLEX<br>best</th><th>ILS<br>best</th><th>mean</th><th>CPLEX<br>best</th><th>ILS<br>best</th><th>mean</th><th>CPLEX<br>best</th><th>ILS<br>best</th><th>mean</th><th>CPLEX<br>best</th><th>ILS<br>best</th><th>mean</th></tr></thead><tbody><tr><td>64</td><td>1</td><td>-</td><td>433.3</td><td>6250.1</td><td>6333.9</td><td>-</td><td>421.15</td><td>4936.6</td><td>5117.1</td><td>-</td><td>420.0</td><td>4987.3</td><td>5118.3</td></tr><tr><td></td><td>2</td><td>-</td><td>429.2</td><td>3164.6</td><td>3202.8</td><td>-</td><td>417.38</td><td>2578.0</td><td>2650.3</td><td>-</td><td>648.5</td><td>2634.8</td><td>2710.9</td></tr><tr><td></td><td>4</td><td>-</td><td>533.9</td><td>1681.4</td><td>1698.2</td><td>-</td><td>417.38</td><td>1401.4</td><td>1429.3</td><td>-</td><td>493.0</td><td>1403.0</td><td>1450.7</td></tr><tr><td></td><td>8</td><td>-</td><td>497.5</td><td>979.7</td><td>986.2</td><td>-</td><td>504.40</td><td>823.0</td><td>838.4</td><td>-</td><td>490.5</td><td>831.1</td><td>850.0</td></tr><tr><td></td><td>16</td><td>-</td><td>591.8</td><td>615.1</td><td>616.6</td><td>-</td><td>489.65</td><td>547.2</td><td>553.2</td><td>-</td><td>542.2</td><td>551.4</td><td>559.1</td></tr><tr><td></td><td>32</td><td>-</td><td><strong>439.3</strong></td><td>442.2</td><td>443.3</td><td>-</td><td><strong>431.0</strong></td><td>-</td><td>431.7</td><td>432.2</td><td><strong>430.5</strong></td><td>-</td><td>431.3</td><td>432.2</td></tr><tr><td></td><td>64</td><td>-</td><td><strong>392.6</strong></td><td>-</td><td><strong>392.6</strong></td><td>-</td><td><strong>392.6</strong></td><td>-</td><td><strong>392.6</strong></td><td>392.6</td><td><strong>392.6</strong></td><td>-</td><td><strong>392.6</strong></td><td>392.6</td></tr></tbody></table>

<figure><img src="image_13.png" /></figure>
* *Scalability and solution quality:* the benchmark instances reveal how the proposed methods scale with the number of tasks ($|V_d|$), which is evident from the increased computational effort required by CPLEX and the performance of the ILS metaheuristic. These insights are crucial for decision-makers who need to effectively plan resources when handling large-scale scheduling problems.

* *Algorithm performance:* the experiments demonstrate the efficiency of ILS compared to CPLEX across different scenarios. These results show that approximate methods like ILS work well for solving large and complex RCPSP-RP problems that can be, otherwise, intractable for exact solvers within a reasonable time-frame.

* *Benchmark design:* The use of a hexagonal grid to design benchmark instances offers a systematic way to study the problem's scalability and tractability. Theoretical insights from this approach include understanding how the topological structure and instance parameters influence both the problem's tractability and solution quality. These insights can guide future research in designing more efficient algorithms and heuristics for similar scheduling problems.

* *Parameter tuning:* the use of IRACE for tuning the ILS parameters underscores the importance of parameter optimization in heuristic methods. This theoretical insight can be extended to other optimization problems, emphasizing the needs for automated parameter tuning techniques to enhance algorithm performance.

In addition, some practical implications include improvements in response strategies and enhancing overall readiness for emergencies. These implications emphasize the importance of the problem and experimental findings in driving advancements in disaster management. Some practical implications include, but are not limited to:

* *Disaster relief operations:* For large-scale disaster relief operations, where travel times and resource allocation are critical, the findings suggest using heuristic methods like ILS with moderate priority policies. This approach allows for quickly generating solutions while still prioritizing high-risk tasks over lower-risk ones.

* *Impact of travel times:* The experiments reveal the significant impact of travel times on the tractability of RCPSP-RP. In scenarios where travel times are negligible, such as within confined industrial sites, the problem becomes more tractable. Conversely, scenarios with substantial travel times, such as large-scale disaster relief operations, are significantly harder to solve. This finding aids decision-makers in determining when travel times should be factored into the problem and when they can be safely disregarded, thereby simplifying the optimization process.

* *Priority constraints:* The results indicate that relaxing priority constraints generally improves objective function values; however, it also increases the combinatorial complexity of the optimization process. Decision-makers can use this insight to balance the trade-off between optimal scheduling and computational feasibility. For instance, in emergency situations requiring rapid decision-making, a moderate priority policy may offer an effective compromise between optimality and computational efficiency.

<figure><img src="image_14.png" /></figure>
* Resource management: The study's insights can be applied to resource management across various fields, such as construction, manufacturing, and service delivery, where scheduling and resource allocation are critical. Predicting the problem's tractability based on the number of tasks and the inclusion of travel times can aid in strategic planning and decision-making.

In conclusion, the computational experiments and the resulting insights offer valuable contributions to both the practical application and theoretical understanding of the RCPSP-RP. By extending these findings to more realistic scenarios, decision makers and researchers can better tackle complex scheduling problems with risks tasks across various domains.

# 6 Conclusions and future works

This paper presents an extended version of the RCPSP which allows the problem to be adapted to new application domains where tasks have priorities associated to their risk attribute. The proposed RCPSP with Risk and Priorities (RCPSP-RP) is an integrated scheduling and routing model that aims at minimizing the sum of completion times weighted by a risk factor, and that allows task prioritization by means of priority constraints. These constraints are represented as precedence relations disposed as a directed acyclic graph with two particularities: i) they can be relaxed by means of a threshold parameter and ii) tasks are allowed to start at the same time as their predecessors as long as there are enough available resources. In addition, two versions, considering or not SDST are investigated.

In order to conduct a study on instances of increasing order of difficulty, we have focused on the application of the problem to the post-catastrophe operations in the event of industrial disasters, where a group of specialized teams are deployed to clean up areas contaminated by dangerous substances. Each polluted area is represented as a node in a connected graph and has an associated risk that depends on the hazardous nature of pollutants.

Two mathematical formulations and an ILS metaheuristic were developed and tested on a theoretical benchmark with two possible scenarios: with and without travel times.

A first conclusion that can be drawn from this study is that travel times make the problem less tractable for the integer models. Particularly in CPLEX, instances with more than 16 tasks start to become unsolvable within the prefixed computing time horizon of 4 h. On the other hand, ILS shows polynomial scalability of the running times, obtaining solutions for any instance under study in the order of seconds. Furthermore, ILS is capable of finding optimal or near-optimal solutions in instances with known optimal values. Therefore, it is advisable to use a metaheuristic approach such as ILS, specially when tackling large or demanding instances.

A second conclusion concerning the RCPSP-RP is that relaxing the priority constraints leads to a greater minimization of the overall risk. In particular, imposing priority constraints significantly impairs the results obtained. The more constraints, the smaller the search space and the worse the optimal value. Meanwhile, results
show that, partially or completely disabling those constraints is a good strategy to improve the attainable optimal values, with the downside of longer running times.

Overall, this preliminary study on the RCPSP-RP shows the capabilities of the problem to address application domains that take into account risks, priorities, and sequence-dependent context changes. In addition to industrial post-disaster situations, the RCPSP-RP may be applied to other application domains that involve risk or priority components such as financial risk management, evacuation planning with priorities or humanitarian logistics, etc.

Finally, this study opens several avenues of research and future work in opera-
tional research in the field of industrial catastrophes. Currently, we are studying
dynamic transformation of chemicals released into the environment, where the risk
associated with a pollutant evolves through time.

**Acknowledgements** The authors would like to thank the anonymous reviewers for their careful reading of our manuscript and their many insightful comments and suggestions. The ORCI project was funded by the RIN PhD program of the Normandie Region and by Le Havre Seine Métropole. It is also part of the ANR LIAD grant (ANR-21-SIOM-0002-01). Juan Luis Jiménez research was supported by the Plan Pro-pio de Investigación y Transferencia project PPJIA2023-031, Proyecto Plan Operativo FEDER Andalucía project C-ING-027-UGR23 and the Ministerio Español de Ciencia e Innovación under project numbers PID2023-147409NB-C21 and PID2020-115570GB-C22.

**Funding** Open access funding provided by Université Le Havre Normandie.

Declarations

**Conflict of interest** The authors declare that they have no Conflict of interest.

**Open Access** This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

References

Akbari V, Salman FS (2017) Multi-vehicle synchronized arc routing problem to restore post-disaster network connectivity. Eur J Oper Res 257(2):625–640

Akbari V, Sadati MEH, Kian R (2021) A decomposition-based heuristic for a multicrew coordinated road restoration problem. Transp Res Part D Transp Environ 95(102):854

Allahverdi A, Ng C, Cheng T et al (2008) A survey of scheduling problems with setup times or costs. Eur J Oper Res 187(3):985–1032. https://doi.org/10.1016/j.ejor.2006.06.060

Anderson E (1996) Mechanisms for local search. Eur J Oper Res 88(1):139–151. https://doi.org/10.1016/0377-2217(94)00164-2

Artigues C (2017) On the strength of time-indexed formulations for the resource-constrained project scheduling problem. Oper Res Lett 45(2):154–159. https://doi.org/10.1016/j.ori.2017.02.001

Barbalho TJ (2022) The optlis package: v0.1.0. https://doi.org/10.5281/zenodo.7386793

Barbalho TJ, Santos AC, Aloise DJ (2023) Metaheuristics for the work-troops scheduling problem. Int Trans Oper Res 30(2):892–914. https://doi.org/10.1111/itor.12925
Birch CPD, Oom SP, Beecham JA (2007) Rectangular and hexagonal grids used for observation, experi-
ment and simulation in ecology. Ecol Model 206(3):347–359. https://doi.org/10.1016/j.ecolmodel.
2007.03.041

Blazewicz J, Lenstra J, Kan A (1983) Scheduling subject to resource constraints: classification and com-
plexity. Discret Appl Math 5(1):11–24. https://doi.org/10.1016/0166-218X(83)90012-4

Bodaghi B, Palaneeswaran E, Shahparvari S et al (2020) Probabilistic allocation and scheduling of mul-
tiple resources for emergency operations; a Victorian bushfire case study. Comput Environ Urban
Syst 81(101):479. https://doi.org/10.1016/j.compenvurbsys.2020.101479

Brucker P, Drexl A, Möhring R et al (1999) Resource-constrained project scheduling: notation, classifica-
tion, models, and methods. Eur J Oper Res 112(1):3–41. https://doi.org/10.1016/S0377-2217(98)
00204-5

Christofides N, Alvarez-Valdes R, Tamarit J (1987) Project scheduling with resource constraints: a branch and bound approach. Eur J Oper Res 29(3):262–273. https://doi.org/10.1016/0377-2217(87)90240-2

Coco AA, Duhamel C, Santos AC (2020) Modeling and solving the multi-period disruptions scheduling problem on urban networks. Ann Oper Res 285(1):427–443

Demeulemeester E, Herroelen W (1992) A branch-and-bound procedure for the multiple resource-con-
strained project scheduling problem. Manage Sci 38(12):1803–1818. https://doi.org/10.1287/mnsc.
38.12.1803

Demeulemeester E, Herroelen W (1997) New benchmark results for the resource-constrained project scheduling problem. Manage Sci 43(11):1485–1492

Demeulemeester E, Herroelen W (2002) Project scheduling: a research handbook. Springer, New York

Doan TT, Bostel N, Hà MH (2021) The vehicle routing problem with relaxed priority rules. EURO J Transp Logist 10(100):039. https://doi.org/10.1016/j.eitl.2021.100039

eMARS (2019) Fire in a plant manufacturing additives for oils and lubricants Oct., 2019. Available in: https://emars.jrc.ec.europa.eu/en/emars/accident/view/923dc1f3-f4a6-11e9-9637-005056ad0167. Accessed 6 Oct 2022

European Commission (2021) On the implementation and efficient functioning of directive 2012/18/eu on the control of major-accident hazards involving dangerous substances for the period 2015-2018 https://ec.europa.eu/environment/pdf/industrial-accidents/seveso_implementation_report.pdf

Farahani RZ, Lotfi MM, Baghaian A et al (2020) Mass casualty management in disaster scene: a sys-
tematic review of OR &MS research in humanitarian operations. Eur J Oper Res 287(3):787–819.
https://doi.org/10.1016/j.ejor.2020.03.005

Graham R, Lawler E, Lenstra J, et al (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Hammer P, Johnson E, Korte B (eds.) Discrete optimization II, Annals of discrete mathematics, vol 5. Elsevier, pp. 287–326, https://doi.org/10.1016/S0167-5060(08)70356-X

Gries D, Martin AJ, Van De Snepscheut JL et al (1989) An algorithm for transitive reduction of an acyclic graph. Sci Comput Program 12(2):151–155. https://doi.org/10.1016/0167-6423(89) 90039-7 (https://linkinghub.elsevier.com/retrieve/pii/0167642389900397)

Görlitz L, Gao Z, Schmitt W (2011) Statistical analysis of chemical transformation kinetics using Markov-Chain Monte Carlo methods. Environ Sci Technol 45(10):4429–4437. https://doi.org/10.1021/es104218h

Hartmann S, Briskorn D (2010) A survey of variants and extensions of the resource-constrained pro-
ject scheduling problem. Eur J Oper Res 207(1):1–14. https://doi.org/10.1016/j.ejor.2009.11.005

Hartmann S, Briskorn D (2022) An updated survey of variants and extensions of the resource-con-
strained project scheduling problem. Eur J Oper Res 297(1):1–14. https://doi.org/10.1016/j.ejor.
2021.05.004

Hu H, He J, He X et al (2019) Emergency material scheduling optimization model and algorithms: a review. J Traffic Transp Eng 6(5):441–454. https://doi.org/10.1016/j.jtte.2019.07.001

Huang Y, Santos AC, Duhamel C (2020) Model and methods to address urban road network problems with disruptions. Int Trans Oper Res 27(6):2715–2739. https://doi.org/10.1111/itor.12641

Keim MEMD (2011) The public health impact of industrial disasters. Am J Disaster Med 6(5):265–272. https://doi.org/10.5055/ajdm.2011.0065

Kim S, Shin Y, Lee GM et al (2018) Early stage response problem for post-disaster incidents. Eng Optim 50(7):1198–1211. https://doi.org/10.1080/0305215X.2017.1419345

Kochetov YA, Stolyar AA (2003) Evolutionary local search with variable neighborhood for the resource constrained project scheduling problem. In: in: proceedings of the 3rd international workshop of computer science and information technologies
Kolisch R (1995) Project scheduling under resource constraints: efficient heuristics for several problem classes. Phys Heidelb. https://doi.org/10.1007/978-3-642-50296-5

Kolisch R, Hartmann S (2006) Experimental investigation of heuristics for resource-constrained project scheduling: an update. Eur J Oper Res 174(1):23–37. https://doi.org/10.1016/j.ejor.2005.01.065

Lourenço HR, Martin OC, Stützle T (2003) Iterated local search. Springer, US, Boston, pp 320–353. https://doi.org/10.1007/0-306-48056-5_11

Lourenço HR, Martin OC, Stützle T (2010) Iterated local search: framework and applications. Springer, US, Boston, pp 363–397. https://doi.org/10.1007/978-1-4419-1665-5_12

López-Ibáñez M, Dubois-Lacoste J, Pérez Cáceres L et al (2016) The irace package: iterated racing for automatic algorithm configuration. Oper Res Perspect 3:43–58. https://doi.org/10.1016/j.orp.2016.09.002

Maya Duque P, Sörensen K (2011) A GRASP metaheuristic to improve accessibility after a disaster. OR Spectr 33(3):525–542. https://doi.org/10.1007/s00291-011-0247-2

Maya Duque PA, Dolinskaya IS, Sörensen K (2016) Network repair crew scheduling and routing for emergency relief distribution problem. Eur J Oper Res 248(1):272–285. https://doi.org/10.1016/j.ejor.2015.06.026

Mendes J, Gonçalves J, Resende M (2009) A random key based genetic algorithm for the resource constrained project scheduling problem. Comput Oper Res 36(1):92–109. https://doi.org/10.1016/j.cor.2007.07.001

Mingozzi A, Maniezzo V, Ricciardelli S et al (1998) An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation. Manag Sci 44(5):714–729. https://doi.org/10.1287/mnsc.44.5.714

Mora AM, Merelo JJ, Millan C et al (2007) Enhancing a MOACO for solving the bi-criteria pathfinding problem for a military unit in a realistic battlefield. In: Giacobini M (ed.) Applications of evolutionary computing. Springer, Berlin, Heidelberg, Lecture notes in computer science, pp. 712–721. https://doi.org/10.1007/978-3-540-71805-5_77

Palpant M, Artigues C, Michelon P (2004) LSSPER: solving the resource-constrained project scheduling problem with large neighbourhood search. Ann Oper Res 131(1):237–257. https://doi.org/10.1023/B:ANOR.0000039521.26237.62

Panchamgam K, Xiong Y, Golden B et al (2013) The hierarchical traveling salesman problem. Optim Lett 7(7):1517–1524. https://doi.org/10.1007/s11590-012-0553-x

Pena GC, Santos AC, Prins C (2022) Solving the integrated multi-period scheduling routing problem for cleaning debris in the aftermath of disasters. Eur J Oper Res. https://doi.org/10.1016/j.ejor.2022.07.005

Ren Y, Tian G (2016) Emergency scheduling for forest fires subject to limited rescue team resources and priority disaster areas. IEEE J Trans Electr Electron Eng 11(6):753–759. https://doi.org/10.1002/tee.22300

Reuters (2019) Over 5,250 tonnes of chemicals burned in Rouen, France, industrial fire. Reuters Oct., 2019. Available in: https://www.reuters.com/article/france-fire-rouen-idUSL5N26M68E. Accessed 12 Sep 2022

Sakuraba CS, Santos AC, Prins C et al (2016) Road network emergency accessibility planning after a major earthquake. EURO J Comput Optim 4(3):381–402

Santos AC (2019) New trends and opportunities in post-disaster relief optimization problems. Braz J Oper Prod Manag 16(3):528. https://doi.org/10.14488/BJOPM.2019.v16.n3.a14

Seine-Maritime (2019) Incendie Lubrizol et NL Logistique du 26 septembre 2019 Dec., 2019. Available in: https://www.seine-maritime.gouv.fr/Actualites/Incendie-Lubrizol-et-NL-Logistique-du-26-septe mbre-2019/Incendie-Lubrizol-et-NL-Logistique-du-26-septembre-2019. Accessed 6 Oct 2022

Seveso-III Directive (2018) The seveso-iii directive. Available in: https://ec.europa.eu/environment/seveso/. Accessed 29 Oct 2021

Sprecher A (2000) Scheduling resource-constrained projects competitively at modest memory requirements. Manag Sci 46(5):710–723. https://doi.org/10.1287/mnsc.46.5.710.12044

Tirkolaee EB, Aydın NS, Ranjbar-Bourani M et al (2020) A robust bi-objective mathematical model for disaster rescue units allocation and scheduling with learning effect. Comput Ind Eng 149(106):790. https://doi.org/10.1016/j.cie.2020.106790

Tormos P, Lova A (2001) A competitive heuristic solution technique for resource-constrained project scheduling. Ann Oper Res 102(1):65–81. https://doi.org/10.1023/A:1010997814183
Vodák R, Bíl M, Křivánková Z (2018) A modified ant colony optimization algorithm to increase the speed of the road network recovery process after disasters. Int J Disaster Risk Reduct 31:1092–1106

Wang L, Wu P, Chu F (2020) A multi-objective emergency scheduling model for forest fires with priority areas. In: 2020 IEEE international conference on industrial engineering and engineering management (IEEM), pp. 610–614, https://doi.org/10.1109/IEEM45057.2020.9309821

Wang Q, Guidolin M, Savic D et al (2015) Two-objective design of benchmark problems of a water distribution system via MOEAs: towards the best-known approximation of the true pareto front. J Water Resour Plan Manag 141(3):04014. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000460

Wex F, Schryen G, Feuerriegel S et al (2014) Emergency response in natural disaster management: allocation and scheduling of rescue units. Eur J Oper Res 235(3):697–708. https://doi.org/10.1016/j.ejor.2013.10.029

Wu P, Cheng J, Feng C (2019) Resource-constrained emergency scheduling for forest fires with priority areas: an efficient integer-programming approach. IEEJ Trans Electr Electron Eng 14(2):261–270. https://doi.org/10.1002/tee.22805. (publisher: John Wiley & Sons Ltd)

**Publisher's Note** Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

## Authors and Affiliations

Thiago J. Barbalho<fnref n="1" /> · Juan Luis Jiménez Laredo<fnref n="1" />,<fnref n="2" /> · Andréa Cynthia Santos<fnref n="1" />

<figure><img src="image_15.png" /></figure>

Thiago J. Barbalho
thiagojobson@gmail.com

Juan Luis Jiménez Laredo
juanlu@ugr.es

Andréa Cynthia Santos
andrea-cynthia.duhamel@univ-lehavre.fr

<footnote n="1">1 LITIS, Université Le Havre Normandie, 25 rue Philippe Lebon, 76000 Le Havre, France</footnote>

<footnote n="2">2 ATC, Universidad de Granada, Calle Periodista Daniel Saucedo Aranda s/n, 18071 Granada, Spain</footnote>