A Counterexample to the Forward Recursion in Fuzzy Critical Path Analysis Under Discrete Fuzzy Sets

International Journal of Fuzzy Logic Systems (IJFLS) Vol.6, No.2,April 2016
DOI : 10.5121/ijfls.2016.6204 53
A COUNTEREXAMPLE TO THE FORWARD
RECURSION IN FUZZY CRITICAL PATH
ANALYSIS UNDER DISCRETE FUZZY SETS
Matthew J. Liberatore1
1
Department of Management and Operations, Villanova School of Business, Villanova
University, Villanova, PA 19085
ABSTRACT
Fuzzy logic is an alternate approach for quantifying uncertainty relating to activity duration. The fuzzy
version of the backward recursion has been shown to produce results that incorrectly amplify the level of
uncertainty. However, the fuzzy version of the forward recursion has been widely proposed as an
approach for determining the fuzzy set of critical path lengths. In this paper, the direct application of the
extension principle leads to a proposition that must be satisfied in fuzzy critical path analysis. Using a
counterexample it is demonstrated that the fuzzy forward recursion when discrete fuzzy sets are used to
represent activity durations produces results that are not consistent with the theory presented. The
problem is shown to be the application of the fuzzy maximum. Several methods presented in the literature
are described and shown to provide results that are consistent with the extension principle.
KEYWORDS
critical path analysis, discrete fuzzy sets, forward recursion, counterexample, project scheduling
1. INTRODUCTION
CPM or the critical path method [11] has been successfully applied to plan and control projects
that are organized as a set of inter-related activities. PERT or Program Evaluation and Review
Technique [16] and Monte Carlo simulation apply probability analysis to address situations where
there is uncertainty related to activity duration. PERT models uncertainty by collecting
optimistic, most likely and pessimistic duration estimates of all activities and makes certain
assumptions about the underlying probability distributions. Since the basic version of PERT
tends to underestimate the expected minimum project duration [15]. Monte Carlo simulation is
often preferred in practice when activity durations are uncertain.
However, the information required to estimate probabilities related to activity duration may not
always be known. Fuzzy logic is an alternative approach for measuring uncertainty related to
activity duration. Fuzzy logic measures imprecision or vagueness in estimation, and may be
preferred to probability theory in those situations where past data concerning activity duration is
either unavailable or not relevant, the definition of the activity itself is somewhat unclear, or the

54
notion of the activity’s completion is vague. Many authors including Chanas and colleagues have
investigated the situation when activity duration can be described by fuzzy numbers [1], [2], [3],
5], [6], [7].
The dominant approach presented in the fuzzy critical path analysis literature is the fuzzy
extension of the forward and backward recursions taken in the project network. This approach
computes the earliest and latest start and finish times and slack, where the maximum, minimum,
addition, and subtraction operators are replaced by their fuzzy counterparts. The application of
the forward recursion with fuzzy activity times was first demonstrated in [3]. In a review of the
fuzzy critical path analysis literature two approaches are described for applying the forward
recursion [4]. They also indicate that the application of the backward recursion would cause a
considerable increase in the range of uncertainty in the start and finish times that are calculated.
These authors present a modification of the backward recursion that has been proposed to
eliminate this disadvantage [12]. Some authors directly apply the backward recursion, while other
authors have proposed different approaches for modifying the backward pass when the activity
times are fuzzy [18], [19], [20], [22]. The backward recursion was found not to compute the sets
of the possible values of the latest starting times and floats of activities [22]. In a stream of
research that uses the joint possibility distribution of activity durations, several authors [8], [9]
have conducted preliminary work for computing fuzzy latest starting times and fuzzy floats,
especially for series-parallel graphs. Polynomial algorithms for determining the intervals of the
latest starting times in the general project network are presented in [22].
Unlike the fuzzy backward recursion, the use of the fuzzy forward recursion is generally accepted
in the literature as providing correct results. As mentioned by several authors [3], [10], [18], [19],
the forward recursion is correct on problems involving fuzzy intervals. The purpose of this paper
is to prove that the fuzzy forward recursion when discrete fuzzy sets are used to represent activity
durations provides results that are not consistent with the direct application of the extension
principle to the critical path problem.
In section 2, we present some background on fuzzy sets and the supporting concepts needed in
the remainder of the paper. In section 3 we provide some brief background on project network
analysis under the assumption that activity durations are certain. Section 4 presents an important
result for fuzzy critical path analysis based on the extension principle. In section 5 the
counterexample to the application of the fuzzy forward recursion is presented and the reason the
results are not consistent with the extension principle is shown. Section 6 discusses two proposed
approaches from the literature that present results consistent with the extension principle.
Conclusions are offered in section 7.
2. FUZZY SETS
Following [17] we give the following definitions of a fuzzy set, fuzzy quantity and the support
set:
Definition 1. A fuzzy set M is a subset of the universe U that is characterized by a membership
function Mµ : U→[0,1] such that:

