Hybrid differential evolution particle swarm optimization (DEA-DCWPSO) for resource-constrained multi-project scheduling problem

Abstract

In this paper, we studied the resource constrained project scheduling problem, and the research object is extended to the multi-project environment. On the basis of multi-project priority evaluation, with the goal of minimizing the weighted duration of multi-project, a multi-project schedule planning model is constructed. Through reasonable scheduling of multiple parallel projects sharing resources under resource constraints, it provides a decision-making basis for project managers to allocate resources reasonably under resource constraints to meet the duration requirements of each project and to shorten the weighted total duration of multiple projects as much as possible. A two-stage hybrid differential evolution particle swarm optimization algorithm is used to solve the model. In the first stage, differential evolution algorithm is used to produce new individuals, and in the second stage, particle swarm optimization algorithm uses a new speed update formula. In the first stage, in order to ensure that the optimal individual will not be destroyed by crossover and mutation, and to maintain the convergence of differential evolution algorithm, we try to introduce Elitist Retention (ER) strategy into differential evolution algorithm. In the second stage, we use a kind of particle swarm optimization algorithm with dynamically changing inertia weight. Through the dynamic changing inertia weight, the global search and local search ability of the algorithm can be adjusted flexibly. The case verification shows that the hybrid differential evolution particle swarm optimization algorithm can be used to solve the RCMPSP model more effectively.

Keywords

DEA-DCWPSO dynamic inertia weight elitist retention multi-project scheduling

1. Introduction

The goal of Resource constrained multi-project scheduling problem (RCMPSP) is to achieve the shortest duration, the lowest cost or the maximum profit, aiming at the task set and limited resource set of multi-projects and projects, considering the resource sharing relationship between projects, the timing relationship between tasks and resource capacity constraints, to find an ideal project scheduling and resource optimization problem. As a typical combinatorial optimization problem, RCMPSP belongs to NP-hard problem [1]. From the current project practice, we can see that with the deepening of the enterprise project process and the continuous increase in the number of projects, more and more enterprises are facing the state of multi-project parallelism in management, and multi-project situations are becoming more and more common. However, the study of project scheduling problem under resource constraints in multi-project environment is more complex than that in single-project environment, because it needs to consider not only the resource allocation problem within the project, but also the allocation of resources among projects. The tasks of different projects do not have the same strict pre-and post-constraint relationship as in a single project, and many effective methods in a single project cannot be directly used in a multi-project environment, and compared with the research on single-project scheduling, the relevant research literature on multi-project scheduling is still less, so the research on RCMPSP also has higher practical research significance. In view of the complexity of NP-hard problem solving, it is often faced with many difficulties, and the difficulty degree of the problem increases geometrically with the increase of the number of tasks. At present, the main algorithms for solving RCMPSP model are exact algorithm, heuristic algorithm and intelligent optimization algorithm [2, 3, 4, 5, 6, 7, 8]. Among them, exact algorithms are usually suitable for exactly solving small-scale scheduling problems, but when solving large-scale problems; These algorithms often have some defects such as complex calculation and low efficiency. And the heuristic algorithms usually only aim at specific problems, so their versatility in practical applications is poor. In recent years, more and more researches on RCMPSP turn to intelligent optimization algorithms. Because MATLAB language has powerful functions such as numerical calculation, symbolic calculation, graphics and visualization, and programming, it is widely used in the research field of scientific and engineering methods of calculation, such as large-scale matrix calculation, optimization calculation, image processing, numerical calculation methods and graphical user interface design. Based on the above analysis, this paper tries to use MATLAB language to choose an algorithm suitable for solving this kind of problem model.

In fact, there are many algorithms for solving this kind of problems. Among them, particle swarm optimization (PSO) algorithm, as an evolutionary computing technology among many intelligent optimization algorithms, is more suitable for solving nonlinear, multi-peak, non-differentiable complex optimization problems, and is applicable to the solution of RCMPSP. However, due to the limitations of the algorithm itself, the PSO algorithm is easy to fall into local optimization when solving the optimal solution, which inevitably leads to differences between the optimized results and the expected results. Therefore, this paper attempts to use a two-stage hybrid differential evolution particle swarm optimization algorithm to solve the model. In the first stage, differential evolution algorithm is used to produce new individuals, and in the second stage, particle swarm optimization algorithm uses a new speed update formula. In the first stage, in order to ensure that the optimal individual will not be destroyed by crossover, mutation and other operations, to maintain the convergence of differential evolution algorithm, we try to introduce Elitist reservation (ER) strategy into differential evolution algorithm. In the second stage, we use a class of PSO algorithm with dynamic inertia weight [9]. Through the dynamic change of inertia weight, the global search and local search ability of the algorithm can be adjusted flexibly. Finally, the improved two-stage hybrid differential evolution particle swarm optimization algorithm is used to solve the RCMPSP model, and a relatively better optimization result is expected.

