# Large-Scale Network Plan Optimization Using Improved Particle Swarm Optimization Algorithm

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

---

## Abstract

No relevant reports have been reported on the optimization of a large-scale network plan with more than 200 works due to the complexity of the problem and the huge amount of computation. In this paper, an improved particle swarm optimization algorithm via optimization of initial particle swarm (OIPSO) is first explained by the stochastic processes theory. Then two optimization examples are solved using this method which are the optimization of resource-leveling with fixed duration and the optimization of resources constraints with shortest project duration in a large network plan with 223 works. Through these two examples, under the same number of iterations, it is proven that the improved algorithm (OIPSO) can accelerate the optimization speed and improve the optimization effect of particle swarm optimization (PSO).


---

## Body

## 1. Introduction

A large-scale network plan that is composed of more than 50 works has become an essential tool for managing large-scale engineering project [1, 2]. However, due to the rapidity of solution increase (called the combustion explosion) and the exponential growth of computing time with the complexity of the problem, which far exceeds the processing capacity of computing resources, the optimization of large-scale network plan becomes an unsolvable problem in the mathematics and computer science fields, also called the NP problem [3–7]. Among the existing optimization methods for network plan, accurate algorithm such as the dynamic planning [8], 0-1 planning [9, 10], and branch and bound method [11, 12] can solve the small network plan optimization; various heuristic algorithms [13–18] cannot solve large-scale network plan optimization. An effective way to solve the complex network plan is by using genetic algorithm (GA), but the works numbers of presented examples (86 and 122) are not large enough [19–23].Proposed in 1995, PSO was applied to optimization, biomedicine, communication, control, plan, prediction, filter, and parameter estimation in rainfall-runoff modeling and so forth [24–30]. It was improved in selecting the parameter, the velocity equation of the particle, uncertainty stimulation, learning abilities, stability, convergence, and more [31–41]. Wang et al. and Chen et al. applied PSO to solve optimization of a nine-work network plan [42, 43]. The initial particle swarm was determined randomly by the improved and the initial PSO.The Monte Carlo method can be applied to solve equations, integral equations, difference equations, integral, shielding radioactive particles, neutron fission security problems, the random service (queuing theory) of economic service problems, signal detection and system simulation, flow field simulation, life test, and more [44]. As it optimizes initial particle swarm to solve the optimization problem of large-scale network plans, it is PSO’s foundation. Zhang and Shi [45] adopted the Monte Carlo method to solve the optimization of the resource-leveling with fixed duration and the resources constraints with shortest project duration of a network plan. But the works number of the presented examples (9) is not large enough. To solve the optimization problem of the resource-leveling with fixed duration in a large network plan, Du et al. [46] proposed partition optimization based on the Monte Carlo method. However, there is not a large enough works number (61), and partition optimization combination may lose the global optimal solution in theory.Without requiring any advanced knowledge of the reliability function, PSO combining with the Monte Carlo method was used to solve complex network reliability problems, while Monte Carlo method was used to evaluate system reliability, but its motivation is different from this paper [47]. In comparison to the random method, the Monte Carlo method in the Monte Carlo Enhanced PSO can calculate the probability of initial particles’ elements and form better initial particles, but there was no analyzation of the improvement mechanism to optimize the initial particle swarm [48]. To solve resource optimization and cost optimization of a large-scale network plan by using PSO, Zhang and Yang used the Monte Carlo method under limited conditions to optimize the initial particle swarm [49, 50]. However, there was no analyzation of the mechanism improvement to optimize the initial particle swarm, and the works number of presented examples (61) is not large enough.In this paper, an improved particle swarm optimization algorithm via optimization of initial particle swarm (OIPSO) is first explained by the stochastic processes theory. Then two optimization examples of a large-scale network plan are solved using this method, which are the optimization of resource-leveling with fixed duration and the optimization of resources constraints with shortest project duration in a large network plan with 223 works. The optimization effect of the improved algorithm (OIPSO) is proven through these two examples.This paper is organized as follows: Section2 analyzes the improvement mechanism of OIPSO, Section 3 solves large-scale (223 works) network plans by OIPSO, Section 4 introduces the superiority of OIPSO compared with the original and existing PSOs, and Section 5 makes conclusions.


## 2. Methodology

### 2.1. OIPSO

The process of the original PSO is as follows [30]:Step 1.
Determining the initial particle swarmStep 2.
Evolving the particle locationStep 3.
Determining each particle’s best experiencing position and all particles doingStep 4.
Outputting the optimization results when the maximal number of iterations is reached; otherwise return to Step2The improved algorithm (OIPSO) in this paper is the same as PSO, except that Step1 determines the initial particle swarm via optimization of initial particle swarm.In the optimization of resource-leveling with fixed duration and the optimization of resources constraints with shortest project duration of a network plan, the following expression determines the initial particle swarm:(1)
C
j
=
d
1
j
+
rand
⁡
%
F
j
+
1
,where C
[
j
] is related to its start time of work j, d
1
[
j
] is the normal duration of the work j, rand
⁡
% is the random function, and F
[
j
] is the total float of the work j. The limiting conditions are resource variance in the optimization of resource-leveling with fixed duration, as well as resources and project duration in the optimization of resources constraints with shortest project duration. In the Monte Carlo method, using the random function r
a
n
g
% is the basic principle.


### 2.2. The Improvement Mechanism of OIPSO

