A study of comprehensive resource scheduling under public health events: An improved heuristic quantum algorithm

2.1 Multi-capability resources

In today’s world, 1/5 of global economic activity is carried out in the form of projects, and the average annual value of these activities is about $12 trillion [21]. As you can see, project management techniques are indispensable in all industries, and effective resource scheduling is essential to the success of a project. In 1963, Kelley et al [22]. proposed the RCPSP problem, and since then, Blazewicz [5], Brucker [23], and other scholars have further refined the theory related to RCPSP based on Kelley’s work. As the research on RCPSP continues, scholars not only study how to seek and design the optimal method that can effectively solve RCPSP but also expand the theory of traditional RCPSP problems so that RCPSP can better reflect the actual environment of project operation. For example, Slowinski et al. [23, 24]. expand the resource types into renewable resources, non-renewable resources, and dual constraints, thus enhancing the practicality and research difficulty of RCPSP. However, in addition to the impact of non-renewable resources, the multi-capacity nature of the resources themselves should also be considered in the emergency project scheduling problem [25]. For example, Bellenguez has extended the theory for the standard resource-constrained project modulation problem by considering the multi-capability of resources based on the RCPSP and mathematically modeling the expansion problem [26]. For example, Almeidal designed a novel heuristic optimization algorithm for the multi-capability resources-constrained project scheduling problem and demonstrated the superiority of the algorithm using comparative experiments [24].

2.2 Multiple execution modes

In emergency construction projects such as public health incidents, project managers are faced with numerous uncertainties and unexpected demands, as well as the combined effects of resource types and multiple project scenarios, which leads to the existence of multiple execution modes for each emergency construction project process to cope with the unexpected situation. Given this, researchers have proposed a Resource Constrained Multi-Modal Project Scheduling Problem (RCMPSP), which was proposed by Elmaghraby as an extension of the RCPSP with more far-reaching research and practical implications, and which has attracted great attention and interest in the field of project management research [27]. For example, Peng et al. proposed a two-stage multimodal resource-constrained project reactive scheduling problem and designed a solution procedure for this problem based on the IBM ILOG optimization programming languages OPL and CPLEX [10]. Wang et al. generalized RCMPSP to the case of considering alternative preconditioning activities (RCMPSP-AP) and also proposed a novel model and solution method [28].

2.3 Multi -project operation

In the resource scheduling process of emergency construction projects, since emergency construction is often in a multi-project environment, researchers need to consider not only the multi-modal nature of individual processes but also resource scheduling among projects, i.e., the resource-constrained multi-project scheduling problem (RCMPSP). For example, Kurtulus proposes a single-project modeling approach that simplifies the MRCPSP solution by combining multiple projects into one overall project [12]. In addition, to consider the independent benefits of each project, Kurtulus also proposes a multi-project modeling approach that considers each sub-project independently. To better solve such problems, researchers have conducted an in-depth analysis of the solution method [29]. For example, Toffolo proposed a heuristic optimization algorithm based on integer programming in the process of solving RCMPSP and designed a local search means based on integer programming to improve the solution performance of this algorithm [30]. Can et al. chose a two-stage decomposition optimization algorithm to decompose the RCMPSP problem into a mathematical model of two-level 0-1 integer programming, and designed an exact optimization algorithm and a genetic optimization algorithm for this model, respectively [31].

2.4 Research gap analysis

The preceding literature review highlights the valuable insights and recommendations provided by existing studies to address the challenge of integrated resource-constrained scheduling in the context of public health. While previous researchers have conducted numerous studies and theoretical explorations to enhance the relevance of resource scheduling to real-world scenarios, such as incorporating multi-skilled resources and considering multiple execution modes, their focus has often been limited to the impact of singular factors. Consequently, these efforts fail to fully capture the intricacies of the actual resource scheduling environment.

Moreover, there is a noticeable dearth of comprehensive studies delving into the intricate challenges posed by resource scheduling during public health events. Recognizing this gap, our study undertakes a thorough investigation of the resource scheduling problem within the framework of public health events. It takes into account multiple factors, including the multi-project environment, changes in process execution patterns, and the multi-skill characteristics of resources. This approach leads to the proposition of a comprehensive resource-constrained project scheduling problem specifically tailored to the dynamics of public health events. In comparison to the original Resource-Constrained Project Scheduling Problem (RCPSP), this novel problem formulation proves to be more practical and inherently more challenging to solve.