2. Problem description

RCMPSP is usually described as: there are multiple parallel projects and a shared resource library, there are many kinds of limited updatable resources in the shared resource library, and there are competitions and conflicts for limited resources among projects; projects are independent of each other except shared resources and there is no tight relationship between projects; There is a tight pre-and post-relationship between project tasks, but it does not involve task preemption, circulation and feedback. This paper takes the weighted total duration minimization of multi-projects as the objective function, and the RCMPSP model is as follows:

$\displaystyle\textit{Minimize}\sum\limits_{i=0}^{n}{\alpha_{i}\left|{t_{i(N+1)% }-t_{i0}}\right|}$ (1) $\displaystyle\textit{subject to}:t_{ij}-t_{ih}\geqslant d_{ih},\forall h\in P_% {ij},\forall i,j$ (2) $\displaystyle t_{00}=0$ (3) $\displaystyle\sum\limits_{T_{ij}\in A_{t}}{r_{\textit{ijk}}\in R_{k},\forall k% ,t}$ (4) $\displaystyle t_{ij}\geqslant 0,d_{ij}\geqslant 0,r_{\textit{ijk}}\geqslant 0$ (5) $\displaystyle\sum\limits_{i=1}^{n}{\alpha_{i}=1}$ (6)

Equation (1) is the objective function, which is used to express the shortest weighted total duration of $n$ projects; Eq. (2) represents the immediate constraint relationship of each project task; Eq. (3) indicates that the start time of the virtual task of the project is 0. That is, it does not occupy project resources and time; Eq. (4) indicates shared resource constraints, that is, the total resource demand for resources $k$ of tasks carried out at $t$ time cannot exceed its supply. Equation (5) indicates that the start time, duration and resources of the task are all non-negative, while Eq. (6) indicates that the sum of priority weight coefficients of each project is 1. The symbol definitions used in the above types are shown in Table 1.

Table 1

Symbol definition

Symbol	Meaning
$i$	The number of the project, $i=1,2,\ldots,n$
$j$	The number of tasks in each project
$k$	The number of the shared resource
$t$	The time point measured in days
$\alpha_{i}$	Priority weight of project $i$
$t_{i0}$	Initial task start time for project $i$
$t_{i(N+1)}$	The completion time of the last task in project $i$
$d_{ih}$	The duration of the $j$ task in the $i$ project
$P_{ij}$	The collection of all the Immediate tasks of the $j$ task in the $i$ project
$r_{\textit{ijk}}$	The number of resources used by the $j$ task of the $i$ project to the $k$ resource per day

3. Model solving

3.1 Differential evolution algorithm

Differential evolution algorithm (DE) is a novel heuristic intelligent search algorithm, which is originally used to solve Chebyshev polynomials problems [10]. Stom and Price [11] found that it has excellent performance in solving complex optimization problems, and through detailed numerical simulation experiments show that DE is an optimization algorithm with simple structure, few adjustable parameters and strong robustness. Similar to GA, DE achieves population evolution through repeated iterations of selection, crossover and mutation, and then tends to global optimization. Different from GA, DE makes individual disturbance with the help of difference vectors among individuals to achieve individual variation, which can effectively make use of the characteristics of population distribution and improve the search ability of the algorithm. In addition, the greedy selection mode of one-to-one elimination mechanism is adopted in the DE selection process, which can avoid the degradation of some individuals.

The basic differential evolution algorithm is mainly composed of four processes: initialization, mutation, crossover and selection. The specific operation process is as follows:

(1)
Population initialization process. The initial population $P^{0}$ should usually cover the whole search area as much as possible, so let $X_{i}^{t}=(x_{i1},x_{i2},\ldots,x_{in}),i=1,2,\ldots,NP$ is the $i$ individual of the $i$ iteration, then the initial population with $N P$ , individual component $n$ can be generated by random sampling.

$\displaystyle x_{ij}^{0}=\textit{rand}_{ij}(0,1)(x_{ij}^{\max}-x_{il}^{\min})+% x_{ij}^{\min}$ (7)
(2)
The process of mutation. Different from GA, the basic principle of DE mutation operation is that some Difference Vectors are scaled and added to the Base Vector of another individual to get the mutated individual. According to the different ways of the number of difference vectors, the calculation formula and the selection of base vectors, there are a variety of difference strategies. These strategies are usually recorded as $DE/x/y/z$ , where $x$ represents the number of base vectors, $y$ represents the number of difference vectors, and $z$ represents the type of crossover operation. The main variation modes are as follows [12, 13].