55
( )M xµ = 0, if x certainly is not a member of M,
( )M xµ = 1, if x certainly is a member of M,
( ) (0,1)M xµ ∈ , if it is uncertain whether x is a member of M, where ( )M xµ represents the
degree to which x is a member of M.
Now assume that activity duration is uncertain due to vagueness or imprecision and is a fuzzy
quantity defined as follows:
Definition 2. A fuzzy quantity M is a fuzzy subset of with membership function
[ ]: 0,1Mµ → such that
sup( ( ) : ) 1M x xµ ∈ = (1a)
( )
1 2 1 2
1 2
, , : ,
, ( ) 0
M M M M
M M
M
x x x x x
x x x xµ
∃ ∈ < ∀ ∈
∉ ⇒ =
(1b)
Definition 3. The support set of Mµ is defined as { }| ( ) 0M MS x xµ= ∈ > .
This definition can include discrete as well as continuous fuzzy sets, such as those that are
triangular or trapezoidal in shape. If the support set MS is finite, condition (1a) above can be
replaced with 0 0: ( ) 1Mx xµ∃ ∈ = . To simplify the presentation, we will assume this condition
hereafter. Condition (1b) implies that the support set is bounded. We will also assume that the
support set is discrete. Let iS be the support set of ia , where , , 1,2,...,i k i it S k n∈ = . That is, ia
has in possible non-zero discrete durations ,i kt in its support set iS .
As an example of a fuzzy activity duration, the vague statement that the duration of activity ia is
“about six weeks” might be represented by the following fuzzy quantity
~
it whose membership
function will be denoted as: (6) .7, (7) 1.0, (8) .8, ( ) 0i i i i itµ µ µ µ= = = = , otherwise. We can
also denote this membership function as 6/0.7, 7/1.0, 8/0.8.
We also need to define fuzzy addition and the fuzzy maximum of fuzzy quantities. Let 1M and
2M be fuzzy quantities with membership functions 1Mµ and 2Mµ , respectively. Following [17]
and as a direct application of the extension principle:
Definition 4. Fuzzy Addition: The membership function for the fuzzy quantity 21 MM ⊕ is
defined as:
)(21
zMM ⊕µ = Max Min { }1 2
( ), ( )M Mx yµ µ (2)

56
z x y= +
Definition 5. Fuzzy Maximum: The membership function for the fuzzy quantity max (M1, M2)
is defined as:
1 2max( , ) ( )M M zµ = Max Min { }1 2
( ), ( )M Mx yµ µ (3)
max( , )z x y=
One final definition is needed:
Definition 6: A configuration Ω is defined as a precise instantiation of the duration of all ia Aε .
In the next section we provide the necessary background on project network analysis.
3. BACKGROUND ON PROJECT NETWORKS AND THE CRITICAL
PATH
Let { }1 2,, ..., NA a a a= be the set of project activities. Let iB , i=1,2,…,N, iB A⊂ , be defined so
that the elements of iB are the immediate predecessors of ia . We let { }1 2, ,..., NB B B B= be the
set of predecessor sets. Cycles of activities within the project network are not allowed. We
assume that 1a is the only element of A such that 1B = ∅. We also assume Na is the only element
of A such that .N ia B i N∉ ∀ ≠ If the project network does not have unique start and finish
activities, we add dummy activities (which have zero duration) for this purpose. Taken together
A and B define the network structure or graph G of a project.
We initially assume that it ∈ , 0it ≥ , is the certain duration for ia , where { }1 2, ,..., NT t t t= . A
path p from start to finish is a finite sequence of activities
{ }1 2
, ,..., sr r ra a a where 1
, 1,2,..., 1k kr ra B k s+
∈ = − , and 1 1ra a= and sr na a= . The length of the
longest path from the start activity to the finish activity is the minimum project completion time.
This path is called the critical path, the activities along it are called critical path activities, and
the length of the path is denoted as CPL . Given G for each unique set of values T we can
compute CPL . Therefore, there is a function f(T|G): ...× × × → that maps T to CPL , or
CPL = f(T|G).
4. FUZZY CRITICAL PATH ANALYSIS
Proposition 1: Fuzzy Critical Path Membership Function
The membership function for the fuzzy set of critical path lengths can be determined as:

57
( )CP CPLµ = Max Min { }( )i itµ (4)
1 2, ,..., Nt t t { }1,2,...,i N∈
1 2( , ,..., | )N CPf t t t G L=
where ( )CP CPLµ is the membership function for the length of the critical path over the fuzzy
subset CP in ; and for a graph G and activity durations 1 2, ,..., Nt t t ,
1 2( , ,..., | )Nf t t t G determines the length of the critical path.
Proof: direct application of the extension principle of fuzzy logic [21] using maximum and
minimum for the disjunction and conjunction operators, respectively.
Because Proposition 1 represents the direct generalization of critical path analysis from the crisp
to the fuzzy domain, any proposed fuzzy critical path analysis approach should provide results
that are consistent with it.
One approach for implementing Proposition 1 requires defining all possible configurations,
determining the belief of each configuration as the minimum of the beliefs associated with all
activity durations included in this configuration, and then determining the maximum belief of all
configurations leading to each possible critical path length. The results form the fuzzy set of
critical path lengths.
5. COUNTER EXAMPLE TO THE FUZZY FORWARD RECURSION
In standard CPM the earliest start (ESi) and earliest finish (EFi) of an activity are defined as:
ESi = max EFj (5)
ij B∈
where we set ES0 = 0, and
EFi = ESi + it (6)
As defined in section 3 activity N does not have any successors, and so EFN is the length of the
critical path.
Assuming it% is a fuzzy quantity representing the duration of ia , the fuzzy earliest start iES and
fuzzy earliest finish iEF are defined as follows:
maxi jES EF= (7)
ij B∈

58
i i iEF ES t= ⊕% (8)
where max and ⊕ represent the extended fuzzy maximum and fuzzy addition, respectively, as
given in definitions 4 and 5.
Proposition 2: The fuzzy forward recursion does not always yield membership functions for the
fuzzy set of critical path lengths that are consistent with Proposition 1.
Proof: By counterexample using the data from a simple series – parallel graph (these graphs are
defined in [8] as shown in Figure 1. In this example there 2*3*3*1 = 18 configurations as shown
in Table 1. For each configuration, we determine the lengths of all paths, identify the critical
path, and following Proposition 1 determine the configuration belief as the minimum of the
beliefs of the possible activity durations. We combine the configurations by taking the maximum
of the beliefs over all configurations having the same critical path length. From Table 1 the fuzzy
set of critical path lengths is shown to be:
( )CP CPLµ = 6/0.1, 7/0.2, 8/0.5, 9/0.2, 10/0.5, 11/0.1, 12/1 (9)
The fuzzy forward recursion is applied using equations (5) and (6), with fuzzy addition and fuzzy
maximum as defined in equations (2) and (3), respectively. The results are as follows:
1ES = 0/1 (10)
1EF = 0/1 ⊕ (3/0.5, 5/1) = 3/0.5, 5/1 (11)
2ES = 1EF = 3/0.5, 5/1 (12)
2EF = (3/0.5, 5/1) ⊕ (3/0.2, 5/0.5, 7/1) = 6/0.2, 8/0.5, 10/0.5, 12/1 (13)
3ES = 1EF = 3/0.5, 5/1 (14)
3EF = (3/0.5, 5/1) ⊕ (2/0.1, 4/1, 6/0.1) = 5/0.1, 7/0.5, 9/1, 11/0.1 (15)
4ES = max { 2EF , 3EF } (16)
= max {(6/0.2, 8/0.5, 10/0.5, 12/1), (5/0.1, 7/0.5, 9/1, 11/0.1)}
= 6/0.1, 7/0.2, 8/0.5, 9/0.5, 10/0.5, 11/0.1, 12/1
4EF = (6/0.1, 7/0.2, 8/0.5, 9/0.5, 10/0.5, 11/0.1, 12/1) ⊕ 0/1 (17)
= 6/0.1, 7/0.2, 8/0.5, 9/0.5, 10/0.5, 11/0.1, 12/1
where 4EF is by definition ( )CP CPLµ , the fuzzy set of critical path lengths.

59
A comparison of equations (9) and (17) show that the range of possible critical path lengths is the
same, but that the belief of the possible critical path length of 9 is 0.2 in equation (9) and 0.5 in
equation (17). This difference proves the assertion.
Discussion: The forward algorithm is generally regarded as providing correct results in the
literature, with no distinction made for activity durations represented as discrete fuzzy sets. The
difference in the belief for the possible critical path length of 9 from Example 1 results from
incorrect comparisons made in the computation of the fuzzy maximum of the earliest finishes.
Specifically, the fuzzy maximum incorrectly compares earliest finish values that are based on
activity durations from different configurations. These configurations differ in terms of the
possible values of the activity that is the immediate predecessor of those activities whose earliest
finishes are being compared.
For example, in equation (16) the possible time 8/0.5 from 2EF is compared with the possible
time 9/1 from 3EF to yield 9/0.5. Folding back, in equation (13) the possible duration 8/0.5
results from the addition of 3/0.5 from 1EF and 5/0.5 from the possible duration of 2a . Since
the 1ES is 0, 3/0.5 is the possible duration of 1a . In equation (15) the possible duration 9/1 results
from the addition of 5/1 from 1EF and 4/1 from the possible duration of 3a . Since the 1ES is 0,
5/1 is the possible duration of 1a . That is, different possible durations of 1a are used to obtain the
possible time 8/0.5 from 2EF and the possible time 9/1 from 3EF . Thus, the fuzzy maximum
incorrectly compares earliest finishes that are based on activity durations from different
configurations. In the example above, if the possible duration of 1a were 3/0.2 instead of 3/0.5,
then the fuzzy forward recursion would have produced the correct result, simply because of the
specific value of a belief. However, since the fuzzy maximum is used repeatedly in the
application of the fuzzy forward recursion, errors are likely to occur in many, if not most,
problems.
6.PROPOSED CRITICAL PATH METHODS THAT ARE
CONSISTENT WITH THE EXTENSION PRINCIPLE
This author has proposed several alternative approaches for computing the fuzzy set of critical
path lengths that are consistent with the extension principle and Proposition 2. The first approach
[13] is based on the idea that rather than enumerate all possible configurations, generate and then
analyze a small number of configurations to achieve convergence to the membership function of
the fuzzy set of critical path lengths. This method uses pseudo-random numbers to select possible
durations for each activity to form configurations. Either the standard forward pass or path
enumeration can be applied to determine the critical path length of a configuration. Following
Proposition 1, the belief associated with the possible critical path length of a given configuration
is the minimum of the beliefs of the possible activity durations in the configuration. Since several
configurations may lead to the same possible critical path length, again following Proposition 1
and the extension principle, the belief of a possible critical path length is the maximum of the
beliefs associated with all possible critical path lengths of the same duration. Additional

60
configurations are analyzed until the percentage change in AREA (sum of the products of all
possible critical path lengths and their beliefs) is less than some tolerance. The proposed method
is evaluated using a series of test problems from the literature.
The second approach [14] begins by using a standard forward-backward pass algorithm to
compute the minimum possible critical path length, using the smallest possible duration for each
activity. A similar approach determines the maximum possible critical path length. Following
Proposition 1 a mathematical programming problem is formulated, whose objective is to
determine the belief associated with a possible critical path length. This mathematical program is
run for all possible critical path lengths, ranging between the possible minimum and maximum
lengths. In this way, the membership function for the fuzzy set of critical path lengths is
constructed. The proposed method is evaluated using a series of test problems from the literature.
7. CONCLUSIONS
In this paper, the direct application of the extension principle leads to a proposition that must be
satisfied in fuzzy critical path analysis. Using a counterexample where discrete fuzzy sets are
used to represent activity durations, it is demonstrated that the fuzzy forward recursion produces
results that are not consistent with the theory presented. The problem is shown to be the
application of the fuzzy maximum, since it compares earliest finishes that are based on activity
durations from different configurations. Several methods offered in the literature that provide
results consistent with the extension principle are described. The development of more efficient
algorithms to compute the fuzzy set of critical path lengths is an area of further research.
Figure 1. Example network with fuzzy activity durations

61
Table 1: Applying proposition 1 to the example
Activity 1 Activity 2 Activity 3 P 1 - 2 - 4 P 1 - 3 - 4 Critical Path CP fuzzy set
Duration Belief Duration Belief Duration Belief Duration Duration Duration Belief Duration Belief
3 0.5 3 0.2 2 0.1 6 5 6 0.1 6 0.1
3 0.5 3 0.2 4 1 6 7 7 0.2 7 0.2
3 0.5 3 0.2 6 0.1 6 9 9 0.1 8 0.5
3 0.5 5 0.5 2 0.1 8 5 8 0.1 9 0.2
3 0.5 5 0.5 4 1 8 7 8 0.5 10 0.5
3 0.5 5 0.5 6 0.1 8 9 9 0.1 11 0.1
3 0.5 7 1 2 0.1 10 5 10 0.1 12 1
3 0.5 7 1 4 1 10 7 10 0.5
3 0.5 7 1 6 0.1 10 9 10 0.1
5 1 3 0.2 2 0.1 8 7 8 0.1
5 1 3 0.2 4 1 8 9 9 0.2
5 1 3 0.2 6 0.1 8 11 11 0.1
5 1 5 0.5 2 0.1 10 7 10 0.1
5 1 5 0.5 4 1 10 9 10 0.5
5 1 5 0.5 6 0.1 10 11 11 0.1
5 1 7 1 2 0.1 12 7 12 0.1
5 1 7 1 4 1 12 9 12 1
5 1 7 1 6 0.1 12 11 12 0.1
*activity 4 is a dummy whose duration is certainly 0
REFERENCES
[1] Chanas, S. (1982) “Fuzzy sets in few classical operational research problems” in Gupta M. &
Sanches, E. (eds.), Approximate Reasoning in Decision Analysis, North-Holland Publishing
Company, pp. 351-361.
[2] Chanas, S., Dubois, D. & Zielinksi, P. (2002) “On the sure criticality of tasks in activity networks
with imprecise durations”, IEEE Transactions on Systems, Man, and Cybernetics – Part B:
Cybernetics, Vol. 32, pp. 393-407.
[3] Chanas, S. & Kamburowski, J. (1981) “The use of fuzzy variables in PERT”, Fuzzy Sets and
Systems, Vol. 1, pp. 11 – 19.
[4] Chanas, S. & Kuchta, D. (1998) “Discrete fuzzy optimization”, Chapter 8 in Slowinski, R. (ed.),
Fuzzy sets in Decision Analysis, Operations Research and Statistics, Kluwer Academic Publishers,
Boston, pp. 249-280.
[5] Chanas, S. & Zielinski, P. (2001) “Critical path analysis in the network with fuzzy activity times”,
Fuzzy Sets and Systems, Vol. 122, pp. 195-204.
[6] Chanas, S. & Zielinski, P. (2002) “The computational complexity of the criticality problems in a
network with interval activity times”, European Journal of Operational Research, Vol. 136, pp. 541 –
550.
[7] Chanas, S. & Zielinski, P. (2003) “On the hardness of evaluating criticality of activities in a planar
network with duration intervals”, Operations Research Letters, Vol. 31, pp. 53 – 59.
[8] Dubois, D., Fargier, H. & Galvagnon, V. (2003) “On the latest starting times and floats in activity
networks with ill-known durations”, European Journal of Operational Research, Vol. 147, pp. 266-
280.
[9] Fargier, H., Galvagnon, V. & Dubois, D. (2000) “Fuzzy PERT in series-parallel graphs”, in Ninth
IEEE International Conference on Fuzzy Systems, San Antonio, TX, pp. 717-722.

62
[10] Hapke, M., & Slowinski, R. (1996) “Fuzzy priority heuristics for project scheduling”, Fuzzy Sets and
Systems, Vol. 83, pp. 291-299.
[11] Kelley, J. (1961) “Critical path planning and scheduling -- mathematical basis”, Operations Research,
Vol. 9, pp. 296-320.
[12] Kamburowski, J. (1983) “Fuzzy activity duration times in critical path analysis”, International
Symposium on Project Management, New Delhi, pp. 194-199.
[13] Liberatore, M. (2007) “A latin hypercube sampling approach for fuzzy critical path analysis”,
International Journal of Operations and Quantitative Management, Vol. 13, No. 4, pp. 235 – 250.
[14] Liberatore, M. (2008) ”Critical path analysis with fuzzy activity times”, IEEE Transactions on
Engineering Management, Vol. 55, No. 2, pp. 329 - 337.
[15] Lootsma, F. A. (1989) “Stochastic and fuzzy PERT”, European Journal of Operational Research, Vol.
43, pp. 174-183.
[16] Malcolm, D., Rosenbloom, J., Clark, C. & and Fazar, W. (1959) “Application of a technique for
research and development project evaluation”, Operations Research, Vol. 7, pp. 646-669.
[17] Mares, M. (1994) Computation Over Fuzzy Quantities, CRC Press, Boca Raton.
[18] Nasution, S. (1994) “Fuzzy critical path method”, IEEE Transactions on Systems, Man, and
Cybernetics, Vol. 24, pp. 48-57.
[19] Rommelfanger, H. (1994) “Network analysis and information flow in fuzzy environment”, Fuzzy Sets
and Systems, Vol. 67, pp. 119-128.
[20] Slyeptsov, A. & Tyschchuk, T. (2003) “A method of computation of characteristics of operations in a
problem of fuzzy network planning and management”, Cybernetics and Systems Analysis, Vol. 39,
pp. 367 – 378.
[21] Zadeh, L. (1975) “Calculus of fuzzy restrictions”, in Zadeh, L., Fu, K., Tanaka, K. & Shimara, J.
(eds.), Fuzzy Sets and Their Application to Cognitive and Decision Processes, Academic Process, pp.
1-39.
[22] Zielinski, P. (2005) “On computing the latest starting times and floats of activities in a network with
imprecise durations”, Fuzzy Sets and Systems, Vol. 150, pp. 53 – 76.

A Counterexample to the Forward Recursion in Fuzzy Critical Path Analysis Under Discrete Fuzzy Sets

Recommended

More Related Content

What's hot (20)

Similar to A Counterexample to the Forward Recursion in Fuzzy Critical Path Analysis Under Discrete Fuzzy Sets (20)

Recently uploaded (20)

A Counterexample to the Forward Recursion in Fuzzy Critical Path Analysis Under Discrete Fuzzy Sets