PERT-path network technique: a new approach to project planning

International Journal ofProject Management 1994 12 (2) 89-99

PERT-path network technique: a new approach to project planning Giovanni Mummolo Department

of Industrial Design and Production,

Polytechnic

of Bari, 70126 Bari, Italy

A new network technique is described, the PERT-path network technique (PPNT), for the planning and control of project activities. The approach requires the same information as classical PERT-type network techniques do, but it uses it more accurately. A new systemic schematization of the classical PERT system is formalized, and the PERT-path network is defined. The main properties of the network are discussed. Analytical relationships which allow evaluations of the time domain of each possible trajectory of the PERTsystem and the PPN topology are provided. An algorithm for the computerized implementation of the technique is described. The approach has proved to be of use in outlining potential inconsistencies in the planners’ estimates when project-time or project-progress targets are pursued. The analysis of projects by paths may help in the resolution of contractual disputes at the planning stage. A case study using PERTand PPNT is provided. Keywords: project planning, network techniques

PERT-type network techniques’,2 are very common and widely adopted management tools that are used in the processes of project planning and control. The use of such techniques has often proved to be ineffective in project planning, and improvements to traditional approaches have for some time been suggested. Although this lack of success may be attributable to managerial inexperience or lack of ability, or unforseeable events (so-called ‘acts of God’), it is necessary to examine more Closely the effectiveness of the PERT-type techniques that are currently available in project management. The current scenario relating to management tools is characterized by several new products that have been improved by computer technology. They are, however, usually based on a traditional theoretical knowledge of current management techniques, such as PERT-type network techniques, which are often inadequate in terms of a full understanding of project phenomena. Sometimes, management awareness of a project’s uncertainties can even be found in the planner’s ‘intuitive rationality’. Management are often unable to point out uncertainties clearly using current management techniques because of the contraintuitive behaviour of many practical situations. Attempts to overcome such limitations in traditional PERT-type techniques are made in References 3-5, in which a new systemic formalization of the PERT system is suggested. In particular, an appropriate state variable to describe a PERT-system evolution (i.e. a possible project-completion sequence of the project activities) is defined. The state variable considers all completed or uncompleted activities at a given time. 0263-7863/94/020089-l 10 1994 Butterworth-HeinemannLtd

PERT, on the other hand, analyses the project by examining certain ‘critical’ activities, but it often neglects the information contained in all the logical constraints and activity-time estimates of a PERT system. An attempt is made to overcome the above-mentioned limitations by proposing a new network technique, the ‘PERT-path’ network technique (PPNT). Defining

PERT-path network

Let us consider a project characterized by a set {A} of N interrelated activities planned by PERT. The probabilitydensity function (PDF) of each activity time and the set of logical constraints which governs the precedences among the activities are known. Project activities can be completed during project time following a possible completion sequence according to activity times and precedences among the activities. We define a sequence of activities as a ‘path’ that the PERT system can follow. According to the number of completed activities, the sequence can result in a partial or complete path. An obvious case is the initial path with no completed activities. Given that different paths are identified at the beginning of a project, this means that different project evolutions are possible. According to the above assumptions, we define the state variable ‘path state’ of a PERT system as ?Tk

=

@,.I,

4,,2,.

3 A+

0, 0,. . ,O} k=

[l,N],

i,=

[l,n,] 89

PERT-path network technique: a new approach to project planning: G Mummolo