$\displaystyle DE/\textit{rand}/1/\textit{bin}:v_{i}^{t}=x_{r1}^{t}+F\cdot(x_{r% 2}^{t}-x_{r3}^{t})$ (8) $\displaystyle DE/\textit{best}/1/\textit{bin}:v_{i}^{t}=x_{\textit{best}}+F% \cdot(x_{r1}-x_{r2})$ (9) $\displaystyle DE/\textit{best}/2/\textit{bin}:v_{i}^{t}=x_{\textit{best}}+F% \cdot[(x_{r1}-x_{r2})+(x_{r3}-x_{r4})]$ (10)
(3)
Crossover process. The mutated individual and the current evolving individual in the population produce the intermediate individual $c_{i}^{t}$ in the way of discrete cross-recombination, and the population diversity is increased through the interaction between the mutated individual and the current evolving individual elements in the population. At present, the commonly used methods can be divided into binomial crossover and exponential crossover [14]. The binomial crossover operation is relatively simple and can be realized according to Eq. (11).

$\displaystyle c_{ij}^{t}=\left\{{{\begin{array}[]{ll}{v_{ij}^{t}}&\text{if }(% \textit{rand}_{ij}(0,1)\leqslant CR)\text{ or }j=\textit{rand}(n)\\ {x_{ij}^{t}}&\text{otherwise}\\ \end{array}}}\right.$ (11)
(4)
The selection processes. The selection process determines the evolution direction of the population as a whole. The basic differential evolution algorithm adopts one-to-one greedy selection between the intermediate individual $c_{i}^{t}$ and the current individual $x_{i}^{t}$ , that is, if the fitness of the intermediate individual is better than the current individual, then the current individual is replaced, otherwise the current individual is selected. The selection process can be expressed by Eq. (12).

$\displaystyle x_{\textit{ide}}=\left\{{{\begin{array}[]{ll}{c_{i}^{t}}&{\text{% if }f(c_{i}^{t})\leqslant f(x_{i}^{t})}\\ {x_{i}^{t}}&\text{otherwise}\\ \end{array}}}\right.$ (12)

3.2 Elitist reservation strategy

Elitist reservation strategy (ER), as an improved evolutionary algorithm mechanism strategy, was proposed by Holland in the early stage [15]. It is mainly used to deal with the problem of optimal individual loss caused by the selection error, crossover and mutation operators in the selection operator which destroy the high-order long-distance patterns in the process of evolution. Because Elitist individuals are the best individuals in the process of evolution, which plays an important role in promoting population evolution, whether we can make full use of the characteristic information of Elitist individuals is the key to improve the performance of the algorithm. The use of Elitist reservation strategy in the optimization algorithm can not only ensure that the individuals with better fitness values in the population will not be destroyed, but also ensure the global convergence of the algorithm [16].

During the operation of differential evolution algorithm, although more and more excellent individuals will be produced with the continuous evolution of the population, it is possible to destroy the individuals with the optimal fitness value in the current population because of the randomness of crossover, mutation and other operations. And then affect the overall efficiency and convergence of the algorithm. The basic idea of Elitist reservation strategy is to retain $n$ Elitist individuals in the parent generation before crossover, mutation and other operations, and then carry out crossover and mutation operations to produce offspring and find out the $n$ individuals with the worst adaptation in the offspring. Use $n$ retained Elitist individuals to replace the worst n individuals in the offspring to produce a new population. Through this strategy, the individuals with the best fitness value in the parent generation can be retained to the next generation population, which ensures that the optimal individual will not be destroyed by mutation and crossover in the differential evolution algorithm, thus ensuring the global convergence of the algorithm.

3.3 Particle swarm optimization

Basic particle swarm optimization (PSO) was proposed by Eberhart and Kennedy in 1995 [17]. As a kind of parallel optimization algorithm based on swarm intelligence, PSO has been widely used in many fields. The particle swarm optimization algorithm is associated with a certain number of subpopulations, and its basic algorithm can be described as follows: in a J-dimensional search space, there are several randomly distributed particles with volume and weight, and each particle has two values, namely velocity vector and position. The position value of the particle represents a potential solution of the problem, and the particle moves in the direction of the velocity vector in the solution space, through the completion of each iteration, the particle flies to a new position and judges the individual optimal position and the group optimal position through the fitness function, so as to determine the new velocity vector and then constantly adjust its own position [18].

Let the search space be J-dimensional and the number of particles $N$ . Then the position of the $i$ -th particle can be expressed as $x_{i}=(x_{i1},x_{i2},\ldots,x_{iJ}),i=1,2,\ldots,N$ ; The corresponding velocity of each particle is expressed as $v_{i}=(v_{i1},v_{i2},\ldots,v_{iJ}),i=1,2,\ldots,N$ Two factors are usually taken into account when searching for each particle, one is the optimal value found by the individual traversing the search. There are usually two factors to be taken into account when searching for each particle, one is the optimal value $p_{i}$ found by traversing the individual, $p_{i}=(p_{i1},p_{i2},\ldots,p_{iJ}),i=1,2,\ldots,N$ , can be marked as $P_{\textit{best}}$ ; The other is the optimal value $p_{g}$ found by traversing all the particles, $p_{g}=(p_{g1},p_{g2},\ldots,p_{gJ}),g=1,2,\ldots,N$ , can be marked as $G_{\textit{best}}$ .

In the standard particle swarm optimization algorithm, update the particle speed and position according to Eqs (13) and (14):

$\displaystyle v_{ij}(t+1)=v_{ij}(t)+c_{1}\cdot\textit{rand}_{1}()\cdot[P_{ij}(% t)-x_{ij}(t)]+c_{2}\cdot\textit{rand}_{2}()\cdot[P_{gj}(t)-x_{ij}(t)]$ (13) $\displaystyle x_{ij}(t+1)=v_{ij}(t+1)+x_{ij}(t)$ (14)

3.4 Dynamically changing inertia weight particle swarm optimization algorithm

PSO algorithm is similar to genetic algorithm (GA), which starts from the random solution and evaluates the solution by fitness function through iterative optimization. Compared with GA and other algorithms, the algorithm rules of PSO are simpler and easier to implement, and the performance of algorithms such as solution accuracy and convergence speed is also better. However, its search ability and local search speed are not good enough. Therefore, in practical application, it is necessary to improve the algorithm according to the different problems and explore the solution of premature convergence to improve the efficiency of the algorithm. Clerc summarizes the law after analyzing the general problems [19], that is, in the process of solving the general problem, the distribution of particles at the beginning of the iterative process is relatively dispersed, and it is necessary to use a strong global search ability to make the particles quickly converge to the optimal solution, while in the later stage of the implementation of the algorithm, after the particles converge to a certain area near the optimal solution, it is necessary to reduce the speed to conduct a detailed local search. Therefore, although the inertia weight coefficient is taken as a constant at the initial stage, but through experiments, scholars find that dynamic $\omega$ can obtain better optimization results than fixed value $\omega$ .

In order to better coordinate the balance between the global search ability and the local search ability of the particle swarm optimization algorithm, so as to control its development and optimization detection ability, the strategy of linearly decreasing weight (LDW) is put forward by Shi and Eberhart [20]. By using the changeable inertia weight, a large $\omega$ value is set at the beginning, and as the iteration becomes smaller, thus gradually turning from exploration to discovery, experiments have proved that the LDW strategy can effectively improve the optimization effect of PSO.

Dai and Yang [21] proposed a logarithmic decreasing weight strategy (LOGW), that is:

$\displaystyle\omega=\omega_{\max}-\alpha\cdot(\omega_{\max}-\omega_{\min})% \cdot\log_{T_{\max}}^{\textit{Iter}}$ (15)

And proposing $\alpha$ as logarithmic regulating factor, when $0<\alpha<1$ , calling it as logarithmic compressing factor, when $\alpha>1$ , calling it as logarithmic inflating factor. Through experimental testing, it can be obtained that the performance of LOGWPSO algorithm is better than LINWPSO.

In order to change the single regulating pattern of LINW strategy, Ren and Wang [22] introduced the concept of Change rate of focusing distance. Defining it as:

$\displaystyle k=\frac{\textit{MaxDist}-\textit{MeanDist}}{\textit{MaxDist}}$ (16)

Among them, MaxDist is the biggest focusing distance, MeanDist is the average focusing distance:

$\displaystyle\textit{MeanDist}=\frac{\sum\limits_{i=1}^{m}{\sqrt{\sum\limits_{% d=1}^{D}{(p_{td}-x_{id})^{2}}}}}{m}$ (17) $\displaystyle\textit{MaxDist}=\mathop{\max}\limits_{i=1,2,\cdots,m}\sqrt{\sum% \limits_{d=1}^{D}{(p_{td}-x_{id})^{2}}}$ (18)

Where $m$ is the number of particles in the particle swarm, $D$ is the dimension of each particle, ${p}_{{td}}$ is the optimal position searched by the particle swarm, and ${x}_{{id}}$ is the optimal position searched by each particle. Based on the adaptive inertia weight of $k$ , it is judged that the particle should improve its global search ability or local search ability by calculating the value of k in each iteration, and then adjust the inertia weight dynamically.

$\displaystyle\omega\left\{{{\begin{array}[]{ll}{(\alpha_{1}+\left|r\right|/2)% \left|{\ln k}\right|}&{\left|k\right|>1}\\ {\alpha_{1}\alpha_{2}+\left|r\right|/2}&{0.05\leqslant\left|k\right|\leqslant 1% }\\ {\alpha_{2}+\left|r\right|/2}&{\left|k\right|<0.05}\\ \end{array}}}\right.$ (19)

Among them, $k$ is the rate of focusing distance, $r$ is the random number of evenly distributions in the interval of [0, 1]. Letting $\alpha_{1}=0.3,\alpha_{2}=0.2$ , the experimental results show that the convergence speed and accuracy of the proposed dynamically changing inertia weight particle swarm optimization algorithm (DCWPSO) are better than those of LINWPSO.

4. DEA-DCWPSO solves RCMPSP

4.1 Particle express

Commanding $X_{i}=(x_{i1},x_{i2},x_{ij},\ldots,x_{in})$ as the $i$ -th particle position in the particle population, on the premise of constraints that satisfy logical relationship between tasks, the value of $X_{i}$ represent prior level of corresponding task. Ranking every elements of position vector $X_{i}$ can obtain a feasible scheduling plan that a sorting sequence $S$ of node number. In the computational process of iterative optimization, the sequences also change ceaselessly along with the update of particulate position vector and the advantages and disadvantages of the performance of each particle depend on fitness value which is set according to the objective function. The initialization of population is the starting point of algorithmic iteration and it can be finished through generating population randomly or the way of selecting appropriate population. Good initial population requires individuality to distribute as evenly as possible in the space of solution. Therefore, the article uses random ways to generate the initial population.

4.2 Particulate fitness function

In the algorithm of particle swarm, the position update and speed update of particle swarm carries on according to the particulate fitness. Therefore, the function of particulate fitness should be set according to the objective function of optimization which is set with the multi-project scheduling problem. Due to the goal of model which the article has built has set as multi-project weighted total time minimization, the advantages and disadvantages of scheduling plan depend on the objective function. Therefore, the article defines the particulate fitness function $\textit{Fitness}(X_{i})$ as:

$\displaystyle\textit{Fitness}(X_{i})=\frac{C}{T}=\frac{C}{\sum\limits_{i=0}^{n% }{\alpha_{i}\left|{t_{i(N+1)}-t_{i0}}\right|}}$ (20)

Among them, $C$ is the regulating coefficient of the fitness function of non-zero and non-negative, $T$ is objective function. Through the fitness function, it is seen easily that the bigger the value of $\textit{Fitness}(X_{i})$ become, the smaller the value $T$ of objective function become, also indicating the better the scheduling plan become.

4.3 Schedule generation schemes

There are two kinds of Project Schedule Generation Schemes: Serial Schedule Generation Schemes, SSGS and Parallel Schedule Generation Schemes, PSGS [23]. Kolisch [24] testifies that SSGS generates positive schemes and PSGS generates non-delayed schemes. For the majority of routine index of minimization project time, SSGS that are treated as a positive scheme often further suit and using PSGS to solve misses possibly optimal solution. On the project of solving larger scale and appropriate resource-constrained, the solving result of SSGS is better. What kind of Schedule Generation Schemes are choosing concretely according to the character of realistic problem? Therefore, for the character of searching problem, the article uses Serial Schedule Generation Schemes, concrete process as follows:

(1)
Initialize relevant parameters, choosing the $n=1$ particle initializes, $n=1,2,\ldots,P,S_{n}=\emptyset,C_{n}=\emptyset,t=0$ , among them, $S_{n}$ is tasks set which has handled, $C_{n}$ is waiting tasks set which will be need to handle.
(2)
Referencing $C_{n}$ , selecting the task $j$ of tallest priority value, computing the time $d_{j}$ of task at the same time.
(3)
The earliest start $\textit{EST}_{j}$ of task $j$ is determined according to the completed time of the processed task and the resource surplus $\Delta R_{{kt}}$ in $S_{n}$ (It is required that $r_{jk}\leqslant R_{tk}$ , that is, the demand of task $j$ for $k$ resources is less than the surplus of $k$ resources at $t$ time.), and then the earliest end time $\textit{EFT}_{j}$ is obtained according to the task duration $d_{j}$ .
(4)
Updating $S_{n}$ and $C_{n}$ , adding task $j$ to $S_{n}$ and deleting task $j$ in the $C_{n}$ . That is $S_{n}=S_{n-1}\cup\{j|j\in C_{n-1}\}$ , $C_{n}=C_{n-1}\backslash\{j|j\in C_{n-1}\}$ .
(5)
Checking tasks whether have been scheduled in all, that is if $j=J$ , getting into 6); If $j\neq J$ letting $j=j+1$ and returning to 2).
(6)
If $n=P$ , getting into 7); If $n\neq P$ , letting $n=n+1$ , returning to 1), $P$ is the scale of particle population.
(7)
Conclusion.

