IN GENERALIZED PROJECT NETWORKS

IN GENERALIZED PROJECT NETWORKS

DAVID BLOKH, GREGORY GUTIN, AND ANDERS YEO Received 20 January 2003 and in revised form 20 June 2003

A project network often has some activities or groups of activities which can be per- formed at different stages of the project. Then, the problem of finding an optimal/accept- able time or/and optimal/acceptable order of such an activity or a group of activities arises. Such a problem emerges, in particular, in house-building management when the beginnings of some activities may vary in time or/and order. We consider a mathematical formulation of the problem, show its computational complexity, and describe an algo- rithm for solving the problem.

1. Introduction

A project network may well has some activities which can be performed at different stages of the project. In such cases, we wish to compute an optimal (or, at least, acceptable) time or order of such an activity. Such problems appear, in particular, in house-building management when the beginnings of some activities may vary in time or/and order (see [1]), in scheduling of medical examinations in areas with difficult ecological situations [7,9], and in building/city evacuation management [2,10]. For other applications, see [3,4,6].

Consider a mathematical formulation of the problem. LetG=(N,A) be a network, that is, finite acyclic digraph with unique sources. We will allow networks to have parallel arcs, that is, arcs with the same endvertices. The arc setAofGis partitioned into disjoint subsetsD,Ai (i=1, 2,...,r):A=_r

i=1Ai∪D. A setAi is called analternatingset. An arc from^r_i=1Ai is called analternatingarc. Avariant G=(N,A) ofGis a maximal subgraph ofGsatisfying the following conditions:sis a unique source ofG,|A∩Ai| =1 for alli=1, 2,...,r. Note that because of the maximality ofG, if distinct verticesxandy are inNand an arcabetween them is inD, thena∈A.

Associate with each arcaofGitstimet(a) andcostc(a). Thecostof a variantGis the sum of the costs of arcs fromGand thetimeofGis the time of a critical path (see [8]) inG. Given constantsCandT, one wishes to find a variant (if any) whose cost is at most Cand time is at mostT(theAV problem). Any such variant is calledacceptable.

Copyright©2005 Hindawi Publishing Corporation

Journal of Applied Mathematics and Decision Sciences 2005:2 (2005) 75–81 DOI:10.1155/JAMDS.2005.75

We prove that the problem of finding an acceptable variant is NP-complete (even ifG has a very simple structure). Moreover, we show that the problem of verifying whetherG has a variant (any variant) is also NP-complete. Therefore, the existence of a polynomial algorithm for solving the AV problem seems to be impossible. We describe an algorithm which generates all variants in a clever way in order to avoid construction of some non- variants. Having a variant, we check whether it is acceptable. The algorithm might be useful for moderate inputs.

The problem of finding an optimal variant in very special networks was first stated by Eisner [4]. Variants in general networks were considered in [6], yet every alternating set in [6] is formed by arcs with common initial vertex.

2. Complexity

Proposition2.1. The AV problem is NP-complete.

Proof. We transform the well-known NP-complete problem, KNAPSACK [5, page 247], to this problem. Let a setU= {1, 2,...,r}, and given integer sizeci≥0 and valuevi≥0, for everyi∈U, as well as positive integersBandK, constitute an arbitrary instance of KNAPSACK. In KNAPSACK, we wish to find a subsetW⊆Usuch that_i∈Wci≤Band i∈Wvi≥K. Let ¯W=U−W andV=_n

i=1vi. Then, KNAPSACK is equivalent to the problem of determining a setW⊆Usuch that_i∈Wci≤Band_j∈W^¯vj≤V−K.

On the other hand, the last problem is clearly equivalent to the following special case of the AV problem: letG=(N,A) be the network withN= {x1,x2,...,xr+1},A=_r

i=1Ai, whereAi= {ai,a_i},ai anda_i are parallel arcs with initial vertexxiand terminal vertex xi+1. The cost of an arcai(ai, resp.) isci(0, resp.) for alli=1,...,r. The time of an arcai

(a_i, resp.) is 0 (vi, resp.). SetC=B,T=V−K.

Now we consider the problem of checking whether a given networkGhas a variant (the EV problem). We first restrict ourselves to a slight extension of networks considered in the proof ofProposition 2.1, namely, to “multipath” networks with vertex set N= {x1,x2,...,xr+1}and arc setA=_r