where Ai ,k is the kth completed activity of the i,th path state in the kth transition, and nk is the’ number of path states with k activities completed. In the case of k = 0, none of the activities has been completed. If k = N, the state variable refers to the set of complete paths, consistently with the planner estimates, that the PERT system can follow before the project gets under way. As soon as the process is under way, some paths are discarded from the possible PERT-system trajectories, depending on the completion sequence actually followed. Given that the PERT system is in the pth path state 7~~,~, among the path states with k completed activities, the completion of a project activity allows the transition towards a contiguous path state ?T$,~+, , the occurrence of which depends on the transition probability between the path states. Transition probabilities depend on the stochastic process describing the PERT system evolutions by 7~~.We define the transition graph of the stochastic process as the PER-r-path network (PPN). Depending on the management goals, the analysis of project paths can be based on one or more significant evaluation parameters. Among these are the state probability of each TV,,+,the transition probabilities among the path states, the domain of the arrival time in each ?r,,,, and the PPN topology. In a general and unsteady stochastic process, state and transition probabilities are time- and statedependent. In this case, numerical simulation4,5, though it is time-consuming from the computational point of view, can be used. Under the hypothesis of exponentially distributed activity times, an analytical approach is possible5. The PPN topology and the domain of the arrival time in each path state depend on the PERT network topology and the domain of each activity time, as shown in the next two sections. PERT-pathnetwork topology A PPN is a directed graph with a tree topology which facilitates deeper analysis of the possible (partial or complete) project evolutions. These are the values that the state variable can assume for k = 0,. . . ,N. Let us consider a PERT network (PN) and the domain of each activity time. If each activity time is defined as a stochastic variable in the [0 + 00 [ domain (e.g. the negative-exponential, Weibull , and Erlang PDFs) , the PPN topology depends only on the corresponding PN topology. The PPN topology can be easily obtained, because there are no time constraints. In this situation, each transition from a given path state in the PPN to a contiguous one is allowed, and therefore all the possible paths of the PPN are allowed. If the activity times, as normally occurs, are defined in bounded domains (e.g. the beta and uniform PDFs), PN topology is no longer enough to determine the corresponding PPN topology. Because of activity-time constraints, the times at which transitions take place are bounded stochastic variables, and, therefore, not all transitions are allowed. Consider, for example, the very simple case in Figure la. The case consists of a PN with three activities A,, A, and A,. If each activity-time domain is unbounded, all the completion sequences of the activities are allowed, according to the precedences among the activities governed by the PN topology. The PPN describing all the activity-completion sequences is shown in Figure lb. If, on the other hand, the activity times are defined in bounded domains [a,, b,] , 90

A2

b

Figure 1

PERT networks: (a) PERT network with three activities, (b) PERT-path network of example in (a)

[a,, b2] and [a,, b3] for activities A,, A, and A,, not all the transitions from a path state to contiguous path states are allowed. In fact, if u2 is greater than b,, activity A, cannot be completed before activity A,. Consequently, path states ~2.2 and, of course, 1r23 represent, according to the planners’ estimates, comple‘tion sequences that the project cannot follow. In the case of overlapping between the time domains of A, and A, (e.g. (a, < u2 < b, < b2) or (a2 < u, < b, < b,) or (a, = u2 and/or b, = bJ), both of the complete path states 1r,,3 and ~2,~ can be followed. In such a case, the effective time domain of each activity (e.g. A,) is shortened by the time of the other activity (A*) which competes with the former to be completed. The A, time is also constrained by the A, time. Consequently, the domain of the project-completion time varies according to whether sequence is followed. the r1.3 or *2,3 activity-completion Such evaluations are obvious for the very simple case we have just considered. However, evaluating the PPN topology as well as the effective domain of each activity time and the domain of the arrival time of each (partial or complete) path state is a complex task in large-scale projects. Activity times and path-state arrival times In order to find the arrival-time domain of each path state of a PPN when activity times are bounded stochastic variables, it is necessary to investigate the relationships between the arrival times in the current pth path state T~,~ at the kth transition, k = 0,. . . ,N, and the time domain of the activity A,, the completion of which allows the transition from 7rp,kto a contiguous path state T,,~+,. The arrival time in rP,k is a continuous variable; however, it can assume discrete values T = {7i (vrp,J}, depending on the maximum number of combinations (25 of the minimum and maximum times of those activities whose completion allows the transitions between each couple of contiguous path states, from the initial one, 7~,,~(k = 0), up to the current path state T~,~. If k = 0, then T(r,,J = 0. If A, starts at T~(K& from T~,~, its time ranges between the extreme values of its planned domain Q, = [a,, b, I ; the values of the arrival time in ?T~,~+,can be evaluated by adding the minimum and maximum value of Q, to T~(T,,~). By varying T~(T&, the extreme values of the arrival International

Journal of Project Management

1994 Volume 12 Number 2

PERT-path

network

to

Figure

International

3

PERT

Journal

-0

and maximum

G Mummolo

activity times Nodes

Activity specification

Activity

Excavations Foundation casting A Foundation casting B Equipment 1 erection Steel structure erection Logic link Internals set up Equipment 2 erection Piping assembly Final testing [a: minimum

activity time, b: maximum

Time, days

Start

End

a

b

1 2 2 3 4 5 5 6 7 8

2 3 4 5 6 I 8 I 8 9

14 1 3

16 3 5 3 16 0 22 4 27 3

1 14 0 18 2 23 1

activity time.]

Equipment

2 /

Equipment

1

/

\

/ /

Figure

-

planning:

case study using PPN technique

Table 1 Minimum

'sCrpTp.~).

5

to project

The example refers to the planning of field-erection activities as shown in Figure 2. The activity specifications and the minimum and maximum time of each activity are listed in Table 1. The PN highlighting the technical constraints of the erection is shown in Figure 3. The network

Not all the arrival times in the path state 7rp,kallow the contiguous path state ?T~,~+,to be reached by means of the completion of A,, which we assume started in B,,~_~. For some values of T, the minimum residual time of A, may be greater than the maximum residual time of competing activities. The transition from T,,~ to ?T,,~+,is not possible for these T values. The elements of T which allow the transition concerned define the set T’, a subset of T. In the same way, not all the T’ values enable the PERT system to follow a given complete path state, because of the constraints that relate to the activities that follow A, and which belong to the above-mentioned complete path state. Those elements of T’ which do enable the PERT system to evolve according to the complete path state define the set T” as a subset of T’. Clearly, T” E T’ G T. By considering the set T and the extreme values of QSor n:, up to 2k+’ values of the residual time of A, can be identified. Each value may be positive (or at least zero) or negative. Both cases and their mathematical implications are discussed in Appendix A. The analytical condition in Expression 4 by which it can be verified whether the PERT system can pass from a given path state rp,k to a contiguous path state x,,~+, is also deduced. If the condition is not satisfied, the transition is not allowed. In this case, T,,~+, cannot be reached from T~,~. Because of the tree topology of the PPN, none of the path states following .1~,,~+,exist. The relationship in Expression 4 enables us, therefore, to evaluate the topology of PPNs when the activity-time domains have lower and upper limits. In Appendix B, we describe an algorithm to evaluate the PPN topology as well as the time domain of each partial or complete path state with the relative set of activity-time domains.

3

a new approach

Developing

time in 7r,,k+, can be evaluated. On the other hand, if A, starts in the path state T,,~., which precedes K~,~in the (k-m)th transition, m E [ 1,k ] , but is not yet completed in x~.,, activity A, has a varying residual time in a reduced domain Q’, [ T,(T~,~)] G Qs, depending on ~~(r&. Let us assume in the example in Figure I that the system evolution follows r,,, = {A,,--,-}. When activity A, is completed, A, is still running, and it has a residual time whose domain is shorter than the one (Q; [ ~~(a,.,)] 5 [a,, b2]) initially estimated by planners, and that depends on the arrival time in K,,,, ~,(r,,,). In general, the residual time of A, (which is still a stochastic variable) is defined as the difference between the activity time and the time range between the arrival time in 7~~.~,~~(r~,~), and the arrival time in T,,$_~, ~~(a~,~_~),with the unique partial sequence of activity times leading from Ti(ar.i-nz)

technique:

6

8

2

Plant assembly for case study

‘-+-&

network of example in Figure 2 of

Project

Management

1994 Volume I2 Number 2

91

PERT-path network technique: a new approach to project planning: G Mummolo

shows a ‘logic link’ with zero time, which states the need for the erection to have activity 4 and activity 8 completed before activity 9 is started. The case study is initially developed by means of PERT, and, at a later stage, by means of PPNT. This enables us to highlight the differences between the two approaches, and to compare the results obtainable from each approach. Table 2 shows the main results obtained when applying PERT to the case in question. PERT initially gives each activity time the expected value based on the planners’ estimates. In our case, we assume that this figure is the arithmetical average of the extreme values of the activity times estimated. The time required for each of the activities is used to calculate the earliest time T,, and the latest time T,,, for the arrival event (end node) of each PERT activity. As we know’, the earliest time for an event is defined as the time at which the event occurs if the preceding activities are started as early as possible. The latest time for an event is defined as the last time at which the event can occur without delaying the completion of the project beyond its earliest time. The last column of Table 2 shows the slack time for each arrival event, defined as the difference between its latest and earliest time. The events with zero slack, shown with an asterisk, identify the critical activities. These are A,, A,, A,, A,, A, and A,,, in the example. Applying widely accepted hypotheses+, the probability of completing the project by a scheduled date has been estimated using PERT. Under these hypotheses, the expected value and the standard deviation of the project time are, respectively, given by T = 64 day and u = 1 day. The limits of the project time are given by T-2a = 62 day and T+2a = 66 day, with a probability of about 95.0%, and T-30 = 61 day and T+3a = 67 day, with a probability of about 99.7%. The results obtainable in the example under examination are quite different if PPNT is applied using the same information as was used for PERT. PPNT provides a more ‘global’ approach in project planning in that it permits the identification of possible, partial or complete, completion sequences of project activities as well as the exact limits of the arrival time in each (partial or complete) project evolution, on the basis of the planners’ evaluation of PERT topology and activity times. In Figure 4, the full PERT-path network (FPPN) (see Appendix B) corresponding to unbounded activity times is reported. The network has 140 path states, of which 30 are complete. The FPPN topology depends only on the PN topology (see Figure 3). For the sake of simplicity, each path state is numbered according to a sequential order, rather than by the symbolism adopted in the theoretical model. After the ‘pruning’ procedure described in Appendix B, the reduced

TThe distribution of each activity time is approximately a beta distribution, with a standard deviation of e = (b-a)/6. The activity times are statistically independent. The critical path requires a longer total elapsed time, in terms of expected times, than any other path (and consequently the expected value and the variance of the project time are given by the sum of the expected time values and variances, respectively, of the times of the activities on the critical path). The last assumption is that the project time has a normal distribution (the rationale for this assumption is in the central-limit theorem).

92

Table 2 Calculation of earliest and latest times and slack time for each end node of example of Figure 2

Activity 1 2 3 4 5 6(+) 7 8 9 10

Nodes Start End 1 2 2 3 4 5 5 6 7 8

2 3 4 5 6 7 8 7 8 9

Time, days 15 2 4 2 15 20 3 24 2

Earliest time, Latest time, days days 15 17 19 19 34 37 61 31 62 64

15 35 19 37 34 37 61 37 62 64

Slack, days o* 18 o* 18 o* 0 0 o* o* o*

[ +: dummy activity.] network (RPPN) is obtained (see Figure 5). It has 30 path states, with five complete path states. The sharp difference between the FPPN and the RPPN outlines the effects of the bounded domains of the activity times on the paths that the project can follow. The path states evaluated highlight the type of limitation in potential project evolutions. Such a situation should be considered by the contractual parties during the projectplanning stage. Each project evolution (path state) has specific characteristics that need to be examined. Table 3 shows the minimum and the maximum times of each complete path state of RPPN (see Appendixes A and B). As each activity time is usually estimated in a bounded domain (e.g. according to the beta distribution), the project time should also range in a bounded domain. Using PPNT, the minimum project time ranged from 57 to 60 days, depending on the complete path state followed by the PERT system. Using PERT, because of the normal distribution of the project time, the minimum project time was estimated as 62 days, with a probability of 95.0%, or 61 days, with a probability of 99.7%. Similarly, using PPNT, the maximum project time was calculated to be exactly 7 1 days for all the complete path states of the PERT system, whereas, using the PERT approach, the maximum project time was estimated as 66 or 67 days, with a probability of 95.0% and 99.7%, respectively. Both techniques are based on the same information provided by the planners. PERT, however, allows only an approximate evaluation at a given probability level of the minimum and maximum project times. PPNT allows an exact evaluation of project times. PERT operates only on the critical path, whereas PPNT operates on any possible project evolution. The approximations of PERT are related to the hypotheses that the technique requires; these hypotheses are not necessary for PPNT. During the planning stage, the complete path state that a PERT system will actually follow is still unknown. During this stage, several project evolutions are possible, each of which has a probability of occurrence that depends on the planners’ estimates of activity-times PDFs and PERTnetwork topology. Table 3 shows the path-state frequencies estimated by numerical simulation (each activity time has a uniform PDF). In the example, the path states have identical maximum arrival times (71 days) and different minimum arrival times. However, the minimum arrival times do not differ significantly, and neither do the ranges of the arrival times in each path state. This could indicate equivalence among the most convenient path states to be followed in order to PERT-path

International

Journal of Project Management 1994 Volume 12 Number 2

PERT-path network technique: a new approach to project planning:

International Journal of Project Management 1994 Volume I2 Number 2

G Mummolo

93

PERT-path network technique: a new approach to project planning: G Mummolo Table 3 Minimum and maximum arrival times and frequency of each path state Arrival times, days

Path state

T,,S: {A,, T,,>: {A,, T,,?: {A,, “116: {A,, T,,,: {A,,

Al> A,, A,. A,, A>>A,, A,, A,, A,, A,,

A,, A,, A,, A,, A,,

A,, A,, A,, A,, A,,

A,, A,, A,, A,, A,,

A,, A,, A,, A,, A,,

A,, A,, A,, A,, A,,

A,,,} A,,) A,,} A,,} A,,]

Min

Max

2;

;;

57 59 57

71 71 71

Path state frequency

6.667E-5 0.109 0.389 I .514E-2 0.487

meet a given project-completion time, a view which might not be shared by top management because they have a different perspective. Let us consider, in fact, path states They differ because, in x,,~, the assembling 7F116 and x117. of equipment 2 (activity 8) comes before the assembling of the internals (activity 7), while the opposite completion sequence of the same activities is followed in K,,~. This simple modification in the erection progress significantly affects the frequency of occurrence of the two path states, increasing the frequency (0.487) of T,,~, which is more likely to be followed than a,16 (1.514E-2). Such a situation could persuade the contractual parties to consider project completion according to a,,,. A rearrangement of the resources allocated (affecting the activity times) is still possible to increase the chances of occurrence of the project evolution desired. Similarly, T,,, differs from a,13 in terms of the completion order of activity 3 and activity 4. If the casting of foundation B (activity 3) comes before the erection of equipment 1 (activity 4), the path followed is r,,,; it has a frequency of occurrence that is greater than that of T,,~ (0.389). Therefore, even if T,,~ and a, ,, have the same minimum and maximum project times, the latter could still be preferred in a contractual agreement. Once the activity-completion order has been established, PPNT allows accurate evaluation of the effective activitytime domains and the arrival time in each partial or complete path state. Figure 6 shows the time domain of each activity in the sequence T,,~. For each activity, Figure 6 shows the planners’ estimated time domain as well as the domains which enable us to reach a current path state T~,~, the path state which follows x~,~, and the final path state (R, ,J. Project evolution according to a given path state requires that the planners’ estimated domains should be modified to ensure that they are mutually compatible and compatible with the given path state. Starting from path state T,~, the transition towards n,9 is allowed if the minimum time of A, increases from three to four days, and the maximum time of A, decreases from 22 to 19 days. The contemporaneous reductions of the maximum times of activities A, and A, (from three to two days) and A, (from 22 to 19 days), and the increase of the minimum times of A, (from three to four days) and of A, (from 14 to 15 days), are necessary to enable the system to evolve according to path state P,,~. The contemporaneous reductions of the time domains of the above activities significantly reduce the likelihood of T,,~ (6.667E-5), as shown by the numerical simulation of the case study. With reference to T,,~, Figure 7 shows the arrival-time domain of a current path state 7rp,k(set T of the arrival times in 7r,,J and the arrival-time domains in TV,,, allowing us to reach the successive path state (set T’ of the arrival International

Journal of Project Management

1994 Volume 12 Number 2

PERT-pathnetwork technique: a new approach to project planning: G b4ummo~o

Activity 30

/

25

--

time (day)

41

A2 n3

A4 rI5

A3 n10

n

Activity

time domain

as per the planner estimates

0

Activity

time domain

to reach the current path-state

q Activity

time domain

to reach the path-state

folllowing

A8 r-I55

A7 n19

A9 II85

A10 rI115

Project activity Current path-state

the

current path-state

n

Activity

time domain

to complete

the project according

to the

final path-state

Figure 6 Time domain of each project activity completed according to path state T,,~ times in ?r,,J and the final path state (set T” of the arrival times in 7r&, starting from T~,~. The arrival time in rr,O = (A,, A,, A,, A3) can range from 16 to 21 days (set Tof rr,,,), whereas the arrival time m rr,,,, which also allows us to reach the contiguous path state 7r,9 = (A,, A,, A,, A,, A,) with the completion of A, and the final path state rr, ,5, must range from 18 to 21 days (T’ of a,, nr T” of T,~). After the completion of activity A,, the critical phase of the project seems to be overcome, and it continues to follow path state T,,~. This can be seen in the slight increase of the arrival-time domains in the path states following K,~. Such considerations could usefully be taken into account during the control stage to reallocate resources among project activities, thereby reducing or increasing the completion times of specific activities which influence the evolution of the project. PPNT allows us to evaluate project sensitivity to planners’ uncertainties about activity times. If each activity time is given its expected value (see Table 2), the PERT system evolves in a deterministic way following path state International Journal of Project Management 1994 Volume12 Number 2

which has the maximum occurrence frequency (f= 0.489). The algorithmic use of the proposed technique and its computerization allow us to determine immediately that the PERT system may evolve either according to 1r,,3 (frequency f = 0.389) or according to T,,~, if the planned activitytime domain is given to one of activities A,, A3 and Ad. The path states T,,~, rr,,5 and rlld are not possible project evolutions if we consider the individual time domain of each activity in the deterministic case above. However, 1r,,* cf= 0.109) is a possible project evolution if the planned time domains of activities A,, A,, and A, are considered together. Finally, the PERT system may also evolve according to path states 1r,,5 and x,,~ if the planned domains of all the project activities are considered together. The use of PPNT shows that, in 99% of cases, the PERT system may evolve according to path states a,,*, 1r,,3 and T,,~. These possible project evolutions can be attributed to the planners’ uncertainties about the A,, A, and A, times. These activities are therefore more critical than others, and =I177

95

PERT-path

network

technique:

a new approach

to project

planning:

G

A3 lIl0

Al n19

A5 rl34

Mummolo

Time (day) 80

Al Il2 0

Arrival times

A2 r13

in a current

path-state

A4 rl5

q Arrival

times

in a current

path-state

to reach its next path-state

n

times

in a current

path-stats

to reach the final path-state

Arrival

A8 rl55

A9 ll85

A10 rl115

Completed project activity Current path-state

Figure 7 Minimum and maximum arrival times in each path state of rrllS they deserve greater attention during the planning stage. The meaning of ‘critical’ in relation to the above activities differs from the meaning given by PERT to the activities of the ‘critical path’. In the case study, only activity A, is defined as critical according to PPNT, and it also belongs to the critical path identified by PERT. As a general result, the use of PPNT in the planning stage highlights planners’ uncertainties about the activity-time estimates which are critical in the identification of the PERT-system evolution, and those which are completely uninfluential. PERT-path technique

in engineering

contracts

Evaluations of the kind carried out in the case study may be useful in drawing up engineering contracts, in that they make the contractual parties more aware of the effects of planners’ uncertainties about project evolutions and the possible origins of these uncertainties. Each project evolution may be of a different type of economic interest to the two contractual parties. The contractor may be interested in the definition of contractual milestones which follow completion sequences entitling him/her to receive the largest instalments of advance payment from the owner. The owner, on the other hand, may prefer completion sequences which minimize his/her 96

financial obligations to the contractor, and increase the real progress of the project. Both cases may relate to sequences that are impossible or unlikely in that they are incompatible with the time estimates and logical constraints of each activity as well as the agreed completion time for the project. A reallocation of resources among the activities, and the establishing of new time estimates, could lead to new completion sequences which could be of mutual benefit from a technical and economic point of view. The procedure of updating estimates and, consequently, project evolutions could be usefully carried out during project control after the project has been launched and when planners’ detailed estimates are available. Further evaluation parameters of the path states can be considered to analyse possible project evolutions from other technical or economic aspects according to the specific goals of the owner or the contractor. The set of evaluation parameters can facilitate a more in-depth analysis of project evolutions, each of which shows better performances for some of the evaluation parameters, but not, of course, for all of them. In a contractual dispute, it is necessary to check the most suitable project evolutions for each of the contractual parties. The analysis of paths might help to put disputes on a more objective basis through an understanding of possible project evolutions and more rational decision making. International

Journal of Project Management

1994 Volume 12 Number 2

PERT-path

network

Summary and conclusions Classical PERT-type network techniques may be improved by a new, although more complex, schematization of the project. The PERT-path network technique constitutes an attempt to pursue such a goal. We discuss the main properties of the PERT-path network and the frame of the analytical relationships that can evaluate the time domain of each possible amount of project progress (see Appendix A). An algorithm that is able to shape the pattern of the network topology is provided (see Appendix B). In the approach suggested, it has been stressed how the project manager may not be really fully acquainted with the intrinsic limitations of conventional project-management network techniques. The study of the properties of PPNT has revealed the possible existence, during the contractual stage, of inconsistencies between the estimated domain and the reduced domain of each activity time, and inconsistencies between the estimated project evolutions and possible project evolutions and project times. The close relationship between the project completion time and possible project evolutions requires a joint evaluation of these parameters, despite the limitations of management in the appraisal of the complexity of the problem as a whole, without a theoretical tool and its algorithmic implementation such as those proposed in this paper. The approach allows us to overcome in part the limitations of numerical simulation, as it permits the exact analytical calculation of the limits of each path state time domain. Simulation however, still has to be adopted to evaluate the frequencies of path states. The PERT-path network has proved to be a useful tool in investigating project evolutions during the contractual stage (time zero). In fact, it has proved to be a suitable tool for highlighting possible project evolutions that are inconsistent with the expectations of one or both of the contractual parties (owner and contractor), even if such inconsistencies were contained in the planners’ estimates. A case study, developed using both PERT and PPNT, has highlighted the differences in the approaches compared. The main feature of the approach proposed consists of the effective ability of PPNT to consider all the information, in terms of PERT topology and activity times, contained in the

technique:

a new approach

to project

planning:

G

Mummolo

planners’ estimates on a PERT system as a whole. Such estimates are usually performed separately when classical PERT-type network techniques are used, while the PPN approach reveals the need for their joint evaluation consistently with the expectations, in terms of project times and project evolutions, of the contractual parties. Further research should aim to overcome, albeit with an approximate procedure, the limitations of numerical simulation in estimating, for a general case, the path-state and transition frequencies of a PPN. The formalization of a structured paradigm supporting decision making on the basis of a set of complex and integrated evaluations could address the problem of determining the best tradeoff between the conflicting interests of the contractual parties.

References Hillier, F S and Lieberman, G J Operations Research Holden Day, USA (1974) Badiru, A B and Whitehouse, G E Models and Techniques for Project Management TAB Books, USA (1989) Albino, V, Cavallone, S and Mummolo, G ‘PERT-State: a network technique to manage the complexity of project planning and control processes’ Management and Network Analysis XXIII Sem. Karlovy Vary, Czechoslovakia (1989) Albino, V, Cavallone, S and Mummolo, G ‘Improvements in the knowledge of planning and control processes of a project by the PERT-State technique’ in D’Amato, V, Maccheroni, C and Angeli, F (Eds.) Dynamic Analysis of Complex Systems Milan, Italy (1990) Albino, V, Cavallone, S and Mummolo, G ‘Project planning and control by the PERT-State approach’ Proc. 11th INTERNET World Congr. Project Management Florence, Italy (1992)

Bibliography Alto, A, Dioguardi, G F and Cardano, E ‘Analisi critica dei metodi di programmazione per commessa’ Proc. ANIMP-INTERNET conf: Sorrento, Italy (1984) Moeller, G L and Digman, L A ‘Operations planning with VERT’ Oper. Res. Vol 29 No 3 (1981) pp 676-697 Phillips, D T, Pritsker, A and Alan, B ‘GERT network analysis of complex production systems’ Int. J. Product. Rex Vol 13 No 3 (1975) pp 223-237 Pritsker, A and Alan, B Modelling and Analysis Using Q-GERTNetworks John Wiley, USA (1979)

Appendix A

ins,,+,}

=

T,l'(R,,k+,)

=

International

pth path state with k activities completed set of activities A, that can be completed given that PERT system is in path state 7~p,~ sth path state with k+ 1 completed activities (can be reached starting from np,k by completion of activity A,) set of path states that can be reached from 7rp,kby completion of activities of S ith arrival time at path state T~,~ set of arrival times at path state rp,t minimum arrival time at path state T,,~+, starting PERT system from rrp,k at ri (?T~.~) maximum arrival time at path state x,,~+, starting PERT system from 7rp,kat r, (T~,~) [ a,,b, ] = planned domain of activity time A, minimum residual time of A, calculated at r, (r/J

Journal of Project Management

1994 Volume 12 Number 2

0, [r, (r&l Q [ri

(Tp,k)l

= maximum residual time of A, calculated at rj (T~.~) = maximum residual time of A, (A, E S, A, f A,) calculated at ri (?T~,~)

In Appendix A, we describe the analytical relationships linking the arrival time at the path state rr, k+l with the residual time of activity A, allowing the transition from the current path state rp,k to T,,~+, . The relationships are deduced according to the cases of positive (at least zero) and negative values of the A, residual time. In the first case, given an arrival time ri (x~,~), the time of A, exceeds (or is at least equal to) the time range that is available for the activity completion. Therefore, the ith couple of the arrival times in ?T,,~+,, corresponding to ri (T~,~), has to be calculated as

97

PERT-path network technique: a new approach to project planning: G Mummolo

bi [7i (rp,kp.k)l=

0:

+

17, (?~p,k) -

7i (~,,,~m)l

(3

where 7/‘(~J.k+,)

= 7i(rp,k)

+ 0s [7i(?Tp,k)l

(2)

v 7, (T&k) E I71(~/A

0,’ 17, (r&l

1

= min P5 17, (TJI,

for A, E S and A, # A,. If D,’ [7, (?~p,dl = 0, [7, (rp,Jl,

where d, [7;(~Jl

= 4

-

[7; (?Tp,k) -

7i (7r,,,-,)I

min D, 17, (?T,JI 1

we have bj 17, (xP,Jl

= b

2 0

O&erwise,

if

and 0, [71(7rp,t)l = 6, -

[7i(?~p,d -

7;(7r+m)l

Q [ 7, (~~~21 = min 0, [7i (n,,dl

2 0

are the residual times of A, that correspond to the extreme values of 9. In the case of negative residual times, two main hypotheses have to be considered. Let us first suppose that d, [ 7i(7rP,k)] < 0 and D, [ 7i(7r,,k)] 2 0 (Hypothesis 1). By imposing d, [7, (TJ] = 0, the minimum time of A, has to increase up to the value al [7i(~~.k)l

= 0, + Ids [7,(rp,k)l

I

(3)

corresponding to an instantaneous transition from np,k to T,.~+~, at time 7, (?~p,d. Also, the maximum value of !J2,may change. Starting from T~,~, the activities of set S = {A,} compete with each other to complete themselves in order to allow the transition towards the path states of {7~,,~+,}. Given a 7, (T~,~), the minimum and maximum residual time of A, (d, [7, (?T&] , D, [7, (T~.~)] , V A, E S) are identified. The path state K,.~+, can be reached from 7rp,kif 3 7; (7rP.i) E {7i(7rp.k)I 3’ 4 [7, (rP.Jl < min D, [7, (TJ

(4)

1

for A, E S and A, + A,. Consequently, time of activity A, is

the maximum

< 0, 17, (~F~,LJI

for A, E S and A, + A,, then bj [ 7i (T~,~)] < b,. Therefore, a time-compression mechanism works not only on the minimum activity time, as in Equation 3, but also on the maximum activity time according to Equation 5. Therefore, the reduced domain of the A, time is

Obviously, Q’, in contrast to a,, depends on 7, (TJ. Under the current Hypothesis 1, at time 7i (TJ, the two arrival times at path state ?T+~+,can still be calculated by Equations 1 and 2, where the Q, domain has to be substituted for by the Qd domain. In the case in which D, [7,(7rP,J] = 0, the transition if the A, time from T~,~to T,,~+~ can occur instantaneously assumes its maximum value. Finally, if we suppose that d, [ 7((?~p,~)] < 0 and D, [ 7i (T~,J I < 0 (Hypothesis 2), the transition from T~,~ to r&k+1 is not allowed for any time for A,. In this case, in fact, A, has already been completed at a time preceding 7i (T&. Therefore, the transition concerned cannot start at 7i (Tp.k).

Appendix B PERT-path

network

algorithm

On the basis of the PPN properties deduced in this paper and discussed in more detail in Appendix A, an algorithm that is able to determine the PPN topology as well as the domain of each path-state arrival time and the domain of each activity time is proposed. The algorithm strategy first requires the determination of the PPN topology by assuming each activity time ranging in the [ 0, + 00 [ domain. In this case, the PPN topology depends only on the PERT network (PN) topology. We define the resulting network as the full PERT-path network. A ‘pruning’ procedure is subsequently adopted to eliminate the branches of the FPPN that cannot be reached because of bounded activity times. The procedure leads us to the reduced PERT-path network (RPPN) and to the domain of the arrival time in each partial or complete path state and to the domain of each activity time in a given transition between path states. Let us consider an FPPN. The sets of the minimum and maximum activity times of the N PERT activities are known. The algorithm is developed in the following steps. Step

98

I.

Initialize

the procedure

by considering

the first

subset of the path states (k = 0) with the unique initial path state with no completed activities. For k = 0, RPPN = FPPN. Set k* = 0. Step 2. Group the set of RPPN path states in subsets {T,,~} with the same number k of activities completed, k = k*, . ,N and k* = 0,. . . ,N. The grouping procedure identifies N - k* + 1 subsets of path states. The path states of each subset have the same number k of activities completed. For k* = 0, the procedure groups all the path states of the FPPN. The first group (k = 0) comprises the initial path state with no completed activities (path state P,,~ in the example of Figure 1). The second group (k = 1) comprises the path states with one activity completed (path states 7r,,, and a,,, in the example), and so on up to k = N, where all the complete path states (x,,~ and 7rZ.3in the example) are grouped. As k* increases (see Step 7 of the algorithm), the grouping procedure is updated, starting from the group of the path states with k* activities completed. Step 3. Consider International

Journal

the kth subset {x,,~}. of

Project Managemenr 1994 Volume 12 Number

2

PERT-path

network

Step 4. Given the path state T,,~ of the subset {T~,~}, identify three sets of PERT activities: -A,,, (~~,~p,k)is the set of the activities that can be started when the PERT system arrives at T,,~. The completion of the activities of the set concerned allows the transition towards the path states of the subset {.lr,q,k+,}contiguous with T~,~. In the example of Figure I, if we assume that K~,~ = a,,?, the set Ap,k (T~,~) comprises only A,. -Ar,k_m (T+) is the set of the activities that have already started in the path state T,,~_~, m E [ l,k] , but not yet completed in T~,~. The completion of each activity of A r,Lmm (T~,~) allows the transition from rpp.kto a path state of IT,.,+,}. In the example of Figure I, if we assume that T~,.~ = a,,, , activity A, is the only activity of the set Ar,k_m (T~,~). It has already been started in the path state a,,,, but not yet completed in T,,, . -A’,,, (T~,~) is the set of the activities that have already been completed in T,,~. In the example, if T,,~ = P,,, , the set A’p,k (T& comprises only activity A,. Step 5. For the transition from 7r,,k to 7~,,~+,, calculate the 2k+’ minimum and maximum residual times d, [T;(?T~,~)] and Q [T, (rp.k)] A,, v 7, (r,,.k) E {7, &,,}. The residual times are equal to the extreme value of fi, if A, E A,,, (T~,~). Otherwise, if A, E Ar,k_m(x+), the extreme values of the domain of the A,T residual time can be calculated using Equations 3 and 5 in Appendix A.

ofactivity

6. At a given 7, (?T~.~),if Expression 4 holds, calculate using Equations 1 and 2 in 7: (a,,,+,) and 7:’ (a,,k+,) Appendix A, referring to 0, or Q: depending, case by case, on whether A, belongs to A,,k(?r,,k) or Ar.kmm (T~,~), respectively. Step

International

Journal of Project Management

1994 Volume 12 Number 2

technique:

a new approach

to project

planning:

G Mummolo

Otherwise, if Expression 4 has not been satisfied, T,~,~+, cannot be reached from T~,~. Therefore, eliminate x~,~+, and all the following path states by ‘pruning’ the branches of the FPPN connecting them. In the case of the example in Figure I, if a, is greater than b, , path state a,,, cannot be reached from ?r, 0, and it has to be eliminated. Of course, path states ~,,,‘and 1r2,3 following a2,, have to be eliminated also. One should note that, because of the tree topology of the PPN, the lower values of k generally determine the greater number of the path states which have to be eliminated. 7. If k* = N, then stop the procedure. Otherwise, let k* = k* + 1, and go to Step 2 to group again the subset of the path states starting from the new value of k*. Step

Giovanni Mummolo, who is a graduate in mechanical engineering, is a professor who is responsible for graduate industrial-engineering training courses at the Politechnic of Bari, Italy. His teaching activities are in postgraduate engineering training courses dealing with projectmanagement topics. In developing his academic activities, he collaborates with engineering-consulting and manufacturing companies. As a project coordinator, he belongs to the directive committee of an international project concerning solidwaste disposal plants involving Italian and US universities. His main research interests are in project-management topics, and in project planning and control techniques in particular.

99