4.4 The procedure of DEA-DCWPSO algorithm

4.4.1 The two-stage of DEA-DCWPSO algorithm

In the first stage, a new individual $x_{\textit{ide}}$ is obtained by using differential evolution algorithm. In the second stage, the particle swarm optimization algorithm is used, and the new individuals generated in the first stage are introduced to generate a new speed update formula, and the individual $x_{\textit{ide}}$ obtained in the first stage is used to replace the individual optimal $P_{ij}$ in the original speed update formula. New speed update formula is:

$\displaystyle v_{ij}(t+1)=v_{ij}(t)+c_{1}\cdot\textit{rand}_{1}()\cdot[x_{% \textit{ide}}(t)-x_{ij}(t)]+c_{2}\cdot\textit{rand}_{2}()\cdot[P_{gj}(t)-x_{ij% }(t)]$ (21)

4.4.2 The specific procedure of DEA-DCWPSO algorithm

(1)
Setting up the relevant parameters of DEA-DCWPSO algorithm and iteration times $t=0$ ; Setting up max iteration times Maxit.
(2)
Initializing population randomly, computing the fitness value, solving the optimal solution $P_{i}$ of individuality and the optimal solution $P_{g}$ in the whole population.
(3)
The two subpopulations of the differential evolution algorithm mutate according to Eqs (9) and (10) respectively, crossover operation according to Eq. (11), and finally select a new individual $x_{\textit{ide}}$ according to Eq. (12).
(4)
Updating speed and position for PSO population according to the Eqs (21) and (14).
(5)
Computing new fitness value after the operation of PSO evolution, updating $P_{i}$ and $P_{g}$ .
(6)
Updating iteration times $t=t+1$ , if attaining the max iteration times, terminating algorithm, outputting optimal solution; Otherwise, turning to the c procedure.

