MARKOV SKELETON PROCESS IN PERT NETWORKS

Available online at www.sciencedirect.com.MalhemiutCcHientiaScienceDirect数学物理学报Acta Mathematica Scientia 2010,30B(5):1440- -1448http:// actams.wipm.ac.cnMA RKOV SKELETON PROCESS IN PERTNETWORKSKong Xiangxing (孔祥星) Zhang Xuan (张玄) Hou Zhenting (侯振挺)School of Mathematics, Central South University, Changsha 410075, ChinaE-mail: kongriangring2008@ 163. com; zxshurue@yahoo. com. cn; zthou@mail. csu. edu.cnnetworks with independently and generally distributed activity durations. For any path inthis network, we select all the activities related to this path such that the completion timetime of this path. We use the elapsed time as the supplementary variables and model .this sub-network as a Markov skeleton process, the state space is related to the sub-sub- network's completion time, which is an important rule in project management andscheduling.Key words PERT networks; Markov skeleton process; backward equation2000 MR Subject Classification 05C20; 60K401IntroductionProgramming Evaluation and Review Technique (PERT) networks are used to plan projectby showing precedence relationship between the various activities that constitute this project.A PERT network is a special case of directed graph in which the nodes (or vertices) representpoints in time and arcs (or edges) representing activities with time values modeling activitydurations.Directed acyclic networks were used extensively in management of projects. We can in-vestigate the project completion time, the total direct costs of the project, and the relationshipbetween this via analyzing the directed acyclic networks. For example, in Critical Path Method(CPM) and PERT models, arcs in those networks represent operationally and logically indivis-ible parts of projects, and will produce a directed acyclic network by the required precedenceconstraints. CPM models assume that the activity durations are definite values, however, PERTmodels assume that the activity durations are independent random variables.* Received December 2, 2008. This work is supported by the National Natural Science Foundation of China(10671212, 10901 164, 90820302), the Graduate Research Innovation Projects in Hunan Province (CX2009B020)and the Graduate Degree Thesis Innovation Foundation of Central Sourth University (2009ybfz11).中国煤化工MHCNM HGNo.5x.X. Kong et al: MARKOV SKELETON PROCESS IN PERT NETWORKS1441Several authors addressed the project completion time analytically in such models. Charnecset al. in [1] developed a chance-constrained programming approach to PERT problems. Theyassumed exponential activity durations, however, analytical procedures are not efficient for gen-eral PERT problems. Attempts were made to develop approximation techniques. Elmaghrabyin [2] provided lower bounds for the true, expected project completion time. Van Slyke in [3]reported the first attempt at straightforward simulation to analyze the distribution of projectcompletion time in PERT networks.Kulkarni et al. in [4] investigated PERT networks with independently and exponentiallydistributed activity durations. They modeled such network as a finite-state absorbing, continu-ous time markov chain (CTMC), with upper triangular generator matrices, and such networkswere named as Markov PERT networks (MPNs). The time from the initial state to beingabsorbed of this CTMC is equal to the project completion time, and we can compute the dis-tribution of this time via the backward equation of the CTMC. There some authors assumedactivity durations are Erlang distributed random variables in the PERT networks, and thesevariables are the sum of some exponentially distributed random variables then transfer to theformer type.The investigation had great progress after assuming the activity duration was exponentiallydistributed random variables in the project programming and scheduling. We assume theactivity duration is exponentially distributed random variable just for modeling the network asMarkov Chains, however, it does't have any practical bases.Hence, it is of great importance to investigate PERT networks with generally distributed(may be normal distribution N(μ,σ2), F-distribution, T-distribution, ..) activity durationsand view it as a practical mathematical model. In our research, we can model a PERT networkwithout any restriction on the distribution of the activity durations as a MSP, which is a newstochastic process developed by Hou et al. in [8].In this article we deal with the PERT networks with independently and generally distrib-uted activity durations. Surely we can't model this network as Markov chain, however, we canmodel this PERT network as MSP via appending elapsed time as supplementary variables, fromwhich we can compute the distribution of any path's completion time by backward equation ofMSP.In this article, we will first review a few terminologies in PERT networks in previous workin the next section. Then, we model the PERT networks as MSP and compute the distributionof the completion time for any path in the third section and a numerical example is given insection four. In the fifth section we draw the conclusion of this article.2 Network TerminologyIn this section, we review some terminologies proposed by Kulkarni et al. in [4-7]. LetG = (V,A) be a network with a set of nodes V = {v1,V2,...,Vm} and a set of arcs A ={a1,a2,..,an}. The words “arc” and“activity”will be used synonymously throughout thearticle. Assume that G is a directed acyclic network with a single source and a single sink,networks with these characteristics are generally classified as PERT networks in the literature.The source node is denoted by 8 and the sink node by t. For a∈A, the duration is a generally中国煤化工MHCNM HG1442ACTA MATHEMATICA SCIENTIAVol.30 Ser.Bdistributed random variable, let a(a) be the starting node of arc a and β(a) be the end node ofarc a. A directed (s, t) path in the network is a sequence of arcs (a1, a2,...ak), such thatai∈Afor i= 1,2,，,k; a(a1) = s,B(ak) = t and a(a;) = 3(ai-1) for i = 2, 3,，.. k. Henceforth,“path" will always mean a directed (s, t) path.Definition 1 Suppose I(v) and O(v) denote the sets of arcs ending at node U and thesets of arcs starting at node U, respectively:I(v)={a∈A:B(a)=v}(v∈V),(1O(v)= {a∈A:a(a)=v}(v∈V).(2Definition 2 Ifs∈ X C V andt∈X=V- X, then an (s, t) cut is defined by(X,X)={a∈A:a(a)∈X,B(a)∈X}.(3Suppose (X,X) is empty, then an (s,t) cut (X,X) is called a uniformly directed cut (U DC).Definition 3 Let D= EUF isa UDC of a network. Then, it is called an admissible2-partition if I(3(a))Z F, fora∈F.Definition 4 During the project execution and at time t, each activity might be in one ofthe active, dormant and idle states, which are defined as follows:1) Active: An activity is active at timet if it is executed at time t.2) Dormant: An activity is dormant at time t, if it has finished but there is at least oneunfinished activity in I(3(a)). If an activity is dormant at time t, then its successor activitiesin O(B(a)) cannot begin.3) Idle: An activity is idle at time t, if it is neither active nor dormant at time t.The sets of active and dormant activities are denoted by Y(t) and Z(t), respectively, andX(t)= (Y(), Z()).3 MSP in PERT NetworkIfL= (a1, a2,.., ak) be a path in PERT network G. We want to calculate the distributionof the completion time of the path L, evidently the completion time of L might be not equal tothe sum of completion time of a1,a2,.,ak (only if L is a critical path). For the reason of theactivities in L might be in dormant in the procedures of the project, so the completion time ofL might be equal or larger than the sum of completion time of a1, a2,.,ak.We calculate the distribution of completion time of L = (a,a,..,ak) in G via thefollowing approach. Suppose Ak = {ar},Ai-1 = {a∈A:a∈I(a(a)),a∈A},i = k,K1,.2, denote A' := A1U A2∪..∪Ak, hence the subnetwork G' consisting of all the arcsin A' stands for a sub-project, and the completion time of this sub-project G' is equal to thecompletion time of the path L. .Example 1 As shown in Fig.1 (a), supposeL= (1,3,5), thenA3= {5},A2= {3,4},A1={1,2}, and A' =A1∪A2∪A3= {1,2,3,4,5}.Thus, G' is shown in Fig.1 (b), and the completion time of the path L is equal to thecompletion time of this sub-project.In Example 1 all the U DC's of the network are (1, 2), (2,3), (1,4), (3, 4), and (5), thereforeall admissible 2-partition cuts of the network are represented in Table 1.中国煤化工MHCNM HGNo.5x.X. Kong et al: MARKOV SKELETON PROCESS IN PERT NETWORKS1443\3@-@→02+0/4a)b)Fig.1Table 11.(1,2)。2.(2,3) 3.(2,3*) 4.(1,4) 5.(1,4*)6.(3,4,) 7.(38.(3.4*)9.(5) 10.(0,0)As mentioned beforethe active and dormant arcs of a UDC, for anya∈E, 0a(t) denotes elapsince the last arrival at time t).Let G(a)(.) denotes the dist butionIf activity duration for any activity a∈A, 0a(t) standsfor the elapsed time of activityt timdHence, the remaining time distribution, denoted byG(a)(0a +t)a)(9。G'W"(),isG"g)(t)=C(9-67.jAdding the supplementary variables 0a(t), the statesin Table 1 are turned intorle1.(1,2,01,02) 2.(2,3.03) 3.( 3*，2)4.(1, 4,01,04) 5.(1, 4*,01)6.(3, 4, 03, 04) 7.(3* ,04) 8.(3,4*,9.(5, 05)LetE=[{1}x{2}x[0,∞)x[0 )]∪[{2 x {3}x[0,∞)x [0,∞)]∪[{2}x{3*}x [0,∞)]..U[{0} x {}].Then, X(t) is a Markov skele process th the state space E.X(t)= (1,2,01,02) dtimeθ1 and 02, ..,X(t)= .4*, 03)es the state that the activity 3 is active with elapsedtime 03 and activity 4 is dormant at tinnet, X(t) = (5, 0s) denotes activity 5 to be active withelapsed time θs at time t. X(t)= (0，) is the state that E =0,F=0 at time t, that is, allthe act vities are idle at time t, hence, the project is completed by time t.Le ro = 0,r1,r2,... be the discontinuous times of X(t) (that is, an activity being com-pleted t t time rn(n ≥1)). Then, rn(n ≥1) are the skeleton time sequence of the Markovskeleton process X (t).For the saevity we use 1,2,..., 10 represent the states in Table 2. The procedureof the M6P Xt it reaches the state 2 or 4 with exactly one time-step from the initialstate 1, nen transfer to3, or 6, or 5, ... and then reaches the state 10 (), ). The procedurecan be re bresented in Fig.2.Let be the completion time of the network, then T = min{t > 0, X(t) = (), 0)|X(0) =(1,2,0, 0)，we can compute the distribution F(t)= P{T≤t} of T by the backward equation.中国煤化工MHCNM HG[a)1444ACTA MATHEMATICA SCIENTIAVol.30 Ser.B=0- +四⑧YFig.2 .Let Fo(0s, t) be the probability from state 9 with elapsed time θs to state 10:F(0s,t)= P{(5, 0s),t, (0,0)}| q((5, 0s5), ds, (0,0))P((0,0),t - s,(),0)}2: / dG(Q(<)=G(%().7(4)Let F8(03, t) be the probability from state 8 with elapsed 03 to state 10F8(03,t)= P((3,4*, 03),t, (0,0)}= | ((3,4*,03),ds, (5,0)P{(5,0),t - s,(0,)}I G8(t -sadG3().(5Let Fz(04, t) be the probability from state 7 with elapsed 04 to state 10Fr(04,t)= P{(3*,4,t, (0,0)}q((3*),ds, (,0)P({(5,0),t - s,(0,0)}9|-}(10= [" ({(-d)d(().(6Let F6(03, 04, t) be the probability from state 6 with elapsed 03, 04 to state 10F6(03, 04,t) = P((3, 4, 03, 04),t, (0,0)}= | q((3,4,03, 04),ds,(3*,4,04 + s))P{(3*,4,04 +s),t-s, (0,)}+ | q((3,4,03, 04),ds, (3,4* ,03 + s))P{(3* ,4,04 + s),t-s, (0,0)}4 + E(()- C)3(<- )(G"()- G%(s- 8((5.0),t- .(0)}8≤t= (1(16)))F(04+s,t - s)dC(3()[" (1- G{()F8(03+s,t -9)dG6(x)+> (G8)(g)- G(})(-))(G(9}(s) - G)(s-))F(0,t-s).(7)δ≤t中国煤化工MHCNM HGNo.5x.X. Kong et al: MARKOV SKELETON PROCESS IN PERT NETWORKS1445Let F3(01, t) be the probability from state 5 with elapsed θ1 to state 10Fs(01,t)= P((1,4*,01),t, (0,0)}[ q((1,4*,01),ds,(3*.,0))P((3*,4,0),t-s, (0,0)}F8(0,t - s)dG}2)(s).(8)Let F3(02, t) be the probability from state 3 with elapsed 02 to state 10F3(02,t)= P((2,3*,02),t, (0,0)}gq((2,3* ,02),ds, (3* ,4,0))P{(3* ,4,0),t-s, (0,0)}= | F+(0,t- s)dG(2(8).(9Let F4(01, 04, t) be the probability from state 4 with elapsed 01, 04 to state 10F4(01, 04,t)= P((1,4,01, 04),t, (0,0)}=f"sga((1,4,01, 0s),ds, (3,4,0,04 + s))P{(3, 4,0,04 +s),t- s, (0,0)}q((1, 4,01,0x),ds,(1,4*,01 + s))P{(1,4*,01 + s),t - s,(,)}- 2(G(<)- G()(G%{(a)- G(-))P(3,4" ,),t - ,(0.,0)} .= | (1-())Fe(0,04 +s,t - s)dG}g?(8)+1. (1 - GgE())Fs(01 +s,t- s)dG'%{(8)+ E(G?(<)- G(M()(C()- G)(1)F(0,t-).(10)Let F2(02, 03, t) be the probability from state 2 with elapsed 02, 03 to state 10F2(02, 03,t) = P({(2,3, 02, 03),t, (0,0)}= q((2,3,02, 03),ds, (2,3* ,日2 + s)P({(2,3* ,日2 +s),t-s, (0,0)}+ | q((2,3,02, 03),ds, (3, 4,03 +s,0))P((3,4,03+s,0),t-s, (0,)} .+ E(G2()- G(=(-)(C()()- G(-))P{(3+ 4,),t-,(0.0}8≤t[(1 - G()B(02 +s,t- sdG&{()[(- C()F6(03 + s0.1- sdl}()+ 2 (G(2)(s)-G}2)(s-))(G"8)(s)- G(3)(s-))F+(0,t-s).(11)中国煤化工MHCNM HG1446ACTA MATHEMATICA SCIENTIAVol.30 Ser.BLet F(01, 02, t) be the probability from state 1 with elapsed 01, 02 to state 10F1(01,02,t)= P((1,2, 01, 02),t, (0, 0)}= | q((1,2,0,02),ds, (2, 3,02 + s,0))P((2,3,02 + s,0),t -s, (0,0)}+ | q((1,2,01, 02),ds,(1,4,01 + s,0))P{(1,4,01 +s,0),t-s, (0,0)} .+ 2(G%?()- G&?(s- )(G})()- G唱(8- )(3,4,0,.0,0 - s(0.0}s≤t: [ (1 - ()F2(O2 + s,0,t - s)dGl)() .f[(a - G()F(Q. +&.0.t- sdC}() .+ > (G})(8)- G})(-))(G(2(3)- G2(s-))F6(0,0,t-s).s≤The completion timeof [= (1,3, 5) is equal to the completion time of G', that is the timefrom the initial state 1 to the absorbing state 10.F(t)= P{T≤t}= Fr(0,0,t),E(T)= | tdF(t),(13)Var(T)= | t2dF(t).4 Numerical ExampleFor showing the numerical stability of the theory developed in this paper, we give a numer-ical example. We consider the Example 3.1, assuming the duration of activity 5 is T-distributedwith parameters a= 1,β= 2, then the density and the remaining time distribution functionsaref()(x)=xe”if x≥0,0if x<0,ro∞ re-xdxAssume the duration of activities 1, 2, 3, 4, 6 are exponentially distributed with intensity para-meters 1,2,3, 4, 6, then the distribution of remaining time of each activity isG'"{(t)=G()(t)=1-e-it (i= 1,2,3,4,6).To calculate the distribution of the completion time of L = (1,3,5)， we only need toinvestigate the subnetwork G' of G. We obtain0sF(0s,t)=1-;1+051+051+05中国煤化工MHCNM HGNo.5 .x.X. Kong et al: MARKOV SKELETON PROCESS IN PERT NETWORKS1447F8(03,t)=- 2Fr(04,t)= 1-3F6(03,04,t)= 1-3tF(01,t)=1+;Fs(02,t)=1+35__9t.3t2F4(01,0s,t)=1-F2(02,03,t)= 1-3624°35F1(01,02,t)=1+-32~+ 322The completion time of L= (1,3, 5) is equal to the completion time of G', that is the time .from the initial state 1 to the absorbing state 10.5t_24~E(T)= | tdF(t) = 3.5119,Var(T)=。tedF()- E(T)2 = 29910.The mean and the variance of the sub-project completion time are computed as 3.5119and 2.9910, respectively.5 ConclusionIn this article, we deal with PERT networks with independently and generally distrib-uted activity durations. Through adding the elapsed times of each activity as supplementaryvariables and constitute the state :which involves an absorbing state, the state space isrelated to the structure of the network. Then, we model this network as a MSP, and computethe distribution of any path's length via the backward equation of MSP.One limitation of the method described in this article is that the state space can growrapidly with the network size. In practice, however, PERT networks tend to be sparse andproduce a reasonable size state space. For example, consider the network in Fig.3, which istaken from Loulou et al. in [9]. This network has 40 nodes and 65 arcs with a state space ofsize 125 441 and its generator matrix has 717 473 positive entries. And we can compute thedistribution of any path with computer easily.中国煤化工MHCNM HG14488ACTA MATHEMATICA SCIENTIAVol.30 Ser.Bjr⑧- 0一→@→@←→国一国Q⑨-0,四@70←→⑥→一φ\φ→0j⑤<\迪\①-四+国\~④<0-→国一 +0一 迪Fig.329References[1] Charnes A, Copper w, Thompson G. Critical path analysis via chance constrained and stochastic pro-gramming. Operations Research, 1964, 12: 460- 4702] Elmaghraby S. On the expected duration of PERT type networks. Management Science, 1976, 13: 299- 306] Van Slyke R. Monte carlo methods and the PERT problem. Operations Research, 1963, 11: 839 860[4 Jlulkarni V, Adlakha V. Markov and Markov. Regenerative PERT networks. Operations Research, 1986,[5] Azaron A, Katagiri H, Sakawa M, et al. Multi-objective resource allocation problem in PERT networks.European Journal of Operational Research, 2006, 172: 838- 8546] Azaron A, Tavakkoli-Moghaddam R. A multi-objective resource allocation problem in dynamic PERTnetworks. Applied Mathematics and Computation, 2006, 181: 163- 174[7] Azaron A, Katagiri H, Kato K, et al. Longest path analysis in network of queues. European Journal ofOperational Research, 2006, 174: 132- 149[8] Hou Z T, Liu G X. Markov Skeleton Processes and Their Applicatiop 2nd ed. Bejing: Science Press,Boston: International Press, 200] Loulou R, Beale T. A comparison of variance reducing techniques in PERT simulations. Canadian Journalof Operations Research and Information, 1976, 14: 259- 269304中国煤化工MHCNM HG