The disaster information collection mission should be executed after the disaster occurs to provide details for the decision-makers. During the execution of the information collection mission, some disruptions may occur and prevent the resource used for information collection from completing the mission as planned. It is difficult for decision-makers to make reactive resource scheduling plan that optimize the mission’s execution time, quality, and cost at the same time under such circumstances. This article focuses on designing the reactive decision support algorithm for the disaster information collection resource scheduling, which aims to provide multi high-quality scheduling plans for decision-makers to choose. The problem studied in this article is modeled as an extension of Resource-Constrained Project Scheduling Problem (RCPSP). First, the basic problem formulation for a normal schedule and two disruption recovery models are presented. Second, a novel framework of a parallel pareto local search based on decomposition is designed to repair the schedule within the time limit. Third, two solution acceptance criteria based on constraint handling and negative correlation are specially designed to maintain high-quality population with diversity. The experiments show that the proposed method outperforms the other competitors with respect to Inverted Generational Distance, Spacing, and Hypervolume, which means that the proposed method can help decision-makers to make better decisions.
Hinweise
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Introduction
Disasters have caused huge losses to human beings. Many scholars have studied different disaster relief issues [1‐4] to reduce losses and save lives. At present, decision-makers can make better decisions through decision support technology in many fields; such as ship trajectory cleansing and prediction [5], maintenance strategies making [6], bank telemarketing sales prediction [7], vehicle routing [8], and smart grid management [9]. The disaster information collection resource scheduling decision support module plays a vital role in modern disaster relief command and control systems, which aims to present high-quality resource allocation plans to decision-makers. A disaster information collection mission has several tasks with precedence relations. The precedence relations restrict that one task cannot be started if at least one of its predecessor tasks is not finished. This is because there are many hidden dangers, such as fire and chemical leakage after the disaster, so the precedence relations are built based on the geographic accessibility of each task to ensure the safety of the information collection agents. Each information collection task needs some skill provided by the information collection agent. The agent represents a team with fewer than 5 people, which is the smallest unit for resource scheduling. The team can own vehicles, laser radars, UAVs, ranging instruments, and other equipment. The information collection in this article includes three types of tasks: urban area information collection, woodland area information collection, and terrain information collection. Because each type of task corresponds to different working modes of agents and uses different sensor combinations, this article models the ability of agents to perform tasks as skill 1–3. Each information collection agent has a pre-defined quality value and a cost value that correspond to each task. An example of an information collection mission in disaster relief scenario is presented in Fig. 1. During the execution of the information collection mission, some unpredictable events may occur and prevent the information collection mission to be processed with the original schedule. Since the information collection agents are performing tasks in the area of interest when the disruption occurs, according to the requirements of the disaster relief decision support systems, the reactive scheduling time needs to be controlled within 60 s. The reactive scheduling of disaster information collection repairs the original schedule, which helps the decision-maker to answer the following questions: (1) each task’s start time; (2) the information collection agents which are assigned to the task; (3) which kind of skill that each agent should use in each task. Three objectives are optimized at the same time, minimize the makespan, minimize the cost, and maximize the quality of the information collection mission.
Fig. 1
Example of an information collection mission
×
The disaster information collection resource scheduling problem is modeled as an extension of resource-constrained project scheduling problem (RCPSP). RCPSP focus on building a resource allocation result for a commercial project of activities, which are constrained by a limited resource supply and the precedence relation network [10]. The information collection mission is just as the “project” in RCPSP, the “task” corresponds to the “activity” in RCPSP, and the agent is very similar to the “multi-skill resource” in RCPSP. The processing time of each activity is assumed to be fixed in RCPSP, but the information collection task’s processing time is not fixed. Actually, it is a non-linear function of the resource allocated to that task. For example, both one agent or two agents can finish an information collection task, but the task completion time for two agents is shorter. In RCPSP, the resource transfer time between activities is usually set to 0. However, the task’s location is different in our problem, so the resource transfer time must be considered. These new features increase the difficulty of solving the problem in this article. Using the traditional RCPSP algorithm to solve the problem in this article is time-consuming and ineffective.
Anzeige
Some related works are addressed in this part. Tradition algorithms for solving RCPSP can be divided into three categories: exact algorithm, heuristic algorithm, and meta-heuristic algorithm. Some articles [11‐13] used the exact method to solve RCPSP and get the best solution. However, the exact algorithm is time-consuming and does not fit the reactive scheduling problem in this article.
Table 1
Differences between the existing research and this article
Some articles [14‐16] developed heuristic methods to solve RCPSP. Although the heuristic algorithm is really fast, it cannot deal the multi-objective optimization cases.
Since the problem in this article is a multi-objective reactive robust optimization problem, the related research progress of meta-heuristic algorithm for solving RCPSP and its extensions are introduced below. Lambrechts et al. [17] focused on the uncertainty in resource availabilities subject to unforeseen breakdowns, a robust schedule model was built that meets the project deadline and minimizes the schedule instability, and proactive strategies are proposed to solve the problem. Chen and Zhang [18] aimed to develop a two-stage model to obtain a proactive and reactive schedule in resource-constrained project scheduling problems under uncertainty, a modified tabu search was employed to ensure scheduling process execution in reactive phase. Davari and Demeulemeester [19] proposed to use the selection-based reactions and the class of buffer-based reactions to deal with the uncertainty and disruptions in resource-constrained project scheduling problem. Chakrabortty et al. [20] focused on finding a robust initial schedule that can protect itself from any possible future disruptions or resource breakdowns, and a variable neighborhood search-based heuristic algorithm was proposed to solve the problem. The above articles focused on finding a robust initial schedule, but they are not targeted to deal with reactive scheduling scenarios.
Table 2
The symbols
Symbols
Description
i, j
Index of tasks, \(i, j = 0, 1, 2,\ldots , N, N + 1\)
l
Index of skill type, \(l = 1, 2,\ldots , LN\)
k
Index of information collection agent, \(k = 1, 2,\ldots , K\)
t
Index of the time step
N
The number of non-dummy tasks
m
The number of objectives
\(V=\{0, \ldots ,i, \ldots ,j, \ldots , N+1 \}\)
Task set, task 0 and N+1 is start and end task, respectively
\(V^*\)
Incomplete tasks set after the disruption occurs
\(R=\{1, \ldots , k, \ldots K\}\)
Agent or resource set
K
The number of agents which can be used
\(R^*\)
Agent or resource set after the disruption occurs
\(L=\{1, \ldots , l, \ldots LN\}\)
Set of information collection skills
\(P_j, P_j^{I} \)
The indirect and direct predecessor of task j
\(S_j, S_j^{I}\)
The indirect and direct predecessor of task j
\(F_j, F_j^*\)
The finish time of task j in the initial and repaired schedule
\(ST_j, ST^*_j\)
The start time of task j in the initial and repaired schedule
\(L_j \)
The skills required by task j
\(L^k\)
Agent k’s skill capacity
\(V_k\)
The set of tasks that can use resource k
\(A_j^l\)
The area size in task j that needs skill l to perform
\(A_j^{*l}\)
The area size in task j which needs skill l to perform
\(R_j\)
The set of agents that can be used in task j
\(RA_j^l\)
The set of agents that are allocated to task j to perform skill l
\(r_l^{\rho }(t)\)
The total skill consumption of skill l in a given time t within the initial schedule
\(r_l^{*\rho }(t)\)
The total skill consumption of skill l in a given time t within the repaired schedule
\(MR_j\)
The maximum number of agents that can be used in task j
Dt
The time point when the disruption happens
\(\Delta _{ij}\)
The time cost for transfer agents from task i to task j
UB
The maximum makespan for the information collection mission
\(T=\{0, \ldots , t, \ldots , UB\}\)
Set of time steps
\(ES_j, LS_j\)
Task j’s earliest and latest time to start
\(p_j\)
Task j’s processing time
\(p_j^{\max }\)
Task j’s maximum processing time
\(\Gamma _j\)
The preparation time for the agents which are allocated to task j
\(u_{kl}\)
The number of skill l that the agent k can provide
\(c_{kl}\)
The cost for agent k to use skill l per time step
\(q_{kl}\)
The quality contribution for agent k to use skill l per time step
\(s^\prime _j\)
The actual start time of task j
\(s_{jt}\) (decision variable)
Equals 1 if task j is started at time t, 0 otherwise
\(x_{jklt}\) (decision variable)
Equals 1 if agent k is allocated to task j to perform skill l at time t, 0 otherwise
\(z_{ijk}\) (decision variable)
Equals 1 if agent k is transferred from task i to task j, 0 otherwise
Some articles focused on the single-objective RCPSP and its extensions. Deblaere et al. [21] addressed the reactive multi-mode RCPSP, and they proposed and evaluated several dedicated exact reactive scheduling procedures as well as a tabu search heuristic for repairing a disrupted schedule under the assumption that no activity can be started before its baseline starting time. Ning et al. [22] constructed the schedule adjustment cost determined by project reactive scheduling to manage disruptions caused by the randomness of activity duration, a tabu simulated annealing, and a variable neighborhood tabu search were developed to solve the problem. Adamu et al. [23] proposed a model called hybrid-RCPSP to solve reactive project scheduling problem. Davari and Demeulemeester [24] studied the reactive resource-constrained project scheduling problem, in which the approach to get a solution to the problem was a proactive and reactive policy that is a combination of a baseline schedule and a set of required reactions. Davari and Demeulemeester [25] addressed the proactive and reactive project scheduling with stochastic duration, and a dynamic programming method was proposed to solve the problem over different classes of proactive and reactive policies. Wang et al. [26] studied the reactive strategies in the multi-project scheduling problem, and a dual population genetic algorithm was designed to solve this problem. The above articles can deal with the reactive scheduling cases, but they are all single-objective optimization problem and assume that the task processing time is fixed. Zheng et al. [27] addressed the proactive and reactive of resource-constrained project problem in which activity durations are stochastic variables, and two reactive scheduling models were proposed to repair the baseline schedules after disruptions. However, it can only deal with single-objective optimization problems.
Fig. 2
Example of a small information collection mission scheduling problem
Fig. 3
Illustration the solution representation and decoding process
×
×
Anzeige
Some articles focused on the multi-objective RCPSP and its extensions. Bagherinejad et al. [28] focused on the multi-mode multi-objective RCPSP and proposed a hybrid ant colony and genetic algorithm to solve the problem. Yeganeh and Zegordi [29] presented a multi-objective optimization approach for constructing resilient project schedules under resource constraints to cope with uncertain activity durations. Li et al. [30] proposed a multi-objective discrete Jaya algorithm to solve the multi-skill multi-objective RCPSP. Zhu et al. [31] presented an efficient decomposition-based multi-objective genetic programming hyper-heuristic algorithm to solve the multi-skill RCPSP with the objectives of minimizing the project’s makespan and the total resource assignment cost at the same time. Hosseinian and Baradaran [32] considered the transfer time in multi-skill RCPSP, and built a model to optimize the project’s makespan and cost simultaneously, and then, a multi-objective multi-agent optimization algorithm is proposed to get feasible schedules. The above articles dealt with multi-objective RCPSP, but the algorithms are not optimized for reactive scheduling, and the calculation time is relatively long.
Some literature focused on designing algorithm strategies. Chand et al. [33] focused on the resource-constrained project scheduling problem with resource unavailability and disruptions, and a genetic programming hyper-heuristic that can automatically evolve the priority heuristic was proposed to solve the problem. Chakrabortty et al. [34] addressed the event-based reactive approach to deal with reactive resource-constrained project scheduling problem, and an enhanced iterated greedy approach was also proposed to solve the large-scale problem. RCPSP and its extension can also be applied in command and control system [35], nuclear laboratory research planning [36], new production development [37], etc. Table 1 shows the differences and gaps between the existing research and the research in this article.
Overall, to solve the problem addressed in this article, the following characteristics should be considered: (1) multi-objectives for reactive scheduling; (2) the precedence relations between tasks; (2) using multi-skill resource (agent); (4) the transfer time is considered; (5) the processing time of a task is a non-linear function of the resource allocation result. The existing RCPSP related literature did not focus on the problem addressed in this article and failed to consider the problem with the above characteristics simultaneously. The existing algorithms are ineffective and time-consuming in solving the problems in this article, and cannot be applied in the decision support system.
To solve the problem better, the above features are all considered in this article, and a parallel pareto local search is proposed to solve the multi-objective reactive information collection mission scheduling problem using the problem-specific information.
The contribution of this article is threefold: (1) the mathematical model of multi-objective information collection mission reactive scheduling problem under preempt-repeat and preempt-resume condition is established; (2) a parallel pareto local search framework is designed, in which the Tchebycheff scalar objective function and Nadir point are combined to decompose the optimization objectives into different parallel search process to speed up the reactive scheduling. (3) Two acceptance criterion based on constraint handling and negative correlation are proposed, the first acceptance criterion uses problem-specific information to guide the search process to better solutions, and the second acceptance criterion significantly increases the diversity of the Pareto fronts without compromising solution quality.
Problem formulation
Three objectives are optimized at the same time in this article: (1) minimizing the information collection mission’s makespan; (2) minimizing the cost caused by the agent performing information collection tasks; (3) maximizing the mission’s quality. A task on node graph \(G=(V, E)\) is adopted to represent the precedence relations, in which V denotes a set of information collection tasks, and E denotes the precedence between tasks. Some assumptions [4, 35] are made in this article:
Task 0 denotes the dummy start task, and task \(N + 1\) denotes the dummy end task.
Preemption is allowed when disruption occurs.
Each agent can only contribute one type of the skills it masters in a task.
The cost and quality are pre-defined for each agent corresponding to each task.
Only after all the allocated resources are transferred to the starting point of the task, the task can be started.
The bold numbers are represent the optimal value of each experiment
Basic formulation for normal schedules
Based on the model presented in [2, 3, 38], the formulation for normal information collection scheduling problem without disruptions is given as follows:
$$\begin{aligned}&f_1 = \min \sum _{t=ES_{N+1}}^{LS_{N+1}} t s_{(N+1) t}~, \end{aligned}$$
$$\begin{aligned}&\sum _{l \in L} \sum _{t = ES_j}^{LS_j}{x_{jklt}} = \sum _{i \in V \backslash \{n+1\}} z_{ijk}~, \nonumber \\&\quad j \in V \backslash \{0, n+1\}, k \in R_i \cap R_j,\end{aligned}$$
(14)
$$\begin{aligned}&s_{jt} \in \{0,1\}~, \quad j \in V, t \in T,\end{aligned}$$
(15)
$$\begin{aligned}&x_{jklt} \in \{0,1\}~, \quad j \in V, k \in R, l \in L,t \in T,\end{aligned}$$
(16)
$$\begin{aligned}&z_{ijk} \in \{0,1\}~, \quad i \in V\backslash \{0\}, j \backslash \{S_j^I\}, k \in R_i \cap R_j. \end{aligned}$$
(17)
Equation (1) is to minimize the makespan of the information collection mission. Equation (2) aims to minimize the cost. Equation (3) is to maximize the mission’s quality, and to make the optimization direction consistent, this article minimizes the reciprocal of the mission’s quality. Constraints (4) show the way to calculate the processing time of an information collection task when given a specific resource allocation result. Constraints (5) ensure that the denominator of Eq. (3) is not equal to zero. The constraints (6) limit the maximum number of agents allocated to a given task. Constraints (7) restrict that the task in information collection mission can be only started to be processed only once. Constraints (8) make sure that once the agent is allocated to a task, it can only perform one type of skill in that task. Constraints (9) make sure that the transfer time and precedence relations must be respected in resource allocation. Constraints (10)–(11) restrict that the agent can only perform one task at the same time. Constraints (12) ensure that if an agent is to be assigned to another task, the current position of that agent should be the direct or indirect predecessor of the corresponding task. Constraints (13) make sure that each task’s processing is less than its maximum processing according to the resource allocation result. Constraints (14) show the relationship between decision variables z and x, which avoid that the agent is assigned from a predecessor task to a successor task. Constraints (15)–(17) define the domain for each decision variable.
Table 5
Performance comparison of IGD in preempt-repeat condition
PPLS
EMOIS
MOIWO
MOTLA
Instance-1
337.289 (19.225)
254.545 (17.818)\(\wr \)
392.454 (45.132)\(\dagger \)
290.945 (33.75)\(\wr \)
Instance-2
335.945 (31.579)
347.225 (19.445)\(\approx \)
388.568 (41.577)\(\dagger \)
305.936 (26.31)\(\wr \)
Instance-3
236.876 (17.055)
253.771 (14.972)\(\dagger \)
313.026 (36.624)\(\dagger \)
244.106 (22.458)\(\approx \)
Instance-4
614.829 (70.705)
602.858 (39.789)\(\approx \)
640.366 (49.949)\(\approx \)
624.096 (52.424)\(\approx \)
Instance-5
676.131 (66.261)
704.918 (64.852)\(\approx \)
818.136 (90.813)\(\dagger \)
705.26 (54.305)\(\approx \)
Instance-6
728.668 (82.34)
841.264 (72.349)\(\dagger \)
841.156 (58.04)\(\dagger \)
855.684 (48.774)\(\dagger \)
Instance-7
790.837 (61.685)
999.644 (109.961)\(\dagger \)
945.279 (72.786)\(\dagger \)
1010.093 (54.545)\(\dagger \)
Instance-8
1442.284 (128.363)
1737.017 (166.754)\(\dagger \)
1797.055 (122.2)\(\dagger \)
1838.744 (187.552)\(\dagger \)
Instance-9
1605.757 (176.633)
1913.732 (130.134)\(\dagger \)
2011.649 (120.699)\(\dagger \)
1970.588 (100.5)\(\dagger \)
Instance-10
1615.725 (93.712)
1878.023 (161.51)\(\dagger \)
1850.601 (142.496)\(\dagger \)
2084.211 (106.295)\(\dagger \)
\(\dagger \)/\(\wr \)/\(\approx \)
–
6/1/3
9/0/1
5/2/3
The bold numbers are represent the optimal value of each experiment
Table 6
Performance comparison of IGD in preempt-resume condition
PPLS
EMOIS
MOIWO
MOTLA
Instance-1
296.889 (29.689)
230.612 (20.294)\(\wr \)
355.844 (40.922)\(\dagger \)
271.226 (27.394)\(\wr \)
Instance-2
294.533 (21.206)
297.767 (21.141)\(\approx \)
354.779 (21.287)\(\dagger \)
281.94 (26.502)\(\approx \)
Instance-3
368.881 (35.413)
374.959 (34.496)\(\approx \)
472.723 (31.2)\(\dagger \)
347.678 (26.771)\(\approx \)
Instance-4
656.057 (76.759)
666.31 (44.643)\(\approx \)
736.49 (58.919)\(\dagger \)
688.686 (42.699)\(\approx \)
Instance-5
1356.051 (115.264)
1291.477 (78.78)\(\approx \)
1398.77 (116.098)\(\approx \)
1258.062 (124.548)\(\wr \)
Instance-6
1216.13 (125.261)
1376.378 (94.97)\(\dagger \)
1507.744 (117.604)\(\dagger \)
1462.239 (99.432)\(\dagger \)
Instance-7
1626.66 (190.319)
1779.951 (177.995)\(\dagger \)
1832.006 (122.744)\(\dagger \)
1865.787 (106.35)\(\dagger \)
Instance-8
1432.015 (104.537)
1683.063 (102.667)\(\dagger \)
1853.527 (174.232)\(\dagger \)
1760.33 (191.876)\(\dagger \)
Instance-9
1764.954 (125.312)
2174.526 (213.104)\(\dagger \)
2177.77 (132.844)\(\dagger \)
2048.478 (219.187)\(\dagger \)
Instance-10
1665.306 (156.539)
2004.089 (140.286)\(\dagger \)
2067.712 (215.042)\(\dagger \)
2146.815 (251.177)\(\dagger \)
\(\dagger \)/\(\wr \)/\(\approx \)
–
5/1/4
9/0/1
5/2/3
The bold numbers are represent the optimal value of each experiment
Table 7
Performance comparison of SP in preempt-repeat condition
PPLS
EMOIS
MOIWO
MOTLA
Instance-1
7.270 (0.785)
7.377 (0.73)\(\approx \)
8.019 (0.473)\(\wr \)
8.498 (0.833)\(\wr \)
Instance-2
7.366 (0.759)
7.811 (0.43)\(\wr \)
8.141 (0.464)\(\wr \)
8.843 (0.964)\(\wr \)
Instance-3
7.981 (0.495)
7.273 (0.662)\(\dagger \)
8.12 (0.438)\(\approx \)
6.629 (0.703)\(\dagger \)
Instance-4
9.850 (0.561)
9.107 (0.61)\(\dagger \)
11.56 (0.728)\(\wr \)
10.767 (0.775)\(\wr \)
Instance-5
9.593 (0.835)
10.269 (0.657)\(\wr \)
9.005 (1.009)\(\dagger \)
10.916 (0.72)\(\wr \)
Instance-6
15.97 (1.182)
18.588 (1.487)\(\wr \)
15.869 (1.063)\(\approx \)
13.202 (0.858)\(\dagger \)
Instance-7
13.163 (1.369)
13.708 (0.836)\(\approx \)
11.846 (0.746)\(\dagger \)
14.147 (1.075)\(\wr \)
Instance-8
14.001 (1.442)
13.809 (1.16)\(\approx \)
13.026 (0.808)\(\dagger \)
13.875 (0.971)\(\approx \)
Instance-9
12.776 (0.779)
12.953 (1.282)\(\approx \)
13.422 (1.248)\(\approx \)
12.626 (1.503)\(\approx \)
Instance-10
19.016 (1.864)
20.507 (1.128)\(\wr \)
21.545 (1.163)\(\wr \)
15.781 (1.294)\(\dagger \)
\(\dagger \)/\(\wr \)/\(\approx \)
–
2/4/4
3/4/3
3/5/2
The bold numbers are represent the optimal value of each experiment
Table 8
Performance comparison of SP in preempt-resume condition
PPLS
EMOIS
MOIWO
MOTLA
Instance-1
6.893 (0.503)
9.479 (0.891)\(\wr \)
5.735 (0.539)\(\dagger \)
7.187 (0.446)\(\approx \)
Instance-2
6.977 (0.733)
8.059 (0.467)\(\wr \)
5.695 (0.513)\(\dagger \)
7.478 (0.733)\(\wr \)
Instance-3
10.261 (0.759)
11.148 (0.557)\(\wr \)
9.851 (0.847)\(\approx \)
11.91 (1.167)\(\wr \)
Instance-4
10.347 (1.159)
11.478 (0.872)\(\wr \)
11.248 (0.686)\(\wr \)
11.834 (1.325)\(\wr \)
Instance-5
8.143 (0.708)
7.998 (0.904)\(\approx \)
8.713 (0.889)\(\wr \)
7.432 (0.81)\(\dagger \)
Instance-6
12.797 (1.472)
13.581 (1.589)\(\wr \)
11.711 (0.843)\(\dagger \)
12.353 (1.136)\(\approx \)
Instance-7
13.346 (0.867)
11.29 (0.948)\(\dagger \)
15.218 (0.791)\(\wr \)
13.778 (1.571)\(\approx \)
Instance-8
15.856 (1.823)
12.449 (1.108)\(\dagger \)
20.719 (2.445)\(\wr \)
13.278 (1.407)\(\dagger \)
Instance-9
13.683 (0.93)
13.523 (1.339)\(\approx \)
14.317 (0.802)\(\approx \)
15.479 (1.099)\(\wr \)
Instance-10
16.81 (1.328)
17.773 (1.102)\(\approx \)
13.782 (1.502)\(\dagger \)
17.922 (0.914)\(\wr \)
\(\dagger \)/\(\wr \)/\(\approx \)
–
2/5/3
4/4/2
2/5/3
The bold numbers are represent the optimal value of each experiment
Table 9
Performance comparison of HV in preempt-repeat condition
PPLS
EMOIS
MOIWO
MOTLA
Instance-1
8.36e+12 (9.78e+11)
8.20e+12 (7.46e+11)\(\approx \)
7.46e+12 (5.37e+11)\(\dagger \)
5.90e+12 (5.55e+11)\(\dagger \)
Instance-2
7.66e+12 (8.81e+11)
5.99e+12 (3.47e+11)\(\dagger \)
7.38e+12 (4.14e+11)\(\approx \)
5.92e+12 (4.14e+11)\(\dagger \)
Instance-3
8.52e+12 (7.84e+11)
6.26e+12 (7.51e+11)\(\dagger \)
8.16e+12 (8.16e+11)\(\approx \)
4.96e+12 (3.87e+11)\(\dagger \)
Instance-4
1.65e+14 (1.72e+13)
1.03e+14 (1.05e+13)\(\dagger \)
1.46e+14 (1.27e+13)\(\dagger \)
1.13e+14 (1.26e+13)\(\dagger \)
Instance-5
4.41e+13 (3.00e+12)
1.93e+13 (9.83e+11)\(\dagger \)
4.71e+13 (2.59e+12)\(\wr \)
4.36e+13 (3.05e+12)\(\approx \)
Instance-6
1.69e+14 (2.01e+13)
1.90e+14 (1.65e+13)\(\wr \)
1.48e+14 (1.69e+13)\(\dagger \)
1.34e+14 (1.50e+13)\(\dagger \)
Instance-7
9.14e+14 (1.02e+14)
7.96e+14 (4.93e+13)\(\dagger \)
4.39e+14 (2.37e+13)\(\dagger \)
9.23e+14 (6.83e+13)\(\approx \)
Instance-8
2.43e+14 (2.21e+13)
2.08e+14 (1.08e+13)\(\dagger \)
1.93e+14 (9.64e+12)\(\dagger \)
2.98e+14 (2.92e+13)\(\wr \)
Instance-9
5.60e+14 (3.14e+13)
5.23e+14 (4.71e+13)\(\dagger \)
3.65e+14 (3.03e+13)\(\dagger \)
4.49e+14 (5.38e+13)\(\dagger \)
Instance-10
8.33e+14 (6.41e+13)
8.25e+14 (8.00e+13)\(\approx \)
6.76e+14 (5.68e+13)\(\dagger \)
8.82e+14 (4.59e+13)\(\approx \)
\(\dagger \)/\(\wr \)/\(\approx \)
–
7/1/2
7/1/2
6/1/3
The bold numbers are represent the optimal value of each experiment
Table 10
Performance comparison of HV in preempt-resume condition
PPLS
EMOIS
MOIWO
MOTLA
Instance-1
9.04e+12 (7.50e+11)
7.59e+12 (7.74e+11)\(\dagger \)
8.86e+12 (1.01e+12)\(\approx \)
7.37e+12 (8.40e+11)\(\dagger \)
Instance-2
9.12e+12 (5.84e+11)
7.87e+12 (6.14e+11)\(\dagger \)
8.84e+12 (9.28e+11)\(\approx \)
7.51e+12 (5.86e+11)\(\dagger \)
Instance-3
1.51e+13 (1.65e+12)
1.39e+13 (1.36e+12)\(\dagger \)
1.41e+13 (7.45e+11)\(\dagger \)
1.20e+13 (1.20e+12)\(\dagger \)
Instance-4
1.85e+14 (1.83e+13)
1.87e+14 (1.19e+13)\(\approx \)
1.38e+14 (1.31e+13)\(\dagger \)
1.54e+14 (1.65e+13)\(\dagger \)
Instance-5
3.46e+13 (3.15e+12)
3.00e+13 (3.42e+12)\(\dagger \)
3.33e+13 (2.33e+12)\(\approx \)
2.43e+13 (2.58e+12)\(\dagger \)
Instance-6
1.65e+14 (1.15e+13)
1.80e+14 (1.91e+13)\(\wr \)
1.59e+14 (1.37e+13)\(\approx \)
1.67e+14 (1.59e+13)\(\approx \)
Instance-7
9.58e+14 (9.58e+13)
8.49e+14 (5.60e+13)\(\dagger \)
7.75e+14 (5.97e+13)\(\dagger \)
8.26e+14 (8.67e+13)\(\dagger \)
Instance-8
1.78e+14 (1.80e+13)
1.09e+14 (9.58e+12)\(\dagger \)
1.11e+14 (1.19e+13)\(\dagger \)
1.46e+14 (1.74e+13)\(\dagger \)
Instance-9
3.29e+14 (3.25e+13)
3.44e+14 (3.68e+13)\(\approx \)
2.08e+14 (1.97e+13)\(\dagger \)
2.88e+14 (2.94e+13)\(\dagger \)
Instance-10
1.36e+15 (1.00e+14)
1.28e+15 (6.65e+13)\(\approx \)
1.12e+15 (5.60e+13)\(\dagger \)
1.12e+15 (1.06e+14)\(\dagger \)
\(\dagger \)/\(\wr \)/\(\approx \)
–
6/1/3
6/0/4
9/0/1
The bold numbers are represent the optimal value of each experiment
Table 11
The effectiveness of the acceptance criterion 2 with respect to SP
Preempt-repeat condition
Preempt-resume condition
PPLS
PPLS-WN
PPLS
PPLS-WN
Instance-1
7.270 (0.785)
7.119 (0.736)
6.893 (0.503)
7.366 (0.496)
Instance-2
7.366 (0.759)
7.541 (0.736)
6.977 (0.733)
6.549 (0.780)
Instance-3
7.981 (0.495)
7.645 (0.477)
10.261 (0.759)
9.649 (0.806)
Instance-4
9.850 (0.561)
10.296 (0.525)
10.347 (1.159)
9.669 (1.239)
Instance-5
9.593 (0.835)
9.219 (0.869)
8.143 (0.708)
8.395 (0.753)
Instance-6
15.970 (1.182)
14.922 (1.222)
12.797 (1.472)
11.937 (1.455)
Instance-7
13.163 (1.369)
12.479 (1.452)
13.346 (0.867)
14.085 (0.915)
Instance-8
14.001 (1.442)
14.472 (1.471)
15.856 (1.823)
14.851 (1.932)
Instance-9
12.776 (0.779)
12.496 (0.796)
13.683 (0.930)
12.750 (0.929)
Instance-10
19.016 (1.864)
18.116 (1.741)
16.810 (1.328)
15.794 (1.318)
The bold numbers are represent the optimal value of each experiment
Table 12
The effectiveness of the acceptance criterion 2 with respect to HV
Preempt-repeat condition
Preempt-resume condition
PPLS
PPLS-WN
PPLS
PPLS-WN
Instance-1
8.36e+12 (9.78e+11)
8.86e+12 (9.76e+11)
9.04e+12 (7.50e+11)
9.54e+12 (7.75e+11)
Instance-2
7.66e+12 (8.81e+11)
7.41e+12 (8.48e+11)
9.12e+12 (5.84e+11)
8.48e+12 (6.05e+11)
Instance-3
8.52e+12 (7.84e+11)
8.05e+12 (7.32e+11)
1.51e+13 (1.65e+12)
1.47e+13 (1.72e+12)
Instance-4
1.65e+14 (1.72e+13)
1.61e+14 (1.67e+13)
1.85e+14 (1.83e+13)
1.94e+14 (1.79e+13)
Instance-5
4.41e+13 (3.00e+12)
4.55e+13 (3.01e+12)
3.46e+13 (3.15e+12)
3.65e+13 (3.23e+12)
Instance-6
1.69e+14 (2.01e+13)
1.62e+14 (1.90e+13)
1.65e+14 (1.15e+13)
1.63e+14 (1.23e+13)
Instance-7
9.14e+14 (1.02e+14)
8.85e+14 (1.09e+14)
9.58e+14 (9.58e+13)
1.02e+15 (9.51e+13)
Instance-8
2.43e+14 (2.21e+13)
2.27e+14 (2.08e+13)
1.78e+14 (1.80e+13)
1.73e+14 (1.89e+13)
Instance-9
5.60e+14 (3.14e+13)
5.81e+14 (3.24e+13)
3.29e+14 (3.25e+13)
3.38e+14 (3.40e+13)
Instance-10
8.33e+14 (6.41e+13)
8.91e+14 (6.47e+13)
1.36e+15 (1.00e+14)
1.27e+15 (1.03e+14)
The bold numbers are represent the optimal value of each experiment
Fig. 4
Performance comparison
Fig. 5
The search process of PPLS
×
×
Disruption recovery model
Disruptions can be caused by the breakdown of agents, the incorrect estimations of environment parameters, and the dangerous situation discovered during the mission. The disruptions can cause the deterioration of the optimization objectives. Two types of disruptions recovery conditions are considered. The symbols are defined in Table 2.
Preempt-repeat condition
In the preempt-repeat condition, the affected tasks should be processed from their very beginning. The reactive scheduling will be executed just after the disruption occurs.
Precedence relations: The precedence relation is the same as Eq. (9).
Start time constraints: Assume the rescheduling is started immediately after the disruption. The incomplete or affected tasks must be finished after the disruption
Skill requirement: The size of the task area and the agent’s availability may change after the disruption. The skill requirement must be satisfied in the repaired schedule
In preempt-resume conditions, the affected task starts from the portion of work it left before the disruption.
Precedence relations: The precedence relation is the same as Eq. (9).
Start time constraints: For the task whose start time is earlier than the disruption, it follows constraints (20). For the task whose start time and finish time are later than the disruption, it should be started twice, as shown in constraints (21). \(s^{\prime }_j\) is the actual start time of task j
Skill requirement: Constraints are the same as Eq. (19) for the task whose start time is earlier than the disruption. For the task whose start time is earlier than the disruption and the finish time is later than the disruption, if the skill requirement increases, more agents should be allocated to the task as constraints (22)
The reactive scheduling of the information collection mission is time-critical (less than 60 s). Although the multi-objective meta-heuristic algorithm has stronger global search ability, given a high-quality initial population in advance and a time limit, it does not always obtain a better solution than the local search method. The approximated pareto front before disruption is the initial population in this article. A parallel pareto local search framework is designed to deal with the information collection mission reactive scheduling problem under two types of disruptions.
Solution representation
A task vector and a resource matrix are combined to represent the solutions. The task vector is denoted as \(\varvec{\pi }=\{\pi _1,\pi _2, \ldots ,\pi _N\}\); each element in the task vector takes a priority value from 0 to 1, which indicates the priority of the corresponding task. Then, the way to decode a task vector to a task list that meets the precedence constraints is presented: all the elements in the task list are rearranged in ascending order, while the precedence constraints are met, and the position of each element represents the index of task, and then, a feasible task list is obtained. The resource matrix is denoted as \({\varvec{M}}\), which decides the resource allocation result. \({\varvec{M}}\) is a \(K \times \sum _{j \in V}|L_j|\) matrix; each value in \({\varvec{M}}\) takes value from 0 to 1. The index of row in \({\varvec{M}}\) denotes the resource index, and the index of column in \({\varvec{M}}\) denotes the types of skill required for each task corresponding to the task list. Assume task i’s index in task list is ip, then the \(\sum _{j \in \{\pi _1 \ldots \pi _{ip-1}\}} |L_j|\) column in matrix \({\varvec{M}}\) represents the agents assigned to task-i to perform the first type of skill in \(|L_j|\). Given an element in \({\varvec{M}}\), if the value of that element is greater than 0.5, the agent corresponding to the row index is assigned to perform the skill and the tasks that are represented by the column index. Following the above procedure, a feasible resource allocation result could be obtained. To show the above decoding process more intuitively, an information collection mission is presented in Fig. 2 and its decoding process is shown in Fig. 3.
Parallel pareto local search
Decomposition method
The Tchebycheff scalar objective function is selected, because it can handle the case in which the shape of pareto front is not convex. W weight vectors \(\lambda ^1, \ldots , \lambda ^W\) are defined, and each vector corresponds to a parallel process. The sum of the elements in each weight vector \(\lambda ^w = (\lambda ^w_1, \ldots , \lambda ^w_m)\) is equal to 1, and \(\lambda _m^w \ge 0, w \in W\). Given a positive integer H, the way to calculate the value of each weight vector and the subregion definition for each parallel process w is the same as [39]. Define \(z^* = (z_1, \ldots , z_m)\) as the Nadir point. Using the Tchebycheff approach, the objective function for process w is defined as
The framework of the proposed parallel pareto local search (PPLS) is shown in Algorithm 1. W processes are running in parallel. In each process, \(A_w\) is initialized to the solutions both in the pareto front before disruption (\(A_0\)) and the subregion \(\lambda ^w\). Mn is number of individuals each parallel process maintains.
×
Individual local search
Given an existing solution x, the Gaussian mutation operator is adopted to conduct local search
where \(x_i\) denotes the ith element of x and \(N(0,\sigma _i)\) denotes a Gaussian random variable with zero mean and standard deviation \(\sigma _i\). If \(x^{\prime }>1\), set \(x^\prime \) to 1. If \(x^{\prime }<0\), set \(x^{\prime }\) to 0. In the beginning, \(\sigma _i\) is initialized to the same value. The value of \(\sigma _i\) is adapted in each based on the \(\frac{1}{5}\) successful rule proposed in [40]
where nc is the number of changed individual in a process, and \(\beta \) is a fixed parameter.
Acceptance criterion based on constraint handling
A problem-specific constraint handling method is proposed in this part. For preempt-repeat condition, given an individual x and using the decoding process designed in Sect. 3.1, the violation of constraints can be computed as
In each parallel process, three different conditions are considered:
(1)
There is no feasible solution in the current population Pop. Considering the constraint violation C(x) as the only objective, optimize C(x) until at least one feasible solution is obtained.
(2)
There are both feasible and infeasible solutions in the current population Pop. We divide the current population into feasible group \(Pop_1\) and infeasible group \(Pop_2\). The objective functions are transformed to Eqs. (28)–(29) to penalize the infeasible solutions
All the solutions in a population are feasible. The fitness value equals the corresponding objective value.
The detail of acceptance criterion 1 is presented in Algorithm 2.
×
Acceptance criterion based on negative correlation
For ith parallel process, the average of the solutions it maintains is denoted as \({\tilde{x}}_i \). The Bhattacharyya distance is used to present the negative correlation between different process. The Bhattacharyya distance between parallel process \(p_i\) and \(p_j\) is defined as
where \(\varvec{\Sigma _i}\) is \(\sigma _i^2 {\varvec{I}}\), \({\varvec{I}}\) is the identity matrix, and \(\varvec{\Sigma } =(\varvec{\Sigma }_i+\varvec{\Sigma }_j)/2\). The main idea behind the criterion based on negative correlation is that, for a parallel process, the selected solution should be with high quality and should lead to a distribution that is distant from the other parallel processes. The former can be represented by Eq. (32). The latter can be represented as
Then, normalization is conducted by requiring \(\mathrm{{Corr}}(x)+\mathrm{{Corr}}(x^\prime )=1\). Using the above definitions, the detail of acceptance criterion 2 is presented in Algorithm 3.
×
Experiment
A computer with Intel E5 3.6 GHz CPU and 32 GB of RAM is used to conduct the experiment in this article. The algorithms discussed in this part are coded in C++. Three effective multi-objective algorithms for RCPSP are selected as the comparison algorithms.
EMOIS [41], which uses an improved NSGA-II to solve multi-objective multi-skill RCPSP.
MOIWO [42], in which a modified multi-objective invasive weeds optimization algorithm is proposed to solve multi-mode multi-skill RCPSP.
MOTLA [43], which uses teaching–learning-based optimization algorithm to solve multi-objective multi-skill RCPSP.
Performance metric
Five metrics are considered. Since the true pareto front is unknown, the \(P^*\) is obtained by merging all the approximation pareto fronts found by all the algorithms. The metrics that describe the quality of the pareto front:
Inverted Generational Distance (IGD) [44]: The value of IGD shows the convergence and the diversity of the obtained pareto front at the same time. IGD can be calculated as
where \(n^{\prime }\) denotes the number of non-dominated solutions, and \(d_i\) is the Euclidean distance between the two nearest non-dominated solutions of the obtained pareto front and the true pareto front, the average of which is denoted as \({\bar{d}}\). The pareto front with a larger SP value shows better performance on solutions diversity.
Hypervolume Metric (HV)[44]: The value of HV shows the convergence and the diversity of the obtained pareto front simultaneously. HV represents the objective space volume which is dominated by the approximation pareto front P and delimited from above by a reference point \(r \in {\mathbb {R}}^n\). HV is defined as
where \(x_i\) denotes a point in the pareto front P, and \(\lambda _{m}\) represents the m-dimensional Lebesgue measure. \((\max f_1, \max f_2, \max f_3)\) is adopted as the reference point. The pareto front with a larger HV value has better performance.
Test instance
The MS-RCPSP test instance generator proposed in [45] is modified to generate new instances for our problem. Some parameters which can be used to describe the difference between the test instances are presented: (1) nAct: the number of non-dummy information collection tasks in a mission. (2) K: the number of resource(agent) which can be used in the information collection mission. (3) |L|: the number of skill types. (4) NC: the average number of successors of each task, which is used to represent the network complexity. (5) MD, the number of tasks that are influenced by the disruption. (6) Skill factor SF: skill factor, which represents the relationship between the number of skill types required to in an information collection task. (7) \(RSS_l\): resource strength, which shows the relative relationship between the task’s skill requirement and the corresponding resource’s supply. Ten test instances are generated, and detailed information of the test instance is shown in Table 3. Each instance is tested under preempt-repeat and preempt-resume conditions.
Parameters’ tuning
Taguchi method is applied to tune the parameters as [44]. Three levels of each parameter are considered (Table 4), and the best value is in bold. The time limit for all algorithms is 60 s.
Performance evaluation
All rendered results are obtained by performing ten independent runs of each algorithm. The time limit is set to 60 s. The average value and standard deviation are calculated and are shown in Tables 5, 6, 7, 8, 9, and 10 and Fig. 4. The Wilcoxon’s rank sum test at 5% significance level is used to present the difference between the comparison algorithm and the algorithm designed in this article. Using \(T^\prime \) to denote the rank sum of the comparison algorithm result. According to the rank sum table, \(P(82<T^{\prime }<128)=0.05\), that is, \(T^{\prime }>128\) means that the comparison algorithm is worse than the proposed algorithm, \(T^{\prime }<82\) represents the comparison algorithm is better than the proposed algorithm, and \(82<T^{\prime }<128\) means the comparison algorithm is similar to the proposed algorithm. The symbols \(\dagger \), \(\wr \), and \(\approx \) denote that the performance of the proposed algorithm in this article is better, worse, and similar than the comparison algorithm. The standard deviation is shown in parentheses, and the data in bold are the best value found in the corresponding test instance.
First, the performance on IGD is discussed. The PPLS outperforms the other algorithms significantly. The PPLS obtains 7 best solutions in preempt-repeat condition and 6 in preempt-resume condition. It is clear that PPLS obtains the best pareto front. MOTLA has the second-best performance generally.
Second, SP of each algorithm is compared. PPLS obtains only 1 best solution in preempt-repeat condition and 0 in preempt-resume condition. The algorithm with higher quality pareto front usually does not has competitive performance on SP, so the performance of PPLS is acceptable. Besides, none of the comparison algorithms has a clear advantage over the others.
Third, with respect to HV, PPLS obtains 5 best solutions in preempt-repeat condition and 7 in preempt-resume condition. MOTLA finds the 3 best solutions in preempt-repeat condition, which is the closest to PPLS. EMOIS finds 3 best solutions in preempt-resume conditions. MOIWO has the worst performance and PPLS has the best performance.
Fourth, the experiment is conducted to show the effectiveness of the proposed acceptance criterion based on negative correlation. PPLS-WN represents the proposed PPLS without the acceptance criterion based on negative correlation. HV and SP are calculated under preempt-repeat and preempt-resume condition, the results are presented in Tables 11 and 12. The results clearly show that the acceptance criterion based on negative correlation can increase the diversity of the obtained pareto front without reducing its quality.
Furthermore, to show the PPLS’s search process better, 5 moments are presented on instance-3 and instance-7, as shown in Fig. 5.
Summarizing, the proposed method outperforms the comparison algorithms generally. The reasons why the proposed method outperforms other algorithms can be concluded as follows:
The framework of PPLS is designed specifically to fit the information collection mission reactive scheduling problem’s characteristics.
The proper design of the solution representation and decoding scheme contributes to reducing the search space.
For the information collection mission reactive scheduling problem within a short time limit, the algorithm with stronger local search ability tends to have better performance, and the importance of global search ability is relatively weak.
Conclusion
This article focuses on providing decision support for the decision-makers when disruption prevents the disaster information collection mission from completing the work as planned. When disruption occurs, it is vary difficult for the decision-makers to make high-quality reactive decisions. The disaster information collection resource scheduling problem is modeled as an extension of resource-constrained project scheduling problem (RCPSP). The mathematical model of the disaster reactive decision support problem with two recovery models is given. A novel framework of a parallel pareto local search based on decomposition is specially designed to provide reactive decisions for the decision-makers within the time limit. Two solution acceptance criteria based on constraint handling and negative correlation are also proposed to maintain high-quality population with diversity. The experiments have been conducted and the results show the proposed method outperforms the other competitors. As a part of our future research plan, we aim to develop new algorithms for solving RCPSPs involving complex practical issues, such as the prediction of dynamic disruptions and resource uncertainty. Although the proposed algorithm is efficient, it is not a real-time algorithm. The user experience of real-time decision support systems is significantly better than that of non-real-time systems. Using the deep reinforcement learning method to train a policy network which represents the reactive policy when disruption happens is a possible way to realize real-time decision support. Although the training process might be time-consuming, it can be viewed as a preparation before the use of the decision support system. Once the policy network is obtained, the time cost of the reactive scheduling process will be in milliseconds. Game theory can also be introduced in the deep reinforcement learning methods to explore the interesting interaction between decision-making and the environment’s feedback.
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/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
