Elsevier

Automation in Construction

Volume 20, Issue 7, November 2011, Pages 916-926
Automation in Construction

Stochastic time–cost tradeoff analysis: A distribution-free approach with focus on correlation and stochastic dominance

https://doi.org/10.1016/j.autcon.2011.03.008Get rights and content

Abstract

The present study explores how correlated Monte Carlo simulation (MCS) coupled with a multiobjective particle swarm optimization algorithm can expand the time–cost tradeoff analysis in the presence of uncertainty. The goal of the proposed framework is to find the optimal set of activity options, whose objectives are evaluated as value-at-risk measures of project duration and total cost. The proposed framework incorporates the Gaussian copula into MCS to treat statistical dependence between uncertain variables, with no restriction on the estimation process and distribution type. This paper elucidates the definition of stochastic dominance relations, based on which a decision rule is established to prescreen dominated solutions so as to alleviate computational burden. A practical project has been used to validate the proposed framework by comparisons with enumeration and NSGA-II (non-dominated sorting genetic algorithm). In addition to nondominated solutions, the proposed framework provides insightful risk assessments.

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 metTu<Tvand CuCvCu<Cvand TuTv.

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)

  • A. Aghaie et al.

    Ant colony optimization algorithm for stochastic project crashing problem in PERT networks using MC simulation

    Int. J. Adv. Manuf. Tech.

    (2009)
  • C.E. Clark

    The PERT model for the distribution of an activity

    Oper. Res.

    (1962)
  • M. Clerc et al.

    The particle swarm-explosion, stability and convergence in a multidimensional complex space

    IEEE Trans. Evol. Comput.

    (2002)
  • I. Cohen et al.

    The stochastic time–cost tradeoff problem: a robust optimization approach

    Networks

    (2007)
  • W.J. Conover

    Practical Nonparametric Statistics

    (1980)
  • K. Deb et al.

    A fast and elitist multi-objective genetic algorithm: NSGA-II

    IEEE Trans. Evol. Comput.

    (2002)
  • A.M. Ezeldin et al.

    Hybrid time–cost optimization of nonserial repetitive construction projects

    J. Constr. Eng. Manage. ASCE

    (2009)
  • F. Farid et al.

    Simulation verifies queuing program for selecting loader-truck fleets

    J. Constr. Eng. Manage. ASCE

    (1994)
  • C. Feng et al.

    Stochastic construction time–cost trade-off analysis

    J. Comput. Civ. Eng. ASCE

    (2000)
  • J.M. Fondahl
  • D.R. Fulkerson

    A network flow computation for project cost curves

    Manage. Sci.

    (1961)
  • J.C. Goodpasture

    Quantitative Methods in Project Management

    (2003)
  • L.D. Graham et al.

    Lognormal distribution provides an optimum representation of the concrete delivery and placement process

    J. Constr. Eng. Manage. ASCE

    (2005)
  • T. Hegazy

    Optimization of construction time–cost trade-off analysis using genetic algorithms

    Can. J. Civ. Eng.

    (1999)
  • T. Hegazy
  • D. Keefer et al.

    Better estimation of PERT activity time parameters

    Manage. Sci.

    (1993)
  • J. Kennedy et al.

    Particle swarm optimization

  • A.M. Law et al.

    Simulation Modeling and Analysis

    (2000)
  • S.S. Leu et al.

    GA-based multicriteria optimal model for construction scheduling

    J. Constr. Eng. Manage. ASCE

    (1999)
  • H. Li et al.

    Improved genetic algorithms for time–cost optimization

    J. Constr. Eng. Manage. ASCE

    (1997)
  • Cited by (25)

    • Dynamic control for construction project scheduling on-the-run

      2022, Automation in Construction
      Citation 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.

    • Sustainable asset management: A repair-replacement decision model considering environmental impacts, maintenance quality, and risk

      2019, Computers and Industrial Engineering
      Citation 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 Engineering
      Citation 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 Engineering
      Citation 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.

    View all citing articles on Scopus
    View full text