Figure 1.
The Network Figure after combination of three projects.

5. Case simulation and result analyze

5.1 Building case

For the simulated experiment of RCPSP, it can use national Patterson problem set or the single-project cases of PSPLIB standard databases generally. But for the RCPSP of multi-project, now experiment lacks corresponding Benchmark databases [25, 26]. For the case of RCPSP, current articles almost have built through the ways of Project Practice and a sprinkle of example case and the single-project case of combination. Therefore, being based on the project practice of construction company, the chapter builds resource-constrained multi-project scheduling case that is constituted with three projects. In the case, three small projects construct parallel and share three limited resources in the same resource-pool. The amounts of three resources is $R_{1}=6$ , $R_{2}=9$ , $R_{3}=11$ respectively. Project I, Project II and Project III have different priorities. In order to compute easily, the priority of three project is $\alpha_{1}=0.5$ , $\alpha_{2}=0.2$ and $\alpha_{3}=0.3$ respectively. Moreover, every process both are expressed with tasks of stationary number and three projects contain in all 36 tasks. Now, there are two methods to handle the multi-project of RCMPSP. The first one is that multiple projects are solved independently; secondly, add virtual start and end nodes to multiple projects, and then convert multiple projects into single projects for solution. Due to multi-project resource requirements of resource-constrained exist conflicts, the plan of dispatch that make project cut apart and solve isolated will be difficult to ensure optimality. The way that makes multiple projects translate single project operates easily and it was applied repeatedly in previous searches. From the result of practice, the result of solution can almost satisfy the requirement of problems. So, the article also uses the second way to solve RCMPSP. Firstly, every project builds respectively Project Network Plan for defining the logical relationship of project tasks. Then, fictitious nodes of beginning ( $S^{*}$ ) and nodes of end ( $F^{*}$ ) are increased at the place of multi-project head and tail and these two fictitious nodes both need 0 resource and time. Letting the Network Plan of three projects in the manner of paralleling merges into a Network Plan of total project as is shown in Fig. 1.