Markov chains are constituted by the PSO M particles [51]. And then by randomly selecting initial particles and setting them out to a certain point, the stochastic optimization series of particles constitute the Markov chains. The probability for a particle to set out from i is π
i, and the probability π
j
(
n
) for a particle to transfer to j after an n time transfer can be determined by the following formula (j represents the optimal position of a limited number of iterations conditions, it can also be the optimization solution, j
∈
I, and I is the state space):(2)
π
j
n
=
P
X
n
=
j
,
π
n
=
π
1
n
,
π
2
n
,
…
,
π
n
=
π
0
P
n
,where X
n represents the arrival state of a particle subsequent to n time transfer; π
(
n
) is called the probability distribution of X
n; π
(
0
)
=
[
π
1
,
π
2
,
…
] and is the initial distribution which is 1
×
(
n
+
1
) matrix of the Markov chains, namely, the probability of the Markov chains starting from i, π
i
=
P
(
X
0
=
i
), i
∈
I (state space), and X
0 is the state for a particle to set out from; P
n is equal to the product of n one-time transfer matrix P (n
+
1 order phalanx), and P is also called matrix of transition probability, expressed as(3)
P
=
p
i
j
,
p
i
j
=
P
X
1
=
j
∣
X
0
=
i
,
i
,
j
∈
I
,where p
i
j is the probability for a particle to transfer to j in the next time setting out from i [52].Optimized and unoptimized initial particles comprise the two columns of Markov chains. The probability of particles starting from the location of the initial particle is equal to 100%, while that of particles starting from the locations of other particles is equal to 0. The excellent particle position close to the optimal solution is increased in the n particle positions, which is the position of the excellent initial particle, regardless of the subsequent excellent particle positions that were generated based on the initial particle. There is a higher probability of the excellent particle flying from the position near the optimal solution than it flying away from the optimal solution. Therefore, as shown in (4),   j column of one-time transfer matrix P of Markov chains to optimize initial particle is bigger.(4)
0
1
2
3
⋯
j
b
i
g
g
e
r
⋯
n
1
2
3
⋮
i
⋮
n
.As a result, j column of P
n and π
(
0
)
P
n of Markov chains to optimize initial particle is bigger.


## 2.1. OIPSO

The process of the original PSO is as follows [30]:Step 1.
Determining the initial particle swarmStep 2.
Evolving the particle locationStep 3.
Determining each particle’s best experiencing position and all particles doingStep 4.
Outputting the optimization results when the maximal number of iterations is reached; otherwise return to Step2The improved algorithm (OIPSO) in this paper is the same as PSO, except that Step1 determines the initial particle swarm via optimization of initial particle swarm.In the optimization of resource-leveling with fixed duration and the optimization of resources constraints with shortest project duration of a network plan, the following expression determines the initial particle swarm:(1)
C
j
=
d
1
j
+
rand
⁡
%
F
j
+
1
,where C
[
j
] is related to its start time of work j, d
1
[
j
] is the normal duration of the work j, rand
⁡
% is the random function, and F
[
j
] is the total float of the work j. The limiting conditions are resource variance in the optimization of resource-leveling with fixed duration, as well as resources and project duration in the optimization of resources constraints with shortest project duration. In the Monte Carlo method, using the random function r
a
n
g
% is the basic principle.


## 2.2. The Improvement Mechanism of OIPSO

Markov chains are constituted by the PSO M particles [51]. And then by randomly selecting initial particles and setting them out to a certain point, the stochastic optimization series of particles constitute the Markov chains. The probability for a particle to set out from i is π
i, and the probability π
j
(
n
) for a particle to transfer to j after an n time transfer can be determined by the following formula (j represents the optimal position of a limited number of iterations conditions, it can also be the optimization solution, j
∈
I, and I is the state space):(2)
π
j
n
=
P
X
n
=
j
,
π
n
=
π
1
n
,
π
2
n
,
…
,
π
n
=
π
0
P
n
,where X
n represents the arrival state of a particle subsequent to n time transfer; π
(
n
) is called the probability distribution of X
n; π
(
0
)
=
[
π
1
,
π
2
,
…
] and is the initial distribution which is 1
×
(
n
+
1
) matrix of the Markov chains, namely, the probability of the Markov chains starting from i, π
i
=
P
(
X
0
=
i
), i
∈
I (state space), and X
0 is the state for a particle to set out from; P
n is equal to the product of n one-time transfer matrix P (n
+
1 order phalanx), and P is also called matrix of transition probability, expressed as(3)
P
=
p
i
j
,
p
i
j
=
P
X
1
=
j
∣
X
0
=
i
,
i
,
j
∈
I
,where p
i
j is the probability for a particle to transfer to j in the next time setting out from i [52].Optimized and unoptimized initial particles comprise the two columns of Markov chains. The probability of particles starting from the location of the initial particle is equal to 100%, while that of particles starting from the locations of other particles is equal to 0. The excellent particle position close to the optimal solution is increased in the n particle positions, which is the position of the excellent initial particle, regardless of the subsequent excellent particle positions that were generated based on the initial particle. There is a higher probability of the excellent particle flying from the position near the optimal solution than it flying away from the optimal solution. Therefore, as shown in (4),   j column of one-time transfer matrix P of Markov chains to optimize initial particle is bigger.(4)
0
1
2
3
⋯
j
b
i
g
g
e
r
⋯
n
1
2
3
⋮
i
⋮
n
.As a result, j column of P
n and π
(
0
)
P
n of Markov chains to optimize initial particle is bigger.


## 3. Solving Large-Scale Network Plans with 223 Works by OIPSO

