Abstract: 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 determine the critical path in a project network with continuous fuzzy activity durations by use of the longest path algorithm. In this study, we will propose fuzzy program evaluation review technique Bellman algorithm by the use of fuzzy sets, program evaluation review technique and Bellman algorithm to specify the critical path and the fuzzy earliest/latest starting time and fuzzy floats of activities in the continuous fuzzy network. Inputs and outputs of the proposed algorithms are fuzzy numbers and this algorithm is able to compute the fuzzy error time and occurrence probability of this error time. The complexity of this algorithm is the indicator its excellent performance. An example is presented to illustrate the proposed algorithm as well as to compare the results with those obtained using the crisp models. The comparisons reveal that the use of fuzzy models is more effective in determining the critical path and floats.
INTRODUCTION
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 on.
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):
(1) |
where, M is the membership space and usually assumed to vary in the interval [0,1].
| Fig. 1: | 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):
(2) |
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, 1995):
(3) |
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.
| Fig. 2: | Trapezoidal fuzzy number |
| Fig. 3: | Triangular fuzzy number |
On the 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:
(4) |
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 numbers.
Let
(5) |
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 fuzzy problems.
Liou and Wang index (Liou and Wang, 1992): This index is defined as follows:
(6) |
Where:
(7) |
(8) |
and λε[0,1] is a degree that might reflect the decision maker`s
optimism/pessimism. Therefore,
García and Lamata index (García and Lamata, 2005): This index improves the discrimination between fuzzy numbers and is defined as follows:
(9) |
where, δε[0,1] is a modality index and λε[0,1] is
an optimism degree. Therefore,
Nayeem and Pal index (Nayeem and Pal, 2005): If
(10) |
Therefore
Ranking Function (RF) (Cheng, 1980; Seda, 2006): If ;
then two inverse functions for each fuzzy number are defined as follows:
(11) |
(12) |
Then:
(13) |
(14) |
from above equations, RF is defined as:
(15) |
Therefore,
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, 2001) .
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 network.
| Table 1: | 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.
| Fig. 4: | Network of a Design-Build project |
| Table 2: | 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 makers.
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:
| |
| Table 3: | 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.
| Fig. 5: | Splitted up network |
| Fig. 6: | Steps 1, 2 of execution of algorithm |
| Fig. 7: | Step 3 of execution of algorithm |
| Fig. 8: | Steps 4-7 of execution of algorithm |
| Fig. 9: | Step 9 of execution of algorithm |
| Fig. 10: | Steps 10-15 of execution of algorithm (determination of critical path A-B-D-F-G) |
| Fig. 11: | Determination of critical path A-C-F-G |
| Table 4: | Floats and earliest/latest starting time |
| Fig. 12: | Fuzzy numbers of the critical paths |
| Fig. 13: | 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.
CONCLUSION
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 were computed.
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.