In recent years, the range of project management applications has greatly
expanded. Project management concerns the scheduling and controlling of
activities (tasks) in such a way that the project can be completed in
as little time as possible. To ensure the project`s success, the project
management team must identify the stakeholders, determine and manage their
needs and expectations. A project network is defined as a set of activities
that must be performed according to precedence constraints stating that
the activities must start after the completion of specified other activities.
In the project network, the nodes represent activities and the arcs represent
precedence relations. A path through a project network is one of the routes
from the starting node to the ending node. The length of a path is the
sum of the durations of the activities on the path. The project duration
equals the length of the longest path through the project network. The
longest path is called the critical path in the network. In order to specify
the critical path in project networks in the traditional models, the durations
of activities (tasks) are represented as crisp numbers. However, the operation
time for each activity is usually difficult to define and estimate precisely
in a real situation. The aim of this study is to present an analytical
method to specify the critical path in a project network with continuous
fuzzy activity durations by use of the longest path algorithm. Two types
of continuous and discrete fuzzy number can be used for the duration of
the project activities. This study investigates specifically the continuous
fuzzy problems and their applications in project network.
The longest path problem concentrates on finding the path with maximum
distance, time or benefit or other variables. And it is one of the basic
problems in networks and is widely applied in transportation, communication
and computer network and has been studied extensively in the field of
computer science, operation research, transportation engineering and so
The aim of the longest path problem is to find longest path between:
(1) two given nodes of a graph, (2) a given node to all other nodes and
(3) all pair of nodes. The bellman algorithm is one of the efficient algorithms
used to determine the longest and/or shortest path in a crisp network.
In real problems, uncertainty cannot be avoided and usually, the arc
lengths cannot be determined precisely. For instance, on road networks,
for several reasons, e.g., traffic, accidents, arc lengths representing
the vehicle travel time are subject to uncertainty. In these cases, deterministic
values for representing the arc weights cannot be used. A typical way
of expressing these uncertainties in the arc weights is to utilize probability
theory. However, sometimes the probability distributions of the lengths
of arcs are difficult to acquire due to lack of historical data. In dealing
with such case, the expert, using the fuzzy theory as a powerful tool,
estimate the approximate lengths of the arcs.
In this study, in order to present more rational and applicable conclusions
for decision makers, we will propose fuzzy PERT Bellman (FPE-Bellman)
algorithm by the use of the fuzzy sets, PERT technique and Bellman algorithm
to determine the longest path in the continuous fuzzy problems.
FUZZY SETS AND NOTATIONS
The concept of fuzzy sets was first introduced by Zadeh in 1965 to deal with
the issue of uncertainty in systems modeling (Dubios and Prade, 1980; Zimmerman,
1991; Kaufmann and Gupta, 1991; Klir and Yuan, 1995). Zadeh chose the membership
functions for these sets. Figure 1 shows the membership measurement
scale of the elements of the fuzzy set A and opposite A (A`). Sets A and A`
are basis of fuzzy theory.
Zadeh defined Fuzzy sets as sets with boundaries that were not precise.
The membership in a fuzzy set is not a matter of affirmation or denial,
but rather a matter of degree, he said (Dubios and Prade, 1980; Zimmerman,
1991; Kaufmann and Gupta, 1991; Klir and Yuan, 1995).
The degrees of membership in fuzzy sets are most commonly expressed by
numbers in the closed unit interval [0,1]. Thus fuzzy sets express gradual
transitions from membership (membership value of 1) to non-membership
(membership value of 0) and vice versa.
Let, X is a space of positive real values associated with a variable
and x is a generic element of X. Mathematically, a fuzzy set A in X is
defined as the set of ordered pairs (Klir and Yuan, 1995):
where, M is the membership space and usually assumed to vary in the interval
||Representation of fuzzy sets
The α-cut of the fuzzy set A is the crisp set αA
that contains all the elements of the universal set X whose membership
grades in A are greater than or equal to the specified value of α
(Klir and Yuan, 1995):
The strong α-cut of a fuzzy set A is the crisp set α+A
that contains all the elements of the universal set X whose membership
grades in A are greater than the specified value of α (Klir and Yuan,
The support of a fuzzy set A within a universal set X is the crisp set
that contains all the elements of X that have nonzero membership grades
in A (Klir and Yuan, 1995).
The most commonly used shapes for fuzzy numbers are the triangular and
trapezoidal (Fig. 2, 3). Working with
triangular fuzzy number is easier with trapezoidal fuzzy number.
||Trapezoidal fuzzy number
||Triangular fuzzy number
other hand, performing the arithmetic operations on both triangular and
trapezoidal numbers are the same. Therefore, in this study, triangular
fuzzy numbers are used to implement the proposed algorithm.
α and β are the least and the most desirable bound values,
respectively. m is the center of fuzzy number. Therefore the membership
function of the triangular fuzzy number ã = (m,α,β) is:
The lengths of arcs in the continuous fuzzy longest path problems are
expressed by the triangular or trapezoidal fuzzy numbers with continuous
membership function. Thus, in this type of project management fuzzy networks,
the duration of performing the activities is expressed by continuous fuzzy
be two fuzzy numbers. Then the fuzzy sum of these two numbers
is given by (Kaufmann and Gupta, 1991; Klir and Yuan, 1995):
A variety of methods for ordering and ranking fuzzy numbers has been
proposed by Cheng, (1980), Delgado et al. (1988), Ishibuchi and
Tanaka (1990), Sengupta and Pal (2000) and Wang and Kerre (2001a, b) that
decision makers can choose their own appropriate method from the list.
In present study we will consider generic ranking indexes for continuous
Liou and Wang index (Liou and Wang, 1992): This index is defined
and λε[0,1] is a degree that might reflect the decision maker`s
García and Lamata index (García and Lamata, 2005):
This index improves the discrimination between fuzzy numbers and is defined
where, δε[0,1] is a modality index and λε[0,1] is
an optimism degree. Therefore, .
Nayeem and Pal index (Nayeem and Pal, 2005): If
be two fuzzy numbers, then it is defined as:
If we use this index, the proposed algorithm may yield more than one solution.
This is only possible if the centers of the numbers are equal.
Ranking Function (RF) (Cheng, 1980; Seda, 2006): If ;
then two inverse functions for each fuzzy number are defined as follows:
from above equations, RF is defined as:
LITERATURE REVIEW IN FUZZY PROJECT MANAGEMENT NETWORK
Here, previous studies on fuzzy project management network are reviewed.
FPERT was first presented by Chanas and Kamburowski (1981), who used fuzzy
numbers to represent activity durations in project networks. The possibility
distribution of the project completion time is derived from the possibility
distributions of the duration of individual activity. The fuzzy α-cut
is then applied to calculate the upper and lower bounds on the completion
time of the project network. In this situation, there is no effective
way to indicate the critical activities and paths for a project network.
Mon et al. (1995) assumed that the duration of each activity is
a positive fuzzy number. Using the α-cut of each fuzzy duration,
they denoted the lower and upper duration bounds. These researches exploited
a linear combination of the duration bounds to represent the operation
time of each activity and to determine the critical activities and paths
by use of the traditional (crisp) PERT technique. However, the α
values would yield different critical activities and paths in this approach.
Shipley et al. (1997) proposed BIFPET technique using fuzzy probability
instead of the beta distribution. In this work, there is no new algorithm
to indicate the critical activities and paths for a project network.
Chanas and Zielinski (2001) proposed a natural generalization of the
criticality concept for project networks with interval and fuzzy activity
times, in which two methods of calculating the degree of possible criticality
and some results are provided. However, as generally known, in deterministic
environments, the critical path can be varied as activity times are varied
in an interval. Clearly, this is indeed true under different possibility
levels in fuzzy environments and it is possible that more than one critical
path should be found at a certain possibility level. Therefore, the results
of examples reported in provided only crisp solutions (Chanas and Zielinski,
Liberatore and Colleny (2001) proposed a new straightforward method for
applying fuzzy logic to assess uncertainty in critical path analysis.
They defined the belief value, based on the meaning of the vague notion
of membership an object versus an object with membership value of 1. Then
they generalized the crisp concept of critical path length to the situation
where fuzzy logic is used to represent the activity times. Critical path
length was the maximum of the belief values over all cases having
this critical path length.
Chanas et al. (2002) proposed a series procedure for necessarily
critical activities. Chanas and Zielinski (2002) assumed that the operation
time of each activity can be represented as a crisp value, interval or
a fuzzy number and discussed the complexity of criticality. The calculation
procedure of Mon et al. (1995) is the same.
In Dubois et al. (2003) and Zielinski (2005) solution methods
for computing the intervals of possible values of the latest starting
times and floats of activities with imprecise durations represented by
fuzzy or interval numbers have been proposed. They are straightforward
extensions of deterministic critical path.
Dubois et al. (2003) proposed several heuristics for computing
the sets of possible values of the latest starting times and floats of
activities. In these methods, the lower or upper bound for duration of
an activity was assumed and then like to crisp methods, the lower or upper
bound of latest starting time and floats of activities are specified.
Therefore, in each stage of these methods, the result is a crisp number.
Zielinski (2005) noted that the backward recursion fails to compute the
sets of possible values of the latest starting times and floats of activities.
Moreover, for the same path, different definitions of the fuzzy critical
path give different estimations of the degree of criticality. Zielinski
(2005) developed new polynomial algorithms to determine the intervals
of the latest starting times in the general network.
Chen (2006) proposed a linear programming to find the critical path in
fuzzy activities network in α-cut different levels. In this model,
all fuzzy activity durations are calculated based on the three time estimates
and there is no way to indicate the latest and earliest starting time
and floats for activities of a project network.
Chen and Huang (2007) used the triangular fuzzy numbers to express the
operation times for all activities in a project network and a new model
was proposed that combines fuzzy set theory with the PERT technique to
determine the critical degrees of activities (tasks) and paths, latest
and earliest starting time and floats. But there exists no new algorithm
to determine the critical path.
In this study, we will propose fuzzy PERT Bellman (FPE-Bellman) algorithm
is proposed by the use of fuzzy sets, PERT technique and Bellman algorithm
to specify the critical path and the fuzzy earliest (ES)/latest (LS) starting
time and floats of activities in the continuous fuzzy network. Calculations
of the ES and LS in this algorithm are based on Chen and Huang`s study
(Chen and Huang, 2007). Inputs and outputs of the proposed algorithms
are fuzzy numbers and this algorithm is able to compute the fuzzy Error
Time (ET) and occurrence probability of this error time (ETP). This subject
is first introduced in this study and has not been considered yet. The
complexity of this algorithm is the indicator its excellent performance.
It is worth noting that above all this algorithm calculates the ES, LS,
ET, ETP and float times simultaneously, when it is implemented.
FINDING THE CRITICAL PATH USING PROPOSED ALGORITHM (FPE-BELLMAN ALGORITHM)
The aim of finding the critical path in project management networks is
to determine a path with longest time. Therefore, the aim of this study
is to investigate the critical path using continuous fuzzy duration for
the activities of a project. To do this, an example is presented to compare
with those obtained using the proposed algorithm as well as crisp models.
Utilizing of fuzzy theory, decision makers can come up with more rational
and realistic decisions in the future.
In this study, Bellman algorithm has been used to specify the longest
path in project network. This algorithm is a subset of shortest path algorithms
that have been designed for finding the shortest path in a network with
exact and crisp duration of arcs (Hernandes et al., 2007). Two
more important challenges in these algorithms are calculating the sum
of labels and comparing the two labels when the duration of activities
is expressed by fuzzy numbers, sum of the fuzzy numbers and their comparison
are performed by indexes. Table 1 shows the FPE-Bellman
algorithm`s notations. This algorithm is suitable to discover the fuzzy
longest path in a fuzzy network.
The ES and LS of the activities of a project are important assessments
that are driven from project`s activities network. Then, fuzzy Total Floats
(TF) and Fuzzy Free Floats (FF) of activities are calculated by ES and
LS. These times assisted an analyzer to identify the critical path and
critical activities. Activity with TF = FF = 0 lies on the critical path
and such an activity that lies on all critical paths, is a critical activity
that a change in its duration affects the project completion time. The
proposed algorithm calculates ES, LS and float times by applying the proposed
method in (Chen and Huang, 2007).
Different phases of proposed algorithm are as follow:
Step 0: [Initialization]
In this step a zero triangular fuzzy number belong to all events in the
||Notations in FPE-Bellman algorithm
Step 1: [Determination of fuzzy distance and calculating the earliest
starting time of events]
In this step the labels of events are compared on the basis of the adopted
ranking index and then ES of events is calculated.
Step 2: [Stop criterion]
This step is run for all events and activities (arcs). Note that the
project network is an acyclic network. Therefore, positive cycle means
that there exists a mistake in precedence constraints between the activities
of the project.
Step 3: [Determination of longest path from event 1 to event i
(i = 2, 3,
, r-1) by the use of ]
In this step, maximum fuzzy label belong to event i in the it = r.
Step 4: [Determination of longest path from event 1 to event r
by the use of ]
In this step, maximum fuzzy number μiεΩ is
elected for μC.
Step 5: [Calculating the latest starting time of events]
This step is run for all events and activities (arcs) and by backward
recursion we can computed the LS, TF and FF of activities.
Step 6: [Calculating the error time]
ETP means that it may that project completion time exceed of μC
to size of ET.
Suppose Dmax is the maximum number of labels of all the events.
In step 1.2, we have a maximum of rDmax additions to calculate
the cost for each path. In step 1.3, we have the maximum rD2max
comparisons of labels. These computations are the same for step 5 of the
algorithm. Thus, for each iteration, we have a complexity of O(rD2max)
and since the proposed algorithm executed in (r-1) iterations, the complexity
of the algorithm is:
A NUMERICAL EXAMPLE
In order to use of the proposed algorithm in determining the critical
path, we should impose a series changes in precedence networks of activities.
||Network of a Design-Build project
||Duration of activities
This network obtained either by performing an activity-on-arc graph or
by split each node up two nodes. Here, the second method was utilized
and expressed those changes by a numerical example. Suppose we have a
Design-Build project and precedence constraints of this project have been
defined as shown in Fig. 4.
Table 2 shows the duration of the activities of the
Design-Build project by triangular fuzzy numbers. Optimistic (α),
most-likely (m) and pessimistic (β) times are determined by decision
For this illustrative project, traditional PERT technique that uses crisp
activity times find two critical paths namely A-B-D-F-G and A-C-F-G with
duration time of 73 time units.
In Fig. 5, each event has been split up two events.
Arc (i, i`) is activity i and its duration corresponds to Table
2 and the duration of other arcs is a zero triangular fuzzy number.
The proposed algorithm was implemented in MATLAB 7 language by the ranking
indexes Liou and Wang`s (LW) for λ = 0, 0.5 and 1; Lamata and García
(LG) for δ = 0, 0.5 and 1 and λ = 0, 0.5 and 1; Nayeem and Pal
(NP) and Ranking Function (RF). When the algorithm is executed, we have
the following critical paths from event A to G` (Table 3).
The functions that have been used for each fuzzy number in Liou and Wang
(LW) and Lamata and Garcla (LG) indexes are defined as follows:
||Results of execution of the proposed algorithm
In ranking function index (RF), the all Integrals have been expressed
clearly, except in the following integral that is:
The paths A-B-D-F-G and A-C-F-G are critical paths based on the different
indexes (Table 3). Figures 6-10 show
the phases of execution of proposed algorithm based on the RF index. In
Fig. 10 and 11, the results of implementation
of FPE-Bellman algorithm in determination of two critical paths are comparable.
Figure 11 shows the result of execution of proposed
algorithm in determining the critical path A-C-F-G.
Figure 12 shows the fuzzy numbers of the critical
paths and error time and probability of its occurrence.
Since β2>β1, the project completion
time to size of ET = β2−β1 = 53−52
= 1 time may be longer than μC by probability of ETP =
0.033. This probability is computed as follows:
Table 4 and Fig. 13 show the ES,
LS, TF and FF of activities based on the RF index in our example. In Fig.
13 critical path has been specified by bold lines.
Fuzzy free float time (0,1,-1) for activity C means that if the duration
of this activity change to (6,4,14)+(0,1,- 1) = (6,5,13), project completion
time will not change.
||Splitted up network
||Steps 1, 2 of execution of algorithm
||Step 3 of execution of algorithm
||Steps 4-7 of execution of algorithm
||Step 9 of execution of algorithm
||Steps 10-15 of execution of algorithm (determination
of critical path A-B-D-F-G)
||Determination of critical path A-C-F-G
||Floats and earliest/latest starting time
||Fuzzy numbers of the critical paths
||Earliest/latest starting time
The results of the execution of FPE-Bellman algorithm in Table
3, 4 based on the RF index are the same. In Table
4, activities A, B, D, F and G have zero float time and based on the
results in the Table 3, activities A, F and G are critical
activities. Since center of float time of activity C is zero, this activity
might be considered as an activity that lies on the critical path. This
has occurred in path A-C-F-G.
PERT is the most widely used technique for planning and coordinating
large-scale projects. The main assumption in PERT is that the activity
durations in a project can be estimated precisely and that they are statistically
independent. As a result, in cases where this assumption does not hold,
PERT appears to lead to poor estimation and inadequate management responses.
In this study, fuzzy theory and, therefore, FPE-Bellman algorithm were
employed to overcome this problem. Triangular fuzzy numbers were used
to represent the activity durations in a project network. By the proposed
algorithm, the starting, finishing and floating time for each activity
In some indexes, the results of implementation of the proposed algorithm
were the same as the results of traditional PERT technique yielding two
critical paths while other indexes yield just one of the critical paths.
This means that validation of conclusions of the proposed algorithm is
at least the same as that of the conclusions of crisp models. But since
imprecise data can be entered in fuzzy theory and the independence assumption
isn`t considered in fuzzy sets, conclusions of fuzzy models in large-scale
projects are more rational and more applicable than results of crisp models.
In other words, decision makers can model their experiences among activity
durations and express expressions such as may be, about,
nearly and other linguistic variables for activity durations,
whereas this specifications do not exist in crisp models. The comparisons
reveal that the use of fuzzy models is more effective in determining the
critical path and floats in a real project network.