Time cost trade off problem is one of the highly important issues in
project accomplishment and has been ever taken into consideration by project
managers. Time and cost as two critical objectives of construction project
management, are not independent but intricately related. Trade-off between
project duration and total cost are extensively discussed in the project
scheduling literature because of its practical relevance. It is generally
realized that when project duration is compressed, the project will call
for an increase in labor and more productive equipment and require more
demanding procurement and construction management and then the cost will
increase. Time-cost optimization may be defined as a process to identify
suitable construction activities for speeding up and for deciding by how
much so as to attain the best possible savings in both time and cost.
Since there is a hidden tradeoff relationship between project time and
cost, it might be difficult to predict whether the total cost (i.e., the
direct and indirect costs) would increase or decrease as a result of the
schedule compression. Since different combinations of possible durations
and costs for the activities can be associated with a project, the problem
is which of these combinations are the best. Determining the best sets
is the goal of time-cost optimization.
Various methods such as heuristic methods and mathematical programming
models have been proposed in recent decades to be applied to construction
time cost optimization. Heuristic methods are based on rules of thumb,
which generally lack mathematical rigor (Siemens, 1971; Moselhi, 1993).
Mathematical programming methods convert the time cost trade off to mathematical
models and utilize linear programming (Pagnoni, 1990; Liu et al.,
1995), integer programming or dynamic programming (De et al., 1995).
Less attention of recent researchers to these methods, insufficiency of
them in discontinuous decision space and successful development and application
of meta heuristic optimization algorithms for solving single objective
optimization problems in recent years, has attracted the attention of
researchers to investigate the possibility of their application to solve
multi objective optimization problems.
There exist numerous difficulties and complexities in applying meta heuristic
algorithms to solve multi objective problems and Feng et al. (1997),
Li and Love (1997, 1999), Hegazy (1999) and Zheng et al. (2005)
have engaged in appropriate use of these methods during past 2 decades.
In this regards, different versions of GAs have successfully been applied
to optimize time cost problem.
Uncertainties in the problem have received less attention due its complexity.
Therefore, most of the studies have been focused on deterministic problems.
In real construction projects however, cost of activities may face significant
changes due to existing uncertainties such as inflation, economical and
social stresses, execution errors of contractor, design errors, natural
events such as climate changes, etc. Therefore, total cost of project
may differ significantly because of these uncertainties.
In this study, a new approach has been investigated in solving time-cost
trade off problem. Fuzzy logic theory is employed to consider affecting
uncertainties in total direct and indirect cost of a construction project.
To obtain appropriate solutions, genetic algorithm has been employed as
an optimizer where uncertainties are considered through fuzzy logic representation.
Project manager can also have different non-dominated solutions or pareto
solutions which are dependent on his measure of accepted risk through
applying α cuts methods in fuzzy logic theory. A case study through
which considerable conclusions is drawn is finally investigated.
Non-dominated Sorting Genetic Algorithm (NSGA): A Genetic Algorithm
(GA) is a search technique used to find true or approximate solutions
to optimization and search problems (Deb, 1999). Genetic algorithms are
categorized as global search heuristics approach. GAs are implemented
as a computer simulation in which a population of abstract representations
(called chromosomes) of candidate solutions (called individuals) to an
optimization problem evolves toward better solutions. The evolution usually
starts from a population of randomly generated individuals and forming
a generation. In each generation, the fitness of every individual in the
population is evaluated, multiple individuals are stochastically selected
from the current population (based on their fitness) and modified (crossover
and possibly mutation) to form a new population. The new population is
then used in the next iteration of the algorithm. Commonly, the algorithm
terminates when either a maximum number of generations has been produced,
or a satisfactory fitness level has been reached for the population.
Non-dominated Sorting Genetic Algorithm (NSGA) is a multi objective optimization
algorithm and provides a trade-off between the various objectives considered
(Deb, 1999). NSGA basically differs from simple genetic algorithm in the
way the selection operator works. Crossover and mutation operators may
be used without any modification. Before the selection is performed, the
population is ranked on the basis of an individual`s non-domination. The
non-dominated individuals present in the population are first identified
from the current population. Then, all these individuals are assumed to
constitute the first non-dominated front in the population and assigned
a large dummy fitness value. The same fitness value is assigned to give
an equal reproductive potential to all these non-dominated individuals.
||Fuzzy presentation of indirect cost
These non-dominated individuals are ignored temporarily to process the
rest of population in the same way to identify individuals for the second
non-dominated front. These new set of points are then assigned a new dummy
fitness value which is kept smaller than the minimum dummy fitness of
the previous front. This process is continued until the entire population
is classified into several fronts.
Fuzzy logic: A fuzzy set can be defined mathematically by assigning
to each possible individual in the universe of discourse a value representing
its grade of membership in the fuzzy set. This grade represents the degree
to which that individual is similar or compatible with the concept represented
by the fuzzy set. Thus, an individual may belong in the fuzzy set to a
greater or lesser degree as indicated by a larger or smaller membership
grade. These membership grades are very often represented by real-number
values ranging in the closed interval between 0 and 1.
A fuzzy number is a fuzzy membership function that is both convex and normal.
Fuzzy numbers are written in the form of a domain value and its corresponding
confidence level. Figure 1 shows an example of a triangle
and a normal fuzzy number. A fuzzy number can be considered a generalization
of the concept of interval of confidence. Therefore, the mathematical operations
of fuzzy numbers (i.e., addition, subtraction, multiplication and division)
can be processed using the concepts of the interval of confidence.
For instance, the set of linguistic variable (A) around 500 as shown
in Fig. 1 can be normalized as:
where, X is the range of possible values and μA(x) is
the membership function taking values from [0,1], specifying to what degree
x belongs to the fuzzy set A.
The α cut is a commonly used method to connect the principles of
fuzzy sets with a collection of crisp sets, which can in turn be fed into
most of the existing systems. The α-cut level set or α-level
cut of A is the set:
The α represents the degree of risk that the managers is prepared
to take. Since the value of α could severely influence the non dominated
solutions, its choice should be carefully considered by decision makers.
As a result, a general survey which aims at identifying the relationship
between the value of α (i.e., 0 to 1) and the corresponding risk
level (i.e., no risk to full risk) by collecting the risk attitudes of
managers would be indispensable.
PROPOSED MODEL STRUCTURE
In solving Time cost trade off problem, for each activity, different
options are considered with different times and costs. In reality due
to different uncertainties involved cost of each option is not a crisp
value. In another words, the actual cost of each option is not certainly
known for the manager in advance. However, after project execution, they
will be known. Lund calls them single value unknown parameter. It means
that even though these parameters are subject to some uncertainties at
the early stages of the project developments yet, they will receive a
known crisp value after project completion and remains unchanged. To apply
cost of each option may be well considered employing fuzzy set theory.
So, the number presented for each activity cost is a fuzzy one.
A triangular fuzzy number (=
(c1, c2, c3)) may be assigned for the cost of that activity. Defining
c1, c2 and c3 as optimistic, pessimistic and the most probable cost for
an activity, respectively. To solve time-cost trade off problem, some
options can be chosen for cost of each activity. For example, if there
exist 7 activities and 5 options for each activity, then 57
sets of solutions will exist. Therefore, genetic algorithm is applied
to obtain optimal solutions of the problem. Length of chromosome or number
of genes equals to the number of activities and value of each gene is
the option considered for fulfillment of the corresponding activity.
In this model, employing critical path concept and considering predecessor
activities in network, project termination time for each trial solution
was also determined. For each randomly generated trial solution, the total
cost as a fuzzy number was determined by fuzzy summation of costs of the
options in the alternative. Assume that
are two fuzzy costs and their α cuts are presented as C1α and
C2α. The sum of these two numbers would be as follows:
Model has the ability to easily calculate the total project cost. Total
project cost will be obtained by multiplying daily cost (indirect cost)
by project execution time and adding this product to the relevant direct
cost. Daily cost of project could be in the form of a crisp value or a
fuzzy number. Model is capable of accounting for both crisp and/or fuzzy
indirect costs. If the indirect cost is fuzzy numbers, fuzzy mathematical
equations will be employed to multiply these numbers because cost is fuzzy
number and time is crisp number. Assume that
is fuzzy number and T is crisp number, the multiplication of these two
numbers would be as follows:
After multiplying indirect cost to time in a fuzzy manner using above
mentioned equations and adding the indirect cost to direct cost in a fuzzy
manner (Eq. 5), total cost which is a triangular fuzzy
number will be obtained.
Therefore, there is a crisp value for total project time and a fuzzy
one for total cost of project. In order to find dominated and non-dominated
solutions, it is necessary to make a comparison between the times and
the costs of chromosomes. In this situation, fuzzy numbers comparison
and ranking methods are applied because costs are fuzzy numbers. Considering
uncertainty essence of the costs and the fact that costs are triangular
fuzzy numbers, a method base on Hamming distance (dH) between
two fuzzy numbers
is defined as follows:
The major idea is to find a fuzzy number as which
is greater than deterministically.
It is obvious that can
not be closed uniquely. can
be selected as MAX(),
a fuzzy number which defined as follows:
So, if hamming distance between
is greater than corresponding distance between ,
it can be concluded that
is greater than .
||The schematic diagram of the proposed model
The cost and time of project termination for each alternative solution
(chromosome) can be compared with other (chromosomes) binarily using fuzzy
numbers comparison method based on hamming distance.
Concepts addressed in NSGA were used to define selection operator. In
the first generation, each solution is assigned fitness equal to its non-domination
level (i.e., 1: corresponds to the best non-domination level, 2: to the
next best level and so on).
To produce population of the next generation, non-dominated solutions
from the previous generation are directly transferred to form part of
the population for the new generation. Tournament selection is used to
select parent chromosomes for crossover and mutation to complete the population
size with reproduced offsprings. The process will continue until a desirable
a set of non-dominated solutions (i.e., pareto front) is achieved. The
schematic diagram of the suggested model is shown in Fig.
Advantage of this model in comparison with similar ones lies on the method
that, uncertainties in project cost are demonstrated aggregated and interpreted.
Triangular fuzzy values are assumed for any individual option with total
cost being presented as a fuzzy number. So, when project manager chooses
his optimum solution, he would face a total cost and corresponding membership
function ahead that considerably help him to make appropriate decisions
based on his own level of risk acceptance.
The project manager may apply his own risk acceptance level to obtain
a new pareto front with new non-dominated solutions using α cuts
property. When he dose not want to risk, he would assign zero for α
and therefore, costs of project activities, direct cost and total cost
obtained for the project may be subject to high range of changes. When
project manager wants to fully risk (i.e., 100%), he sets α equal
to 1 and so, costs of project activities, direct cost and total cost would
be transformed from a fuzzy value to a crisp one and problem would enter
into a crisp space from a fuzzy one. In this situation, uncertainties
in cost estimation would be practically ignored. Determination of α
(i.e., accepting different risk percentage), would lead to different pareto
To demonstrate the concept and test the performance of the proposed model,
a simple case example was adopted from Zheng et al. (2004). It
consists of 7 activities with different possible options. The cost data
reported by Mr. Dasiy X.M. Zheng et al. (2004) were assumed associate
with the most probable condition with membership of 1; while for the minimum
and maximum cost for any option cost values were assumed to form the triangular
membership functions. Adopted and assumed values for cost of options along
with other required data for 7 activity project are shown in Table
1. Assumed value for indirect cost is shown in Fig.
The example has been solved for different values of α cuts. Assuming
α = 1, disregards uncertainties and solve the model in an absolutely
crisp space. In this case, it is expected to obtain the same solution
reported by previous researcher for a fully crisp problem. The same problem
was approached by Zheng et al. (2004, 2005) in a fully deterministic
environment (i.e., α = 1), employing Modified Adaptive Weighted Approach
(MAWA). Their results are shown in Table 2. As is clear,
the proposed approach has dominated the solution for duration of 62 days,
as well as providing one more non-dominated solutions for 60 days of project
To demonstrate the pareto front in a time-cost coordinate system, fuzzy
cost will be transformed to a crisp value through application of center
of gravity defuzzifier. Therefore, if total fuzzy cost ()
is covered by membership function A, the center of gravity defuzzifier
defines point C* as the center of region which is covered by A. For α
= 1, value of C* will represent the total cost of the project in fully
Fuzzy costs related to α = 0, α = 0.5 and α = 1 have been
transformed to crisp values by center of gravity defuzzifier and pareto
fronts in a time-cost coordinate system are shown in Fig.
3 and Table 3.
||Time and cost data for case example
||Non-dominated solution; MAWA vs. proposed model for
α = 1
||Non-dominated set of different α cuts
The lower the α, the higher
the total cost for any given time has been resulted. In another words,
pareto front moves upward as it value of α approaches to zero. This
issues means that for the lower risk, the higher cost would be accrued
for project execution. In this case total cost will have smaller range
of changes. However, assuming bigger values for α associates with
the higher risk acceptance, which results in the lower cost with quite
the larger range of changes. This is the major benefit of this model application.
The example can be solved for different values of α cuts for direct
and indirect cost. It means that, project manager may apply different
risk acceptance level for direct cost and indirect cost separately.
||Pareto fronts for different α cuts
||Pareto fronts (α = 0.2 for direct costs, α
= 0.2 and α = 0.9 for indirect cost)
shown in Fig. 4, the project manager may apply his own
risk acceptance level for direct cost to obtain the relevant pareto fronts.
Trade-offs between project duration and total cost are extensively discussed
in the project scheduling literature because of its practical relevance.
In a real construction project, cost of each activity and daily cost change
as a result of many uncertainties such as inflation, economical and social
stresses, execution errors of contractor, design errors, natural events.
The model adopts fuzzy sets to simulate the degree of uncertainty of the
input data. The incorporation of fuzzy sets theory in TCO problems is
therefore a sensible step to emulate the decision-making process of human
experts based on a set of uncertain or incomplete data. To find dominated
and non-dominated solutions, fuzzy numbers comparison is applied because
costs are fuzzy numbers. Non-dominated Sorting Genetic Algorithm (NSGA)
is used for extraction the pareto front. Unlike the traditional models
which focus primarily on the deterministic TCO problem, this model has
the ability to adapt to deterministic and uncertain environment by changing
the value of α. The project manager can apply his own risk acceptance
level to obtain a new pareto front with new non-dominated solutions using
α cuts property. For any given time, the lower the α, the higher
the total cost has been resulted. Project manager can apply different
risk acceptance level for direct cost and indirect cost separately.