# Robust Optimization for Time-Cost Tradeoff Problem in Construction Projects

Authors: Ming Li; Guangdong Wu
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

Construction projects are generally subject to uncertainty, which influences the realization of time-cost tradeoff in project management. This paper addresses a time-cost tradeoff problem under uncertainty, in which activities in projects can be executed in different construction modes corresponding to specified time and cost with interval uncertainty. Based on multiobjective robust optimization method, a robust optimization model for time-cost tradeoff problem is developed. In order to illustrate the robust model, nondominated sorting genetic algorithm-II (NSGA-II) is modified to solve the project example. The results show that, by means of adjusting the time and cost robust coefficients, the robust Pareto sets for time-cost tradeoff can be obtained according to different acceptable risk level, from which the decision maker could choose the preferred construction alternative.


---

## Body

## 1. Introduction

Widespread uncertainty in projects will directly affect the achievement of the project schedule and cost management goals. Some studies also discuss the project time-cost tradeoff problem and relevant resource constrained project scheduling problem under conditions of uncertainty for the duration [1, 2].Under random conditions of uncertainty, most studies are based on known activity period and cost parameters probability distribution. Azaron and Tavakkoli-Moghaddam [3] researched the time-cost tradeoff problem of activity period when it exhibits exponential and generalized Erlang distribution. The study constructed a Markov chain to calculate probability distribution of time of completion and got a multiobjective tradeoff model. Bruni et al. [4] studied project scheduling problem of activity period when it was normal distribution. The paper established and compared three β-robust scheduling models. Wu et al. [5] proposed a heuristic approach for solving project scheduling problem, when activity period was an independent random variable and renewable resources were a determined value. Klerides and Hadjiconstantinou [6] researched time-cost tradeoff problem of activity period when it was a discrete random variable and proposed a two-stage stochastic integer programming approach based on path. Wiesemann et al. [7] studied project scheduling problem when activity period and cash flow were discrete random variables and ensured the scheduling strategy in pursuit of the project’s biggest net present value. Shou and Wang [8] studied project scheduling problem when activity period was a discrete random variable. They proposed robust optimization model and designed the genetic algorithms for the model. Wang [9] researched project scheduling problem when time and cost are discrete random variables. He proposed DSPSP model in pursuit of the biggest expected value of net present value and solved two instances to confirm the superiority of the model by simulated annealing algorithm. However, due to the one-off characteristics of projects, in most cases, it is difficult to get the accurate information on the probability distributions of these parameters [10].Under circumstances without accurate probability distributions, some researches also use nominal values and their variation ranges to indicate random parameters, giving parameters interval uncertainty [11]. Janak et al. [12] studied the activity period intervals with project scheduling problem of uncertainty. Robust optimization model containing certain parameters only was obtained by introducing a few auxiliary variables and constraints. Given the uncertain parameters, feasibility of the tolerance interval, and reliability standards, the model can produce optimal solutions under the worst conditions. Hazir et al. [13] studied the project equilibrium problems of activity cost which has interval uncertainty under BOT model. The research established and compared three different robust optimization models of time-cost tradeoff problems and explored exact and heuristic algorithms for those models. However, these studies only considered the situations of uncertainty in activity time or cost without taking into account the uncertainties of both time and cost in the project [14, 15]. Therefore, it is necessary to research time and cost tradeoff problems with uncertainties of both time and cost.Discrete time-cost tradeoff problem (DTCTP) is the classic time-cost equilibrium problem [16, 17] in the project. This paper researched the DTCTP problem with uncertainties of both time and cost and used multiobjective robust optimization to build robust model of time and cost and at last employed NSGA-II to analyze engineering example.


## 2. Multiobjective Robust Optimization