5.2 Solving result

Set the parameters of DCWPSO algorithm. Assuming populations of particle swarm popsize $=$ 100; The numbers of iteration ITmaxgen $=$ 200; The coefficients of initial inertia weight respectively set up $\omega\min i_{\max}$ ; The coefficients of study $c_{1}=1.8$ , $c_{2}=1.4$ . Algorithm operates 50 times. As is shown in Table 2, the multi-project scheduling results of optimal solution are indicated. The multi-project scheduling Gantt Figure is indicated in Fig. 2.

Table 2
The results of multi-project scheduling

Project I	Task number	1	2	3	4	5	6	7	8	9	10	11	12
	Start time	1	5	4	7	11	8	10	14	14	16	19	23
	End time	3	6	7	9	13	10	12	15	18	18	22	26
Project II	Task number	A	B	C	D	E	F	G	H	I	J	K	L
	Start time	1	3	19	27	22	29	26	31	29	34	39	43
	End time	2	4	21	28	25	30	28	33	30	38	42	46
Project III	Task number	a	b	c	d	e	f	g	h	i	j	k	l
	Start time	34	39	47	49	42	51	54	46	54	58	61	63
	End time	37	41	48	50	45	53	57	50	57	60	62	66

Figure 2.

The Gantt Figure of example results of multi-project scheduling.

