Proceedings of the 2008 Winter Simulation Conference

S. J. Mason, R. R. Hill, L. Mönch, O. Rose, T. Jefferson, J. W. Fowler eds.

A DYNAMIC CRASHING METHOD FOR PROJECT MANAGEMENT

USING SIMULATION-BASED OPTIMIZATION

Michael E. Kuhl
Radhamés A. Tolentino-Peña

Industrial & Systems Engineering Department

Rochester Institute of Technology
Rochester, NY 14623 USA

up accomplishment of scheduled activities.” Since crashing

ABSTRACT
a project represents additional costs, crashing decisions
A dynamic simulation-based crashing method is introduced need to be made in a cost-effective way. When crashing a
in this research to evaluate project networks and determine project the tradeoff between the crashing cost and the pen-
the optimum crashing configuration that minimizes the av- alty cost needs to be evaluated. A typical scenario involv-
erage project cost due to lateness penalties and crashing ing a project that has potential for being completed late (re-
costs. This dynamic approach will let the user evaluate the sulting in a penalty), and may benefit from crashing is
project network to determine a crashing strategy at the be- illustrated in Figure 1. As crashing of activities is imple-
ginning of the project and also during the life of the pro- mented, the total cost of crashing plus the penalty cost may
ject. By reevaluating the project network possible adjust- initially decrease. As the crashing amount is increased, di-
ments to the crashing strategy may be identified and minishing returns will be realized until a point where the
implemented. The output of the method includes a distribu- total cost may begin to increase. The objective is to deter-
tion of the project completion time, a distribution of the mine the optimal crashing point (indicated by the arrow)
project total cost, and the project cost savings. where the total cost will be minimized.

1 INTRODUCTION The crashing method is focused on reducing the time

of the activities on the critical path. The critical path is the
Project management is a tool that is used by many compa- one that can cause a delay of the project because there is no
nies to help improve performance and competitiveness. slack on that path. The traditional method of crashing
Projects and their execution, in general, require resources. CPM/PERT networks only considers average activity times
Project management, which is characterized by techniques for the calculation of the critical path, ignoring the uncer-
intended to provide a better use of project resources (Kerz- tainty related with the duration of the activities. Conse-
ner 2003), can positively impact the profitability of a com- quently, other paths that may have a high probability of
pany. becoming critical are ignored. As a way to overcome this
issue, simulation can be used to model the stochastic nature
An important aspect of project management is risk of the durations of the activities. Incorporating stochastic
management. Different types of risk are present in any giv- durations in the crashing process allows the generation of
en project, but the emphasis of this research will be fo- the project completion time distribution and enables the
cused on schedule/time risk and associated costs. The analysis of the real effect that a specific crashing configu-
schedule/time risk essentially implies not completing pro- ration may have on the project.
ject activities on time, resulting in a late completion of the
project. Late project completion generally has negative ef- Several simulation based crashing methods are de-
fects for the company such as penalty costs and customer scribed in the literature (Bissiri and Dunbar 1999, Haga
dissatisfaction. If a project is running late project managers and Marold 2004, Haga and Marold 2005). These methods
might be able to bring the project back on track by incor- are heuristics that are developed to return satisfactory solu-
porating additional resources (Eisner, 2002). In project tions but not necessarily an optimal solution.
management, this method of mitigating risk is known as
crashing. The goal of this research is to develop a method that
allows project managers to make optimal dynamic, data
Rosenau and Githens (2005) state crashing is driven crashing decisions that minimize the average project
“spend[ing] more money on the project in order to speed

978-1-4244-2708-6/08/$25.00 ©2008 IEEE 2370

 Kuhl and Tolentino-Peña

cost (the project cost in this research is the sum of crashing a confidence interval for the project mean duration and al-
costs and penalty costs). so determines the minimum number of simulation runs ne-
cessary to have a better estimator of the mean project dura-
tion. Simmons (2002) and Pritsker (1986) also describe
simulation models that evaluate project networks. These
simulation models provide a histogram of the project com-
pletion time distribution, which can be used to perform risk
analysis.
Crash + penalty cost

2.2 Simulation-based Crashing Methods

Bissiri and Dunbar (1999) present a method to crash a pro-

