Stochastic time–cost tradeoff analysis: A distribution-free approach with focus on correlation and stochastic dominance
Research Highlights
► We integrate correlated Monte Carlo simulation with multiobjective Particle Swarm Optimization. ► We model statistical dependence between uncertain variables. ► Stochastic dominance and a prescreening strategy are proposed to increase efficiency. ► The proposed framework is flexible as it is distribution-free and non-parametric. ► The proposed framework outperforms enumeration and NSGA-II.
Introduction
Time–cost tradeoff (TCT) analysis is a well defined subject in management of construction projects. The analysis is based on the assumption that an acceleration of activity requires more labor and more efficient equipment, and thus higher cost [21]. The earliest goal is to crash project duration to fall within the contractual time limit at a minimum cost. A more generalized goal is to obtain the complete time–cost curve, which indicates the minimum cost at various project durations. This goal represents a bi-objective optimization problem. A solution on the time–cost curve can be related to a set of activity options, which identifies a selected set of working method, equipment choice, and crew selection for each activity.
The literature of TCT analysis is flourishing. The pioneering work used manual calculation to sequentially reduce the durations of activities on critical paths to crash the project [16]. Others approached the problem by different means of mathematical programming methods, such as network flow computations [17], [40], linear programming [38], integer programming [33], [42], hybrid of linear and integer programming [30], and network decomposition [12]. With the aid of increasing computer power, computationally intensive meta-heuristics have recently been applied to find good solutions in a reasonable period of time. The most popular tool is genetic algorithms [13], [20], [27], [28], [29], [60]. Recent advances have been made to make use of particle swarm optimization [55], scatter search [47], ant colony system [35], and neural network [37].
The estimation of activity time and cost is usually made long before project commencement, and thus with limited accuracy. Moreover, during the course of project implementation, many uncertain factors may dynamically affect the times and costs of activities. Examples of the uncertain factors include weather condition, material price and supply, labor skill, and equipment capacity. As a result, it has been extensively argued that activity time and cost in the TCT analysis should be estimated as probabilistic distributions to reflect the relatively large variances and to better manage inherent risks [9], [22], [23]. This class of problem is called the stochastic time–cost tradeoff (STCT) problem.
The STCT problem has been tackled by several studies. Modern approaches adopt multiobjective meta-heuristics to find the optimal set of solutions so as to optimize project duration and cost, both of which are evaluated through simulation. The goal is to approximate the non-dominated set of solutions, which dominates the other solutions found during the process. Here, a solution is said to dominate the other by having shorter duration and lower cost. Feng et al. [15] developed genetic algorithms to perform optimization when activity durations and costs are assumed normally distributed. Their algorithm is a double loop. The outer loop searches for better activity options whereas the inner loop performs Monte Carlo simulation (MCS) to evaluate the mean values of objectives. Since the mean values are point estimates, different trials of simulation would produce different mean values, even for the same set of activity options. This creates a problem that one cannot be sure whether the dominance relation between solutions is consistent or just by chance. The present study intends to provide a theoretical foundation for the stochastic dominance relation.
Azaron et al. [4] applied a goal attained technique to optimize the mean and variance of project duration and cost. In their model, activity durations are assumed to have Erlang distributions whereas activity costs were expressed as functions of durations. Aghaie and Mokhtari [3] employed MCS to find the most critical path and then used it to calculate the probability of project completion. An ant colony algorithm was developed to minimize the probability of project completion by a given time.
The double-loop approach of the existing STCT models is highly computationally demanding due to the iterative nature of the optimization and simulation procedures. For n trials in m optimization iterations with k MCS samples, the number of evaluation of the objective functions (project duration and cost) would be 2 × n × m × k. The computational load is unacceptable, even for a small-to-medium sized project.
The existing STCT models are inadequate to treat the correlation between input variables. Yet, in practical situations, times and costs of activities cannot be assumed statistically independent; they are correlated in several ways. The durations of activities are correlated because activities are performed under the same supervision, weather, and site condition. The importance of modeling such correlation has been repeatedly acknowledged in previous studies [50], [54], [56]. The costs of activities are also correlated because of the use of the same resources (material, equipment, and labor). When the unit cost of a resource rises either due to limited supply or higher transportation expense, it would affect all the related activities [48], [52]. The last type of correlation exists between the time and cost of each activity. This correlation is realized when labor and equipment are paid on a daily or weekly base. For the same activity option, longer duration therefore entails higher cost. Such a correlation can be estimated by a regression analysis on historical data [5], [59].
The present study aims to enhance the STCT analysis by addressing the following issues.
- 1.
All the three types of aforementioned correlation should be incorporated into the STCT analysis to assess the risk with higher accuracy.
- 2.
To provide the greatest modeling capability, the proposed STCT analysis framework should be distribution-free and nonparametric, in that no prior restrictions are placed on the distribution type and estimation process.
- 3.
Using the mean values to be the optimization objectives is dangerous because this would neglect the variation and underestimate associated risks. Alternatively, this study adopts the value-at-risk (VaR) measures, specified quantiles of the outcome distributions, to be the objectives.
- 4.
The optimization model is hard to solve analytically in the sense that the objective functions are non-differentiable. Therefore, this study develops a multiobjective particle swarm optimization (PSO) algorithm to perform the optimization process.
- 5.
The dominance relation between solutions in multiobjective optimization should be redefined for the stochastic environment, where the objective values are not certain.
- 6.
The proposed framework improves the efficiency of the double-loop STCT analysis, by developing a prescreening strategy to discard dominated solutions.
Section snippets
Estimation of activity time and cost
The TCT analysis starts with an estimated set of durations and costs of activities. To extend the analysis to the stochastic case, one must define the probabilistic distributions of durations and costs. This can be accomplished in two ways. When historical data from similar projects is available, the first alternative is to fit theoretical distributions to the data and verify goodness-of-fit statistically. A complete review of popular goodness-of-fit tests is given in [26]. The fitting process
Correlation in Monte Carlo simulation
The inner loop of the proposed framework is to obtain the PDFs of project duration and cost, using MCS. MCS samples the durations of activities and performs CPM calculations to find project duration, along with criticality indices of activities (the probability that an activity is critical). At the same time, MCS also samples the costs of activities and sums them up to get the direct cost, which can be expanded to the total cost by including indirect costs.
The input variables for MCS may be
Objective value: value-at-risk
After the inner loop of MCS is completed, the outer loop compares the PDFs of the objectives to guide further search for better solutions. The comparison can be made based on a variety of statistical measures. Fig. 2 illustrates two PDFs of project duration: (A) and (B). Using the mean value as the comparison base is a common choice, but unfortunately misleading because it does not take into account variations, which may seriously impact the analysis. In lieu of the mean values, the present
Dominance relations between solutions
In the deterministic context, a multiobjective solution u is said to dominate another solution v if the former is superior to the latter in at least one objective and not worse in the other objective. Because project duration and cost are the two objectives being minimized, the dominance relation, denoted by u≻ v, holds if any of the following conditions is met
The goal of multi-objective optimization is to find the non-dominated solutions, which cannot be further
Proposed framework: Integration of PSO and MCS
The flow diagram of the proposed framework is depicted in Fig. 5. Since the STCT analysis is non-differentiable, gradient-based optimization methods are of limited use. In contrast, the use of particle swarm optimization (PSO) to solve the STCT problem is appealing because it converges fast within a high dimensional search space and has only few parameters to adjust [58]. Consequently, the outer loop is performed by a multiobjective PSO algorithm. The original PSO scheme was designed to mimic
Practical example
A practical project from [15] is used to demonstrate the performance of the proposed framework. Activity descriptions and precedence relationships are shown in Fig. 7. Table 1 lists the three-point estimates for activity durations and costs. Note that although subjective estimates are used here, the proposed framework can accept input inferred from historical data.
All three types of correlation are integrated into a correlation structure listed in Table 2. In the second column, T denotes time
Validation
The optimization results are compared with a complete enumeration, which consists of all permutations on possible activity options. The project includes 7 activities, each of which has 3–5 options. Despite the relative small size, a complete enumeration with 500 MCS samples requires 4860 × 500 × 2 = 4.86 × 106 evaluations of objective functions that take 1129 min = 18.82 h on a personal computer with Core 2 Quad 2.4 GHz processors and 2 GB RAM. All the solutions are shown as hollow circles in Fig. 9.
In
Risk analysis
Another merit of the proposed framework is that important risk assessments would be readily available upon completion of optimization. Fig. 11 plots the mean values and 90% CIs of both objectives. The upper bound of the 90% CIs represents the VaR at the 0.95 level as we have seen in Fig. 8. On the top-right corner is the zoom-in view of the mean value (circle) and bounds of the CIs (square and diamond): horizontal interval stands for time whereas vertical interval stands for cost. The CIs are
Overall best plan
Having the entire Pareto front assists project planners in exercising their judgment on the overall best plan. Although every project has its management background, we will illustrate some scenarios here to reflect practical considerations about the best plan. The mean values of direct costs (time–cost curve) are represented by the solid line in Fig. 14. It becomes apparent that both ends of the Pareto front are not worth consideration. Solution 1 costs a lot more than solution 2 just to crash
Conclusions
The present study develops an analysis framework, which incorporates correlated MCS into a multiobjective PSO algorithm, to solve the time–cost tradeoff problem under uncertainty. The proposed STCT framework is unique in several respects. First, it treats three types of correlation: correlation between durations of activities, costs of activities, and duration and cost for individual activities. Second, it sheds light on the stochastic dominance relation between solutions and also provides a
Acknowledgments
This study is supported by the National Science Council, Taiwan under Grant NSC-98-2221-E-011-135-MY3.
References (60)
- et al.
A genetic algorithm approach for the time–cost trade-off in PERT networks
Appl. Math. Comput.
(2005) Time–cost relationship of public sector projects in Malaysia
Int. J. Project Manage.
(2001)- et al.
Probabilistic simulation for developing likelihood distribution of engineering project cost
Autom. Constr.
(2009) - et al.
Optimal procedures for the discrete time/cost trade-off problem in project networks
Eur. J. Oper. Res.
(1996) - et al.
Project scheduling under uncertainty: survey and research potentials
Eur. J. Oper. Res.
(2005) - et al.
Optimization models and a GA-based algorithm for stochastic time–cost trade-off problem
Appl. Math. Comput.
(2009) - et al.
A solution procedure for the discrete time, cost and quality tradeoff problem using electromagnetic scatter search
Appl. Math. Comput.
(2007) - et al.
Multiobjective optimization for manpower assignment in consulting engineering firms
Appl. Soft Comput.
(2011) - et al.
Statistical properties of construction duration data
J. Constr. Eng. Manage. ASCE
(1992) - et al.
Visual interactive fitting of beta distributions
J. Constr. Eng. Manage. ASCE
(1991)
Ant colony optimization algorithm for stochastic project crashing problem in PERT networks using MC simulation
Int. J. Adv. Manuf. Tech.
The PERT model for the distribution of an activity
Oper. Res.
The particle swarm-explosion, stability and convergence in a multidimensional complex space
IEEE Trans. Evol. Comput.
The stochastic time–cost tradeoff problem: a robust optimization approach
Networks
Practical Nonparametric Statistics
A fast and elitist multi-objective genetic algorithm: NSGA-II
IEEE Trans. Evol. Comput.
Hybrid time–cost optimization of nonserial repetitive construction projects
J. Constr. Eng. Manage. ASCE
Simulation verifies queuing program for selecting loader-truck fleets
J. Constr. Eng. Manage. ASCE
Stochastic construction time–cost trade-off analysis
J. Comput. Civ. Eng. ASCE
A network flow computation for project cost curves
Manage. Sci.
Quantitative Methods in Project Management
Lognormal distribution provides an optimum representation of the concrete delivery and placement process
J. Constr. Eng. Manage. ASCE
Optimization of construction time–cost trade-off analysis using genetic algorithms
Can. J. Civ. Eng.
Better estimation of PERT activity time parameters
Manage. Sci.
Particle swarm optimization
Simulation Modeling and Analysis
GA-based multicriteria optimal model for construction scheduling
J. Constr. Eng. Manage. ASCE
Improved genetic algorithms for time–cost optimization
J. Constr. Eng. Manage. ASCE
Cited by (25)
Dynamic control for construction project scheduling on-the-run
2022, Automation in ConstructionCitation Excerpt :In [44], a method was introduced to account for the correlation between project activities in repetitive projects. However, his approach is only applicable in projects that constitute repetitive tasks or in repeated projects; hence, it does not extend to other types of correlations that exist in non-repetitive projects/activities. [43] proposed to explicitly impose correlations between the random variables as inputs.
An improved stochastic life-cycle cost analysis model for examining the impact of environmental policy instruments on construction equipment replacement
2021, Environmental Impact Assessment ReviewSustainable asset management: A repair-replacement decision model considering environmental impacts, maintenance quality, and risk
2019, Computers and Industrial EngineeringCitation Excerpt :Unlike traditional statistical methods which rely on the type of a distribution, BNs are agnostic about it and about the way an NPT is defined. In quantitative risk analysis, Triangular, Normal, Lognormal, Uniform, and Beta are common distributions to handle the uncertainty of cost/time items (Yang, 2011). In this research, we use Triangular distribution, since it captures asymmetrical situations.
High-level integrated deterministic, stochastic and fuzzy cost-duration analysis aids project planning and monitoring, focusing on uncertainties and earned value metrics
2017, Journal of Natural Gas Science and EngineeringCitation Excerpt :This study describes and evaluates such a methodology. Methodologies exist that integrate earned value management (EVM) principles, project uncertainty, duration and cost analysis applying stochastic techniques (e.g., Yang, 2011; Pajares and Lopez-Paredes, 2011; Acebes et al., 2015). These have evolved from many years of research rooted in work breakdown scheduling (WBS), project network analysis, the program evaluation and review technique (PERT) (Clark, 1962), critical path analysis (CPA; Krishnamoorthy, 1968).
A multi-objective invasive weeds optimization algorithm for solving multi-skill multi-mode resource constrained project scheduling problem
2016, Computers and Chemical EngineeringCitation Excerpt :Wuliang and Chengen (2009) extended the discrete time-cost trade off problem to a new multi-mode resource constrained project scheduling problem considering a constraint to preserve the upper bound of the project budget. There are heuristic algorithms such as multi-pass algorithm (Ahn and Erenguc, 1998), and meta-heuristic algorithms such as particle swarm optimization (Yang, 2011) and simulated annealing (Anagnostopoulos and Kotsikas, 2010) in the literature to solve this strictly NP-Hard problem. Tavana et al. (2014) developed a preemptive multi-mode multi-objective model for TCQTP.