5.3 Comparative analysis of solution results and computational performance

In order to further test effectiveness that the algorithm of DEA-DCWPSO which article use solves RCMPSP, continuing to use algorithms of GA and PSO and DCWPSO solve same model. And solving result and computational performance is compared to algorithm of DEA-DCWPSO and analyzing. The algorithmic parameters of GA set to algorithmic population popsize $=$ 50; The number of algorithmic iterations GA max $=$ 200. The variant probability PM $=$ 0.3; The intersecting probability PC $=$ 0.6. The value of algorithmic parameters of PSO and DCWPSP are same as the article. As is shown in Table 3, through algorithmic calculation, result of solution is obtained respectively. Among them, comparing the value of the objective function of the algorithm of DCWPSO and DEA-DCWPSO with the experimental curve of the number of iterations as is shown in Fig. 3.

Table 3
The comparisons of solving result of multiple algorithm

Algorithms	Convergence algebra	Average iteration time (s)	Obtains the optimal solution times	Weighted total duration (day)	The latest project completion time (day)
GA	31	86.69	50	44.7	75
PSO	17	69.24	49	44.1	73
DCWPSO	13	75.08	50	43.9	72
DEA-DCWPSO	48	191.57	50	42	66

Figure 3.

Comparing the value of the objective function of the algorithm of DCWPSO and DEA-DCWPSO with the experimental curve of the number of iterations.

In the four algorithms, the result of solution of the algorithm of DEA-DCWPSO is better than solution of the other three kinds of algorithm. At the iteration of algorithm, the algorithm of DEA-DCWPSO that have character of two stage optimization reduce algorithmic premature convergence and promote conspicuously algorithmic spread of solution. According to computation, the multi-project weighted total period and the longest period of project are respectively 42 days and 66 days and it is both less than the computational result of algorithms of GA, PSO and DCWPSO. Therefore, the algorithm of DEA-DCWPSO can be stable, effective and better solve RCMPSP. Although iterative optimization time that DCWPSO operate 50 times spend 191.57 s averagely and it is more than other three algorithm, the article’s final target which study multi-project scheduling is achieving resource optimized allocation, compressing effectively multi-project overall period, reducing project delay for evading risks and decreasing expense. The spending time that algorithm solve problem is not the key promoting index.

6. Conclusion

The article extends the RCPSP in multi-project environment, using Multi-project weighted total time as a goal of optimization to build RCMPSP model. Based on the complexity of solving such NP-hard problems, a two-stage hybrid differential evolution particle swarm optimization algorithm is used to solve the constructed model by using MATLAB, which is widely used in the research field of scientific and engineering methods of calculation. The algorithm employs DE to produce new individuals in the first stage. PSO uses new spread to update formula in the second stage. During the first phase, it is assured that the optimal individuals cannot be devastated in the operation of crossover and mutation and makes DE keep convergence and tries to introduce ER into DE. During the second phase, the article uses a kind of PSO that has the feature of dynamic inertia weight and the algorithmic abilities of global searching and local searching can be regulated flexibly through the dynamic changes of inertia weight. In order to test effectiveness that the algorithm of DEA-DCWPSO solves RCMPSP, the article applies the algorithms of GA, PSO and DCWPSO to address model and calculative results are compared with the results of DEA-DCWPSO. Through testing, the case indicates that using the algorithm of DEA-DCWPSO can achieve effectively solution of model which has built, and it has certain advantages on resolving problems and effectively can conduct optimal scheduling of multi-project. It can offer reference of task scheduling and resource allocation in the project implementation process.

