J. Cent. South Univ. Technol. (2010) 17: 1006-1010

DOI: 10.1007/s11771-010-0591-4

A new analytical algorithm for computing probability distribution of project completion time

HOU Zhen-ting(侯振挺) , ZHANG Xuan(张玄), KONG Xiang-xing(孔祥星)

School of Mathematics, Central South University, Changsha 410075, China

? Central South University Press and Springer-Verlag Berlin Heidelberg 2010

Abstract: An analytical algorithm was presented for the exact computation of the probability distribution of the project completion time in stochastic networks, where the activity durations are mutually independent and continuously distributed random variables. Firstly, stochastic activity networks were modeled as continuous-time Markov process with a single absorbing state by the well-know method of supplementary variables and the time changed from the initial state to absorbing state is equal to the project completion time. Then, the Markov process was regarded as a special case of Markov skeleton process. By taking advantage of the backward equations of Markov skeleton processes, a backward algorithm was proposed to compute the probability distribution of the project completion time. Finally, a numerical example was solved to demonstrate the performance of the proposed methodology. The results show that the proposed algorithm is capable of computing the exact distribution function of the project completion time, and the expectation and variance are obtained.

Key words: stochastic activity networks; project completion time; distribution function; Markov process; supplementary variable technique

1 Introduction

The evidence from large numbers of history data reveals that for large projects, the majority of them overrun by time [1-2]. The primary tools used for planning and scheduling large projects are critical path method (CPM) and program evaluation and review technique (PERT). CPM is a traditional method to schedule a project assuming deterministic durations. However, most durations are of random nature in reality. Therefore, activity duration is well represented by random variables with some distribution functions. PERT is based on the assumption that the duration of each activity is a random variable that behaves according to some known probability distributions. In this case, a project can be represented by a stochastic activity network (SAN).

So far, there have been considerable studies concerning the analysis of the project completion time in SANs. The methodologies can be classified into three main categories as follows [3-4].

(1) Exact analysis. MARTIN [5] presented a method to compute the distribution function of the project duration through series-parallel reductions, where the activity durations are independent random variables with polynomial distributions. LEEMIS et al [6] provided an algorithm based on conditioning upon the durations of the multiple-use activities to compute the distribution of the project completion time when activity durations are single function defined in (0, ∞). In each of the above methods, the solution often involves a multivariate integral, so the calculation of the distribution function is an extremely arduous task. KULKARNI and ADLAKHA [7] developed analytical procedures for Markov PERT networks with independent and exponentially distributed activity durations.

(2) Monte Carlo simulation. VAN SLYKE [8] first developed a straightforward simulation to analyze the distribution function of the project completion time by using crude Monte Carlo techniques. Many researchers improved the sampling techniques of VAN SLYKE by using conditional sampling to achieve variance reduction. FISHMAN [9] estimated the distribution function of the project completion time by using a combination of quasi-random points and conditional sampling.

(3) Bounding methods. ELMAGHRABY [3] provided a detail discussion of bounding methods and presented a method for bounding the expected project completion time.

The aforementioned studies are restricted to special types of distribution function for the activity durations.In this work, attention was paid to the stochastic networks with independent and continuously distributed activity durations, and a new analytical approach for computing the probability distribution of the project completion time was presented.

2 Preliminary definitions

Let G=(V, A) be a SAN with single source node s and single sink node t, where V and A represent the sets of nodes and arcs of the network, respectively. For aA, let α(a) be the starting node of arc a, and β(a) be the ending node of arc a.

Definition 1 For any vV, let I(v) and O(v) be the sets of arcs ending and starting at node v, respectively, i.e.,

                      (1)

Definition 2 If XV, such that sX, tV-X, then an (s, t) cut is defined as

            (2)

The (s, t) cut (X, ) will be called uniformly directed cut (UDC), if (, X) is empty.

Definition 3 Let D be a UDC of a network, and D=E∪F. Then, (E, F) is called an admissible 2-partition, if E∩F=and I(β(a))F for any aF.