To comprehensively evaluate the efficacy of different solution methods, our research adopts two widely used multi-item scheduling problem approaches for formulating assumptions and models. Furthermore, to efficiently tackle the complexities inherent in our scheduling problem and to contribute to the enrichment of scheduling problem-solving algorithms, we introduce an improved quantum particle swarm algorithm in this article. The objective of this study is twofold: to fortify the theoretical foundation of the resource-constrained project scheduling problem and to propose a more robust solution method.

This study examines the Comprehensive Contingency Resource Constrained Project Scheduling Problem (MCMRCMPSP), which involves multiple parallel multi-modal contingency projects. The projects are represented by arbitrary directed acyclic graphs (AON) denoted as G _p  = (V _p , E _p ). The graphs illustrate the logical constraints among the processes of each emergency project, indicating the immediately preceding and following relationships. The set V _p  = [{0, 1, 2 . . . . . . . . m1, m2, . . . m}] represents the active processes, while E represents the arcs denoting dependencies between processes. Process 0 represents project initiation, and process m represents project completion, both without resource allocation or time consumption. The study also considers a shared Multi - capability resource library with diverse limited and updatable resources. Each contingency multimodal project is denoted by P ={ 1 . . . … . p }, and the required capabilities for each project process are represented by A ={ 1 . . .   . . . . a }. The set R ={ 1 . . .  r } represents the multi-capability resources needed for each project process.

3.2 Basic hypothesis

Two solutions exist for the prevailing multi-project scheduling challenge. The first, referred to as the “a” method, predominantly addresses each project individually. Conversely, the second “b” method introduces a virtual initial and end node to amalgamate multiple projects into one for concurrent consideration. Given this context, and to undertake a comprehensive analysis of resource scheduling about public health events, as well as to evaluate the comparative merits of the “a” and “b” approaches, this paper posits assumptions, models, and solutions for both methods. The foundational assumptions are as follows:

The “b” approach makes the following assumptions:

Competing and conflicting relationships exist among multi-modal emergency projects for multi-capability resources.

When taking the “a” approach, assumption 1 is not considered, while multi-capability resource conflicts are not considered between multiple contingency projects.

The MCMRCMPSP model developed in this paper is as follows:

The mathematical notation used in the above model and the explanatory notes are shown in the following Table 1:

(1) Objective function

When the solution is taken in a way, the objective function:

Min : F , F = max { ∑ ρ p * S m , p | m ∈ V , p ∈ P }(1)

Equation (1) represents the weighted total completion time of multiple contingency projects;

When the solution is taken b way, the objective function:

Min : F , F = max { ∑ S m , p | m ∈ V }(2)

Equation (2) represents the minimum completion period of the combined project consisting of multiple contingency projects.

(2) Decision Variables

Table 2 shows the table of decision variables.

(3) Binding Conditions

When taking the b approach to the solution, the following constraints are present:

∑ p ∈ P ρ p = 1(3)

Equation (3) indicates that the sum of the priority weight coefficients of emergency items is 1;

G m p ≥ 1 , G m p ∈ Z , ∀ m ∈ V , p ∈ P(4)

Equation (4) indicates that each contingency process in project p has at least one execution mode;

D m , g , p a ≥ 0 , D m , g , p a ∈ Z , ∀ m ∈ V , ∀ g ∈ { 1 , 2 , . . . , Gm } , ∀ a ∈ A , p ∈ P(5)

Equation (5) indicates that the emergency process m in project p requires at least one capability for execution in g mode;

E m , p ≥ 0 , S m , p ≥ 0 , ∀ m ∈ V , p ∈ P(6)

Equation (6) indicates that the start time and end time of each process of contingency item p are greater than or equal to 0;

∑ a ∈ A RC M r , a ≥ 1 , ∀ r ∈ R , ∀ a ∈ A , p ∈ P(7)

Equation (7) indicates that each multi-capability resource has at least one capability in the emergency construction project p;

P m 1 , m 2 = 1 , ∀ m 1 ∈ V , ∀ m 2 ∈ V(8)

E m 2 , p - S m 1 , p ≥ 0 , ∀ m 1 ∈ V , ∀ m 2 ∈ V(9)

Equations (8) and (9) represent logical relationship constraints, i.e., in an emergency construction project p, each process must be completed after all of its immediately preceding operations have been completed before it can be started;

