Engineering, 2009, 1, 1-54
Published Online June 2009 in SciRes (
Copyright © 2009 SciRes. Engineering, 2009, 1, 1-54
The Effect of Price Discount on T ime-Cost Trade-off
Problem Using Genetic Algorithm
Hadi Mokhtari1, Abdollah Aghaie2
Industrial Engineering Department, K. N. Toosi University of Technology, Tehran, Iran
Received April 21, 2009; revised May 13, 2009; accepted May 18, 2009
Time-cost trade off problem (TCTP), known in the literature as project crashing problem (PCP) and project
speeding up problem (PSP) is a part of project management in planning phase. In this problem, determining
the optimal levels of activity durations and activity costs which satisfy the project goal(s), leads to a balance
between the project completion time and the project total cost. A large amount of literature has studied this
problem under various behavior of cost function. But, in all of them, influence of discount has not been in-
vestigated. Hence, in this paper, TCTP would be studied considering the influence of discount on the re-
source price, using genetic algorithm (GA). The performance of proposed idea has been teste d on a medium
scale test problem and several computational experiments have been conducted to investigate the appropriate
levels of proposed GA considering accuracy and computational time.
Keywords: Project Management, PERT Networks, Time Cost Trade off, Genetic Algorithm, Discount
1. Introduction
Time-cost trade off problem (TCTP) is an important part
of the project management in planning phase. It is a sub
problem of project scheduling when finding the most
cost effective way to finish a project within time limit is
desirable. In the TCTP, the objective is to determine the
duration of each activity in o rder to obtain the minimum
costs of the proj ect. All existing patterns of this problem
satisfy the objective function through expediting the
activity durations. In this problem, determining the opti-
mal levels of activity d ur ations and activ ity costs leads to
a balance between the project completion time and the
project total cost. There are some procedures in TCTP
(e.g. extra resource allocation, improvement in technol-
ogy level, increase in the quality of materials, hiring
highly skillful human resou rces, etc.) used for expeditin g
the activity durations, according to activity characteris-
tics. These procedures can be summarized to a unique
cost function corresp onding to each activity.
Herroelen and Leus [1] evaluated some stochastic
models of the TCTP under two main categories: “The
stochastic discrete time/cost trade-off problem” and
“Multi-mode trade-off problem in stochastic networks”.
In the stochastic TCTP, when objective function of the
model is related to the time, Bowman [2] presents a
heuristic algorithm based on simulation technique and
solves a general project compression problem using the
derivative estimators. Besides, the application of mathe-
matical programming for the stochastic project crashing
problem was suggested by Abbasi and Mukattash [3], in
which activities are assumed to have three time estimates.
Unfortunately, it seems that the proposed approach has
been developed for a network with a single path and is
not applicable for the ne tworks with slight differences in
the path durations. Arisawa and Elmaghraby [4] sug-
gested the use of fractional linear programming for the
optimal allocation of resources to the activities in order
to maximize the reduction in project mean duration per
unit investment in GERT type networks. A novel re-
source-constrained project scheduling problem has been
modeled by Golenko and Gonik [5] as a knapsack re-
Copyright © 2009 SciRes. Engineering, 2009, 1, 1-54
source reallocation problem in which a heuristic algo-
rithm has been to determine the optimal amount of re-
sources allocated to the activities and their start times.
Some authors have investigated the stochastic TCTP
to minimize the project total costs [6-8]. Gutjahr et al. [9]
studied the discrete model of this problem by using the
stochastic branch and bound method to improve the
probability of meeting project deadline. In their work,
they assumed that the crashing of activity durations (by
using additional costs) leads to higher direct costs and
lower penalty costs. In another research, Mitchell and
Klastorin [10] have formulated the objective function
with the direct, indirect, and penalty costs. This study
presents a Stochastic Compression Project (SCOP) heu-
ristic based on decomposition of PERT networks into th e
serial and parallel subnets. Recently, some researchers
have considered the multi criteria/objective formulation
for the stochastic TCTP [11-14].
In all of the presented papers, TCTP have investig ated
under various behaviors of the cost function such as
discrete cost function [5,15-19], linear continuous cost
function [20-22], nonlinear convex cost function [23,24],
nonlinear concave cost function [25] and linear piece-
wise cost function [26,27]. But, in all of them, influence
of discount has not been investigated. In this study, we
develop a new TCTP based on discoun t in resource price
to maximize the project completion probability in a pre-
defined deadline using a limited available budget. In
order to construct the model we assume that activity
durations follow the normal distribution and the activity
mean durations represent the decision variables. In order
to solve this problem, we organize the genetic algorithm
(GA) technique. Recently, some researchers use the GA
in order to solv e the project scheduling problems such as
TCTP [11].
This paper is organized in the following way. The
mathematical model is presented in Section 2. Section 3
describes the structure of the proposed approach, which
is based on the GA algorithm. The characteristics of a
large scale numerical example and results of applying the
proposed approach to that example are presented in Sec-
tion 4. The appropriate levels of GA parameters are in-
vestigated in this section. Finally Section 5 consists of
concluding remarks.
2. Mathematical Model
Let be an acyclic Activity on Arrow ((,)GNA
OA )
graph with arrow set and node set, where the
source and sink node are denoted by
, respectively.
( ,,...,)
Nnn n
represents the set of events,
( ,,...,)
aa a
represents the set of activities in a
project PERT netw or k wi t h m nodes andn activities.
Considered notation s are presented as follows:
(, )ij
Activity with i head node and j tail node
Random variable of activity (i, j) duration
Mean duration of activity (i, j) (decisionvariable)
Standard deviation of activity (i, j)
Cost slope of activity (i, j)
Amount of allocated resource to activity (i, j)
Project completion deadline
Upper limit of mean of ith activity.
Lower limit of mean of ith activity.
Total number of paths.
Amount of available budget (i, j).
Number of activities which lie on path r.
Random variable of path r duration.
The mean duration of path r.
The standard deviation of path r.
Cumulative distribution function (CDF) ofnormal
standard distribution.
Generally, the TCTP is a nonlinear optimization prob-
lem. In order to investigate the effect of discount on this
problem, we extract the objective function (project com-
pletion probability) and constraints, separately. The ob-
jective function (OF) is concerned with the maximization
of project completion probability. To construct the OF,
we can write a single path completion probability ac-
cording to the central limit theo rem (CLT), in the fo llow-
ing way:
rij ij
rij ijd
Pr ij
Equation (1) is related to a single path and can’t im-
prove the total project completion probability. Thus,
considering all of the paths, the following objective fun c-
tion is suggested:
MinMax d
,.. L.. (2)
Two type of restrictions should be modeled in a
mathematical formulation to ensure the obtained solu-
Copyright © 2009 SciRes. Engineering, 2009, 1, 1-54
Using (4) we can formulate the cost function for activ-
ity as a mathematical representation, in the following way:
tions satisfy the budget limitation and real conditions.
Each activity can be planned between two maximum and
minimum limit of its mean duration. Following mathe-
matical representation show this type of constraint:
min 1
11 2
22 3
ijijij ij
ijij ijij
ijij ijij
ijijij ij
ijij ijij
It is assumed that each activity needs a unique type of
resource. Using this assumption, in order to model the
budget limitation, we can define the effect of discount on
resource price in a mathematical representation. For this
purpose, cost slope (CS) due to various levels of ij
presented below:
max max
max11 1
() 1
min 1(mi
max1minmin 1min
()()( )
Sijijij ij
ij ij
nkkk nnnn
ij ijij
ijij ijijij ijijij ij
Cij ijk
kk k
ij ijij
ijij ijijijijijijij
 
 
 
 
 
 n) 1
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Using (4) and (5), we can formulate the second con-
straint that satisfies budget limitation, in the following
model help us to use the available extra budget more
efficiently, when we could find suppliers with discount
(6) ()C
ij ij
3. Applying Genetic Algorithm
So, the proposed TCTP can be summarized as a
nonlinear optimization model, as follows:
Genetic Algorithm (GA) is one of the popular metaheu-
ristic algorithms, which can explore the feasible space
using computational intelligence inspired from natural
genetics and evolutionary concepts. It is a search method
based on random selection policy can be used to solve
the nonlinear mathematical programs. In this technique,
an initial populatio n containing several feasib le solutions
(chromosome) is generated randomly. Interesting fact is
that GA does not need a good initial solution. In this
procedure, algorithm starts from an initial solution and
then it would be improved through an evolutionary proc-
ess. After production of initial randomly generated popu -
lation, parents are selected from this primary population
and produce offspring. Second population is a combina-
tion of parent and offspring. The generation procedure
has been done using two effective operators, cross over
and mutation. The crossover is a genetic operator used to
vary the programming of a chromosome or chromo-
somes from one generation to the next and the mutation
operator can prevent th e premature convergence of a new
{1,2,...., }
ij r
ax MinrL
ij r
Subject to:
() ,C
ij ij
M (8)
ctivitiy ijr
  (9)
This is a new formulation of TCTP in PERT networks.
In order to shorten each activity, some amount of extra
resources is needed. This amount of resources may be
provided by external su ppliers, who may determine some
incentive policy such as price discount. Our proposed
TCTP, models this situation. Using this model, project
manager can increase confidence level of on-time project
completion and prevent project delay. Also, proposed
Copyright © 2009 SciRes. Engineering, 2009, 1, 1-54
generation [28]. Desirability of obtained offspring is
investigated using fitness function which is concerned
with objective function and feasibility. The most com-
mon steps for GA follow:
Generate the initial population
Evaluate the fitness of all solutions in popula-
Select parents
Apply the cross over and mutation operators to
produce children
Evaluate the fitness of children
Establish new population using a combination of
parents and children
Until a satisfactory solution has been obtained
About the proposed GA for the discount based TCTP, we
develop the chromosome structure as a simple string of
decision variables. Indeed, each chromosome repre-
sents ij
for all of the activities. Proposed GA algorithm
steps are presented in the fo llowing way:
Initial random population is generated using
uniform random number generator.
Fitness of individuals is evaluated.
Population is ranked in terms of computed fit ness.
Parents are selected randomly.
Cross over and mutation are applied to produce
Produced offspring are evaluated using fitness
Form the new population using half of the fit-
test parent and half of the fittest children .
About the fitness function some points should be men-
tioned. In order to evaluate a solution (chromosome),
two parameter should be investigated, goodness of solu-
tion and meaningfulness of solution. The goodness is
concerned with objective function (project completion
probability) and the meaningfulness indicates the feasi-
bility. According to these parameters the fitness function
can be represented as follows:
1, 2,...,
ij r
itness FunctionMinrL
ij ij
ij projectij r
 
In which, the first term represents feasibility and sec-
ond one is concerned with project completion probability.
would be equal to one, ifl
ijij iju
 &
and otherwise, indicates zero.
ij ij
4. Numerical Example
In order to investigate the performance of the presented
GA approach for the proposed discount based model of
stochastic TCTP, a numerical example are described in
this section. We conducted the proposed approach for the
large scale example with 15 nodes, 20 independent ac-
tivities and 44 interrelated paths to show that how the
presented approach optimally improves the project com-
pletion probability. Characteristics of this network are
presented in Table 2. The objective is to obtain optimal
allocated budget to the activities in order to improve the
all path completion probability from a risky value to a
maximum confident one. It is assumed that the time unit
is in weeks and the co st is in thousan d dollars. Accord ing
to the presented characteristics, initial probability of the
project completion time at Td =150 which can be com-
uted by using the Central Limit Theorem (CLT) is equal
to 55%. This value is related to a situ ation that all activi-
ties are planned in their upper bound of
. The pro-
posed approach attempts to improve this value to a
maximum level using the limited available budget in
order to decrease the risk of project tardiness. It is also
assumed that the available amount of additional budget
for this purpose is equal to 10,000 thousand dollars. We
conducted our analysis of the presented example in two
steps. In first step we run the developed procedure with
the random initial values for parameters of the proposed
GA. Then the obtained results are considered to deter-
mine the efficient values of the parameters in terms of
the accuracy and computation time. For this purpose we
developed a computer simulation program based on the
proposed approach and randomly initial values of GA
parameters have been considered in primary computa-
tional effort. The obtained simulatio n results for the con-
sidered ex ample are organized in Table 1.
To investigate efficiency of the proposed GA ap-
proach, best obtained project completion probability and
CPU time have been considered. In order to make trade
off between the accuracy and computation time, we also
solve the example with the different values of popula-
tion size (k), mutation and cross over probabilities, then
Copyright © 2009 SciRes. Engineering, 2009, 1, 1-54
Table 1. Characteristics of considered example.
compute thecomputation time and efficiency measure.
The appropriate levels of these parameters can conduct
the GA toward optimal solution, directly and therefore,
the analysis of these parameters is an important aspect of
the proposed GA approach. Tables 2, 3 and 4 provide the
behavior of the model results according to different lev-
els of parameters, for presented example.
According to the simulation results provided by Tables
2, 3 and 4 the best prob ability of cross over and mutation
rates are 0.8 and 0.2, respectively and best values of
considered criteria (accuracy and CPU time) obtained by
setting population size at 25-30. In this example the
project completion probability has been improved from
55% to 0.79%.
5. Model Validation
The appropriate levels of the GA parameters have been
investigated in section 4 to reach the accurate results
with reasonable computation time. By using this proce-
dure we reach the maximum capabilities of the proposed
GA approach in terms of accuracy and computational
time, but these maximum capabilities should be compared
Table 2. Model results (objective function) for different
levels of (k = 25).
P Run 1* Run 2 Run 3 Run 4 Best
0.1 0.73900.71420.6952 0.7202 0.7390
0.2 0.69660.64140.7157 0.7377 0.7377
0.4 0.72220.61970.7585 0.6726 0.7585
0.6 0.72470.62530.7822 0.6792 0.7822
0.8 0.70090.69570.7951 0.7823 0.7951
* Each runs containing 200 iterations
Table 3. Model results (objective function) for different
levels of (k = 25).
PRun 1 Run 2 Run 3 Run 4 Best
0.10.71080.75610.6970 0.7896 0.7896
0.20.68760.78570.7952 0.7396 0.7952
0.40.71850.69690.7355 0.7291 0.7355
0.60.68270.68730.6269 0.7565 0.7565
0.80.70070.70670.7477 0.6900 0.7477
Activity l
S 1
S ij
1 8.51 12.32 13.29 14.26 201.59 250.00 265.95 0.25
2 11.60 - 14.56 16.70 - 195.25 225.45 0.60
3 9.56 - 10.05 15.09 - 302.70 321.28 0.45
4 12.95 15.29 16.09 17.77 259.30 295.52 305.04 0.15
5 11.72 12.56 14.05 16.79 252.27 265.33 294.37 0.51
6 11.14 13.00 15.25 16.34 257.84 301.04 326.65 0.67
7 10.43 - 12.05 15.77 - 254.05 295.73 0.65
8 13.43 14.59 17.05 18.15 194.51 201.36 254.00 0.41
9 13.03 15.05 16.32 17.83 241.08 259.32 294.21 0.62
10 12.61 - 15.02 17.50 - 201.51 285.54 0.57
11 9.46 10.25 12.98 15.01 199.65 209.21 225.31 0.14
12 13.22 - 16.02 17.99 - 295.84 309.74 0.03
13 12.41 - 17.02 17.34 - 229.74 276.48 0.24
14 11.32 - 15.25 16.48 - 207.97 257.54 0.10
15 10.17 14.52 15.02 15.57 154.95 174.04 198.74 0.58
16 8.58 10.21 14.09 14.32 174.00 198.32 254.13
17 9.00 - 12.06 14.65 - 205.27 211.37 0.50
18 10.50 11.65 14.21 15.84 298.57 314.45 365.36 0.25
19 9.31 - 14.09 14.89 - 302.12 341.91 0.17
20 9.41 11.64 13.92 14.97 157.37 164.18 187.47 0.63
Copyright © 2009 SciRes. Engineering, 2009, 1, 1-54
Table 4. Model results (computational time, objective function) for different levels of k ().
with other standard solutions which are available in the
literature to validate the solution. Since, this paper is
the first combination of price discount with the TCTP,
there isn’t any standard test problem for the proposed
model, in the published literature. We use the global
optimum solution obtain ed by LINGO software to evalu-
ate the performance of proposed approach. Indeed,
LINGO can handle nonlinear programming problems
involving bo th continuous and binary variables and solve
such problem by generalized reduced gradient (GRG).
For this purpose a mathematical model based on a sin-
gle path of PERT network has been considered. The
results of comparing the proposed GA’s best objective
function (obtained by appropriate levels of GA parame-
ters based on the procedure described in section 4) and
LINGO’s global optimu m for a single path are presented
in Ta ble 5.
According to the Table 5, the proposed GA approach
shows a difference with LINGO’s global optimum with
the average of 1.84%. Such a little difference can be
reliable and shows the good performance of proposed
6. Conclusions
In this paper, we proposed a new approach based on
price discount for TCTP in PERT networks in which
activity durations follow the normal distribution. The
main objective o f the developed model is to improve the
Table 5. Comparing the proposed GA best objective function and LINGO’s global optimum.
Run 1 Run 2 Run 3 Run 4
time Obj.
Func. CPU
Time Obj. Func.CPU
Time Obj. Func.CPU
Time Obj. Func.
CPU T ime Best
5 10.40 0.692 11.24 0.642 9.80 0.716 15.590.701 10.40 0.716
10 16.10 0.722 15.92 0.707 25.21 0.757 20.650.740 15.92 0.757
12 17.41 0.710 16.10 0.735 29.51 0.740 23.620.727 16.10 0.740
18 30.60 0.731 29.25 0.765 39.74 0.788 45.410.751 29.25 0.788
25 40.25 0.758 45.62 0.761 54.30 0.780 42.200.796 40.25 0.796
30 51.50 0.793 47.26 0.757 59.20 0.798 65.200.795 47.26 0.798
Problem Limited Budget (M) Proposed GALINGODifferences (LINGO-GA) % Differences
1 10,000 0.7425 0.7489 0.0064 0.8620
2 15,000 0.7689 0.7909 0.0220 2.8612
3 20,000 0.7849 0.7981 0.0132 1.6817
4 25,000 0.8001 0.8214 0.0213 2.6622
5 30,000 0.8149 0.8236 0.0087 1.0676
6 35,000 0.8311 0.8544 0.0233 2.8035
7 40,000 0.864 0.8764 0.0124 1.4352
8 60,000 0.9049 0.9171 0.0122 1.3482
Average 1.8402 %
Copyright © 2009 SciRes. Engineering, 2009, 1, 1-54
project completion probability from a risky amount to a
maximum value using limited additional budget. To our
knowledge, this is the first combination of price discount
as a supplier’s policy, with the TCTP, in the published
literature. The presented model determines the optimal
additional resources should be allocated to activities
using the genetic algorithm. The GA algorithm has or-
ganized to allocate the available budget to activities. In
order to illustrate the model efficiency, a computer pro-
gram using MATLAB 7.6.0 was developed and the
model was tested on a medium scale PERT network. Best
amount of objective function and CPU time have been
recorded and efficient levels of GA parameters have been
investigated through the several computational experi-
ments. In order to validate the GA approach, proposed
model have been compared with the LINGO’s global
optimum solution and obtained results showed the good
performance of the proposed solution approach.
7. References
[1] W. Herroelen and R. Leus, “Project scheduling under
uncertainty: Survey and research potentials,” European
Journal of Operational Research, Vol. 165, pp. 289–306,
[2] R. A. Bowman, “Stochastic gradient-based time-cost
tradeoffs in PERT networks using simulation,” Annals of
Operations Research, Vol. 53, pp. 533–551, 1994.
[3] G. Abbasi and A. M. Mukattash, “Crashing PERT networks
using mathematical programming,” International Journal o f
Project Management, Vol. 19, pp. 181–188, 2001.
[4] S. Arisawa and S. E. Elmaghraby, “Optimal time-cost
trade-offs in GERT networks,” Management Science, Vol.
18, pp. 589–599, 1972.
[5] L. V. Tavares, “A multi stage non-deterministic model for
a project scheduling under resource consideration,” Euro-
pean Journal of Operational Research, Vol. 49, pp. 92–
101, 1990.
[6] R. L. Bergman, “A heuristic procedure for solving the
dynamic probabilistic project expediting problem,” Euro-
pean Journal of Operational Research, Vol. 192, pp. 125–
137, 2009.
[7] S. Foldes and F. Soumis, “PERT and crashing revisited:
Mathematical generalization,” European Journal of Op-
erational Research, Vol. 64, pp. 286–294, 1993.
[8] L. Sunde and S. Lichtenberg, “Net-present value cost/
time trade off,” International Journal of Project Manage-
ment, Vol. 13, pp. 45–49, 1995.
[9] W. J. Gutjahr, C. Strauss and E. Wagner, “A stochastic
branch-and-bound approach to activity crashing in project
management,” INFORMS Journal on Computing, Vol. 12,
pp. 125–135, 2000.
[10] G. Mitchell and T. Klastorin, “An effective methodology
for the stochastic project compression problem,” IIE
Transaction, Vol. 39, pp. 957–969, 2007.
[11] A. Azaron, C. Perkgoz, and M. Sakawa, “A genetic algo-
rithm approach for the time-cost trade-off in PERT net-
works,” Applied Mathematics and Computation, Vol. 168,
pp. 1317–1339, 2005.
[12] A. Azaron and R. Tavakkoli-Moghaddam, “A multi
objective resource allocation problem in dynamic PERT
networks,” Applied Mathematics and Computation, Vol.
18, pp. 163–174, 2006.
[13] A. Azaron, H. Katagiri, and M. Sakawa, “Time-cost
trade-off via optimal control theory in Markov PERT net-
works,” Annals of Operations Research, Vol. 150, pp. 47–
64, 2007.
[14] P. C. Godinho and J. P. Costa, “A stochastic multimode
model for time cost tradeoffs under management flexibil-
ity,” OR Spectrum, Vol. 29, pp. 311–334, 2007.
[15] W. Crowston and G. L. Thompson, “Decision CPM: A
method for simultaneous planning, scheduling, and con-
trol of projects,” Operations Research, Vol. 15, pp. 407–
426, 1967.
[16] E. Demeulemeester, S. E. Elmaghraby, and W. Herroelen,
“Optimal procedures for the discrete time/cost trade-off
problem in project networks,” European Journal of Op-
erational Research, Vol. 88, pp. 50–68, 1996.
[17] E. Demeulemeester, B. De Reyck, B. Foubert, W. Herroe-
len, and M. Vanhoucke, “New computational results on
the discrete time/cost trade-off problem in project net-
works,” Journal of the Operational Research Society, Vol.
49, pp. 1153–1163, 1998.
[18] D. R. Robinson, “A dynamic programming solution to
cost-time tradeoff for CPM,” Management Science, Vol.
22, pp. 158–166, 1975.
[19] M. Vanhoucke and D. Debels, “The discrete time/cost
trade-off problem: Extensions and heuristic procedures,”
Journal of Scheduling, Vol. 10, pp. 311–326, 2007.
[20] I. Cohen, B. Golany, and A. Shtub, “The stochastic time–
cost tradeoff problem: a robust optimization approach,”
Networks, Vol. 49, pp. 175–188, 2007.
[21] D. R. Fulkerson, “A network flow computation for pro-
ject cost curves,” Management Science, Vol. 7, pp. 167–
178, 1961.
[22] P. S. Pulat and S. J. Horn, “Time-resource tradeoff prob-
lem,” IEEE Transactions on Engineering Management,
Copyright © 2009 SciRes. Engineering, 2009, 1, 1-54
Vol. 43, pp. 411–417, 1996.
[23] E. B. Berman, “Resource allocation in PERT network
under activity continuous time-cost functions,” Manage-
ment Science, Vol. 10, pp. 734–745, 1964.
[24] R. Lamberson and R. R. Hocking, “Optimum time com-
pression in project scheduling,” Management Science,
Vol. 16, pp. B597–B606, 1970.
[25] J. Falk and J. Horowitz, “Critical path problems with
concave cost-time curves,” Management Science, Vol. 19,
pp. 446–455, 1972.
[26] R. Kelley, “Critical-pathplanning and scheduling: Mathe-
matical basis,” Operations Research, Vol. 9, pp. 296–320,
[27] P. Vrat and C. Kriengkrairut, “A goal programming model
for project crashing with piecewise linear time-cost trade-
off,” Engineering Costs and Production Economics, Vol.
10, pp. 161–172, 1986.
[28] I. Kaya, “A genetic algorithm approach to determine the
sample size for control charts with variables and attrib-
utes,” Expert Systems with Applications, Vol. 36, pp.
8719–8734, 2009.