At any point of time t, each activity can be in the active, dormant or idle states. An activity will be active if it is executed; it will be dormant if it is finished but there is at least one unfinished activity in I(β(a)). If an activity is dormant at time t, then its successor activities in O(β(a)) cannot begin; and it is idle if it will be neither active nor dormant.

3 Project completion time analysis in SANs

Define X(t)=(Y(t), Z(t)), where Y(t) and Z(t) represent the sets of active and dormant states at time t, respectively. Denote the set of all admissible 2-partition of all UDCs of the network by S, and let Ω=S∪. Note that X(t)= implies that Y(t)= and Z(t)=, i.e., all activities are idle at time t and hence the project is completed at time t.

In particular, if the activity durations are independent random variables with exponential distributions, {X(t), t≥0} will be a finite-state, continuous time Markov chain with state space Ω [7].

Although KULKARNI’s algorithm [7] is elegant, it holds only for networks with exponentially distributed activity durations. When the activity durations are generally continuously distributed, {X(t), t≥0} will be not, in general, a Markov process. Fortunately, one can make it Markovian by supplementary variable technique (SVT) [10].

Assume that the activity durations are independent and continuously distributed random variables. As mentioned above, X(t)=(Y(t), Z(t)). Suppose that Y(t)={ a₁, a₂, …, a_k } at time t. Let  denote the time elapsed from the start of activity a_i to time t (i.e., the elapsed work time of activity a_i at time t), R⁺, i=1, 2, …, k.

Further, define

(Y(t), Z(t), …,              (3)

It is evident that t≥0} is a continuous-time Markov process.

Owing to the complexity of the states of  the classical theory of stochastic process cannot give satisfied results. However, the usual Markov process can be regarded as a special case of Markov skeleton processes [11-14].

Time t is called a jump point of if X(t)≠X(t-). Let τ₀=0 and τ_k(k=1, 2, …) be the kth jump point of  Then, τ₀ and τ_k are Markov time, and   t≥0} is a Markov skeleton process (MSP) with τ_k (k=1, 2, …) as its skeleton time sequence.