S m , p = E m , p + ∑ g ∈ 1 , 2 , . . G m T m , g , p X m , g , p , ∀ m ∈ V , ∀ g ∈ 1 , 2 , . . G m , p ∈ P(10)

Equation (10) represents the formula for calculating the end time for the execution of process p in emergency construction projects;

∑ g ∈ 1 , 2 , . . G m X m , g , p = 1 , ∀ m ∈ V , ∀ g ∈ 1 , 2 , . . G m , p ∈ P(11)

Equation (11) represents the mode constraint of the emergency construction project p, i.e., only one execution mode can be selected for each process in the emergency construction project p;

Y m , a , p r ≤ Rc m r , a , ∀ a ∈ A , ∀ m ∈ V , ∀ r ∈ R , p ∈ P(12)

Equation (12) indicates that in the emergency project p, only multi-capable resources with corresponding capabilities can be used to perform the corresponding processes;

∑ a ∈ A Y n , a , p r ≤ 1 , ∀ m ∈ V , ∀ r ∈ R , p ∈ P(13)

Equation (13) indicates that in the emergency construction project p, each multi-capacity resource can use only one capacity to perform the corresponding process;

∑ r ∈ R Y m , a , p r = ∑ g ∈ 1 , 2 , . . g m D m , g a X m , g , p , ∀ m ∈ V , ∀ a ∈ A , ∀ r ∈ R , p ∈ P(14)

Equation (14) represents the need to meet the demand for capacity of each process in the emergency construction project p;

∑ a ∈ A Y m 1 , a , p r = 1 , ∑ a ∈ A Y m 2 , a , p r = 1(15)

max ( E m 1 , p , E m 2 , p ) - min ( S m 1 , p , S m 2 , p ) ≥ 0(16)

∀ r ∈ R , ∀ m 1 ∈ V , ∀ m 2 ∈ V , m 1 ≠ m 2 , p ∈ P(17)

Equations (15)-(17) represent the non-preemption of each multi-capacity resource, i.e., in the construction process, each multi-capacity resource can be used for the execution of another corresponding process only after the execution of the corresponding process.

When taking “a” approach, the constraint (3) is not considered.

To effectively solve the multi-modal multi-item scheduling problem under multi-skill resource constraints in the context of public health events, an improved quantum particle swarm optimization algorithm based on the QPSO algorithm is proposed in this section for the following main reasons [34]:

The Quantum Particle Swarm Optimization (QPSO) algorithm has excellent global search capabilities, while the number of control parameters is small, making it well suited for solving more complex resource scheduling problems.

3.4.2 Hybrid quantum algorithm design

The previous analysis shows that the QPSO algorithm no longer uses the particle velocity and position update means of the PSO algorithm, and also has better global convergence performance with fewer control parameters [31]. Nevertheless, the QPSO algorithm still suffers from weak local search performance and the problem of easily falling into local optimality in the problem-solving process exists [37]. Therefore, to effectively deal with the multi-capability resources-constrained multimodal multi-project scheduling problem based on major public health events, the following improvements are made to the quantum particle swarm algorithm in this section [34]:

(1) Logistic chaos initialization population

In the standard QPSO algorithm, particle population initialization relies on a uniform distribution of randomly selected values [38]. However, this approach lacks the guarantee of uniformity in the initial population distribution, leading to suboptimal algorithm performance and convergence speed [39]. To address this issue and enhance solution performance and convergence speed, we adopt logistic mapping for population initialization in this study. This ensures a more even distribution of initial particle positions, as depicted below [40]:

p ( j + 1 ) = ∂ * p j ( 1 - p j )(31)

In Equation (31), ∂ is the chaos parameter, which takes values in the range of ∂  ∈   [3.57, 4], and the quantum particle population is more easily distributed equally when ∂ is closer to 4. And in this paper ∂=4.

(2) Multiple Tournament Selection Strategy

The tournament selection strategy is commonly utilized in the mutation operation of genetic algorithms and consists of the following primary steps [41]:

Determine the number of particles to be selected in each iteration, denoted as x (in this study, x = 2).

Randomly select x particle individuals from the population, with equal probabilities of selection, to form a cluster. Evaluate the fitness of each individual within the cluster and choose the particle individual with the highest fitness. Subsequently, include the selected individual in the offspring population.

Repeat the above steps until the size of the new population matches that of the original population. The key steps are illustrated in Fig. 2 below.

