# Accelerated Particle Swarm Optimization to Solve Large-Scale Network Plan Optimization of Resource-Leveling with a Fixed Duration

Authors: Houxian Zhang; Zhaolan Yang
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Large-scale network plan optimization of resource-leveling with a fixed duration is challenging in project management. Particle swarm optimization (PSO) has provided an effective way to solve this problem in recent years. Although the previous algorithms have provided a way to accelerate the optimization of large-scale network plan by optimizing the initial particle swarm, how to more effectively accelerate the optimization of large-scale network plan with PSO is still an issue worth exploring. The main aim of this study was to develop an accelerated particle swarm optimization (APSO) for the large-scale network plan optimization of resource-leveling with a fixed duration. By adjusting the acceleration factor, the large-scale network plan optimization of resource-leveling with a fixed duration yielded a better result in this study than previously reported. Computational results demonstrated that, for the same large-scale network plan, the proposed algorithm improved the leveling criterion by 24% compared with previous solutions. APSO proposed in this study was similar in form to, but different from, particle swarm optimization with contraction factor (PSOCF). PSOCF did not have as good adaptability as APSO for network plan optimization. Accelerated convergence particle swarm optimization (ACPSO) is similar in form to the APSO proposed in this study, but its irrationality was pointed out in this study by analyzing the iterative matrix convergence.


---

## Body

## 1. Introduction

The network plan is considered by the engineering community as a promising management method. A large-scale network plan with many works (such as more than 50) is an effective tool for solving large project management problems [1, 2]. However, the number of possible solutions in large-scale network plan optimization sharply increases with the number of works, and the time of calculation is exponential, far beyond the processing capacity of computing resources, so mathematics and computer science cannot solve the problem known as NP problem [2, 3]. In recent years, genetic algorithm [4, 5], Monte Carlo partition optimization [6], and particle swarm optimization (PSO) [7, 8] have provided an effective means to solve this problem.PSO was proposed in 1995. Although the convergence of PSO is still controversial, its applied research has shown good results [9–13]. Experimental research includes optimization, biomedicine, communication, control, and so forth. Theoretical research includes PSO improvement, parameter selection, stability, convergence, and so forth. Improvement in performance of PSO reported in the literature included adjusting the parameters of PSO (inertial factor) [14–17], adopting the neighborhood topology [18], and combining with other algorithms (genetic algorithm, simulated annealing algorithm, and differential evolution algorithm) [19–22]. It does not include the solution to large-scale network plan optimization problems.Accelerated optimization can be marked by better-optimized solutions with the same number of iterations for iterative optimization. Yang et al. introduced some virtual particles in random directions with random amplitude to enhance the explorative capability of particles in PSO [23]; Qi et al. hybridized an improved estimation of distribution algorithm (EDA) using historic best positions to construct a sample space with PSO both in sequential and in parallel to improve population diversity control and avoid premature convergence for optimization of a water distribution network [24]; Zhang et al. added the random velocity operator from local optima to global optima into the velocity update formula of constriction particle swarm optimization (CPSO) to accelerate the convergence speed of the particles to the global optima and reduce the likelihood of being trapped into local optima [25]; Zhou et al. adjusted random functions with the density of the population so as to manipulate the weight of cognition part and social part and executed mutation on both personal best particle and group best particle to explore new areas [26]. Zhang and Yang accelerated the optimization of large-scale network plan resources and analyzed the acceleration optimization mechanism via stochastic process by optimizing the initial particle swarm using the Monte Carlo method under limiting conditions [7, 8, 27]; Ren and Wang proposed a PSO algorithm with accelerated convergence, theoretically proved the fast convergence of the algorithm, and optimized the parameters in the algorithm [28].Inspired by previous efforts [28] to accelerate the convergence of PSO algorithm, this study proposed the method for the large-scale network plan optimization of resource-leveling with a fixed duration through debugging acceleration coefficient (it might also be described as accelerated PSO, or APSO for short) and yielded a better solution than reported in the previous literature.This paper is organized as follows. Section2 describes the experimental research of the large-scale network plan optimization of resource-leveling with a fixed duration using APSO. Section 3 analyzes the difference between APSO and PSO with a contraction factor (PSOCF) [29]. Section 4 analyzes the irrationality of accelerated convergence PSO (ACPSO) reported in [28].