Definition 4 Let (E, F) be an admissible 2-partition of a UDC D, and θ(t)={…,  be the set of the elapsed work time of all active activities at time t. Then, (E, F, θ(t)) is called a generalized admissible 2-partition of D.

Theorem 1 (Y(t), Z(t), …, is a generalized admissible 2-partition cut of a UDC in the SAN.

Let N be the number of the admissible 2-partition cuts of the network. The state set of  t≥0}, , is divided into N classes, which are numbered as S₁, S₂, …, S_N. State S₁ is the initial state, namely (O(t), …,where O(s)=(a₁, a₂, …, a_k). And S_N is the absorbing state For convenience,is presented by

4 Distribution of project completion time

Let T represent the project completion time, obviously,

T=min{t≥0;|          (4)

where…,  0}, O(s)={a₁, a₂, …, a_k}

Thus, T is the time until absorption in state S_N, starting from state  Denote the distribution function of the project completion time by F(t). Therefore, F(t)= P(T≤t)=P(t,

Assume that the project has n activities, and let X_k be the duration of activity k, distributed with A^(k)(t), thus A^(k)(t)=P(X_k≤t), k=1, 2, …, n.

Define

≤θ_k+t|X_k＞θ_k)                   (5)

where θ_k(t)R⁺, k=1, 2, …, n.

Let (Ω, F, P) be a complete probability space, (E, ε) a measurable space. And let {X(t), 0≤t＜∞} be a right-continuous stochastic process defined on (Ω, F, P) with values in (E, ε). For any xE, t≥0, Aε, define

q(x, t, A)=P(X(τ₁)A, τ₁≤t|X(0)=x)              (6)

h(x, t, A)=P(X(t)A, t＜τ₁|X(0)=x)               (7)

P(x, t, A)=P(X(t)A|X(0)=x)                   (8)

Lemma 1 For any t≥0, S_i, S_jif S_i≠S_j, then

h(S_i, t, S_j)=0                                 (9)

Let S_ucc(S_i) denote the set of immediate successors of state S_i. Applying the backward equations of MSPs and Lemma 1, one can obtain the following theorem.

Theorem 2 For any t≥0, S_i, S_j

P(S_i, t, S_N)=

(1≤i＜N)                              (10)

By theorem 2, P(S₁, t, S_N) can be easily obtained in the backward fashion, starting with P(S_N, t, S_N)=1 for t≥0, and computing P(S_N-1, t, S_N), …, P(S₂, t, S_N), P(S₁, t, S_N).

The new algorithm will be introduced through an example in the remainder of this section.

The MSP related to the project completion time analysis of the example network in Fig.1 has 17 states, as illustrated in Table 1. The phase diagram for the network depicted in Fig.1 is shown in Fig.2.

Fig.1 Example network

It is obvious that

      (11)

Moving from state S₁₇ to state S₁ in the phase diagram (Fig.2), F(t) can be obtained as follows.

(1) Consider state S₁₆, as mentioned in Table 1, S₁₆= (5, 6^*, θ₅). It implies that activity 5 is active and activity 6 is dormant at this state. Change in the state of the project can come about in only one possibility: activity 5  is completed and the process transfers to the new state S₁₇=By theorem 2, it follows that

Table 1 All generalized admissible 2-partition cuts of network depicted in Fig.1

Fig.2 Phase diagram for network depicted in Fig.1

   (12)

Recall that  It is easy to check that  Hence

             (13)

Similarly,

                        (14)

(2) Consider S₁₄=(5, 6, θ₅, θ₆). Change in the state of the project can come about in one of two possibilities: (a) If activity 5 completes before activity 6, the process will transfer to new state (5^*, 6, θ₆+s); and (b) if activity 6 completes before activity 5, the process will transfer to new state (5, 6^*, θ₅+s) (note that the case in which activities 5 and 6 complete at the same time can be ignored, because this happens with probability zero when the distributions are continuous). Using Eqs.(10)-(14), P(S₁₄, t, S₁₇) can be derived as follows:

 (15)

(3) The remaining P(S_i, t, S₁₇), 1≤i≤13, can be computed recursively by P(S₁₇, t, S₁₇)=1 and Eq.(10). Finally, based on the above formulations, P(S₁, t, S₁₇)= is given by

             (16)

Let θ₁=θ₂=0, it follows that

                  (17)

Remark: By referring to the proposed algorithm above, F(t) can be easily computed analytically and the algorithm avoids the complexity of numerical evaluation of multivariate integral.

The proposed algorithm for the computation of F(t) is given by the seven steps shown below. Each step is illustrated with the network from Fig.1.

Algorithm:

Step 1: Identify network UDCs, and present all admissible 2-partition cuts of the network.

Step 2: Identify all generalized admissible 2- partition cuts, as illustrated in Table 1.

Step 3: Draw the phase diagram for the network, as illustrated in Fig.2.

Step 4: Compute P(S₁₆, t, S₁₇) and P(S₁₅, t, S₁₇) by Eqs.(13) and (14).

Step 5: Compute P(S₁₄, t, S₁₇) by Eq.(15).

Step 6: Compute P(S_i, t, S₁₇) (1≤i≤13) recursively.

Step 7: Compute F(t) by Eq.(17).

5 Numerical example

The durations of activity network in Fig.1 are assumed to be mutually independent and identically distributed random variables having the γ distribution with parameter 2 and 1, i.e., the distribution function is A(t)=1-(t+1)e^-t, t≥0. Then

                 (18)

According to the proposed algorithm, P((1, 2, θ₁, θ₂), t, can be easily obtained by using Eq.(16). To obtain the distribution function of the project completion time, let θ₁=θ₂=0. Hence, F(t) is given by

(19)

The expectation and variance of T are computed as 7.23 and 5.69, respectively.

All computations were carried out on a PC using MATLAB 7.0. It should be noted that the state space of the Markov process  t≥0} grows rapidly with the network size. From the example network in Fig.1, it is easy to show that N depends on the number of nodes. In fact, the root problem facing this algorithm arises from its nature of NP hardness. Consequently, it is essentially intractable to obtain the exact answers for large-scale networks [15-17].

6 Conclusions

(1) A new analytical algorithm for computing the probability distribution of the project completion time in stochastic networks is proposed. This algorithm can be used for stochastic networks with continuously distributed activity durations.

(2) The proposed algorithm avoids the complexity of numerical evaluation of multivariate integral.

(3) The algorithm can be extended to the general PERT networks, where general activity durations are allowed. Such networks can be also modeled as continuous-time Markov processes by supplementary variables technique.

References

[1] HARDIE N. The prediction and control of project duration: A recursive model [J]. International Journal of Project Management, 2001, 19(7): 401-409.

[2] COPPENDALE J. Manage risk in product and process development and avoid unpleasant surprises [J]. Engineering Management Journal, 1995, 5(1): 35-38.

[3] ELMAGHRABY S E. The estimation of some network parameters in the PERT model of activity networks: Review and critique [C]// Advances in Project Scheduling. Amsterdam: Elsevier, 1989: 371- 432.

[4] YAO Ming-jong, CHU Weng-ming. A new approximation algorithm for obtaining the probability distribution function for project completion time [J]. Computers & Mathematics with Applications, 2007, 54(2): 282-295.

[5] MARTIN J J. Distribution of the time through a directed acyclic network [J]. Operations Research, 1965, 13(1): 46-66.

[6] LEEMIS L, DUGGAN M, DREW J, MALLOZZI J, CONNELL K. Algorithms to calculate the distribution of the longest path length of a stochastic activity network with continuous activity durations [J]. Networks, 2006, 48(3): 143-165.

[7] KULKARNI V G, ADLAKHA V G. Markov and Markov- Regenerative PERT networks [J]. Operations Research, 1986, 34 (5): 769-781.

[8] van SLYKE R M. Monte Carlo methods and the PERT problem [J]. Operations Research, 1963, 11(5): 839-861.

[9] FISHMAN G S. Estimating critical path and arc probabilities in stochastic activity networks [J]. Naval Research Logistic Quarterly, 1985, 32(2): 249-261.

[10] ALFA A S, RAO T S. Supplementary variable technique in stochastic models [J]. Probability in the Engineering and Informational Sciences, 2000, 14(2): 203-218.

[11] HOU Zhen-ting, LIU Guo-xin. Markov skeleton processes and their application [M]. Beijing: Science Press and International Press, 2005:1-6.

[12] HOU Zhen-ting. Markov skeleton processes and application to queueing systems [J]. Acta Mathematicae Applicatae Sinica, 2002, 18(4): 537-552.

[13] HOU Zhen-ting, YUAN Cheng-gui, ZOU Jie-zhong, LIU Zai-ming, LUO Jiao-wan, LIU Guo-xin, SHI Peng. Transient distribution of the length of GI/G/n queueing systems [J]. Stochastic Analysis and Applications, 2003, 21(3): 567-592.

[14] YU Zheng, LIU Zai-ming, HOU Zhen-ting. Distribution of the transient queue length in SMAP/INID/1 [J]. Journal of Central South University: Science and Technology, 2004, 35(2): 341-344. (in Chinese)

[15] AZARON A, TAVAKKOLI-MOGHADDAM R. A multi-objective resource allocation problem in dynamic PERT networks [J]. Applied Mathematics and Computation, 2006, 181(1): 163-174.

[16] ABDELKADER Y H. Evaluating project completion times when activity times are Weibull distributed [J]. European Journal of Operational Research, 2004, 157(3): 704-715.

[17] ABDELKADER Y H. Erlang distributed activity times in stochastic activity networks [J]. Kybernetika, 2003, 39(3): 347-358. (in Czechish)

(Edited by LIU Hua-sen)

Foundation item: Project(10671212) supported by the National Natural Science Foundation of China; Project(20050533036) supported by the Specialized Research Found for the Doctoral Program Foundation of Higher Education of China

Received date: 2009-10-12; Accepted date: 2010-04-26

Corresponding author: HOU Zhen-ting, Professor; Tel: +86-13548653582; E-mail: zxshuxue@yahoo.com.cn