OPEN IN VIEWER

Fig. 2

Tournament selection.

OPEN IN VIEWER

Fig. 3

Algorithm calculation process.

This strategy can effectively avoid the stagnation of the quantum algorithm due to the over-similarity of adaptation among individual particles as the number of population iterations increases. This broadens the coverage of individual particles in the sample space and speeds up the convergence rate of the quantum algorithm.

(3) Gaussian variation

The probability density function of the Gaussian distribution is [42]

y ( x ) = 1 2 π ∅ * e - ( x - m ) 2 2 ∅ 2(32) where: ∅ is the variance in the Gaussian distribution; and m is the mean. When ∅ is smaller, the Gaussian distribution will be more concentrated near the axis of x = m, and vice versa, its distribution will be more dispersed.

During the iterations of the standard QPSO algorithm, particle diversity decreases as iterations increase, leading to a local optimum. To address this, we introduce a Gaussian variation mechanism in this paper. This mechanism generates a random perturbation term following a Gaussian distribution for the particle-optimal individuals selected via binary tournament strategy. It improves local search performance and enhances particle diversity [42, 43]. The primary variation is achieved using the following equation:

p m ( t ) ∧ = p m ( t ) * [ 1 + φ * G ( m , θ 2 ) ](33)

Equation (33), p_m (t) is the particle-optimal individual selected by the tournament strategy; φ refers to a random number belonging to [0, 1]; G (m, θ²) denotes a Gaussian distributed random vector.

While Gaussian variation can assist in escaping local optima, it remains uncertain whether the post-variation position surpasses the original position. Hence, to address this uncertainty, the study adopts the greedy rule after introducing the variation. The purpose is to compare the fitness before and after the variation, enabling a determination of whether the original individual should be updated.

(4) Resource process deployment algorithm based on multiple heuristic rules (HR)

To efficiently solve the multi-capability resource-constrained multi-modal multi-project scheduling problem model based on public health events and determine the optimal scheduling strategy for each emergency project, this study establishes the following heuristic rules to assist the QPSO algorithm in process-resource allocation [42]:

When sequencing all emergency project processes, equations b to e must be satisfied.

Under the premise of rule a, prioritize the critical processes of each emergency project.

Once the processes are arranged, no interruptions are allowed.

When ranking non-critical processes for emergency projects, prioritize the processes with earlier ES. In case of equal ES values, select the processes with smaller LS for higher ranking.

In the allocation of multi-capability resources, prioritize the resources that can be used earlier. In case of equal scheduling time, prefer resources with fewer capabilities.

The specific steps are as follows:

Step 1: Based on multiple heuristic rules, select process x that requires multi-capability resource allocation. Update the set of capabilities required for process x, denoted as A, and proceed to Step 2.

Step 2: Traverse set A, starting with the first skill a, and update the set R of multi-capability resources possessing skill a. Proceed to Step 3.

Step 3: Select eligible multi-capability resources for allocation based on multiple heuristic rules. If the process resource allocation is complete, move to Step 4.

Step 4: Terminate the algorithm.

3.5 Weight determination

In this section, the entropy weight-Gauss cloud evaluation model will be used to determine the weight of each emergency project, and the required capacity of each emergency project and the expert’s score will be used as evaluation indicators. The calculation mainly includes the following four steps:

Let the items to be evaluated be x and the related evaluation indexes be y, thus forming the original data matrix M = (m _ij )  _xy , i, j, x, y∈ { 1, 2 … . n } of the related evaluation indexes of each emergency item.

In this section, the article will evaluate the performance of the algorithm under various scenarios using the PSPLIB (Project Scheduling Problem Library) benchmark [6]. Specifically, we will test the algorithm in the context of multi-mode projects with multi-skilled resource constraints, single-mode projects with multi-skilled resource constraints, and multi-mode projects with single-skilled resource constraints. Additionally, the algorithm will be tested at different case scales. In order to highlight the superiority of the improved algorithm, the article will compare the solution results using the improved algorithm with those of the Genetic Algorithm, Ant Colony Algorithm, iCSPM2 Algorithm, Particle Swarm Algorithm, and Standard QPSO. However, due to the unavailability of the required test cases in the PSPLIB, the article has made adjustments to the baseline cases of standard resource-constrained project scheduling problems and resource-constrained multi-mode project scheduling problems to meet the experimental requirements of the study.

(1) Algorithm parameter setting