ject network. They suggest the use of simulation to obtain
the average time of each activity, the critical path, and the
near critical paths. A near critical path in this model is a
path which length is smaller than the original completion
date but it is larger than the target completion date after
crashing. After the path information is collected a linear
program is applied to determine the crashing strategy.
Haga (1998) along with Haga and Marold (2004), and
Haga and Marold (2005) present a series of papers involv-
Crashing amount
ing heuristic crashing methods for project management uti-
Figure 1: Relationship between crashing amount and the lizing simulation.
total cost (crash + penalty). Haga and Marold (2004), propose a simulation-based
method that deals with the time-cost trade-off involved
2 RELATED WORK with crashing a project. The authors state that “the com-
plete distribution of project completion time needs to be
2.1 Determining Project Completion Times considered when crashing”. The method that they proposed
is a two steps approach. The first step is to apply the tradi-
The Critical Path Method (CPM) and the Project Evalua- tional PERT method to crash the project, and the second
tion and Review Technique (PERT) methods have been step consists in testing each activity that had not been
used since the 1950s to estimate the completion time of a crashed to the upper crashing limit to determine if crashing
project. CPM is a deterministic approach to calculate the that activity further reduces the average total cost of the
duration of a project, and PERT is a probabilistic approach project. The authors considered two sources that can in-
that enhances CPM by considering uncertainty in activity crease the cost of the project, which are crashing costs and
durations by calculating the probability to complete the overrun costs.
project by a given time (Lee and Arditi 2006). Hillier and Haga and Marold (2005) developed a method to moni-
Lieberman (2001) state that even when the original ver- tor and control a project. The output of this method is a list
sions of CPM and PERT have some significant differences, of dates at which the project manager “should review the
with time they have been considered as one technique project to decide if activities need to be crashed”. These
called CPM/PERT. The PERT method considers the mean dates are called crashing points, and they are determined
and variance of each activity to describe its duration and to by a backward run through the project network. The crash-
represent the uncertainty associated with it; however, ing points are established at the beginning of the project
PERT only considers the mean times to calculate the criti- and they remain fixed during the entire project life.
cal path, ignoring the variances, thus making a determinis-
tic analysis (Ahuja et al. 1994). 3 METHODOLOGY
The research of Lu and AbouRizk (2000) presents a
CPM/PERT simulation model that incorporates the discrete The purpose of this research is to develop a dynamic simu-
event modeling approach and a simplified critical activity lation-based analysis method capable of evaluating project
identification method. Lee (2005) presents a software tool, networks to answer the following questions:
SPSS, which can be used to determine the probability as-
sociated with the completion of the project by a target date • What activities should be crashed in order to mi-
specified by the user. Lee and Arditi (2006) describe a nimize the average project cost?
new simulation system, S3, which is an improvement over • To what extent should the activities be crashed?
SPSS. An advantage of S3 over SPSS is that S3 calculates

2371
 Kuhl and Tolentino-Peña