i=1Ai, where every arc inAj has the formxjxj+1 (Aj

may contain several arcs). Then the EV problem is polynomial time solvable due to its simple transformation into the perfect matching (in bipartite graphs) problem. However, in general, the EV problem is NP-complete.

Theorem2.2. The EV problem is NP-complete.

Proof. We transform the well-known problem 3-SAT [5, page 46] to the EV problem. Let U= {u1,...,uk}be a set of variables, letC= {c1,...,cm}be a set of clauses such that every cihas three literals, and letvilbe thelth literal in the clauseci. We will construct a network Gwhich has a variant if and only ifCis satisfiable.

We construct networkG as follows. We start with the verticess,x1,...,x2k and arcs sx1,...,sx2k. For everyi=1,...,kand every j=1,...,m, if the variableuibelongs to the clausecj, we add the arcx2i−1yij, where yij is a new vertex. Analogously, for everyi= 1,...,kand everyj=1,...,m, if the negation ofuibelongs to the clausecj, we add the arc x2izij, wherezijis a new vertex. The arcssx2i−1,sx2iconstitute the setAi(i=1,...,k). All arcs of the formsx2i−1yijandx2izijconstitute the setAk+jfor j=1,...,m.

We will prove thatGhas a variant if and only ifCis satisfiable.

Suppose first thatCis satisfiable and consider a truth assignmentαforUthat satis- fies all the clauses inC. Letvj,lj, j=1, 2,...,m, be true underα. Construct a variantG (starting from emptyG) as follows. For every j=1, 2,...,m, ifvj,lj is a variableui, then the arcssx2i−1andx2i−1yij(along with their vertices) are added toG, otherwise, that is, vj,lj is the negation of a variableui, the arcssx2i andx2izij are added toG(we do not append arcs which are already inG). Clearly,Gcontains exactly one arc from each of the setsAk+1,...,Ak+m. Moreover, it has at most one arc from each of the setsA1,...,Ak

since a variable and its negation cannot be both true underα. However,Gmay contain no arcs from some of the setsA1,...,Ak. After appending representatives of such sets to Gwe clearly obtain a variant ofG.

The above arguments can be “reversed” in order to prove that ifGcontains a variant,

thenCis satisfiable.

3. Algorithm

In this section, we describe an algorithm, which finds all variants of a network. The algo- rithm is illustrated by an example in the full version of the paper inwww.cs.rhul.ac.uk/

home/gutin/. LetG=(N,A) be a network, as described in the introduction. SetAr+1=D and let (A1,A2,...,Ar) be some ordering of the alternating sets inG. Furthermore, let Ai=(a⁽1ⁱ⁾,a⁽2ⁱ⁾,...,a⁽_|Aⁱ⁾_i|) be some ordering of the arcs inAi(i=1, 2,...,r). Define the ver- ticesu⁽_kⁱ⁾andv_k⁽ⁱ⁾, such thata⁽_kⁱ⁾=u⁽_kⁱ⁾v_k⁽ⁱ⁾for alli=1, 2,...,randk=1, 2,...,|Ai|. Afeasi- bler-tuple,α=(α1,α2,...,αr) is an ordered set of integers, such that 1≤αi≤ |Ai|for all i=1, 2,...,r. Ifαis a feasibler-tuple then let (α)j(or justαj) denote thejth entry in the tupleα. Ifαandβare feasibler-tuples, and there exists an integer j≥1, such thatαi=βi

for alli=1, 2,...,j−1 andαj< βj, then we say thatα≺βand thatω(α,β)=ω(β,α)=j. Finally, ifαis a feasibler-tuple, thenA^∗(α)= {a⁽¹⁾α1,a⁽²⁾α2,...,a⁽α^rr⁾}.

We now show the following lemma.

Lemma3.1. Given a feasibler-tupleα, we can, inO(|N|²)time, decide if there is a variant G=(N,A), withA^∗(α)⊆A.

Furthermore if such a variant exists, then it is unique.

Proof. Define a networkG^∗, a vertex setB, and an arc setCas follows:

G^∗=

V(G),A^∗α∪Ar+1 , B=

b: there is a path fromstobinG^∗, C=A^∗α∪

uv:uv∈Ar+1and{u,v} ⊆B.

(3.1)