## 2. APSO to Solve the Large-Scale Network Plan Optimization of Resource-Leveling with a Fixed Duration

Large-scale network plan optimization of resource-leveling with a fixed duration achieved the balance of resource demand in each period during the entire period of the project. Equilibrium could be marked by the variance of resources. The formula used to calculate the variance was as follows:σ2=∑i=1Jxi-μ2/J where the total number of samples xi is J, and the arithmetic mean of xi is μ. The smaller the variance, the more balanced the resource.The evolutionary equation of basic PSO was as follows:(1)vijt+1=wvijt+c1rand1tpgjt-xijt+c2rand2tpgt-xijtxijt+1=xijt+vijt+1,where t is the number of iterations; xij(t+1) is j-dimension space coordinates of particle i in t+1 iteration; xij(t) is j-dimension space coordinates of particle i in t iteration; w is inertial factor, usually taking the value of 1 according to the experience; vij(t) is the j-dimension flight speed of particle i; c1 and c2 are accelerators evaluated usually between 0 and 2 by experience; rand1 and rand2 are random functions of value in the range of [0,1]; pgj(t) is the best place to be experienced by particle j; and pg(t) is the best place for all particles to experience. The convergence condition was adopted by setting maximum iteration times G.The evolutionary equation of accelerated PSO (APSO) was as follows:(2)vijt+1=awvijt+c1rand1tpgjt-xijt+c2rand2tpgt-xijtxijt+1=xijt+vijt+1,where a is the acceleration coefficient, and the other signs are the same as earlier. The evolution equation of accelerated particle swarm algorithm has one more a than with that of the basic PSO algorithm and one more w than that of the particle swarm algorithm with contraction factor. However, it has produced significant results for solving large-scale network plan optimization of resource-leveling with a fixed duration as follows.For example, a large network plan with 223 works is the same as Figure1 in [27]. The debugging results of changea are shown in Table 1, where the variance of the corresponding optimization results is 17.58 (better than the variance 22.99 quoted in [27]). The start time of each work is shown in Table 2, and the resource requirements of each unit time are shown in Table 3.Table 1
Optimization parameter’s debugging results of the large-scale network plan optimization of resource-leveling with a fixed duration using the accelerated particle swarm algorithm (particle number is 50;G = 100).
sequence number w c 1 c 2 a σ 2 1 1 2.05 2.05 1 23.97 2 1 2.05 2.05 0.33 19.31 3 1 2.05 2.05 0.31 18.97 4 1 2.05 2.05 0.3 17.58 5 1 2.05 2.05 0.29 18.61 6 1 2.05 2.05 3 31.43 7 1 2.05 2.05 0.1 31.39 8 1 2.05 2.05 0.03 31.43 9 1 3.5 0.4 1 22.99 10 1 3.5 0.4 0.03 31.43 11 1 3.5 0.4 0.5 21.4 12 1 3.5 0.4 0.8 31.43 13 1 3.5 0.4 0.3 23.02 14 1 3.5 0.4 0.6 16.35 error 15 1 3.5 0.4 0.4 20.8 16 1 3.5 0.4 0.35 19.9 17 1 3.5 0.4 0.33 18.4 18 1 3.5 0.4 0.31 25.5 19 0.8 2.05 2.05 1 24.53 20 0.8 2.05 2.05 0.3 31.43 21 0.8 2.05 2.05 1.2 31.43 22 0.8 2.05 2.05 0.4 31.43 23 0.8 2.05 2.05 0.5 31.00 24 0.8 2.05 2.05 0.6 25.85 25 0.8 2.05 2.05 0.7 18.93 26 0.8 2.05 2.05 0.8 22.38 27 0.729 1.454 1.454 1 17.83 28 0.729 1.454 1.454 0.8 25.00 29 0.729 1.454 1.454 1.05 20.54 30 0.729 1.454 1.454 0.9 18.33 error Note. The value in italics is the optimal value under certain parameter conditions.Table 2
The parameters and their optimization solution for the optimization example of the resource-leveling with a fixed duration.
Number Work Duration Resource Quantity ES Optimized ES 1 1–3 2 2 0 0 2 1–4 2 1 0 0 3 3-4 2 1 2 2 4 1-2 1 2 0 0 5 4–6 4 1 4 3 6 5–8 4 1 7 7 7 5–9 5 1 7 8 8 6–8 5 3 13 13 9 7-8 8 3 15 15 10 3–6 3 2 2 3 11 2–4 3 2 1 1 12 3–5 5 1 2 2 13 2–8 3 2 1 1 14 5-6 6 2 7 6 15 2–6 1 3 1 1 16 6-7 2 0 13 12 17 8-9 7 3 23 22 18 8–11 2 2 23 25 19 8–10 2 1 23 23 20 7–10 2 1 15 15 21 9-10 1 2 30 29 22 9–12 4 1 30 28 23 18-19 8 3 57 57 24 17–20 2 1 51 52 25 16–19 4 1 49 48 26 18–21 5 1 57 58 27 17–19 5 3 51 51 28 16-17 2 2 49 49 29 15–17 2 1 46 46 30 14–18 2 1 42 41 31 14–17 1 2 42 41 32 13–15 2 1 44 44 33 10-11 4 1 31 30 34 12-13 5 1 39 39 35 10–13 5 3 31 30 36 10–12 8 3 31 30 37 17-18 6 0 51 51 38 15-16 3 2 46 46 39 11–15 5 1 35 34 40 14-15 3 2 42 41 41 11–17 5 1 35 35 42 12–14 3 2 39 38 43 11–13 6 2 35 34 44 12–15 2 0 39 38 45 21-22 2 2 70 69 46 22–24 2 1 75 88 47 20–22 2 1 73 85 48 20–24 1 2 73 85 49 20–26 2 1 73 84 50 19–21 5 1 65 64 51 19–22 5 3 65 65 52 19-20 8 3 65 76 53 24-25 3 2 77 90 54 24–26 5 1 77 96 55 26-27 3 2 85 101 56 25-26 5 1 80 93 57 23–27 3 2 72 99 58 23–26 6 2 72 70 59 23-24 1 3 72 71 60 21–23 2 0 70 69 61 21–24 7 3 70 70 62 3–28 1 2 2 2 63 3–30 3 2 2 2 64 3–31 1 3 2 3 65 28–30 2 1 3 3 66 28-29 2 2 3 3 67 29-30 2 1 5 5 68 29–31 3 2 5 5 69 29–34 3 2 5 5 70 30-31 4 1 7 8 71 5–31 6 2 7 7 72 5–34 5 3 7 7 73 31-32 2 0 13 14 74 31–34 4 1 13 12 75 32-33 2 1 15 16 76 32–34 8 3 15 16 77 9–34 7 3 30 29 78 9–33 2 1 30 29 79 34-35 2 2 44 44 80 33-34 1 2 43 43 81 33–35 8 3 43 44 82 33–36 5 3 43 42 83 12–33 4 1 39 39 84 12–36 6 2 39 37 85 12–37 5 1 39 37 86 35-36 5 1 51 53 87 35–37 2 0 51 52 88 35–39 5 1 51 53 89 36-37 2 1 56 58 90 14–37 3 2 42 41 91 14–39 2 1 42 41 92 37-38 3 2 58 60 93 37–39 1 2 58 60 94 38-39 2 2 61 63 95 18–39 6 0 57 57 96 18–40 5 3 57 57 97 39-40 8 3 63 77 98 39–41 2 1 63 66 99 40-41 5 1 78 86 100 40–42 5 3 78 84 101 21–40 8 3 70 70 102 21–42 2 1 70 69 103 21–43 1 2 70 69 104 41-42 2 2 83 92 105 41–43 7 3 83 91 106 41–45 2 1 83 91 107 42-43 2 1 85 95 108 23–43 1 3 72 72 109 23–45 5 1 72 72 110 43-44 3 2 90 98 111 43–45 6 2 90 98 112 44-45 5 1 93 101 113 27–45 3 2 88 104 114 38–40 4 1 61 63 115 47-48 2 2 8 9 116 48–50 2 1 10 11 117 47–50 2 1 8 9 118 48-49 1 2 10 11 119 50–53 4 1 14 16 120 52–57 4 1 49 49 121 52–58 5 1 49 61 122 53–57 5 3 55 56 123 56-57 8 3 57 59 124 47–53 3 2 8 9 125 49-50 3 2 11 12 126 47–52 5 1 8 8 127 49–57 3 2 11 13 128 52-53 6 2 49 50 129 49–53 1 3 11 12 130 53–56 2 0 55 56 131 57-58 7 3 65 68 132 57–61 2 2 65 68 133 57–59 2 1 65 67 134 56–59 2 1 57 58 135 58-59 1 2 72 75 136 58–60 4 1 72 76 137 71-72 8 3 99 102 138 69–75 2 1 93 98 139 68–72 4 1 91 94 140 71–73 5 1 99 103 141 69–72 5 3 93 98 142 68-69 2 2 91 95 143 67–69 2 1 88 92 144 65–71 2 1 84 88 145 65–69 1 2 84 87 146 64–67 2 1 86 90 147 59–61 4 1 73 76 148 60–64 5 1 81 85 149 59–64 5 3 73 77 150 59-60 8 3 73 77 151 69–71 6 0 93 97 152 67-68 3 2 88 92 153 61–67 5 1 77 80 154 65–67 3 2 84 87 155 61–69 5 1 77 80 156 60–65 3 2 81 85 157 61–64 6 2 77 81 158 60–67 2 0 81 86 159 73–76 2 2 112 115 160 76–79 2 1 117 121 161 75-76 2 1 115 119 162 75–79 1 2 115 118 163 75–83 2 1 115 118 164 72-73 5 1 107 110 165 72–76 5 3 107 110 166 72–75 8 3 107 110 167 79–82 3 2 119 123 168 79–83 5 1 119 123 169 83-84 3 2 127 132 170 82-83 5 1 122 126 171 78–84 3 2 114 118 172 78–83 6 2 114 119 173 78-79 1 3 114 119 174 73–78 2 0 112 116 175 73–79 7 3 112 116 176 46-47 1 2 7 8 177 47–51 3 2 8 9 178 47–54 1 3 8 8 179 46–51 2 1 7 8 180 29–46 2 2 5 6 181 29–51 2 1 5 5 182 29–54 3 2 5 5 183 51–54 4 1 11 12 184 52–54 6 2 49 51 185 34–52 5 3 44 45 186 54-55 2 0 55 57 187 34–54 4 1 44 44 188 55–62 2 1 57 59 189 34–55 8 3 44 43 190 34–58 7 3 44 44 191 58–62 2 1 72 75 192 34–62 1 2 44 45 193 35–62 8 3 51 52 194 62-63 5 3 85 90 195 60–62 4 1 81 86 196 60–63 6 2 81 85 197 60–66 2 1 81 86 198 35–63 5 1 51 53 199 35–66 2 0 51 52 200 63–66 2 1 90 95 201 65-66 3 2 84 88 202 39–65 2 1 63 64 203 66–70 3 2 92 97 204 39–66 1 2 63 65 205 39–70 2 2 63 66 206 39–71 6 0 63 66 207 71–74 5 3 99 103 208 39–74 8 3 63 64 209 41–74 5 1 83 92 210 74–77 5 3 120 120 211 73-74 8 3 112 112 212 73–77 2 1 112 115 213 73–80 1 2 112 115 214 41–77 2 2 83 92 215 41–80 7 3 83 91 216 77–80 2 1 125 125 217 78–80 1 3 114 118 218 45–78 5 1 98 107 219 80-81 3 2 127 127 220 45–80 6 2 98 108 221 81–84 5 1 130 130 222 45–84 3 2 98 107 223 70–74 4 1 95 100 Note. “ES” is the early start time of each work. “Optimized ES” is the start time optimized.Table 3
The resource requirements of each unit time of large-scale network plan optimization of resource-levelling with a fixed duration using accelerated particle swarm algorithm (duration is 135).
unit time 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 resource requirements 5 10 10 17 9 12 17 16 17 19 18 14 12 9 9 11 12  unit time 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 resource requirements 11 7 7 6 6 9 7 4 5 5 3 4 7 12 11 10 10  unit time 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 resource requirements 12 10 7 10 9 10 7 13 13 13 16 21 19 16 15 16 15  unit time 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 resource requirements 12 12 14 13 13 11 15 15 19 18 13 10 10 15 15 14 11  unit time 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 resource requirements 13 16 17 17 15 12 12 12 13 17 14 14 14 16 13 13 14  unit time 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 resource requirements 14 14 15 15 12 12 13 20 18 14 13 14 11 11 13 11 11  unit time 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 resource requirements 12 13 10 10 9 10 8 8 10 10 12 12 10 11 12 9 14  unit time 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 resource requirements 15 11 9 9 8 8 4 3 4 3 3 2 1 3 3 3As shown in Table1, for w=1, c1=c2=2.05, the number of particles 50, and G=100, the minimum variance 17.58 could be obtained by adjusting the acceleration coefficient a, which was significantly optimized compared with the variance quoted in [27] without the acceleration coefficient (that is 22.99). For w=1, c1=3.5, c2=0.4, the number of particles 50, and G=100, the minimum variance 18.4 could be obtained by adjusting the acceleration coefficient a, which was significantly optimized compared with the variance quoted in the literature [27]. For w=0.8, c1=c2=2.05, the number of particles 50, and G=100, the minimum variance 18.93 could be obtained by adjusting the acceleration coefficient a, which was significantly optimized compared with the variance quoted in [27]. For w=0.729, c1=c2=1.454, the number of particles 50, and G=100, variance smaller than 17.83 (acceleration coefficient 1) could not be obtained by adjusting the acceleration coefficient a.