As shown in Figure1, a large-scale network plan has a works number of 223 and a calculated project duration of 135. Table 1 shows each work’s resources amount, duration, and earliest start time, corresponding to the resource variance of 37.51. The biggest quantity of resources at one period is 27. The optimization of resource-leveling with fixed duration can be unchanged project duration and resource demand equilibrium of each period. The resources supply capacity limit can be met by the optimization of resources constraints with shortest project duration, and it can have minimal extended project duration.Table 1
The parameters and their optimization solution for the optimization example of the resource-leveling with fixed duration.
Number
Work
Duration
Resources 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
4
6
5–8
4
1
7
7
7
5–9
5
1
7
7
8
6–8
5
3
13
13
9
7-8
8
3
15
15
10
3–6
3
2
2
2
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
7
15
2–6
1
3
1
1
16
6-7
2
0
13
13
17
8-9
7
3
23
23
18
8–11
2
2
23
23
19
8–10
2
1
23
23
20
7–10
2
1
15
15
21
9-10
1
2
30
30
22
9–12
4
1
30
30
23
18-19
8
3
57
58
24
17–20
2
1
51
51
25
16–19
4
1
49
49
26
18–21
5
1
57
71
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
42
31
14–17
1
2
42
42
32
13–15
2
1
44
44
33
10-11
4
1
31
31
34
12-13
5
1
39
39
35
10–13
5
3
31
31
36
10–12
8
3
31
31
37
17-18
6
0
51
51
38
15-16
3
2
46
46
39
11–15
5
1
35
35
40
14-15
3
2
42
42
41
11–17
5
1
35
35
42
12–14
3
2
39
39
43
11–13
6
2
35
35
44
12–15
2
0
39
39
45
21-22
2
2
70
86
46
22–24
2
1
75
88
47
20–22
2
1
73
74
48
20–24
1
2
73
74
49
20–26
2
1
73
74
50
19–21
5
1
65
81
51
19–22
5
3
65
66
52
19-20
8
3
65
66
53
24-25
3
2
77
96
54
24–26
5
1
77
96
55
26-27
3
2
85
104
56
25-26
5
1
80
99
57
23–27
3
2
72
88
58
23–26
6
2
72
88
59
23-24
1
3
72
88
60
21–23
2
0
70
86
61
21–24
7
3
70
89
62
3–28
1
2
2
2
63
3–30
3
2
2
2
64
3–31
1
3
2
2
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
7
71
5–31
6
2
7
7
72
5–34
5
3
7
7
73
31-32
2
0
13
13
74
31–34
4
1
13
13
75
32-33
2
1
15
15
76
32–34
8
3
15
15
77
9–34
7
3
30
30
78
9–33
2
1
30
30
79
34-35
2
2
44
44
80
33-34
1
2
43
43
81
33–35
8
3
43
43
82
33–36
5
3
43
43
83
12–33
4
1
39
39
84
12–36
6
2
39
39
85
12–37
5
1
39
39
86
35-36
5
1
51
51
87
35–37
2
0
51
51
88
35–39
5
1
51
51
89
36-37
2
1
56
56
90
14–37
3
2
42
42
91
14–39
2
1
42
42
92
37-38
3
2
58
58
93
37–39
1
2
58
58
94
38-39
2
2
61
76
95
18–39
6
0
57
57
96
18–40
5
3
57
57
97
39-40
8
3
63
76
98
39–41
2
1
63
63
99
40-41
5
1
78
98
100
40–42
5
3
78
98
101
21–40
8
3
70
90
102
21–42
2
1
70
86
103
21–43
1
2
70
86
104
41-42
2
2
83
103
105
41–43
7
3
83
103
106
41–45
2
1
83
103
107
42-43
2
1
85
105
108
23–43
1
3
72
88
109
23–45
5
1
72
88
110
43-44
3
2
90
110
111
43–45
6
2
90
110
112
44-45
5
1
93
113
113
27–45
3
2
88
107
114
38–40
4
1
61
61
115
47-48
2
2
8
8
116
48–50
2
1
10
10
117
47–50
2
1
8
8
118
48-49
1
2
10
10
119
50–53
4
1
14
14
120
52–57
4
1
49
49
121
52–58
5
1
49
49
122
53–57
5
3
55
55
123
56-57
8
3
57
57
124
47–53
3
2
8
8
125
49-50
3
2
11
11
126
47–52
5
1
8
8
127
49–57
3
2
11
11
128
52-53
6
2
49
49
129
49–53
1
3
11
11
130
53–56
2
0
55
55
131
57-58
7
3
65
65
132
57–61
2
2
65
65
133
57–59
2
1
65
65
134
56–59
2
1
57
57
135
58-59
1
2
72
72
136
58–60
4
1
72
72
137
71-72
8
3
99
99
138
69–75
2
1
93
93
139
68–72
4
1
91
91
140
71–73
5
1
99
99
141
69–72
5
3
93
93
142
68-69
2
2
91
91
143
67–69
2
1
88
88
144
65–71
2
1
84
84
145
65–69
1
2
84
84
146
64–67
2
1
86
86
147
59–61
4
1
73
73
148
60–64
5
1
81
81
149
59–64
5
3
73
73
150
59-60
8
3
73
73
151
69–71
6
0
93
93
152
67-68
3
2
88
88
153
61–67
5
1
77
77
154
65–67
3
2
84
84
155
61–69
5
1
77
77
156
60–65
3
2
81
81
157
61–64
6
2
77
77
158
60–67
2
0
81
81
159
73–76
2
2
112
112
160
76–79
2
1
117
117
161
75-76
2
1
115
115
162
75–79
1
2
115
115
163
75–83
2
1
115
115
164
72-73
5
1
107
107
165
72–76
5
3
107
107
166
72–75
8
3
107
107
167
79–82
3
2
119
124
168
79–83
5
1
119
124
169
83-84
3
2
127
132
170
82-83
5
1
122
127
171
78–84
3
2
114
123
172
78–83
6
2
114
123
173
78-79
1
3
114
123
174
73–78
2
0
112
112
175
73–79
7
3
112
112
176
46-47
1
2
7
7
177
47–51
3
2
8
8
178
47–54
1
3
8
8
179
46–51
2
1
7
7
180
29–46
2
2
5
5
181
29–51
2
1
5
5
182
29–54
3
2
5
5
183
51–54
4
1
11
11
184
52–54
6
2
49
49
185
34–52
5
3
44
44
186
54-55
2
0
55
55
187
34–54
4
1
44
44
188
55–62
2
1
57
57
189
34–55
8
3
44
44
190
34–58
7
3
44
44
191
58–62
2
1
72
72
192
34–62
1
2
44
44
193
35–62
8
3
51
51
194
62-63
5
3
85
85
195
60–62
4
1
81
81
196
60–63
6
2
81
81
197
60–66
2
1
81
81
198
35–63
5
1
51
51
199
35–66
2
0
51
51
200
63–66
2
1
90
90
201
65-66
3
2
84
84
202
39–65
2
1
63
63
203
66–70
3
2
92
92
204
39–66
1
2
63
63
205
39–70
2
2
63
63
206
39–71
6
0
63
63
207
71–74
5
3
99
99
208
39–74
8
3
63
63
209
41–74
5
1
83
103
210
74–77
5
3
120
120
211
73-74
8
3
112
112
212
73–77
2
1
112
112
213
73–80
1
2
112
112
214
41–77
2
2
83
103
215
41–80
7
3
83
103
216
77–80
2
1
125
125
217
78–80
1
3
114
123
218
45–78
5
1
98
118
219
80-81
3
2
127
127
220
45–80
6
2
98
118
221
81–84
5
1
130
130
222
45–84
3
2
98
118
223
70–74
4
1
95
95
“ES” is the early start time of each work. “Optimized ES” is the optimized start time.Figure 1
A large-scale network plan (223 works).