To validate the effectiveness of the proposed algorithm, the study utilizes a testbed consisting of a 64-bit operating system, specifically Windows 10 Professional, equipped with an Intel(R) Core (TM) i5-8300 H CPU running at 2.30 GHz, and 8.00 GB of RAM. The algorithm development environment employed is MATLAB 2022a. In addition, to ensure the accuracy of the performance test experiments and the results of the practical application experiments, the setting parameters of the algorithm are based on previous relevant studies and discussed by experts in the field of resource scheduling [44-48]. The specific parameter configurations are shown in the following table:

In this study, two different approaches will be taken to solve separately for the actual case being adapted.

(1) Case description

To address the multi-modal multi-project scheduling problem with multi-skill resource constraints during public health events, this paper focuses on the XX emergency construction project in Hunan Province as a case study. The research problem is examined in conjunction with actual cases, ensuring relevance and practicality. The project comprises three emergency sub-projects, and Fig. 4 provides the schematic diagram of each emergency project network. To effectively evaluate the algorithm’s practical applicability, the article simplifies the project by considering only the impact of human resources. In this particular project, the available human resources amount to 40.

OPEN IN VIEWER

Fig. 4

Schematic diagram of emergency project network.

4.1 Performance test results

Multi-skill resource-constrained multi-modal project environment

4.2 Practical case solving results

In this section, the article presents the results of two approaches for solving the multi-capacity resource-constrained multi-modal multi-item scheduling problem based on public health events.

(1) Combining multiple projects for solution

In this section, we verify the effectiveness of the proposed algorithm by solving the multi-modal multi-emergency project scheduling problem based on public health events using the “b” method and the improved heuristic quantum particle swarm algorithm. The minimum duration obtained for the project is 56 days. Figure 5 below illustrates the operation of the algorithm, and Table 7 shows the combined project resource scheduling scheme.

(2) Solving multiple contingent multi-mode projects independently

This section presents the solution for multiple emergency multi-modal projects and calculates the weighted total duration of the projects with different weights. The entropy weight method is used to determine the weights of the three multi-modal emergency projects. Table 8 shows the required competencies for each item, expert scores, and weights obtained through entropy weighting. Additionally, Fig. 6 shows the Gauss cloud model for each project evaluation.

We construct each contingency project independently, without considering conflicts between the resource requirements of multiple projects with resource qualifications. We present the individual solution results for each contingency multi-modal project in Fig. 7 and Table 9. Additionally, we present the resource scheduling options for each single project in Table 10.

5.1 Discussion of performance test results

From the optimal, worst, and average solutions in Tables 4-6, it can be seen that the QPSO algorithm outperforms the Genetic Algorithm, Ant Colony Algorithm, and Particle Swarm Algorithm in different project environments because it adopts the principle of quantum mechanics. However, the improved QPSO algorithm achieves better results compared to the original QPSO algorithm due to the use of techniques such as chaos initialization and Gaussian variation. However, compared with iCSPM2, its optimization effect is still average. However, after adding the heuristic rule (HR), the solution performance of the improved QPSO algorithm is significantly improved, which is because the heuristic rule effectively reduces the invalid computation and thus improves the solution performance, which also proves the superiority of the algorithm proposed inOPEN IN VIEWER

OPEN IN VIEWER

Fig. 6

Gauss cloud model for each project evaluation.

OPEN IN VIEWER

Fig. 7

Individual solution results of each emergency project.

As can be seen from the real case-solving experiments, method “b” yields a minimum duration of 56, while method “a” yields a minimum weighted total duration of 18.67, even though method “a” requires a better duration. However, methodology “a” ignores the conflicting multi-capacity resource requirements that exist between contingency projects and does not reflect the realities of the environment in which multiple projects operate. In addition, method “a” is more cumbersome than method “b”;, which converts a multi-project to a single-project solution by simply adding an initial node and an end node. The data provided in the resource scheduling Tables 7 and 10 show that the algorithm designed in the article can generate a targeted resource scheduling solution based on real project information.

The model and algorithm presented in this article offer an efficient and stable resource scheduling plan, reducing schedule delays. The practical implications are as follows:

Effective schedule solutions are provided based on different decision preferences of project managers. Specific references for process start times and emergency project urgency are also provided.

In summary, the introduced model and algorithm have practical implications for delivering efficient resource scheduling, mitigating delays, and facilitating effective decision-making in resource allocation.