Robust Optimization for Time-Cost Tradeoff Problem in Construction Projects

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.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Academic Editor:Hamid Karimi

School of Tourism and Urban Management, Jiangxi University of Finance & Economics, Nanchang 330013, China

Received 7 May 2014; Accepted 19 June 2014; 4 August 2014

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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: [figure omitted; refer to PDF] 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 of f ( _{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.

[figure omitted; refer to PDF]

3. Robust Model for Time-Cost Tradeoff Problem

DTCTP issues involve a project network G ( 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: [figure omitted; refer to PDF]

In 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: [figure omitted; refer to PDF] 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 from _{P 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 the _{P 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 distance CD ( 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 generation _{Q 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 ...4; _{q cos ...} ...4; 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 Table 1.

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 algorithm m = 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. When RT and RC are not 0.3 at the same time, the solutions are robust Pareto. When RT and RC are 0.3 at the same time, the solution is Pareto.

Table 2: Pareto solution under different RT 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	3

As Table 2 shows, when RC is 0.3, although Pareto front porch has intersection in different RT , the number of Pareto solutions is increasing with RT increasing from 0.1 to 0.3. So relevant Pareto front porch area is extending. And, as RT increases, robust Pareto frontier constantly moves left gradually approaching the nominal Pareto frontier.

In Figure 3, when RT is 0.2, there is intersection between robust Pareto front porch and nominal Pareto. Similar to Figure 2, when RT 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 different RT .

[figure omitted; refer to PDF]

Figure 3: Pareto front porch under different RC when RT = 0.3.

[figure omitted; refer to PDF]

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 coefficient RT or cost robust coefficient RC 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.

Acknowledgments

This work was supported by the National Natural Science Funds of China (Grant no. 71301065), University Social Sciences and Humanities Funds of Jiangxi Province (Grant no. JC1309), and Scientific and Technological Research Funds of Department of Education of Jiangxi Province (Grant no. GJJ14341).

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] W. Zhang, Q. Zhang, G. Wu, "Interorganizational knowledge division decision model based on cooperative innovation of supply chain system," Abstract and Applied Analysis , vol. 2014, 2014.

[2] S. Yin, S. X. Ding, A. H. A. Sari, H. Hao, "Data-driven monitoring for stochastic systems and its application on batch process," International Journal of Systems Science , vol. 44, no. 7, pp. 1366-1376, 2013.

[3] A. Azaron, R. Tavakkoli-Moghaddam, "A multi-objective resource allocation problem in dynamic PERT networks," Applied Mathematics and Computation , vol. 181, no. 1, pp. 163-174, 2006.

[4] M. E. Bruni, P. Beraldi, F. Guerriero, E. Pinto, "A heuristic approach for resource constrained project scheduling with uncertain activity durations," Computers and Operations Research , vol. 38, no. 9, pp. 1305-1318, 2011.

[5] C. W. Wu, K. N. Brown, J. C. Beck, "Scheduling with uncertain durations: modeling β -robust scheduling with constraints," Computers and Operations Research , vol. 36, no. 8, pp. 2348-2356, 2009.

[6] E. Klerides, E. Hadjiconstantinou, "A decomposition-based stochastic programming approach for the project scheduling problem under time/cost trade-off settings and uncertain durations," Computers and Operations Research , vol. 37, no. 12, pp. 2131-2140, 2010.

[7] W. Wiesemann, D. Kuhn, B. Rustem, "Maximizing the net present value of a project under uncertainty," European Journal of Operational Research , vol. 202, no. 2, pp. 356-367, 2010.

[8] Y. Shou, W. Wang, "Project scheduling strategy genetic algorithm based on robust optimization model," Journal of Industrial Engineering and Engineering Management , vol. 23, no. 4, pp. 148-152, 2009.

[9] J. Wang, "Uncertainty of the time and cost optimization schedule," Systems Engineering-theory & Practice , vol. 19, no. 1, pp. 93-98, 2002.

[10] S. Yin, H. Luo, S. Ding, "Real-time implementation of fault-tolerant control systems with performance optimization," IEEE Transactions on Industrial Electronics , vol. 64, no. 5, pp. 2402-2411, 2014.

[11] S. Yin, G. Wang, H. Karimi, "Data-driven design of robust fault detection system for wind turbines," Mechatronics , vol. 24, no. 4, pp. 298-306, 2014.

[12] S. L. Janak, X. Lin, C. A. Floudas, "A new robust optimization approach for scheduling under uncertainty. II. Uncertainty with known probability distribution," Computers and Chemical Engineering , vol. 31, no. 3, pp. 171-195, 2007.

[13] Ö. Hazir, E. Erel, Y. Gnalay, "Robust optimization models for the discrete time/cost trade-off problem," International Journal of Production Economics , vol. 130, no. 1, pp. 87-95, 2011.

[14] S. Yin, X. Yang, H. R. Karimi, "Data-driven adaptive observer for fault diagnosis," Mathematical Problems in Engineering , vol. 2012, 2012.

[15] W. Zhang, Q. Zhang, H. Karimi, "Seeking the important nodes of complex networks in product R&D team based on fuzzy AHP and TOPSIS," Mathematical Problems in Engineering , vol. 2013, 2013.

[16] D. Prabuddha, E. James Dunne, J. B. Ghosh, C. E. Wells, "The discrete time-cost tradeoff problem revisited," European Journal of Operational Research , vol. 81, no. 2, pp. 225-238, 1995.

[17] S. Yin, S. X. Ding, A. Haghani, H. Hao, P. Zhang, "A comparison study of basic data-driven fault diagnosis and process monitoring methods on the benchmark Tennessee Eastman process," Journal of Process Control , vol. 22, no. 9, pp. 1567-1581, 2012.

[18] S. Gunawan, S. Azarm, "Multi-objective robust optimization using a sensitivity region concept," Structural and Multidisciplinary Optimization , vol. 29, no. 3, pp. 50-60, 2005.

[19] W. M. Wang, Y. H. Peng, J. Hu, Z. M. Cao, "Collaborative robust optimization under uncertainty based on generalized dynamic constraints network," Structural and Multidisciplinary Optimization , vol. 38, no. 2, pp. 159-170, 2009.

[20] E. G. Bekele, J. W. Nicklow, "Multi-objective automatic calibration of SWAT using NSGA-II," Journal of Hydrology , vol. 341, no. 3-4, pp. 165-176, 2007.

[21] P. Murugan, S. Kannan, S. Baskar, "NSGA-II algorithm for multi-objective generation expansion planning problem," Electric Power Systems Research , vol. 79, no. 4, pp. 622-628, 2009.