## 3. Difference between APSO and PSOCF [29]

APSO proposed in this study was similar in form to PSOCF. The evolution equation of PSOCF was as follows [29]:(3)vijt+1=ηvijt+c1rand1tpgjt-xijt+c2rand2tpgt-xijtxijt+1=xijt+vijt+1,where contraction factor η=2κ/2-φ-φ(φ-4), κ∈[0,1], φ=c1+c2. The other signs are the same as earlier.Forc1=3.5, c2=0.4, η=2κ/2-φ-φ(φ-4)=2κ/2-3.9-3.9(3.9-4) does not exist. The PSOCF could not be used, but APSO in this study was used for optimization of network plan and the results were good, as shown in Table 1.Forc1=2.05, c2=2.05, η=2κ/2-φ-φ(φ-4)=2(0~1)/2-4.1-4.1(4.1-4) = 0~0.73. The acceleration factor a is outside the scope of the contraction factor η, and the optimization of APSO in this study was performed as usual, as shown in Table 1.Thus, although, in this study, APSO was similar in form to PSOCF, essentially, for network plan optimization, PSOCF did not have as good adaptability as APSO.


## 4. Irrationality of ACPSO Reported in [28]

APSO proposed in this study was inspired by the ACPSO algorithm quoted in [28]. APSO was similar in form to ACPSO. The evolution equation of ACPSO algorithm proposed in [28] was as follows:(4)vijt+1=sin⁡αβwvijt+c1rand1tpgjt-xijt+c2rand2tpgt-xijtxijt+1=sin⁡αβxijt+vijt+1,where α is angle value with a distinct optimization effect when its value is within [0,π/8]; β is a constant greater than zero, and the optimization effect is good when the value is 3. The other signs are the same as earlier.The ACPSO algorithm quoted in [28] was based on one inference: PSO is iterative. The iterative converges when the spectral radius of iterative matrix L (that is the maximum absolute value of the matrix eigenvalue) is less than 1. The smaller the spectral radius of L, the faster the iteration converges. The absolute value of the eigenvalues of L is as follows: λ1,2=1+w-c1+c2/2±((-1-w+c1+c2/2)2-4w)1/2/2, where (-1-w+c1+c2/2)2-4w≥0. The reasoning was problematic, and the analysis was as follows.The evolution equation of PSO can be written in the matrix form:(5)vt+1xt+1=Atvtxt+φ1φ2φ1φ2pi,tpg,t,where At=w-φw1-φ, φ=φ1+φ2=c1r1+c2r2, pi,t is the best place ever found, and pg,t is the best location for the whole particle swarm to date. The other signs are the same as earlier.Set,(6)yt=vtxt,ϕt=φ1pi,t+φ2pg,tφ1pi,t+φ2pg,t.Then, (5) can be changed to(7)yt+1=Atyt+ϕt.E is the mathematical expectation. (8)Eyt+1=Evt+1Ext+1,EAt=w-c1+c22w1-c1+c22,Eϕt=c1Epi,t+c2Epg,t2c1Epi,t+c2Epg,t2.SetQt+1=E(y(t+1)), M=E(At), Z=E(ϕt). The characteristic value of M is(9)λ1,2=1+w-c1+c2/2±-1-w+c1+c2/22-4w2.As long as1-c1+c2/2≠-w±2w, matrix A is going to be(10)AMA-1=L=λ100λ2.SetAQt+1=Ht. It could be deduced that the PSO algorithm was an iteration:(11)Ht+1=LHt+AZ,where L is an iterative matrix.The following two equations are equivalent to the inference in [30]:(12)Ax=bx=Bx+g,where A is the coefficient matrix, x is the unknown column vector, b is a constant number column vector, and g is a constant matrix determined by A and b.The following iterative matrixB could be obtained by the aforementioned system:(13)xk+1=Bxk+g.Setx∗ as the solution of the system. Then,(14)x∗=Bx∗+g.The aforementioned two formulas (13) and (14) on subtraction yield(15)xk+1-x∗=Bxk-x∗=BBxk-1-x∗=B2xk-1-x∗=⋯=Bk+1x0-x∗.Becausex0-x∗ has nothing to do with k, limk→∞⁡(xk+1-x∗)=0 is equivalent to limk→∞⁡Bk+1=0. The theorem quoted in [30] shows limk→∞⁡Bk+1=0 equivalent to ρ(B)<1, where ρ(B) is the spectral radius of matrix B.Thus, the iterative matrix did not necessarily converge. Because the particle swarm algorithm did not have a set of equations to solveQt+1, the aforementioned reasoning could not be executed using the iterative matrix L convergence.In Table1, for w=1, c1=c2=2.05 (or c1=3.5, c2=0.4), the number of particles 50, and G=100, the acceleration coefficient a=(sin(α))β=sin⁡π/103=0.03 reflects the fact that the optimization of ACPSO in [28] was poor. This was the experimental verification of the problems of ACPSO quoted in [28].


## 5. Conclusions

This study proposed the method for the large-scale network plan optimization of resource-leveling with a fixed duration through adjusting the coefficient of APSO based on the algorithm quoted in [27] to obtain a better solution than previously reported. In other words, for the same large-scale network plan, the proposed algorithm improved the leveling criterion by 24% compared with previous solutions. Thus, the resource variances of 17.58 and 223 of a large-scale network plan are the best results for the large-scale network plan optimization of resource-leveling with a fixed duration to date in the literature.Section3 discusses the difference between APSO proposed in this study and PSOCF quoted in [29]. The proposed APSO was similar in form to PSOCF, but, essentially, PSOCF did not have as good adaptability as APSO for the network plan optimization.Section4 describes the difference between APSO proposed in this study and ACPSO quoted in [28]. Through analyzing the iterative matrix convergence of equations, it was pointed out that the derivation of iterative matrix convergence of ACPSO algorithm proposed in [28] was problematic, although it experimentally proved APSO was similar in form to ACPSO.The effect of the APSO proposed in this study was verified to be obvious experimentally. However, the internal working mechanism of APSO is still a core issue worth investigation.



---

*Source: 9235346-2018-05-16.xml*