It is easy to check that there is a variant (containing the arcs fromC) inG^∗if and only if{u⁽αⁱi⁾,vα⁽ⁱi⁾} ⊆B, for alli=1, 2,...,r. Furthermore using normal breadth-first search,B can be found inO(|N|²) time, which implies thatCcan be found inO(|N|²) time. This proves the first part of the lemma.

The second part follows immediately since if there is a variant inG^∗, then it must be

precisely the one containing all the arcs inC.

The trivial algorithm now consists of generating all feasibler-tuples, and for each one testing if there is a corresponding variant, usingLemma 3.1. This implies an algorithm which is quite simple and runs inO(|N|²Π^r_i=1|Ai|) time. However, in many cases, we can do better than this. Before we describe our algorithm we need a few definitions and lemmas.

For a network G=(N,A) and set B, GB denotes the subgraph of G induced byB.

Definition 3.2. Letαbe a feasibler-tuple andG=GA^∗(α)^r_k⁺¹_=jAk.Definem(α,v) for all verticesv∈N, as well asp(α) andq(α) in the following manner:

mα,v=maxj≤r+ 1 :∃a path fromstovinG, (3.2) pα=minmaxmα,u⁽ⁱ⁾_k : 1≤k≤Ai: 1≤i≤r, (3.3) qα=minmaxmα,u⁽ⁱ⁾_αi ,i: 1≤i≤r. (3.4)

Observe fromDefinition 3.2that a variant including the arcs{a⁽¹⁾α1,a⁽²⁾α2,...,a^(l)αl}(0≤ l≤r) cannot include any vertexv, withm(α,v)≤l. The definition of p(α) implies that p(α) is the largest value, such that for every alternating set,Ai, there is an arcu⁽ⁱ⁾_k v_k⁽ⁱ⁾∈Ai

withm(α,u⁽ⁱ⁾_k )≥p(α). Similarly,q(α) is the smallest number, such that there is ani∈ {1, 2,...,r}withm(α,a⁽ⁱ⁾αi)≤q(α) andi≤q(α). The meaning ofm(α,v), p(α), andq(α), should hopefully become clear afterLemma 3.3.

Lemma3.3. Letαandβbe feasibler-tuples, withω(α,β)= l. Then the following hold.

(i)Any variant including the arcsA^∗(β)cannot include any vertexv, withm(α,v)< l. (ii)If l > p(α), then there is no variant including the arcsA^∗(β).

(iii)If l > q(α), then there is no variant including the arcsA^∗(β).

(iv)Givenαwe can computem(α,v)for allv∈N,p(α)andq(α)inO(|N|²)time.

Proof. (i) Any variant including the arcs A^∗(β) also includes the arcs {a⁽¹⁾α1,a⁽²⁾α2,..., a⁽α^ll⁻−1¹⁾}. By the remarks afterDefinition 3.2, there is no path from stov, inGA^∗(β)∪ Ar+1, for any vertexvwithm(α,v)≤l−1< l.

(ii) Ifl > p(α), then there exists an alternating setAi, with max{m(α,u⁽_kⁱ⁾) :k=1, 2,...,

|Ai|} =p(α)< l. Thereforem(α,u⁽_kⁱ⁾)< l, for all arcsu⁽_kⁱ⁾v_k⁽ⁱ⁾∈Ai. By (i), no arc inAilies in any variant includingA^∗(β), so there is no variant including A^∗(β).

(iii) Ifl > q(α), then there is ani∈ {1, 2,...,r}, such that max{m(α,u⁽αⁱi⁾),i} =q(α)< l.

This implies thatm(α,u⁽ⁱ⁾αi)< landi < l. It follows thata⁽ⁱ⁾αi does not lie in any variant includingA^∗(β), so there is no such variant.

(iv) LetGr=GA^∗(α)∪Ar+1. Using breadth-first search onGr, we find all the ver- ticesVrwhich can be reached fromsinGr. We then contract all the vertices inVr(note s∈Vr) into the vertexs. Then we add all the arcs fromArto obtain the graphGr−1. Using

breadth-first search onGr−1, we find all the verticesVr−1which can be reached fromsin Gr−1. Continuing this process, we obtain the setsVr,Vr−1,Vr−2,...,V1. Clearly if a vertex vis not inVr∪Vr−1∪ ··· ∪Vk+1, butv∈Vk, thenm(α,v)=k. Furthermore, the time used in total isO(^r_k=1|Vi|²)=O(|N|²).