### 3.1. Solving the Optimization of Resource-Leveling with Fixed Duration

The variance method can be applied to evaluate the resource leveling, and the calculation formula of the variance is(5)
σ
2
=
∑
i
=
1
J
x
i
-
μ
2
J
,where the total number of the samples x
i is J; the arithmetic average of x
i is μ.The evolution equation is [49](6)
x
i
j
t
+
1
=
x
i
j
t
+
f
l
o
o
r
(
w
v
i
j
t
+
c
1
rand
1
⁡
t
p
g
j
t
-
x
i
j
t
+
c
2
rand
2
⁡
t
p
g
t
-
x
i
j
t
,where t is the number of iterations, x
i
j
(
t
+
1
) is the j-dimensional space coordinates of the particle i at (
t
+
1
) times of iterations, x
i
j
(
t
) is the j-dimensional space coordinates of the particle i at t times of iterations, w is inertia weight (its general value is 1), v
i
j
(
t
) is the j-dimensional flight velocity of particle i, c
1 and c
2 are the acceleration constant with a general value of 0–2, r
a
n
d
1 and r
a
n
d
2 are the random function with the value in the range of (0, 1), p
g
j
(
t
) is the best position of particle j experienced, p
g
(
t
) is the best position of all particles, and f
l
o
o
r
(
) is the integral function.Table1 also shows the start time of each work for resource-leveling optimization with fixed duration solution, corresponding to the resource variance of 22.41. The parameters applied in the OIPSO are the following: the inertia weight w
=
1 (empirical value), the acceleration constant c
1
=
3.5 (empirical value), c
2
=
4.0 (empirical value), the particle number M
=
50 (experimental value), the initial particle variance <30 (experimental value), and the number of iterations G
=
100 (experimental value). It is obvious that the optimized resource variance (22.41) is much less than the original one (37.51).


### 3.2. Solving the Optimization of Resources Constraints with Shortest Project Duration

As shown above, the methods of the optimization of resources constraints with shortest project duration in a large-scale network plan and the optimization of resource-leveling with fixed duration are similar. Besides, the initial particle swarm constraint is applied with resources constraints and as small as possible duration. The optimal solutions criteria are different; the constraint range of the feasible solutionC
[
i
]
[
j
]
+
V
[
i
]
[
j
] is also different, where the spatial coordinates of particles C
[
i
]
[
j
]
+
V
[
i
]
[
j
] are the N-dimension variables related to the work start time; their initial values are the coordinates of the initial particle swarm c
[
i
]
[
j
]; V
[
i
]
[
j
] is the flight speed of particles.The example is as shown in Figure1, and Table 2 lists the start time of each work for resources constraints with shortest project duration optimization, where 25 is the resource constraint, 199 is the project duration, and 22 is the biggest resources quantity. The applied parameters of the resources constraints with shortest construction period optimization of the OIPSO are the following: the inertia weight w
=
1 (empirical value), the acceleration constant c
1
=
3.5 (empirical value), c
2
=
0.4 (empirical value), the quantity of particle M
=
10 (experimental value), the number of iterations G
=
1000 (experimental value), the resource constraint of the initial particle swarm is 25 (experimental value), and the constrained duration is 300 (experimental value). The range of C
[
i
]
[
j
]
+
V
[
i
]
[
j
] is d
1
[
j
] and 2
∗
d
1
[
j
] (the meaning of C
[
i
]
[
j
], V
[
i
]
[
j
], and d
1
[
j
] is the same as the previous). The resource constraint (25) is met, and the corresponding project duration (199) is not too long after optimization.Table 2
The parameters and their optimal solution of resources constraints with shortest project duration.
Number
Work
Duration
Resources quantity
ES
Optimized ES
1
1–3
2
2
0
1
2
1–4
2
1
0
7
3
3-4
2
1
2
4
4
1-2
1
2
0
0
5
4–6
4
1
4
10
6
5–8
4
1
7
9
7
5–9
5
1
7
15
8
6–8
5
3
13
18
9
7-8
8
3
15
20
10
3–6
3
2
2
5
11
2–4
3
2
1
2
12
3–5
5
1
2
3
13
2–8
3
2
1
2
14
5-6
6
2
7
9
15
2–6
1
3
1
1
16
6-7
2
0
13
16
17
8-9
7
3
23
33
18
8–11
2
2
23
28
19
8–10
2
1
23
28
20
7–10
2
1
15
19
21
9-10
1
2
30
40
22
9–12
4
1
30
43
23
18-19
8
3
57
84
24
17–20
2
1
51
82
25
16–19
4
1
49
81
26
18–21
5
1
57
97
27
17–19
5
3
51
77
28
16-17
2
2
49
72
29
15–17
2
1
46
69
30
14–18
2
1
42
76
31
14–17
1
2
42
61
32
13–15
2
1
44
64
33
10-11
4
1
31
44
34
12-13
5
1
39
58
35
10–13
5
3
31
41
36
10–12
8
3
31
45
37
17-18
6
0
51
74
38
15-16
3
2
46
68
39
11–15
5
1
35
49
40
14-15
3
2
42
63
41
11–17
5
1
35
51
42
12–14
3
2
39
58
43
11–13
6
2
35
48
44
12–15
2
0
39
53
45
21-22
2
2
70
104
46
22–24
2
1
75
126
47
20–22
2
1
73
107
48
20–24
1
2
73
112
49
20–26
2
1
73
122
50
19–21
5
1
65
96
51
19–22
5
3
65
95
52
19-20
8
3
65
99
53
24-25
3
2
77
129
54
24–26
5
1
77
131
55
26-27
3
2
85
148
56
25-26
5
1
80
142
57
23–27
3
2
72
108
58
23–26
6
2
72
109
59
23-24
1
3
72
112
60
21–23
2
0
70
102
61
21–24
7
3
70
107
62
3–28
1
2
2
3
63
3–30
3
2
2
10
64
3–31
1
3
2
29
65
28–30
2
1
3
30
66
28-29
2
2
3
5
67
29-30
2
1
5
7
68
29–31
3
2
5
8
69
29–34
3
2
5
9
70
30-31
4
1
7
35
71
5–31
6
2
7
12
72
5–34
5
3
7
43
73
31-32
2
0
13
42
74
31–34
4
1
13
44
75
32-33
2
1
15
61
76
32–34
8
3
15
49
77
9–34
7
3
30
46
78
9–33
2
1
30
41
79
34-35
2
2
44
76
80
33-34
1
2
43
63
81
33–35
8
3
43
67
82
33–36
5
3
43
79
83
12–33
4
1
39
53
84
12–36
6
2
39
57
85
12–37
5
1
39
57
86
35-36
5
1
51
81
87
35–37
2
0
51
79
88
35–39
5
1
51
88
89
36-37
2
1
56
87
90
14–37
3
2
42
63
91
14–39
2
1
42
62
92
37-38
3
2
58
91
93
37–39
1
2
58
94
94
38-39
2
2
61
94
95
18–39
6
0
57
82
96
18–40
5
3
57
83
97
39-40
8
3
63
97
98
39–41
2
1
63
97
99
40-41
5
1
78
118
100
40–42
5
3
78
116
101
21–40
8
3
70
107
102
21–42
2
1
70
121
103
21–43
1
2
70
120
104
41-42
2
2
83
123
105
41–43
7
3
83
127
106
41–45
2
1
83
130
107
42-43
2
1
85
126
108
23–43
1
3
72
129
109
23–45
5
1
72
108
110
43-44
3
2
90
134
111
43–45
6
2
90
139
112
44-45
5
1
93
141
113
27–45
3
2
88
151
114
38–40
4
1
61
96
115
47-48
2
2
8
31
116
48–50
2
1
10
48
117
47–50
2
1
8
32
118
48-49
1
2
10
43
119
50–53
4
1
14
70
120
52–57
4
1
49
74
121
52–58
5
1
49
73
122
53–57
5
3
55
87
123
56-57
8
3
57
86
124
47–53
3
2
8
32
125
49-50
3
2
11
67
126
47–52
5
1
8
33
127
49–57
3
2
11
49
128
52-53
6
2
49
69
129
49–53
1
3
11
82
130
53–56
2
0
55
84
131
57-58
7
3
65
94
132
57–61
2
2
65
103
133
57–59
2
1
65
95
134
56–59
2
1
57
100
135
58-59
1
2
72
101
136
58–60
4
1
72
104
137
71-72
8
3
99
138
138
69–75
2
1
93
130
139
68–72
4
1
91
127
140
71–73
5
1
99
138
141
69–72
5
3
93
131
142
68-69
2
2
91
126
143
67–69
2
1
88
123
144
65–71
2
1
84
118
145
65–69
1
2
84
128
146
64–67
2
1
86
119
147
59–61
4
1
73
104
148
60–64
5
1
81
113
149
59–64
5
3
73
106
150
59-60
8
3
73
105
151
69–71
6
0
93
129
152
67-68
3
2
88
122
153
61–67
5
1
77
111
154
65–67
3
2
84
119
155
61–69
5
1
77
112
156
60–65
3
2
81
114
157
61–64
6
2
77
112
158
60–67
2
0
81
114
159
73–76
2
2
112
152
160
76–79
2
1
117
162
161
75-76
2
1
115
159
162
75–79
1
2
115
168
163
75–83
2
1
115
160
164
72-73
5
1
107
146
165
72–76
5
3
107
150
166
72–75
8
3
107
151
167
79–82
3
2
119
171
168
79–83
5
1
119
174
169
83-84
3
2
127
181
170
82-83
5
1
122
175
171
78–84
3
2
114
163
172
78–83
6
2
114
162
173
78-79
1
3
114
161
174
73–78
2
0
112
151
175
73–79
7
3
112
155
176
46-47
1
2
7
30
177
47–51
3
2
8
33
178
47–54
1
3
8
101
179
46–51
2
1
7
37
180
29–46
2
2
5
25
181
29–51
2
1
5
9
182
29–54
3
2
5
98
183
51–54
4
1
11
130
184
52–54
6
2
49
69
185
34–52
5
3
44
64
186
54-55
2
0
55
134
187
34–54
4
1
44
110
188
55–62
2
1
57
138
189
34–55
8
3
44
71
190
34–58
7
3
44
70
191
58–62
2
1
72
132
192
34–62
1
2
44
123
193
35–62
8
3
51
83
194
62-63
5
3
85
142
195
60–62
4
1
81
115
196
60–63
6
2
81
118
197
60–66
2
1
81
118
198
35–63
5
1
51
81
199
35–66
2
0
51
83
200
63–66
2
1
90
148
201
65-66
3
2
84
130
202
39–65
2
1
63
98
203
66–70
3
2
92
152
204
39–66
1
2
63
100
205
39–70
2
2
63
129
206
39–71
6
0
63
101
207
71–74
5
3
99
148
208
39–74
8
3
63
105
209
41–74
5
1
83
140
210
74–77
5
3
120
164
211
73-74
8
3
112
155
212
73–77
2
1
112
154
213
73–80
1
2
112
168
214
41–77
2
2
83
123
215
41–80
7
3
83
123
216
77–80
2
1
125
170
217
78–80
1
3
114
161
218
45–78
5
1
98
156
219
80-81
3
2
127
174
220
45–80
6
2
98
159
221
81–84
5
1
130
177
222
45–84
3
2
98
155
223
70–74
4
1
95
158
“ES” is the early start time of each work. “Optimized ES” is the optimized start time.


## 3.1. Solving the Optimization of Resource-Leveling with Fixed Duration

The variance method can be applied to evaluate the resource leveling, and the calculation formula of the variance is(5)
σ
2
=
∑
i
=
1
J
x
i
-
μ
2
J
,where the total number of the samples x
i is J; the arithmetic average of x
i is μ.The evolution equation is [49](6)
x
i
j
t
+
1
=
x
i
j
t
+
f
l
o
o
r
(
w
v
i
j
t
+
c
1
rand
1
⁡
t
p
g
j
t
-
x
i
j
t
+
c
2
rand
2
⁡
t
p
g
t
-
x
i
j
t
,where t is the number of iterations, x
i
j
(
t
+
1
) is the j-dimensional space coordinates of the particle i at (
t
+
1
) times of iterations, x
i
j
(
t
) is the j-dimensional space coordinates of the particle i at t times of iterations, w is inertia weight (its general value is 1), v
i
j
(
t
) is the j-dimensional flight velocity of particle i, c
1 and c
2 are the acceleration constant with a general value of 0–2, r
a
n
d
1 and r
a
n
d
2 are the random function with the value in the range of (0, 1), p
g
j
(
t
) is the best position of particle j experienced, p
g
(
t
) is the best position of all particles, and f
l
o
o
r
(
) is the integral function.Table1 also shows the start time of each work for resource-leveling optimization with fixed duration solution, corresponding to the resource variance of 22.41. The parameters applied in the OIPSO are the following: the inertia weight w
=
1 (empirical value), the acceleration constant c
1
=
3.5 (empirical value), c
2
=
4.0 (empirical value), the particle number M
=
50 (experimental value), the initial particle variance <30 (experimental value), and the number of iterations G
=
100 (experimental value). It is obvious that the optimized resource variance (22.41) is much less than the original one (37.51).


## 3.2. Solving the Optimization of Resources Constraints with Shortest Project Duration

As shown above, the methods of the optimization of resources constraints with shortest project duration in a large-scale network plan and the optimization of resource-leveling with fixed duration are similar. Besides, the initial particle swarm constraint is applied with resources constraints and as small as possible duration. The optimal solutions criteria are different; the constraint range of the feasible solutionC
[
i
]
[
j
]
+
V
[
i
]
[
j
] is also different, where the spatial coordinates of particles C
[
i
]
[
j
]
+
V
[
i
]
[
j
] are the N-dimension variables related to the work start time; their initial values are the coordinates of the initial particle swarm c
[
i
]
[
j
]; V
[
i
]
[
j
] is the flight speed of particles.The example is as shown in Figure1, and Table 2 lists the start time of each work for resources constraints with shortest project duration optimization, where 25 is the resource constraint, 199 is the project duration, and 22 is the biggest resources quantity. The applied parameters of the resources constraints with shortest construction period optimization of the OIPSO are the following: the inertia weight w
=
1 (empirical value), the acceleration constant c
1
=
3.5 (empirical value), c
2
=
0.4 (empirical value), the quantity of particle M
=
10 (experimental value), the number of iterations G
=
1000 (experimental value), the resource constraint of the initial particle swarm is 25 (experimental value), and the constrained duration is 300 (experimental value). The range of C
[
i
]
[
j
]
+
V
[
i
]
[
j
] is d
1
[
j
] and 2
∗
d
1
[
j
] (the meaning of C
[
i
]
[
j
], V
[
i
]
[
j
], and d
1
[
j
] is the same as the previous). The resource constraint (25) is met, and the corresponding project duration (199) is not too long after optimization.Table 2
The parameters and their optimal solution of resources constraints with shortest project duration.
Number
Work
Duration
Resources quantity
ES
Optimized ES
1
1–3
2
2
0
1
2
1–4
2
1
0
7
3
3-4
2
1
2
4
4
1-2
1
2
0
0
5
4–6
4
1
4
10
6
5–8
4
1
7
9
7
5–9
5
1
7
15
8
6–8
5
3
13
18
9
7-8
8
3
15
20
10
3–6
3
2
2
5
11
2–4
3
2
1
2
12
3–5
5
1
2
3
13
2–8
3
2
1
2
14
5-6
6
2
7
9
15
2–6
1
3
1
1
16
6-7
2
0
13
16
17
8-9
7
3
23
33
18
8–11
2
2
23
28
19
8–10
2
1
23
28
20
7–10
2
1
15
19
21
9-10
1
2
30
40
22
9–12
4
1
30
43
23
18-19
8
3
57
84
24
17–20
2
1
51
82
25
16–19
4
1
49
81
26
18–21
5
1
57
97
27
17–19
5
3
51
77
28
16-17
2
2
49
72
29
15–17
2
1
46
69
30
14–18
2
1
42
76
31
14–17
1
2
42
61
32
13–15
2
1
44
64
33
10-11
4
1
31
44
34
12-13
5
1
39
58
35
10–13
5
3
31
41
36
10–12
8
3
31
45
37
17-18
6
0
51
74
38
15-16
3
2
46
68
39
11–15
5
1
35
49
40
14-15
3
2
42
63
41
11–17
5
1
35
51
42
12–14
3
2
39
58
43
11–13
6
2
35
48
44
12–15
2
0
39
53
45
21-22
2
2
70
104
46
22–24
2
1
75
126
47
20–22
2
1
73
107
48
20–24
1
2
73
112
49
20–26
2
1
73
122
50
19–21
5
1
65
96
51
19–22
5
3
65
95
52
19-20
8
3
65
99
53
24-25
3
2
77
129
54
24–26
5
1
77
131
55
26-27
3
2
85
148
56
25-26
5
1
80
142
57
23–27
3
2
72
108
58
23–26
6
2
72
109
59
23-24
1
3
72
112
60
21–23
2
0
70
102
61
21–24
7
3
70
107
62
3–28
1
2
2
3
63
3–30
3
2
2
10
64
3–31
1
3
2
29
65
28–30
2
1
3
30
66
28-29
2
2
3
5
67
29-30
2
1
5
7
68
29–31
3
2
5
8
69
29–34
3
2
5
9
70
30-31
4
1
7
35
71
5–31
6
2
7
12
72
5–34
5
3
7
43
73
31-32
2
0
13
42
74
31–34
4
1
13
44
75
32-33
2
1
15
61
76
32–34
8
3
15
49
77
9–34
7
3
30
46
78
9–33
2
1
30
41
79
34-35
2
2
44
76
80
33-34
1
2
43
63
81
33–35
8
3
43
67
82
33–36
5
3
43
79
83
12–33
4
1
39
53
84
12–36
6
2
39
57
85
12–37
5
1
39
57
86
35-36
5
1
51
81
87
35–37
2
0
51
79
88
35–39
5
1
51
88
89
36-37
2
1
56
87
90
14–37
3
2
42
63
91
14–39
2
1
42
62
92
37-38
3
2
58
91
93
37–39
1
2
58
94
94
38-39
2
2
61
94
95
18–39
6
0
57
82
96
18–40
5
3
57
83
97
39-40
8
3
63
97
98
39–41
2
1
63
97
99
40-41
5
1
78
118
100
40–42
5
3
78
116
101
21–40
8
3
70
107
102
21–42
2
1
70
121
103
21–43
1
2
70
120
104
41-42
2
2
83
123
105
41–43
7
3
83
127
106
41–45
2
1
83
130
107
42-43
2
1
85
126
108
23–43
1
3
72
129
109
23–45
5
1
72
108
110
43-44
3
2
90
134
111
43–45
6
2
90
139
112
44-45
5
1
93
141
113
27–45
3
2
88
151
114
38–40
4
1
61
96
115
47-48
2
2
8
31
116
48–50
2
1
10
48
117
47–50
2
1
8
32
118
48-49
1
2
10
43
119
50–53
4
1
14
70
120
52–57
4
1
49
74
121
52–58
5
1
49
73
122
53–57
5
3
55
87
123
56-57
8
3
57
86
124
47–53
3
2
8
32
125
49-50
3
2
11
67
126
47–52
5
1
8
33
127
49–57
3
2
11
49
128
52-53
6
2
49
69
129
49–53
1
3
11
82
130
53–56
2
0
55
84
131
57-58
7
3
65
94
132
57–61
2
2
65
103
133
57–59
2
1
65
95
134
56–59
2
1
57
100
135
58-59
1
2
72
101
136
58–60
4
1
72
104
137
71-72
8
3
99
138
138
69–75
2
1
93
130
139
68–72
4
1
91
127
140
71–73
5
1
99
138
141
69–72
5
3
93
131
142
68-69
2
2
91
126
143
67–69
2
1
88
123
144
65–71
2
1
84
118
145
65–69
1
2
84
128
146
64–67
2
1
86
119
147
59–61
4
1
73
104
148
60–64
5
1
81
113
149
59–64
5
3
73
106
150
59-60
8
3
73
105
151
69–71
6
0
93
129
152
67-68
3
2
88
122
153
61–67
5
1
77
111
154
65–67
3
2
84
119
155
61–69
5
1
77
112
156
60–65
3
2
81
114
157
61–64
6
2
77
112
158
60–67
2
0
81
114
159
73–76
2
2
112
152
160
76–79
2
1
117
162
161
75-76
2
1
115
159
162
75–79
1
2
115
168
163
75–83
2
1
115
160
164
72-73
5
1
107
146
165
72–76
5
3
107
150
166
72–75
8
3
107
151
167
79–82
3
2
119
171
168
79–83
5
1
119
174
169
83-84
3
2
127
181
170
82-83
5
1
122
175
171
78–84
3
2
114
163
172
78–83
6
2
114
162
173
78-79
1
3
114
161
174
73–78
2
0
112
151
175
73–79
7
3
112
155
176
46-47
1
2
7
30
177
47–51
3
2
8
33
178
47–54
1
3
8
101
179
46–51
2
1
7
37
180
29–46
2
2
5
25
181
29–51
2
1
5
9
182
29–54
3
2
5
98
183
51–54
4
1
11
130
184
52–54
6
2
49
69
185
34–52
5
3
44
64
186
54-55
2
0
55
134
187
34–54
4
1
44
110
188
55–62
2
1
57
138
189
34–55
8
3
44
71
190
34–58
7
3
44
70
191
58–62
2
1
72
132
192
34–62
1
2
44
123
193
35–62
8
3
51
83
194
62-63
5
3
85
142
195
60–62
4
1
81
115
196
60–63
6
2
81
118
197
60–66
2
1
81
118
198
35–63
5
1
51
81
199
35–66
2
0
51
83
200
63–66
2
1
90
148
201
65-66
3
2
84
130
202
39–65
2
1
63
98
203
66–70
3
2
92
152
204
39–66
1
2
63
100
205
39–70
2
2
63
129
206
39–71
6
0
63
101
207
71–74
5
3
99
148
208
39–74
8
3
63
105
209
41–74
5
1
83
140
210
74–77
5
3
120
164
211
73-74
8
3
112
155
212
73–77
2
1
112
154
213
73–80
1
2
112
168
214
41–77
2
2
83
123
215
41–80
7
3
83
123
216
77–80
2
1
125
170
217
78–80
1
3
114
161
218
45–78
5
1
98
156
219
80-81
3
2
127
174
220
45–80
6
2
98
159
221
81–84
5
1
130
177
222
45–84
3
2
98
155
223
70–74
4
1
95
158
“ES” is the early start time of each work. “Optimized ES” is the optimized start time.


## 4. The Superiority of OIPSO Compared with the Original and the Existing PSOs

After changing optimization parameters, the superiority of OIPSO in optimization of resource-leveling with fixed duration and resources constraints with shortest project duration of a large-scale network plan in Figure1 is shown in Tables 3 and 4.Table 3
The superiority of OIPSO in optimization of resource-leveling with fixed duration.
Optimization parameters
Case  1
Case  2
Case  3
Case  4
w
1
1
1
1
c
1
3.5
3.5
3.5
3.5
c
2
0.4
0.4
0.4
0.4
M
50
50
50
50
G
100
100
100
100
The project duration of the network plan
135
135
135
135
The project duration of the initial particle
135
135
135
135
The resource variance corresponding to the initial particle
30
50
—
25
The resource variance corresponding to the optimization results
22.41
22.99
22.99
—
“—” denotes “no restrictions” or “no solution in a limited amount of computing time.” The other symbols’ meanings are the same as the previous.Table 4
The superiority of OIPSO in optimization of resources constraints with shortest project duration.
Optimization parameters
Case  5
Case  6
Case  7
Case  8
Case  9
w
1
1
1
1
1
c
1
3.5
3.5
3.5
3.5
3.5
c
2
0.4
0.4
0.4
0.4
0.4
M
10
10
10
10
10
G
1000
1000
1000
1000
1000
The constrained resources of the network plan
25
25
25
25
25
The constrained resources of the initial particle
25
25
—
—
25
The constrained project duration of the initial particle
300
—
300
—
200
The biggest resources quantity after optimization
22
21
22
19
—
The calculated project duration after optimization
199
206
199
206
—
Annotation is the same as Table3.Case  3 in Table3 and case 8 in Table 4 are obtained by the original and existing PSOs in which the initial particles are randomly decided. Case  1 in Table 3 and case 5 in Table 4 are obtained by the improved algorithm (OIPSO) in which optimization is used to decide the initial particles. For the optimization of resource-leveling with fixed duration or resources constraints with shortest project duration of a large-scale network, it can be found that the improved algorithm (OIPSO) can accelerate the optimization speed and improve the optimization effect of particle swarm optimization under the same number of iterations by adding proper optimization constraints of the initial particle swarm, such as the variance restriction or resources limitation and project duration constraint. The optimization constraints of the initial particle swarm are decided gradually through the experiment such as case 2 (the resource variance corresponding to the initial particle is 50) and case 4 (the resource variance corresponding to the initial particle is 25) in Table 3 and case 6 (the constrained resources of the initial particle are 25 and there is no constrained project duration of the initial particle), case 7 (there are no constrained resources of the initial particle and the constrained project duration of the initial particle is 300), and case 9 (the constrained resources and the constrained project duration of the initial particle are, respectively, 25 and 200) in Table 4.


## 5. Conclusion

In this paper, the improved particle swarm optimization algorithm via optimization of initial particle swarm (OIPSO) has been proven to improve the solution probability of optimal solution or by the theory of Markov chains in random process and the optimization examples accelerates the optimization speed and improves optimization effect of particle swarm optimization under the same number of iterations. In existing publications on the larger-scale network plan optimization, the optimization examples of the resource-leveling with fixed duration and the resources constraints with shortest project duration on the large-scale network plan with 223 works have the largest work quantity.



---

*Source: 3271969-2017-02-27.xml*