Footnotes

Acknowledgments

The authors are grateful for their support. The contribution of this research was based on previous studies, and the authors of this paper express their heartfelt thanks to the authors of all listed previous works.

Funding

This research was funded by the Initial Scientific Research Fund in the Shandong University of Science and Technology, grant number 2019RCJJ026.

References

Brucker

Drexl

Mohring

Neumannd

Pesche

. Resource-constrained project scheduling: Notation, classification, models, and methods. Eur J Oper Res. 1999; 112(1): 3-41.

Mohanthy

Siddiq

. Multiple projects multiple resources-constrained scheduling: Some studies. Int J Prod Res. 1989; 27(2): 261-280.

Deckro

Winkofsky

Hebert

Gagnon

. A decomposition approach to multi-project scheduling. Eur J Oper Res. 1991; 51(1): 110-118.

Vercellis

. Constrained multi-project planning problems: A Lagrangean decomposition approach. Eur J Oper Res. 1994; 78(2): 267-275.

Kurtulus

. Multi-project scheduling: Categorization of heuristic rules performance. Manage Sci. 1982; 28(2): 161-172.

Lova

Tormos

. Combining random sampling and backward-forward heuristics for resource-constrained multi-project scheduling. In: Proceedings of the Eight International Workshop on Project Management and Scheduling. Valencia, Spain; 2002; pp. 244-248.

Goncalves

Mendes

JJM

Resende

MGC

. A genetic algorithm for the resource constrained multi-project scheduling problem. Eur J Oper Res. 2008; 189(3): 1171-1190.

Liang

Zhang

Ding

. Resource constrained multi-project scheduling problem based on back scheduling and genetic algorithm. Comput Eng Des. 2011; 32(2): 4178-4185.

Wang

Wen

. Adaptive particle swarm optimization algorithm for resource constrained multi-project scheduling problem. J Ind Eng Eng Manage. 2017; 31(4): 220-225.

10.

Nizami

Perveen

Nazeer

Baqir

. Walk polynomial: A new graph invariant. Appl Math Nonlinear Sci. 2018; 3(1): 321-330.

11.

Stom

Price

. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. J Global Optim. 1997; 11(4): 341-359.

12.

Brest

Boskovic

Greiner

Zumer

Maucec

. Performance comparison of self-adaptive and adaptive differential evolution algorithms. Soft Comput. 2007; 11(7): 617-629.

13.

Das

Abraham

Chakraborty

Konar

. Differential evolution using a neighborhood-based mutation operator. IEEE Trans Evol Comput. 2009; 13(3): 526-553.

14.

Acar

Izgi

Serenbay

. Note on Jakimovski-Leviatan operators preserving E-X. Appl Math Nonlinear Sci. 2019; 4(2): 543-550.

15.

Holland

. Adaptation in natural and artificial systems [Dissertation]. Ann Arbor: The University of Michigan Press, MI; 1975.

16.

Colorni

Dorigo

Maniezzo

. Distributed optimization by ant colonies. In: The First European Conference on Artificial Life. France; 1991; pp. 134-142.

17.

Eberhart

Kennedy

. A new optimizer using particle swarm theory. In: Proceedings of the Sixth International Symposium on Micro Machine and Human Science. 1995; pp. 39-43.

18.

Sun

Feng

. Particle swarm optimization with particles having quantum behavior. IEEE Congr Evol Comput. 2004; pp. 325-331.

19.

Clerc

. The swarm and the queen: Towards a deterministic and adaptive particle swarm optimization. Proc Congr Evol Comput. 1999; 3: 1951-1957.

20.

Shi

Eberhart

. Empirical study of particle swarm optimization. In: Proceedings of the Congress on Evolutionary Computation. Piscataway: IEEE Service Center. 1999; pp. 1945-1950.

21.

Dai

Yang

. Particle swarm optimization algorithm based on inertia weight logarithmic decreasing. Comput Eng Appl. 2015; 51(17): 14-19.

22.

Ren

Wang

. New adaptive particle swarm optimization algorithm with dynamically changing inertia weight. Comput Sci. 2009; 51(2): 227-229.

23.

Kelly

. Critical-path planning and scheduling: Mathematical basis. Oper Res. 1961; 9(3): 296-320.

24.

Kolisch

. Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. Eur J Oper Res. 1996; 90(2): 320-333.

25.

Viana

Sousa

. Using metaheuristics in multi-objective resource constrained project scheduling. Eur J Oper Res. 2000; 120(2): 359-374.

26.

Shou

. Resource-constrained multi-project scheduling models and methods [Dissertation]. Hangzhou: Zhejiang University Press; 2010.