• How often should the project network be reevalu- the target completion time. Although activity times could
ated? follow any probability distribution if the appropriate pa-
rameters that define the PDF are known, using the beta dis-
The overall procedure is presented in two phases. Phase I tribution to represent activity times is common in the field
considers the evaluation of the project prior to the start of of project management and we will keep with this conven-
the project. This phase will produce an optimal crashing tion in this paper. The duration of each activity is defined
strategy (with respect to information available prior to the by three estimates consisting of the optimistic, most likely,
start of the project) as well as recommendations for re- and pessimistic duration times; these estimates are used to
evaluation during the Phase II where the dynamic crashing estimate the parameters of the general beta distribution,
portion of the method is implemented. from which the activity durations are sampled.
This procedure is designed to evaluate the impact that Once the information that describes the project net-
crashing each activity (by integer time units) has on the av- work is defined in the simulation model the activity times
erage project cost. The method is intended to be robust and will be generated, and the starting and completion times of
produce optimum results for analyzing project networks each activity will be calculated. The starting time of each
with only one dominant critical path or multiple critical activity will be equal to the time at which all its predeces-
paths. sors are completed. The completion time of each activity is
The output of the method includes a distribution of the represented by the following expression:
project completion time, a distribution of the project total
cost, the activities to crash and the extent of the crashing, cti = st i + t i − xi ,
confidence and tolerance intervals on the project comple-
tion time, and the time points at which the project network
where ct represents the activity completion time, st repre-
might be reevaluated.
In the next sections, Phase I and Phase II of the proce- sents the activity starting time, t represents the activity du-
dure are presented. Although the methods are designed to ration, and x represents the number of time units by
be used together to maximize the benefit of the method, which the activity is crashed.
Phase I can be applied independently from Phase II at the After calculating the completion time for each activity
start of the project with Phase II being optional. the project duration is calculated; the project duration is
equal to the longest activity completion time. There is a
3.1 Phase I: Optimal Crashing Method Applied penalty cost associated with a late completion of the pro-
Prior to the Start of the Project ject, and for some projects there is an additional profit as-
sociated with early completion. It is necessary to incorpo-
The objective of Phase I of the procedure is to obtain the rate in the simulation model the functions that represent the
optimal crashing configuration prior to the start of the pro- penalty cost or additional profit. In this phase of the re-
ject that will minimize the total project cost with respect to search linear functions are considered. Finally, the total
crashing costs and penalty costs. Phase I involves the fol- cost is calculated, which is equal to the crashing cost plus
lowing steps: the penalty cost. (For the examples presented in this pa-
per, the simulation model is developed using the C++.)
1. Construct a simulation model of the project net- The simulation model is used to generate the distribu-
work. tion of the project cost and project completion time when
2. Identify the potential/feasibility of crashing each no crashing is applied to the project network; the distribu-
activity in the network and the related costs. tion of project cost is the baseline used to determine the
3. Utilize a stochastic simulation optimization tool level of risk associated with penalty costs.
such as Industrial Strength COMPASS (ISC) to The simulation model uses integer decision variables
determine the optimal project crashing configura- that represent the number of time units by which an activ-
tion. ity is crashed; a particular set of values for these integer
4. Proceed to Phase II or implement the optimal decision variables represents a crashing configuration. The
crashing solution. simulation model interacts with an optimization engine
with the purpose of determining the crashing configuration
The simulation model is used to determine the project with the minimum average total cost.
duration and the additional project cost (crash + penalty The optimization engine used in this step of the meth-
costs). The first step in using the simulation model is to in- odology is Industrial Strength COMPASS (ISC) (Xu et al.
put the data that describes the project network, which con- 2007). ISC is a tool which is derived from the COMPASS
sists of the probability distribution functions (PDF) that framework developed by Hong and Nelson (2006) for lo-
represent the activity durations, the crashing cost per time cally convergent, discrete optimization-via-simulation
unit for each activity, the predecessors of each activity, and (DOvS). To utilize ISC the C++ simulation model is inte-
grated into the ISC code. ISC requires inputs such as an in-

2372
 Kuhl and Tolentino-Peña

itial solution, the range of possible values for each decision Table 1: Dependency relationships for the project network
variable (crashing amounts), and the confidence level de- used for the example.
sired for the solution; these inputs must be provided in a
separate text file from which ISC reads them. (For a com- Activity Predecessors Activity Predecessors
plete list of the inputs required to use ISC please refer to
Xu et al. 2007). ISC searches the feasible region defined by 1 - 19 8, 15
the potential activities that can be crashed and returns an 2 1 20 10, 17
optimal solution within the specified tolerance. 3 1 21 10, 17
Next we present an example illustrating the Phase I
method. 4 1 22 12, 20
5 2 23 12,20
3.2 Phase I: Example 6 2 24 4
7 5 25 16, 24
The following project network, is bases on an example pre-
sented by Haga (1998), to illustrate Phase I of the crashing 8 5 26 18, 25
method. Table 1 shows the 36 activities in the network 9 7 27 26
along with the precedence relationships. The project net- 10 7 28 26
work is depicted graphically in Figure 2. In this example,
11 9 29 19, 27
the network contains only 1 possible critical path which
will be the focus of this example. The activities on this crit- 12 9 30 19, 27
ical path each have a potential of crashing up to 3 time 13 11 31 21, 22, 29
units. The respective parameters of the activity time distri- 14 11 32 28, 30
butions and unit crashing costs are shown in Table 2. The
target completion time of the project is time 180, and the 15 3, 6 33 32
equation defining the penalty cost for late completion is 16 3, 6 34 23, 31, 33
17 8, 15 35 13, 34
⎧ 0, if T ≤ 180
P=⎨ 18 8, 15 36 14, 35
⎩10(T − 180), if T > 180,