To compute p(α), we first compute temp(i)=max{m(α,u⁽ⁱ⁾_k ) :k=1, 2,...,|Ai|}, for eachi=1, 2,...,r, inO(^r_i=1|Ai|) time. Then we can computep(α) inO(r) time using the values temp(i), which implies thatp(α) can be computed inO(|N|²) time.

We can computeq(α) in O(|N|²) time as we can get max{m(α,u⁽ⁱ⁾_k ),i}in constant time for eachi=1, 2,...,r. This completes the proof of the lemma.

We now present our algorithm.

Step 1. Letα1=(1, 1,..., 1) be a feasibler-tuple (it hasrones). Letc=1.

Step 2. UseLemma 3.1to decide whether there is a variant including the arcsA^∗(αc). If there is a variant, then print it.

Step 3. Computem(αc,v) for allv∈N, and computep(αc) andq(αc) (seeDefinition 3.2 andLemma 3.3). Letβ=αcandk=min(p(αc),q(αc),r).

Step 4. Setβk=βk+ 1. Whilem(αc,u^(k)_βk)< kandβk≤ |Ak|increase the value of βkby one. Afterwards ifβk>|Ak|, then decrease the value of kby one and stop if k=0, or return to the start ofStep 4otherwise.

Step 5. For j=k+ 1,k+ 2,...,r, letβjbe the smallest value such thatm(αc,u^(j)_βj)≥k.

Step 6. Letc=c+ 1,αc=βand return toStep 2.

Theorem3.4. The above algorithm finds all possible variants inO(C|N|²)time, whereC is the value ofcwhen the algorithm terminates.

Proof. We first show that, inStep 5, there is always a valueβj, such thatm(αc,u⁽_β^j_j⁾)≥k, for all j=k+1,k+2,...,r. Assume that this is false, then max{m(αc,u⁽_β^j_j⁾) :βj=1, 2,...,|Aj|}

< k, which implies thatk > p(αc). This is however a contradiction against the definition ofk, and the fact that the value ofknever increases inStep 4. Asα1≺α2≺ ··· ≺αC, this implies that the algorithm terminates.

We will show that if there is a feasibler-tupleγ=(γ1,γ2,...,γr), and an integer c, such thatαc≺γ≺αc+1, then there is no variant including the arcsA^∗(γ). The case when

αC≺γ(Cis the maximum value ofc) will then be analogous. This will imply the theorem since we have usedLemma 3.1to check if there is a variant including a feasibler-tuple, for all feasibler-tuples which may be included in a variant.

Letx=ω(αc,γ),z=ω(αc+1,γ). Consider two cases.

Case 1. x >min(p(αc),q(αc),r).

We have eitherx > p(αc) orx > q(αc), which byLemma 3.3implies that there is no variant including the arcsA^∗(γ).

Case 2. x≤min(p(αc),q(αc),r).

Note that every newr-tupleαc+1equals currentβinStep 6. Note that byStep 4per- formed last time beforeStep 6,k=ω(αc,αc+1). We havez > kasαc<γ <αc+1.

We now prove thatm(αc,u⁽γ^zz⁾)< k. Then, byLemma 3.3, there is no variant including the arcs ofA^∗(γ). Assume thatm(αc,u⁽γ^zz⁾)≥kand consider the following three subcases.

Subcase 2.1(x > z). By the assumption ofCase 2,x≤min(p(αc),q(αc),r). Clearly,γx>

(αc)_x. Therefore, inStep 4, the algorithm would have chosenk≥x. Thus,k≥x > zwhich impliesk > z. However, (αc+1)z> γz=(αc)z(asx > z), which means thatz≥k; a contra- diction.

Subcase 2.2(x=z). Hence, (αc)_z< γz<(αc+1)_z.Thus,Step 4would have terminated with βz=γzrather than (αc+1)z; a contradiction.

Subcase 2.3(x < z). We have (αc)_x< γx=(αc+1)_x (asx < z). It follows thatk≤x < z. Thus, inStep 5,βz would have been smaller than or equal toγz rather than (αc+1)_z; a contradiction.