A multiobjective optimization model is shown below:(1)
min
⁡
x
f
m
(
x
,
p
)
,
m
=
1
,
…
,
M
;
s
.
t
.
:
g
l
(
x
)
≤
0
,
l
=
1
,
…
,
L
,
l
l
l
where f
m refers to the objective function of number (
m
), m
=
1
,
…
,
M. g
l stands for constraint function of number (
l
), l
=
1
,
…
,
L. x is decision vector, and p is parameter vector. As p is uncertain, its value range can be shown as tolerance region. The solid black spots in p tolerance region are nominal value p
0, which is the most likely value. When x
=
x
0, the value range of functional vector can be shown as objective sensitivity region (OSR) in f, and solid black spot is nominal value f
(
x
0
,
p
0
). Vector Δ
f
=
(
Δ
f
1
,
…
Δ
f
M
) specifies acceptable objective variation region (AOVR) of f
(
x
0
,
p
) in the f-space. If OSR of f
(
x
0
,
p
) is in the f
(
x
0
,
p
) acceptable target change area, x
0 is the robust solution.In the sensitivity analysis of the objective function, worst-case objective sensitivity region (WCOSR) can be used to estimate the target sensitive areas. WCOSR off
(
x
0
,
p
) is through f
(
x
0
,
p
) sensitive area of the target objective function corresponding to the maximum point and the straight line parallel to the axis of the enclosed area. If WCOSR of f
(
x
0
,
p
) is in the acceptable target change areas, OSR of f
(
x
0
,
p
) must be also in its acceptable target change areas. So x
0 is the robust solution of the model and vice versa [18, 19] (see Figure 1).Figure 1
Multiobjective robust optimization principle.


## 3. Robust Model for Time-Cost Tradeoff Problem