where T is the resulting completion time of the project.

ISC was used to obtain the optimal crashing configu-
ration which is to crash activity 29 three time units. The Table 2: Minimum (a), most likely (ml), and maximum (b)
original project without crashing and the project with the duration and crashing cost for each activity.
optimal crashing configuration were each simulated 50,000
times to produce the distribution of completion time (Fig- Crash
ure 3) and the cumulative distribution of the total project Activity a ml b cost
cost (Figure 4). In addition, Table 3 provides the average 1 10 20 30 9
and standard deviation of the project duration and project
4 12 14 16 8
cost. The optimal crashing configuration generated by ISC
is consistent with the one presented by Haga (1998). 24 14 18 22 4
25 12 18 30 6
26 10 20 30 9
4 24 25 26 28
32
27 8 12 16 9
27 30
33 29 18 25 32 1
18
3 16 31 10 20 30 8
1
19 29
31
34
34 15 20 25 9
6 15
21 35
35 6 12 18 4
17 20 22
2 8 36
13
10 12 23

5 7 9 11 14

Figure 2: Project network used for example (based on Ha-

ga 1998).

2373
 Kuhl and Tolentino-Peña

Table 3: Summarized comparison between no crashing and the activities of the project. As activities are completed the
optimal crashing. overall uncertainty about the project completion time is re-
duced, and as a result the initial optimal solution might
change. In order to take into account the effect that the un-
Duration Cost
certainty reduction has on the project completion time and
Average Std. Dev. Average Std. Dev. the crashing configuration, the Phase II, dynamic crashing
Original 179.997 7.63 30.51 44.88 method, is used. The purpose of the dynamic method is to
determine the optimal crashing configuration for the re-
Optimal 176.997 7.63 20.93 34.54 maining activities.
After the project begins, the following steps make up
the dynamic method. We will assume that the initial re-
16% evaluation points will be the crashing points identified in
14% Phase I.
12%
[Link] the project progresses, when the first activity
Probability

10% that requires crashing as identified by Phase I is

8% encountered, begin the reevaluation process.
6% 2. Determine which activities are completed or in
4% process when the reevaluation point is reached.
2% For those in process, estimate the remaining proc-
0%
essing time.
3. Reevaluate the remaining project network using
140 160 180 200 220 the simulation model and ISC as described in
original Phase I.
Duration
optimal 4. Implement the project network under the new
crashing configuration and continue until either
Figure 3: Project completion times comparison – Original a) the next activity that requires crashing is en-
versus Optimal. countered and go to step 2; or
b) the project is complete.
For each iteration of steps 2-4 of the dynamic crashing
procedure, a new crashing configuration for the remainder
100% of the project will be identified that takes into account the
90% sunk activity times and costs associated with the activities
80% in progress and the activities that have been completed.
Cummulative %

70%
60%
50% 3.4 Dynamic Crashing Example (Phases I and II)
40%
30% To illustrate the dynamic crashing method the following
20% project network shown in Figure 5 is used. The activity du-
10% rations are represented by beta distributions; the minimum
0% (a), most likely (b), and maximum (b) duration for each ac-
0 100 200 300 400 tivity, as well as randomly generated crashing cost are
shown in Table 4. The penalty for late completion is equal
original
Cost to 40 cost units per time unit. The target completion time is
optimal set to 70 time units.
The project network is evaluated when no crashing is
Figure 4: Project costs comparison – Original versus Opti- applied (by running 10,000 replications), and the average
mal. cost is 21.21 cost units with a variance of 1556.38. The op-
timal crashing configuration provided by ISC is that activ-
3.3 Phase II: Dynamic Crashing ity 2 should be crashed two time units, and activity 9
should be crashed one time unit. In this case the average
In Phase I, prior to the start of the project an initial optimal cost is 14.39 cost units, and the variance is 417.87.
crashing configuration is obtained by analyzing the entire To illustrate Phase II, the dynamic crashing involving
project network. This initial optimal crashing configuration reevaluation during the project, we have conducted 10 tri-
considers the uncertainty associated with the duration of all als. Each trial represents a single realization of the project