We have now shown that if there is a variant inG, then our algorithm must find it. It is easy to show that the complexity of our algorithm isO(C|N|²) (usingLemma 3.3).

We note thatCdenotes a number of distinct feasibler-tuples, which implies thatC≤ Π^r_i=1|Ai|. Therefore our algorithm will never take more time asymptotically, than the trivial algorithm. In some cases our algorithm will however be considerably faster than the trivial algorithm. The speed of our algorithm also depends on the ordering of the alternating setsA1,A2,...,Ar. We will not use great length to describe an optimal ordering of the alternating sets, however it is always a good idea to let the alternating sets which can reach many other alternating edges have small indices.

Using the proof ofTheorem 2.2, we can transform every instance of the 3-SAT prob- lem into a network. We call the networks obtained in this way3-SAT networks. We will now see how much time we may need to find a variant in a 3-SAT network. LetVdenote the number of variables in an instance of the 3-SAT problem and letCbe the number of clauses. LetN=V+C. Clearly the trivial algorithm takesO(N²2^V3^C) time. For com- parison we prove the following theorem, which shows that our algorithm is considerably faster than the trivial algorithm in some cases.

Theorem3.5. LetGbe a 3-SAT network. If we order the alternating sets, such that the sets corresponding to variables have smallest indices, then our algorithm takesO(N²2^V)time to find a variant inG.

Proof. Let the alternating setsA1,A2,...,AV correspond to variables and the alternating setsAV+1,AV+2,...,AV+Ccorrespond to clauses. Letr=V+Cand letαc=(α1,α2,...,αr) be a feasibler-tuple at thecth iteration of our algorithm. Let theith variable be true if and only ifαi=1. If some clause is false, then we note that all arcsuvin the corresponding alternating set havem(αc,u)≤V. Therefore our algorithm will have p(αc)≤V, which implies that no two tuples in{α1,α2,...,αC}can have the same values in the firstVplaces.

ThereforeC≤2^V, which implies the theorem.

It can be shown that the value ofqin our algorithm does not speed up the algorithm, except possibly in the first iteration. After the first iteration we will always haveq(αc)≥ min(p(αc),r).

References

[1] H. M. Ahuja,Construction Performance Control by Networks, John Wiley & Sons, New York, 1976.

[2] L. G. Chalmet, R. L. Francis, and P. B. Saunders,Network models for building evacuation, Man- agement Sci.28(1982), no. 1, 86–105.

[3] E. A. Dinic,The fastest algorithm for the PERT problem with AND-and OR-nodes, Proc. Integer Prog. and Combinatorial Opt. Conference, University of Waterloo Press, Waterloo, 1990, pp. 185–187.

[4] H. Eisner,A generalized network approach to the planning and scheduling of a research project, Oper. Res.10(1962), no. 1, 115–125.

[5] M. R. Garey and D. S. Johnson,Computers and Intractability. A Guide to the Theory ofNP- Completeness, W. H. Freeman and Company, California, 1979.

[6] N. A. J. Hastings and J. M. C. Mello,Decision Networks, John Wiley & Sons, Chichester, 1978.

[7] V. K. Ivanov, A. I. Gorsky, A. F. Tsyb, M. A. Maksyutov, and E. M. Rastopchin,Dynamics of thyroid cancer incidence in Russia following the Chernobyl accident, J. Radiol. Prot.15(1990), 305–318.

[8] E. Minieka,Optimization Algorithms for Networks and Graphs, Industrial Engineering, vol. 1, Marcel Dekker, New York, 1978.

[9] K. B. Moysich, R. J. Menezes, and A. M. Michalek,Chernobyl-related ionising radiation exposure and cancer risk: an epidemiological review, Lancet Oncol.3(2002), no. 5, 269–279.

[10] Z. Sinuany-Stern and E. Stern,Simulating the evacuation a small city: the effects of traffic factors, Socio-Econ. Plann. Sci.27(1993), no. 2, 99–108.

David Blokh: Department of Physics, Bar-Ilan University, Ramat Gan 52900, Israel E-mail address:[email protected]

Gregory Gutin: Department of Computer Science, Royal Holloway University of London, Egham, Surrey TW20 0EX, UK

E-mail address:[email protected]

Anders Yeo: Department of Computer Science, Royal Holloway University of London, Egham, Surrey TW20 0EX, UK

E-mail address:[email protected]