DTCTP issues involve a project networkG
(
N
,
A
), where N is the set of all activities of the project and A is a collection of logical relationships among activities. Each activity in the network can work in a different construction model, and each construction model has its corresponding time and cost. Decision-maker can choose different construction schemes, that is, distribute different construction models to different activities, in order to achieve different time-cost equilibrium in projects. However, there are many uncertainties in the process of implementing the project. These factors make the activity time and cost uncertain and bring difficulties in the project’s time and cost. For the DTCTP problems with interval of uncertainty in the activity time and cost, the paper uses multiobjective robust optimization method to analyze the problems and construct model to achieve time-cost tradeoff robust optimization model. The equations are showed as follows:
(2)
min
⁡
T
0
=
max
⁡
p
∑
j
=
1
J
∑
m
∈
M
j
w
j
p
d
j
m
x
j
m
,
l
l
l
l
l
l
l
l
(3)
min
⁡
C
0
=
∑
j
=
1
J
∑
m
∈
M
j
c
j
m
x
j
m
,
llllllllllllllllllll
(4)
s
.
t
.
∑
m
∈
M
j
x
j
m
=
1
x
j
m
∈
{
0,1
}
,
llllllllll
(5)
l
l
l
l
l
l
l
l
l
(
max
⁡
p
∑
j
=
1
J
∑
m
∈
M
j
w
j
p
(
d
j
m
+
Δ
d
j
m
)
x
j
m
l
l
l
l
l
l
l
l
l
l
l
l
-
max
⁡
p
∑
j
=
1
J
∑
m
∈
M
j
w
j
p
d
j
m
x
j
m
)
l
l
l
l
l
l
l
l
l
×
(
max
⁡
p
∑
j
=
1
J
∑
m
∈
M
j
w
j
p
d
j
m
x
j
m
)
-
1
l
l
l
l
l
l
l
l
≤
R
T
,
(6)
∑
j
=
1
J
∑
m
∈
M
j
Δ
c
j
m
x
j
m
∑
j
=
1
J
∑
m
∈
M
j
c
j
m
x
j
m
≤
R
C
,
(7)
w
j
p
=
{
1
j
∈
p
0
j
∉
p
,
l
l
l
l
l
l
l
l
l
l
l
l
l
(8)
j
=
1
,
…
,
J
,
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
(9)
p
=
1
,
…
,
P
.
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
lIn the model, the nominal time of the project is sum of each activity nominal time in the critical path for the network. Nominal project cost is sum of each activity nominal cost in the network.d
j
m and c
j
m are nominal duration and cost under model m of activity j. The variable w
j
p is used to determine whether activity j is on the path p. If j is on the path, it is 1, otherwise 0. x
j
m, a decision variable, is 1 if activity j is in m mode execution, and 0 otherwise. Formula (4) ensures that each activity has one construction model only. Equations (5) and (6) are robust constraints, where R
T and R
C are duration and cost robust coefficients, respectively. They reflect the level of risk which decision-maker can accept. R
T
·
T
0 and R
C
·
C
0 specify an acceptable change area of project duration and cost of scheduling scheme in multiobjective function space. If the project duration and cost sensitive areas under the worst-case conditions fall within the acceptable varied target areas, that is, (10) are satisfied simultaneously, the scheme is robust:
(10)
max
⁡
p
∑
j
=
1
J
∑
m
∈
M
j
w
j
p
(
d
j
m
+
Δ
d
j
m
)
x
j
m
≤
(
1
+
R
T
)
·
T
0
,
∑
j
=
1
J
∑
m
∈
M
j
(
c
j
m
+
Δ
c
j
m
)
x
j
m
≤
(
1
+
R
C
)
·
C
0
.
In formula (10), Δ
d
j
m and Δ
c
j
m are the duration and cost upper limit change value of activity j in the pattern m. Simplifying (10) can get robust constraints (5) and (6).


## 4. Modified NSGA-II Algorithm

NSGA-II algorithm is the modified version of nondominated sorting genetic algorithm. Because of its excellent property, this algorithm has been used widely and gradually became a reference multiobjective algorithm [20, 21]. This paper modified the simulated binary intersection and the polynomial mutation so as to assure the feasibility of construction plans denoted by chromosomes after intersections and mutations. By the modified algorithm, the duration-cost equilibrium robust model under specific example was solved in the next parts.The main steps of modified NSGA-II algorithm are as follows.(
1
)
Population Initialization. The initial population P
t of size m is generated randomly where t
=
0. Individuals are encoded by real numbers and the chromosome length is equal to the number of activities in the project. The genes at different locations indicate different construction modes. For instance, if an individual’s gene at location 3 is 2, that is, x
32
=
1, it means the construction mode of activity 3 is 2.(
2
) Filial generation Q
t is produced through dual tournament that mainly consists of noninferior sorting and crowding distance calculating for individuals of the parent generation P
t. The noninferior sorting works as(a)
finding out noninferior solutions fromP
t and putting them into noninferior class F
i where i
=
1;
(b)
ending sorting if the number of rest individuals is 0 and going to (c) otherwise;
(c)
continuing to find out noninferior solutions from the rest of theP
t and putting them into noninferior class F
i where i
=
i
+
1 and going to (b).The crowding distance indicates the density of target function area. Sorting individuals that belong to the same noninferior class according to their target values and calculating the average length of sides of the cube constructed by two adjacent individuals, the crowding distanceCD
(
i
) can be obtained as the sum of the average length of sides under different target values. When the objective function value of some individual i reaches the maximum or the minimum, CD(
i
) is defined as Inf.After that, two randomly chosen individuals are compared. If they fall into different noninferior classes, the one within higher class remains in the filial generationQ
t. Otherwise, the individual with bigger crowding distance keeps in the filial generation Q
t. The process continues until the size of the filial generation reaches the designed requirement.(
3
) One-point intersection is practiced with the intersection probability of P
c. Two parent individuals of Q
t are chosen and they exchange their genes at random location of q
cos
⁡ (1
≤
q
cos
⁡
≤
J), thus producing two filial individuals.(
4
) Uniform mutation would occur on individuals of Q
t with the mutation probability of P
m. One individual is chosen and its genes will be changed with a small probability.(
5
)
Population Aggregation. A new population can be got by aggregating the parent and filial generations (R
t
=
P
t
∪
Q
t). In R
t, individuals are sorted by their noninferior classes first. Given the same noninferior class, they will be sorted by crowding distance then. The best m individuals are chosen to form the next population P
t
+
1.(
6
)
Ending Judgment. In this paper, when the designed number of generations is reached, the calculation ends and results will be printed. Otherwise, calculation goes to step (
2
) with t
=
t
+
1.


## 5. Example Analysis

### 5.1. Engineering Example

A project is shown as in Table1.Table 1
Engineering example.
Activity (j)
Immediate predecessor
Construction model (m)
d
j
m/day
Δ
d
j
m/day
c
j
m/ten thousand
Δ
c
j
m/ten thousand
1
1
28
8
46
4
2
40
8
36
7
3
48
4
24
7
2
1
1
30
9
60
6
2
36
7
48
9
3
40
4
36
10
3
1
1
30
9
90
9
2
44
8
80
16
3
66
6
64
19
4
1
1
24
7
90
9
2
32
6
70
14
3
40
4
60
18
5
2.3
1
44
13
40
4
2
48
9
35
4
3
56
5
30
9
6
4
1
28
8
80
8
2
36
7
64
12
3
48
4
36
4
7
5.6
1
18
5
60
6
2
30
6
48
9
3
36
3
44
13


### 5.2. Result and Discussion

This paper uses NSGA-II algorithm and the above example to solve time-cost robust tradeoff model. In the algorithm parameters, we define the size of the population of algorithmm
=
50, evolving algebra n
=
1000, crossover probability p
c
=
0.85, and mutation probability p
m
=
0.01. Table 2 is Pareto solutions which are calculated under different sums. WhenRT andRC are not 0.3 at the same time, the solutions are robust Pareto. WhenRT andRC are 0.3 at the same time, the solution is Pareto.Table 2
Pareto solution under differentRT and RC.
RT
RC
Serial number
T
0
C
0
Scheduling plan
0.1
0.3
1
172
349
3
1
1
3
2
3
3
2
180
320
3
3
1
3
3
3
3
3
206
294
3
3
3
3
3
3
3
0.2
0.3
1
134
363
1
3
1
3
2
3
1
2
142
358
1
3
1
3
3
3
1
3
146
348
1
3
2
3
3
3
1
4
152
347
1
3
1
3
2
3
3
5
154
336
3
3
2
3
1
3
1
6
158
331
3
3
2
3
2
3
1
7
166
324
3
3
2
3
1
3
2
8
170
319
3
3
2
3
2
3
2
9
176
315
3
3
2
3
2
3
3
10
178
314
3
3
2
3
3
3
2
11
184
310
3
3
2
3
3
3
3
12
188
308
3
3
3
3
1
3
2
13
192
303
3
3
3
3
2
3
2
14
198
299
3
3
3
3
2
3
3
15
200
298
3
3
3
3
3
3
2
16
206
294
3
3
3
3
3
3
3
0.3
0.1
1
120
466
1
1
1
1
1
1
1
2
124
461
1
1
1
1
2
1
1
0.3
0.2
1
120
422
1
1
1
1
1
3
1
2
122
420
1
1
1
3
1
2
1
3
124
415
1
1
1
3
2
2
1
4
126
390
1
2
1
2
1
3
1
5
130
378
1
3
1
2
1
3
1
6
134
358
1
3
2
3
1
3
1
7
146
351
1
3
1
3
2
3
2
8
154
341
3
3
1
3
2
3
1
9
166
339
3
3
1
2
2
3
2
0.3
0.3
1
120
422
1
1
1
1
1
3
1
2
122
420
1
1
1
3
1
2
1
3
124
415
1
1
1
3
2
2
1
4
126
390
1
2
1
2
1
3
1
5
130
378
1
3
1
2
1
3
1
6
134
358
1
3
2
3
1
3
1
7
138
353
1
3
2
3
2
3
1
8
146
346
1
3
2
3
1
3
2
9
150
341
1
3
2
3
2
3
2
10
154
336
3
3
2
3
1
3
1
11
158
331
3
3
2
3
2
3
1
12
166
324
3
3
2
3
1
3
2
13
170
319
3
3
2
3
2
3
2
14
176
315
3
3
2
3
2
3
3
15
178
314
3
3
2
3
3
3
2
16
184
310
3
3
2
3
3
3
3
17
188
308
3
3
3
3
1
3
2
18
192
303
3
3
3
3
2
3
2
19
198
299
3
3
3
3
2
3
3
20
200
298
3
3
3
3
3
3
2
21
206
294
3
3
3
3
3
3
3As Table2 shows, whenRC is 0.3, although Pareto front porch has intersection in differentRT, the number of Pareto solutions is increasing withRT increasing from 0.1 to 0.3. So relevant Pareto front porch area is extending. And, asRT increases, robust Pareto frontier constantly moves left gradually approaching the nominal Pareto frontier.In Figure3, whenRT is 0.2, there is intersection between robust Pareto front porch and nominal Pareto. Similar to Figure 2, whenRT increases from 0.3 to 0.1, the number of Pareto solutions is increasing, and the corresponding Pareto front porch area also is expanding and moving to the bottom left gradually approaching the nominal Pareto frontier.Figure 2
Pareto front porch under differentRT.Figure 3
Pareto front porch under differentRC whenRT = 0.3.To sum up, increasing duration or cost robust coefficient will obtain more alternative scheduling plans within certain ranges, including some better ones with higher risks. Decision-maker needs to make a tradeoff between the optimization of alternative scheduling plan and the acceptable level of risk. By adjusting the robust coefficient of the model, we can obtain robust Pareto solutions of time-cost tradeoff under different acceptable risk levels in order to help decision-maker choose better construction plans.


## 5.1. Engineering Example

A project is shown as in Table1.Table 1
Engineering example.
Activity (j)
Immediate predecessor
Construction model (m)
d
j
m/day
Δ
d
j
m/day
c
j
m/ten thousand
Δ
c
j
m/ten thousand
1
1
28
8
46
4
2
40
8
36
7
3
48
4
24
7
2
1
1
30
9
60
6
2
36
7
48
9
3
40
4
36
10
3
1
1
30
9
90
9
2
44
8
80
16
3
66
6
64
19
4
1
1
24
7
90
9
2
32
6
70
14
3
40
4
60
18
5
2.3
1
44
13
40
4
2
48
9
35
4
3
56
5
30
9
6
4
1
28
8
80
8
2
36
7
64
12
3
48
4
36
4
7
5.6
1
18
5
60
6
2
30
6
48
9
3
36
3
44
13


## 5.2. Result and Discussion

This paper uses NSGA-II algorithm and the above example to solve time-cost robust tradeoff model. In the algorithm parameters, we define the size of the population of algorithmm
=
50, evolving algebra n
=
1000, crossover probability p
c
=
0.85, and mutation probability p
m
=
0.01. Table 2 is Pareto solutions which are calculated under different sums. WhenRT andRC are not 0.3 at the same time, the solutions are robust Pareto. WhenRT andRC are 0.3 at the same time, the solution is Pareto.Table 2
Pareto solution under differentRT and RC.
RT
RC
Serial number
T
0
C
0
Scheduling plan
0.1
0.3
1
172
349
3
1
1
3
2
3
3
2
180
320
3
3
1
3
3
3
3
3
206
294
3
3
3
3
3
3
3
0.2
0.3
1
134
363
1
3
1
3
2
3
1
2
142
358
1
3
1
3
3
3
1
3
146
348
1
3
2
3
3
3
1
4
152
347
1
3
1
3
2
3
3
5
154
336
3
3
2
3
1
3
1
6
158
331
3
3
2
3
2
3
1
7
166
324
3
3
2
3
1
3
2
8
170
319
3
3
2
3
2
3
2
9
176
315
3
3
2
3
2
3
3
10
178
314
3
3
2
3
3
3
2
11
184
310
3
3
2
3
3
3
3
12
188
308
3
3
3
3
1
3
2
13
192
303
3
3
3
3
2
3
2
14
198
299
3
3
3
3
2
3
3
15
200
298
3
3
3
3
3
3
2
16
206
294
3
3
3
3
3
3
3
0.3
0.1
1
120
466
1
1
1
1
1
1
1
2
124
461
1
1
1
1
2
1
1
0.3
0.2
1
120
422
1
1
1
1
1
3
1
2
122
420
1
1
1
3
1
2
1
3
124
415
1
1
1
3
2
2
1
4
126
390
1
2
1
2
1
3
1
5
130
378
1
3
1
2
1
3
1
6
134
358
1
3
2
3
1
3
1
7
146
351
1
3
1
3
2
3
2
8
154
341
3
3
1
3
2
3
1
9
166
339
3
3
1
2
2
3
2
0.3
0.3
1
120
422
1
1
1
1
1
3
1
2
122
420
1
1
1
3
1
2
1
3
124
415
1
1
1
3
2
2
1
4
126
390
1
2
1
2
1
3
1
5
130
378
1
3
1
2
1
3
1
6
134
358
1
3
2
3
1
3
1
7
138
353
1
3
2
3
2
3
1
8
146
346
1
3
2
3
1
3
2
9
150
341
1
3
2
3
2
3
2
10
154
336
3
3
2
3
1
3
1
11
158
331
3
3
2
3
2
3
1
12
166
324
3
3
2
3
1
3
2
13
170
319
3
3
2
3
2
3
2
14
176
315
3
3
2
3
2
3
3
15
178
314
3
3
2
3
3
3
2
16
184
310
3
3
2
3
3
3
3
17
188
308
3
3
3
3
1
3
2
18
192
303
3
3
3
3
2
3
2
19
198
299
3
3
3
3
2
3
3
20
200
298
3
3
3
3
3
3
2
21
206
294
3
3
3
3
3
3
3As Table2 shows, whenRC is 0.3, although Pareto front porch has intersection in differentRT, the number of Pareto solutions is increasing withRT increasing from 0.1 to 0.3. So relevant Pareto front porch area is extending. And, asRT increases, robust Pareto frontier constantly moves left gradually approaching the nominal Pareto frontier.In Figure3, whenRT is 0.2, there is intersection between robust Pareto front porch and nominal Pareto. Similar to Figure 2, whenRT increases from 0.3 to 0.1, the number of Pareto solutions is increasing, and the corresponding Pareto front porch area also is expanding and moving to the bottom left gradually approaching the nominal Pareto frontier.Figure 2
Pareto front porch under differentRT.Figure 3
Pareto front porch under differentRC whenRT = 0.3.To sum up, increasing duration or cost robust coefficient will obtain more alternative scheduling plans within certain ranges, including some better ones with higher risks. Decision-maker needs to make a tradeoff between the optimization of alternative scheduling plan and the acceptable level of risk. By adjusting the robust coefficient of the model, we can obtain robust Pareto solutions of time-cost tradeoff under different acceptable risk levels in order to help decision-maker choose better construction plans.


## 6. Conclusions

This paper studies the time-cost tradeoff problems where activity duration and cost present interval uncertainties under multimodel in the project. We build time-cost tradeoff robust model based on multiobjective robust optimization and apply the improved NSGA-II algorithm to solve the model under specific engineering examples. The results showed that increasing time robust coefficientRT or cost robust coefficientRC offers more alternative scheduling plans within certain ranges, including some better options with higher risks. Decision-maker needs to make a tradeoff between the optimization of alternative scheduling plan and the acceptable risk levels. By adjusting the robust coefficient of the model, we can obtain robust Pareto solutions of time-cost tradeoff under different acceptable risk levels in order to help decision-maker choose better construction plans. In the future, researches will consider the effect of resource constraints on this basis and go on to study time-cost tradeoff problems of resource constraint under uncertain conditions. At the same time, we will make better intelligent algorithms to improve model solving efficiency.



---

*Source: 926913-2014-08-04.xml*