2374
 Kuhl and Tolentino-Peña

evaluated without crashing, with Phase I crashing only, and Table 4: Minimum (a), most likely (ml), and maximum (b)
with the Phase II crashing. The detailed description for duration and crashing cost for each activity.
Trial 1is as follows. Crash
In Trial 1, a realization of the project activity times is Activity a ml b Cost
generated (via simulation) and applying the dynamic me- A1 8 10 12 6
thod algorithm, the first reevaluation point will be the start A2 6 10 14 3
time of activity 2. By the start time of activity 2, activity 1
A3 6 8 10 5
is completed, and there are no activities in process. The du-
ration of activity 1, which is equal to the start time of activ- A4 10 15 20 4
ity 2, is equal to 10.21 time units. The network is reevalu- A5 12 17 22 5
ated assuming the duration of activity one as being A6 3 5 7 8
deterministic (a sunk cost); the new optimal crashing con- A7 6 9 12 5
figuration is that activities 2 and 9 should be crashed two A8 4 6 8 5
time units each. This new solution confirms that activity 2 A9 11 13 15 2
should be crashed, and suggests that activity 9 should also
be crashed but by two time units instead of by one time A10 13 15 17 8
unit as initially suggested. The new average cost is 14.53 A11 5 7 9 7
with a variance of 278.51.
After crashing activity 2, the project proceeds. The Table 5: Summary of results of the dynamic method im-
next reevaluation point is the start time of activity 9. Just plementation.
before the start of activity 9, activities 1 to 4 have been Project Cost
completed and activity 5 is in process. The network is re- Static Dynamic
evaluated considering the duration of activities 1 to 5 as Trial No Crashing Crashing Crashing
deterministic, and crashing activity 2 two time units. The 1 0.0 8.0 6.0
new optimal crashing configuration indicates that activity 9
2 18.2 8.0 7.0
shouldn’t be crashed, nor any other activity. The average
cost is 6 cost units with a variance of 0; that cost is the re- 3 0.0 8.0 0.0
sult of crashing activity 2 twice and resulting in an on-time 4 82.0 50.0 43.1
project. 5 61.8 29.8 17.0
Similarly, a total of ten trials of the dynamic method 6 0.0 8.0 6.0
were performed. The results of each trial are shown in Ta- 7 85.6 53.6 17.0
ble 5 and Table 6. Over these 10 trials, implementing 8 45.9 8.0 9.0
Phase I alone provided an average cost savings of 36%
9 104.8 72.8 12.0
over not crashing at all. The dynamic crashing method
provided a cost reduction of 69% over not crashing at all 10 0.0 8.0 6.0
and an additional 52% reduction over using the Phase I Average 39.8 25.4 12.3
crashing method alone. These results demonstrate the types
of benefits that can be obtained when the project network Table 6: Activities crashed in each trial of the dynamic me-
is dynamically crashed during the project life. thod.
Crashing Amount
2 5 7 Trial A2 A9 A11
1 2 0 0
2 1 2 0
1 3 6 8 10 11
3 0 0 0
4 2 2 0
4 9 5 2 2 1
6 2 0 0
Figure 5: Project network used to evaluate the dynamic 7 2 2 1
method. 8 1 0 0
9 2 3 0
10 2 0 0

2375
 Kuhl and Tolentino-Peña

4 CONCLUSION Lee, D. 2005. Probability of project completion using sto-

chastic project scheduling simulation. Journal of Con-
We have presented a simulation-based methodology to struction Engineering and Management, 131(3): 310-
evaluate project networks and determine an optimal crash- 318.
ing strategy. The methodology has two phases: Phase I, Lee, D., and D. Arditi. 2006. Automated statistical analysis
crashing applied prior to the start of the project, and Phase in stochastic project scheduling simulation. Journal of
II, dynamic crashing applied during the project life to up- Construction Engineering and Management, 132(3):
date the crashing strategy. Applying Phase I to a project 268-277.
network reduces the average cost, and in certain cases the Lu, M., and S. M. AbouRizk. 2000. Simplified CPM/PERT
achieved average cost reduction might be enough for the simulation model. Journal of Construction Engineer-
decision makers; however, when Phase II is applied all the ing and Management, 126(3): 219-226.
uncertainty that has been eliminated is taken into account Nelson, L.J. and B. L. Nelson. 2006. Discrete optimization
to produce an updated crashing strategy, which generally via simulation using COMPASS. Operations Re-
yields lowest project costs. These methods utilize a proven search, 54:115-129.
stochastic optimization procedure that provides asymptoti- Pritsker, A. A. B. 1986. Introduction to Simulation and
cally optimal results which provides a significant contribu- SLAM II. 3rd Ed., Wiley & Sons, Inc, New York.
tion to the literature that currently consists primarily of Rosenau, M. D. and G. D. Githens. 2005. Successful Pro-
heuristic methods. ject Management : a Step-by-step Approach with
The future research efforts will be focused on conduct- Practical Examples. 4th Ed., Wiley, Hoboken, N.J.
ing a rigorous experimental performance evaluation, inves- Simmons, L. F. 2002. Project management - critical path
tigating alternative methods for determining reevaluation method (CPM) and PERT simulated with Process
points for Phase II, and investigating the scalability of the Model. Proceedings of the 2002 Winter Simulation
computational methods for large project networks. In addi- Conference, Dec 8-11 2002: 1786-1788.
tion, we intend to generalize the approach to include alter- Xu, J., B. L. Nelson, and L. J. Hong. 2007. Industrial
native probability distributions for crashed activity times as Strength COMPASS: A Comprehensive Algorithm and
opposed to the standard assumption in the literature of in- Software for Optimization via Simulation. Website
teger reductions in activity times for crashed activities. <[Link]
~nelsonb/ISC/>.
REFERENCES
AUTHOR BIOGRAPHIES
Ahuja, H. N., S. P. Dozzi, and S. M. AbouRisk. 1994.
Project Management Techniques in Planning and MICHAEL E. KUHL is an Associate Professor in the In-
Controlling Construction Projects. 2nd Ed., Wiley, dustrial and Systems Engineering Department at Rochester
New York. Institute of Technology. He has a Ph.D. in Industrial Engi-
Bissiri, Y., and S. Dunbar. 1999. Resource allocation mod- neering from North Carolina State University (1997). His
el for a fast-tracked project. International Conference research interests include simulation modeling and analysis
on Intelligent Processing and Manufacturing of Mate- with application to input modeling, healthcare, project
rials, 635-640. management, and semiconductor manufacturing. He served
Eisner, H. 2002. Essentials of Project and Systems Engi- as Proceedings Editor for the 2005 Winter Simulation Con-
neering Management. 2nd Ed., Wiley, New York. ference. He is currently president of the INFORMS Simu-
Haga, W. A. 1998. Crashing PERT networks. Ph.D. Dis- lation Society, and a member of IIE and ASEE. His e-mail
sertation, University of Northern Colorado, Colorado. address is <[Link]@[Link]> and his web
Haga, W. A., and K. A. Marold. 2004. A simulation ap- address is <[Link]/mekeie>.
proach to the PERT CPM time-cost trade-off problem.
Project Management Journal, 35(2): 31-37. RADHAMÉS A. TOLENTINO-PEÑA is a Master of
Haga, W. A., and K. A. Marold. 2005. Monitoring and Science candidate in Industrial Engineering in the Indus-
control of PERT networks. The Business Review, 3(2): trial and Systems Engineering Department at Rochester In-
240-245. stitute of Technology. His research interests include the
Hillier, F. S., and G. J. Lieberman. 2001. Introduction to application of simulation and operations research methods
Operations Research. 7th Ed., McGraw-Hill, New to the areas of project management and logistics. He is a
York. member of IIE, APICS, and SHPE. His e-mail address is
Kerzner, H. 2003. Project management: a systems ap- <[Link]@[Link]>.
proach to planning, scheduling, and controlling. 8th
Ed., Wiley, Hoboken, NJ.

2376