BOUNDS ON EXPECTED PROJECT TARDINESS John R. Birge Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Marilyn J. Maddox Ford Motor Company Manufacturing Development Center Detroit, MI 48239 Technical Report 93-1 January 1993

Bounds on Expected Project Tardiness John R. Birge* Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109 Marilyn J. Maddox Ford Motor Co. Manufacturing Development Center Detroit, MI 48239 December 28, 1992 Abstract A frequent goal in scheduling projects and production operations is determining the costs associated with the project duration or production lead time. This paper considers costs that increase proportionally to time in excess of a deadline. New bounds on the expected value of these tardiness costs are given. The bounds provide robust measurements without requiring extensive assumptions about activity distributions. Keywords: Bounds, Stochastic programs, Project Networks, Scheduling. Project management requires information on future activity durations. This information helps determine when the project will be completed under a given scheduling policy. The random nature of most future activity durations, however, makes a complete description of project completion time difficult. Even calculating the expected project completion time, or any other function of project completion time, is difficult. Thus, many approximations and bounds on functions of completion time have been proposed. *Supported in part by Office of Naval Research Grant N00014-86-K-0628 and the National Science Foundation under Grant ECS-8815101 and DDM-9215921. 1

Tight bounds on completion time generally require complete information about the joint distribution of the project activities. In most applications, however, little data is available on the probability distributions of the individual random activity durations and the interactions among activity durations. In this paper, we assume limited information on individual activity durations to develop bounds on the expected tardiness of a project. The tardiness of a project rises linearly after a deadline is passed but it is zero before the deadline. Thus, tardiness is a piecewise linear function of completion time and is, therefore, more difficult to calculate than the expected completion time. Much of the literature in stochastic project scheduling is devoted to estimating the expected completion time for a project. The traditional approach to this problem is PERT, Program Evaluation and Review Technique, developed by Malcolm, Roseboom, Clark, and Fazar [1959] among others. When the activities in a project are independent and the critical path determined by substituting expected activity durations for the actual durations is longer than any realized path, the PERT procedure may yield the true mean and variance of project completion time. In general, the PERT estimate of expected completion time is a lower bound on the true expected project completion time. The PERT lower bound is attractive because it requires relatively little information about the activity duration distributions and makes no assumptions about the relationships among the activities. At the expense of requiring more information about the activity durations, Fulkerson [1962], Clingen [1964], Elmaghraby [1967], and Robillard and Trahan [1976], among others, derived tighter lower bounds on project completion time. Each assumed full activity distributions and that durations on all pairs of arcs terminating at different nodes were independently distributed. Under similar assumptions, Kleindorfer [1971], Shogan [1977] and Dodin [1985] all found upper bounds on the expected project completion time. The upper bounds discussed above and the refinements of the PERT lower bound all require complete information about the activity duration distributions. They also assume that at least some of the activities are independent. From a practical standpoint, bounds which require only partial information about the activity durations and allow general dependence among the activities are desired. Assuming only the means and variances of the activity duration distributions are known, Devroye [1979] obtained upper bounds on the first two moments of the project completion time. He 2

assumed independence among the activities, however. Kamburowski [1985) also made limited assumptions to derive an upper bound on the expected project completion time. He assumed the mean of each activity duration and that the distributions of the activity durations were independent and "new-better-than-used" in expectation (NBUE, see, for example, Barlow and Proschan [1975]). Several researchers have derived bounds without making independence assumptions. Anklesaria and Drezner [1986], for example, derive bounds on the probability of completing a project by time T. They assume the mean and variance of each arc and the correlation coefficient between every pair of arcs. Meilijson and Nadas [1979] present an upper bound on the expected project completion time which does not require correlation information, but they assume the complete. marginal distributions. Riishendorf[1982] uses their method to find a closed form upper bound for the expected completion time in a series network. Weiss[1986] considers their work in a more general framework and applies the method to several other types of network problems. The above literature establishes bounds on the project completion time distribution and its moments. These bounds are useful for some scheduling objectives, but tardiness is often the key factor in the scheduling objective. Tardiness costs could be contractual, for expedition or overtime, or reflections of loss of market share. Our goal here is to provide ranges for expected tardiness costs that can be used in making informed scheduling decisions. Generally, bounds on expected project tardiness do not follow directly from the completion time bounds. An exception is the Meilijson and Nadas bound, which because of its form, is also an upper bound on the expected tardiness of a project. Their bound is equivalent to an upper bound on the expected project tardiness developed by Klein Haneveld [1986] using a moment problem approach. Klein Haneveld allows general dependence among the activities and extends his approach to the case where only limited information on the marginal distributions is available. A more thorough discussion of his work is included in a later section. This paper is organized as follows. Our notation is summarized in Section 1. In Section 2, a moment problem formulation for determining the expected tardines of a project is described. Relevant theory on the solution of moment problems is presented in Section 3. In Section 4, bounds on the expected tardiness of a given project are discussed, asssuming various levels of information about the activity durations. Each of these bounds is the solution of a moment problem. Section 5 extends our approach to bounding the expected total tardiness of a project with multiple due 3

date. Some computational results are presented in Section 6 that demonstrate the usefulness of additional information about the random activity durations. 1. Notation In the network representing a project, each arc represents a project activity and each node indicates the completion of all activities leading into that node. We follow Klein Haneveld's notation. Let i = 1,..., n represent the arcs in the project network. Denote the length of arc i by the random variable (i and let 4 = (41,...,n). Let ai be the minimum length of arc i and let bi be the maximum length. We assume the minimum length of each arc is nonnegative and finite. The maximum length may be infinite. Let S be the range of 4. Here, - = (al, bl) x (a2, b2) x... x (a1, bn). Denote the mean length of arc i by (i and denote the joint mean by Z = (41,..., n) We are interested in the tardiness of a project. Let Bj, j = 1,..., p be the index set of activities on path j from the initial node to the final node of the project network. The project completion time is: R() = max i. j=i,...,P i E B Similarly, lower and upper bounds on the project completion time are given by: R(a)= max a ai R(b)= max bi. j=1,...,p. i E B1 j= l,...P i Bj Let T be the project due date. Then, the project tardiness is (R(4) - T)+. Table 1 summarizes the notation used in this work. 2. Moment Problem Assuming the first N moments of each arc, or activity, duration distribution are known, the problem of determining an. upper bound on some function of the random arc durations, 0(4), can be written mathematically as follows. Find: sup E(~(4)) s.t. f4idP(4) = E(4i) i=l,...,n 4

= length of arc (duration of activity) i n = number of activities = mean length of arc i ai = minimum length of arc i bi = maximum length of arc i Bj = index set of arcs on path j from the initial node to node n R(,) = project completion time R(a) = lower bound on project completion time R(b) = upper bound on project completion time Cj = upper bound on jth moment of project completion time T = project due date b(~) = objective function 5 = range of E(x) = expectation of random variable x Var(x) = variance of random variable x Pr(A) = probability of event A 1{A} = indicator function of event A Table 1: Summary of Notation /f'~dP(() = E(e) i = l,...,n (2.1) ai _ ~i < bi, i = 1,..., n, where P is a joint distribution of 4 satisfying the given constraints. Let P be the family of all such distributions. Then, our goal is to find a P E P maximizing E(4(()). If the objective is expected tardiness, 0(() = (R(4) - T)+. The above problem belongs to the class of moment problems (see Krein and Nudelman [1977]). These problems are of interest in many areas of mathematics and its applications, including statistics (see, e.g., Dantzig and Wald [1951]). Project scheduling decisions fit into the framework of stochastic programming. Uses of the moment problem in this context appear in Dupacova [1977], Ermoliev, Gaivoronski and Nedeva [19851, Prekopa [19881 and Birge and Wets [1987]. The next section reviews relevant theory on moment problems and presents a procedure for solving them. 3. Solving Moment Problems This section begins by presenting several theorems which are important in the development of a general solution procedure for moment problems. Suppose we wish to solve the following moment 5

problem with power moment constraints: sup(inf) f b0() dP(g) s.t. Ia dP(g) < E(g) |fN dP(() < E((N), (3.1) where, - is the range of C. The first two theorems treat instances where E is compact. In our application, E is compact when the maximum length of each arc is finite. The results use the theory of weak convergence of probability measures (see Billingsley [1968]). Thereom 1 Suppose _ is compact. Then the set of probability measures that satisfy (1.1), P, is convex and compact (with respect to the weak topology) on the set of probability measures over the domain of. Proof See Birge and Wets [1986], Theorem 6.9.. As a result of the above theorem, any probability measure in P can be represented as a convex combination of the extreme points of P. As the proof in Birge and Wets explains, this indicates that maxima and minima exist. Any measure in P that extremizes fa 0()) dP(~) is called an extremal measure of P, i.e., the extreme points of P are called extremal measures. The following theorem characterizes these extremal measures. Thereom 2 Assuming 0 is continuous relative to _, the probability measure that extremizes fE 0(g) dP(g) is an extreme point of P. Moreover, the extremal measures of P are precisely those having a finite number of points with positive probability, (~,...., ), with L < N + 1. Proof See Birge and Wets [1986], Theorem 6.9.. As a consequence of the above theorem, the search for an optimal distribution need only involve distributions with N +1 or less atoms, i.e., distributions with N + 1 or less points with positive probability. When 2 is not compact, the above theorems no longer pertain. In our application, E is not compact if the maximum length of any arc is infinite. In order to get a solution to the moment problem when 5 is not compact, we must expand P to include nonnegative measures. 6

In this case, we must consider the recession directions, d, of E, i.e., directions such that +XAd E E for all ( E - and A > 0. Extreme directions of the cone spanned by the recession directions are included in the representation of P. Essentially, this is a way to "compactify" - (Birge and Wets [1987]). Then, any measure in P can be described by a convex combination of extreme points and nonnegative combination of extreme directions of P. Note that the measures in P are nonnegative measures, but not necessarily probability measures. Thus, the function attaining the extreme value may not be a distribution function. However, the extremal measures of P still have finite molecular support. Hence, for a moment problem with N constraints, the optimal extremal measure has at most N + 1 points or directions with positive measure. Consider the upper bounding moment problem 2.1 where q(() = (R(,) - T)+. The preceding theorems ensure that any extremal measure P* solving this problem has at most M = nN + 1 atoms. Let the atoms be l',...,M, where d denotes the ith element of (J. Let pj = P*( = P*) = *(l = i,...,n = n). To determine P* we need to find l,...,M and pi,...,PM. If the maximum arc lengths are all finite, P* is a probability measure and pi +.. +PM = 1 If not, P* is a nonnegative measure and the subset of P1,..., PM corresponding to extreme points sums to one. All of the pj, j = 1,..., M are nonnegative. In the following, we consider a basic generalized linear programming (see Dantzig [1963]) procedure to develop bounds, assuming finite arc lengths. The procedure is the same with infinite arc lengths. Select some feasible ~1,..., M. Problem 2.1 can now be written: sup W_( )pi s.t. EM i = E(i) i=,...,n E =l())Npj) i,...,n Pi +...+PM = 1 pj>O, j=1,...,M. Since l,...,M are chosen to make this problem feasible, it must have a solution. The solution, Pl.,,PM and fl,...,M, is optimal if the corresponding dual problem is feasible. The dual 7

variables, (ull,..., ul,..., UNl,..., UN, UO), are chosen to find: inf uo + t=l E(4i)uli +... + Z?=1 E(N)UNi s.t. uo + t =iui+... + E=()NuN > 0() V uo and Uji, j = 1,..., N, i = 1,..., n unrestricted, where by complementary slackness, n n uo + E uul +... + E(g)NuN, = (j) V j = 1,..., M. i=1 i=l If a feasible dual solution can be found, the distribution P*(4 = 4j) = pj, j = 1,..., M is optimal. Otherwise, there must exist some 4 for which Uo + Fiuli, +... + E(4,)N uN <'(). i=l i=l Substitute this 4 for some atom iJ to obtain a new measure P**, such that f 0() dP**(4) ~> () dP*(4). Repeat the process until an extremal measure is found that is dual feasible. This generalized linear programming algorithm is guaranteed to converge to within any sneighborhood of the optimum in a finite number of iterations (Birge and Wets [1986]). Generalized linear programming may, however, be too time consuming for project scheduling implementation. Thus, of particular interest to us are special cases of moment problems for which closed form solutions are available. The next subsection outlines the particular cases that we will consider. An alternate moment problem for finding the upper bound on the tardiness of a project is also described. This moment problem is sometimes easier to solve than the one stated above. 4. Upper Bounds on Expected Tardiness In general, a moment problem can be solved to obtain either lower or upper bounds. Since lower bounds are easily obtained, we concentrate on upper bounds. They represent conservative estimates on the expected tardiness and can be used in conjuntion with the lower bounds to make prudent decisions. 8

A lower bound on the expected project tardiness is obtained by replacing each random arc length by its expected value and computing the tardiness in the resulting deterministic network. This bound is a direct application of Jensen's inequality. Another obvious lower bound results from using the minimum length on each arc. Arc lengths often do not have obvious maximum lengths, however, and Jensen's inequality does not apply. The computation of upper bounds, therefore, requires a different type of analysis. We follow the moment problem framework to establish upper bounds given various moments of the individual arc duration distributions. In general, as more information is available, the bounds become tighter. In all cases, no particular dependence relationship among the arcs is presumed. Studying the bounds obtained under different information levels allows us to examine the value of additional information about the arc durations. Thus, we can begin to understand the tradeoff between requiring more information about the arc durations and the tightness of our bound. The particular levels of information treated are: * finite range known; * range, finite or infinite, and finite mean known; * range, finite or infinite, finite mean and second moment known. In each case, the given arc moment information is incorporated into the moment problem 2.1. The solution of this problem yields an upper bound on the expected project tardiness. Thus, we are interested in solving moment problems with O,n, and 2n constraints respectively. This is the approach taken by Klein Haneveld. It obtains an expected tardiness value that is tight in the sense that some distribution that meets the assumed criteria achieves that bound. The rest of this section presents bounds, or procedures for finding bounds, on the expected project tardiness when different numbers of moments of the arc duration distributions are available. We extend Klein Haneveld's results to additional cases below. Finite Range Known Thereom 3 When only the finite range, [ai, bi], of arc i is known, E(R() - T)+ < E(R(b) - T)+. 9

Proof When only the finite range, [ai, bi], of arc (i is known, the optimal value of the following moment problem provides an upper bound on the expected project tardiness: sup E(R(~)-T)+ s.t. al <_ 1 < bl an S < n < bn One feasible distribution is Pr(~i = bi) = 1. Under this distribution, E(R() - T)+ = (R(b) - T)+. Since this is the absolute maximum value of E(R(() - T)+, it is an upper bound. u Range and Mean Known When the range and mean of each arc (i are known, the optimal value of the following moment problem provides an upper bound on the expected project tardiness: sup E(R() - T)+ s.t. f e dP(,) = l f fn dP() = ai < Ci <: bi, V i,i = 1,...,n, where bi, the maximum length of each arc, may be infinite. Klein Haneveld assumed finite arc lengths in deriving his results. We present his basic analysis below and then derive more extensive results. Using duality theory, Klein Haneveld solves: sup E0 (R(~) - T)+ eEe(Fl,...,Fn) where Fi denotes the distribution function of the duration of the ith arc and e is the family of joint distributions compatible with this marginal arc distribution information. After several simplifications, the dual problem reduces to the following simple recourse stochastic program: m n ((R(z) - T)+ + E( - zi)+). (4.1) 10

Each zi can also be restricted to [ai, bi] without increasing the optimal value. Klein Haneveld extends his approach to the case when only partial information on the arc duration distributions is available. Mathematically, the procedure is to find: n sup min (R(z) - T) + EF i - zi)+ (4.2) <Ii z~E \ i=l / where 4i is the class of distribution functions Fi compatible with the partial information. Klein Haneveld's main requirement for solving the problem is that the same Fi E 1i be the worst-case distribution for all Zi E en. Let Ff* be the distribution which maximizes EFi (i - zi)+ for all Zi E son. The supremum and minimum above can now be interchanged and the new problem is to find: i ((R(z) - T)+ + E. (hi - zi)+. This is just the reduced moment problem (4.1). Note that if the Fi are known completely, then this minimization represents the worst case over all joint distributions with given marginals. This result appears in Meilijson and NAdas [1979]. Weiss [1986] shows how to obtain a worst case distribution with known marginals that has the same expectation as (4.2). To use Klein Haneveld's procedure when the mean and range of each arc are known, we must first determine the worst-case distribution of each arc. When bi is finite, the worst case distribution is known as the Edmundson-Madansky (Madansky [1960]) inequality and has the form, Pri = Pr(~i = ai) = = a bi -a li bi - ai Note that this distribution is independent of zi. Klein Haneveld does not consider instances where bi is infinite. The following theorem establishes the worst-case measure for (i when bi is infinite. In this case, as described in Section 3, we must include the recession directions of 3 in our search for an optimal measure. Thereom 4 When bi is infinite, the nonnegative measure, P*, solving sup (i - zi)+dP(c) s.t. i dP(~) = (i ai <_ i < bi 11

has measure 1 on extreme point ai and measure 4i - ai on recession direction 1. Thus, the optimal objective value is (ai - zi)+ + i - ai. Proof Ben-Tal and Hochman [1972] show that the optimal objective value is (ai - zi)+ + (i - ai. The corresponding optimal nonnegative measure is calculated using the procedure outlined in Birge and Wets [1987]. Here, the range of 4i, 2i, equals [ai, oo). We require ext Ei, a collection of points containing the extreme points of -i and ext-rc -i, a collection of points spanning the recession cone of -i. Let ext i = ai and ext-rc -i = 1. Let f((i) = (4i - zi)+. Denote by rc f(x) the recession function of function f in the direction x. By definition, rc f (c) = lim f (6i + tx)-f ((i) rc f(x)= lim t —,oo t By Theorem 2.1 in Birge and Wets, sup (i - zi)+dP()= sup J f(e) v(de) +1 rc f (r)T(dr), v, xt ext-rc = where v is a probability measure on (ext 2i, A), and /i is a nonnegative measure on (ext-rc Ei, B) such that f e (de) + r p(dr) = Jext2, ext-rc 2 A and B are Borel sets. Now, ext Ei = ai, hence v(ai) = 1. Then, since ext-rc -i = 1, we have ai + 1p(1) =, and thus, i(1) = i - ai. Therefore, the nonnegative measure P* solving this moment problem has P*(ext,) = 1 and P*(rc-ext,) = i - ai. It remains to evaluate rc f(1): rcf(1) = lim f(~i+t)-f(i) t —oo t lim (i + t- zi)+ -(i-Zi)+ lim t t —oo t = 1. Thus, the optimal objective value is (ai - zi)+ + l(4i - ai). Since the optimal measure is independent of zi V i, the supremum and minimum in (4.2) can be 12

interchanged. Thus, we can use Klein Haneveld's procedure whether the range of the arcs is finite or infinite. Let H1 denote the index set of arcs with finite maximum length and H2 denote the index set of arcs with infinite maximum length. Then, an upper bound on the expected tardiness is found by solving: mm ((R(z) - T)+ + E (Pr(i = ai)(ai - zi)+ + Pr(4i = b)(bi - z)+)+ ZE~~n ~ iEH1i E [ -ai-^) + Hi-a]i, where Pr(fi = ai) = (bi - i)/(bi - ai) and Pr(fi = bi) = ( - ai)/(bi - a). Since zi can be restricted to [ai, bi] without affecting the optimal value, the (ai - zi)+ portions of the objective can be set to zero. Then, the problem we must solve reduces to min (R(z) - T)+ + A Pr(~i = bi)(b - z)+ + [- a]) (4.3) iEH1 iEH2 Problem 4.3 is a linear program which is easily solved to yield an upper bound. When the maximum duration of every arc is infinite, this linear program can be solved by inspection. It reduces to: m ((R(z) - T) + -ai Since (R(z) - T)+ is nondecreasing in z, the optimal solution in this case is zi = ai for every i. The optimal objective value is (R(a) - T)+ +?=l[i - ai]. Range, Mean and Second Moment Known When the range, mean and second moment of each arc duration distribution are known, an upper bound on the expected project tardiness is given by the optimal value of the following problem: sup E(R() - T)+ s.t. f1 dP(0) = 1 f 2 dP(,) = E(-2) n dP(~) = -' JfdP(f) = E(f2) 13

ai <: i < bi, V i, i = l,...,.n. The dual problem in (4.2) can again be solved where (i includes second moment information. As Klein Haneveld suggests, the problem is simplfied when the supremum and minimum in (4.2) can be switched. This is possible if the same measure maximize the following problem for all zi: sup E(i - i)+ s.t. f i dP(C) = f dP(t ) = E(4) ai, _ i < bi. (4.4) For any feasible moment problem with two constraints, there is a feasible distribution in (4.4) with two atoms. Dula [1986] (following Scarf [1958], Dupacova [1977], and Jagannathan [1977]) shows that the following two atom distribution is optimal. (A characterization of this property appears in Birge and Dula [1991].) For this problem, Let region Ai = (a, (E(~2) - 2aii + a)/(2(i - ai))) + ai), region Bi = ((E(2) - 2ai, + a/(2( ai)/ + a+ ai, (b? - E(2) - 2a,(bi-,i))/(2(b, - ())) + ai) and region Ci = ((b2 - E(2) - 2ai(bi - i))/(2(bi - i))) + ai, bi). Let X1 and X2 denote the atoms of the optimal distribution. Then, the optimal solution to (4.4) is: (aj, (E(2) - 2aii + a?)/(Zi - ai)) + ai) if Zi E Ai (X1 X2) =_ (Zi - (zi - ai)2 - 2(zi - ai)(i - ai) + E(() - 2ai(i) + a,(45 zi + (zi - ai)2 - 2(zi - ai)(i - ai) + E((2) - 2ai(i) + a?) if zi e B ((bi(( - ai) + aii - E( ())/(bi - i) + ai, bi) otherwise. The corresponding probabilities are: pi = (X2 - Zi)/(X2 - X1) and P2 = ( Xi - X')/(X2 - X1). Since this optimal measure depends on zi, we cannot immediately switch the supremum and minimum in (4.2). In this case, however, note that zi can be restricted to [ai, b1i and that, if the first and second moments are finite, then all quantities in (4.2) are finite. Now, finding minsup (R(z) - T)+ + ZEF,((i - zi)+, (4.6) 14

5 91 4 Figure 1: Project Network for Example 1 leads to a finite problem which bounds the value of (4.2) from above. We can thus (4.6) as a looser upper bound than (4.2). We solve (4.6) when O = A1 x. * * x biy that each yi includes all probability measures with means, &, and second moments, (2) = E(=). To solve (4.6) with these range, first and second moment bounds, we first solve for F*(z) that is optimal in the supremum in (4.6). The outer minimization in (4.6) is then performed by computing the integral in EF.(z)(,i - zi)+ as a function of zi where Fi*(z) is defined in (4.5). This yields a nonlinear but separable function in the components of zi. In our examples, we solved this problem using a successive linearization procedure. 5. Comparison of Bounds In this section, we compare bounds on the expected project tardiness when different amounts of information about the random activity durations are available. Three sample networks are chosen for comparison from the literature on unconstrained project scheduling. A fourth sample is from an actual manufacturing facility. Example 1 This example is taken from Robillard and Trahan [19771. Its project network is depicted in Figure 1. Robillard and Trahan assume each arc duration has a uniform distribution, and also that the arcs are independent. Table 2 lists the range, mean, and second moment for each arc. In our bounds, we assume only the range, the mean and the second moment of each arc duration distribution. For each information level, we look at the case where the maximum range of each arc is finite, with the value given in Table 2, and the case where the maximum range of each arc is 15

arc minimum maximum mean second moment 1 1.U 1.U LU. U 2 2.0 4.0 3.0 9.333 3 1.0 3.0 2.0 4.333 4 2.0 3.0 2.5 6.333 5 3.0 7.0 5.0 26.333 6 3.0 5.0 4.0 16.333 7 1.0 5.0 3.0 10.333 8 4.0 5.0 4.5 20.333 9 1.0 2.0 1.5 2.333 10 4.0 6.0 5.0 25.333 Table 2: Arc duration data for Example 1 Due Date Information Available 0.00 15.00 18.33 21.67 25.00 upper bound range 25.00 10.00 6.67 3.33 0.00 range, mean 20.00 5.00 3.33 1.67 0.00 range, mean, second moment 20.00 5.00 2.56 0.89 0.00 range, mean, second - unif 20.00 5.00 2.94 0.13 0.00 lower bound range 15.00 0.00 0.00 0.00 0.00 range, mean 20.00 5.00 0.00 0.00 0.00 Table 3: Bounds On Expected Tardiness for Example 1 - bounded case infinite. Tables 3 and 4 tabulate bounds on the expected project tardiness given various due dates. Table 3 summarizes the bounds when each arc duration has a finite upper bound. The upper bounds on expected tardiness also appear in Figure 2. Table 4 summarizes the bounds when each arc duration has an infinite upper bound. In this case and all cases below, "unbounded" refers only to the upper bound. We assume that the lower bounds are known. The tables include both upper and lower bounds. The unbounded upper bounds appear in Figure 3. For a given due date and information level, the upper bound on the expected project tardiness is calculated using the appropriate method outlined in the previous section. The corresponding lower bound is obtained by substituting in the mean value, or lower bound, for each arc duration and solving the Due Date Information Available 0.00 15.00 18.33 21.67 25.00 upper bound range, mean 24.50 9.50 9.50 9.50 9.50 range, mean, second moment 20.35 5.35 2.98 1.27 0.73 lower bound range, mean 20.00 5.00 0.00 0.00 0.00 Table 4: Bounds On Expected Tardiness for Example 1 - unbounded case 16

30. 0 1l0 20 30 e-\ \ — * — Range, Mn 20 a 5 l \ i Range. Mn, Sec 2 10- \ Range, Mn. Sec u o 0., a. 0 10 20 30 Due Date Figure 2: Upper Bounds on Expected Tardiness - Example 1, Bounded Case 3017 1. C 20 * N- N^ * Range. Mn t Range, Mn. Sec o 10 0 10 20 30 Due DatO Figure 3: Upper Bounds on Expected Tardiness - Example 1, Unbounded Case 17

Figure 4: Project Network for Example 2 Due Date Arc Information Available 0.00 2.00 4.00 6.00 upper bound range 6.00 4.00 2.00 0.00 range, mean 4.00 2.00 1.00 0.00 range, mean, second moment 4.00 2.00 0.77 0.00 lower bound range 0.00 0.00 0.00 0.00 range, mean 3.00 0.00 0.00 0.00 Table 5: Bounds On Expected Tardiness for Example 2 - bounded case distribution. Table 5 summarizes bounds on the expected project tardiness when the maximum length of each arc is finite. Figure 5 shows the upper bounds in this case. Table 6 summarizes bounds obtained when the maximum length of each arc is infinite. Again, the upper bounds appear in Figure 6. The due date levels are R(a), R(a) + (1/3)(R(b) - R(a)), R(a) + (2/3)(R(b) - R(a)), and R(b). Assuming the durations have discrete uniform distributions and are independent, the expected tardiness of this project is (3.32 -due date)+. We make neither of these assumptions in computing our bounds. In all of the situations considered, summarized in Tables 5 and 6, information on the mean of each arc duration is helpful in obtaining tighter bounds. As in Example 1, bounds obtained assuming each arc duration is bounded are tighter than the corresponding bounds developed assuming each arc duration is unbounded. This again illustrates the importance of knowing upper bounds on the arc durations. In Table 6, the upper bounds utilizing second moment information are tighter than those which do not utilize this information. This is true for all due dates and represents greater improvement 19

resulting deterministic problem. The due dates are equal to 0.0, R(a), R(a) + (1/3)(R(b) -R(a)), R(a) + (2/3)(R(b) - R(a)), and R(b). In Table 3, the bounds summarized in the row marked "uniform" were derived using Robillard and Trahan's estimates of the first two moments of project completion time. Assuming each activity duration is a discrete uniform random variable and the activity durations are independent, Robillard and Trahan present 20.562 as an upper bound on the expected completion time of this project and 422.759 as an upper bound on the second moment of completion time. Using these bounds (with assumed uniform components), we computed the maximum expected project tardiness over all completion time distributions with these moments. In general, our bounds assuming only first and second moments on individual activity durations are comparable to assuming specific arc. distributions and using them to bound overall completion time moments. Tables 3 and 4 illustrate that each incremental piece of information about the arc durations is beneficial. The value of additional information is more pronounced at looser due date levels. Overall, the bounds with mean, range, individual arc second moment information, and no assumptions of independence provide fairly tight bounds on expected tardiness. In the unbounded case, Table 4 also confirms the value of information about the variance, or second moment. When only the mean and range are known, the upper bound on the expected tardiness is constant for all due dates greater than R(a). Thus, for looser due dates, bounds obtained using second moment information are much tighter that those obtained using only the means and ranges. An upper bound on the duration of each arc also facilitates developing a tighter bound on the expected project tardiness. To see this, compare each upper bound in Table 3 with the corresponding upper bound in Table 4. Having a finite maximum length for each arc is especially helpful when only the mean and range of each arc are known. As the maximum length of each arc is increased, the upper bounds in Table 3 approach those in Table 4. Example 2 This example is a modification of Example 1 in Fulkerson [19621. The project network for this example is depicted in Figure 4. Fulkerson assumes the operations have independent, identically distributed durations. Each has a discrete uniform distribution, with P(gi = Ij) = 1/3 and 11 = 0, 12 = 1, 13 = 2. Thus, the range of arc i is [0,2], the mean of arc i is 1 and the second moment of arc i is 5/3. Here, we assume only the range of hi and at most the first two moments of its 18

Due Date Arc Information Available 0.00 2.00 4.00 6.00 upper bound range, mean 5.00 5.00 5.00 5.00 range, mean, second moment 5.00 2.27 1.16 0.73 lower bound range, mean 3.00 0.00 0.00 0.00 Table 6: Bounds on Expected Tardiness for Example 2 - unbounded Case 8 4 v 6 e CN — a- Range 11~~~~~~~~~~~~~~~~ ^< N,^ - Range. Mn la"g~~~~~ NW. N. Range, Mn, Sec 0 0 2 4 6 8 Due Date Figure 5: Upper Bounds On Expected Tardiness - Example 2, Bounded (;ase 0 I 0 2 c \ Figure 6: Upr B s On E d Rarnge Mn 20K * Range, Mn. Sec 2~0~ ~20

Due Date Arc Information Available 0.00 2.00 4.00 6.00 upper bound range, mean, second moment 5.00 3.34 2.23 1.66 Table 7: Bounds On Expected Tardiness for Example 2 - increased variance I 1 4' 18 65 16 17 Figure 7: Project Network for Example 3 than in the bounded case. If the variance of each arc is increased, the upper bounds employing this information are naturally looser than the upper bounds developed using the smaller variance, but still represent significant improvement over ignoring the second moment. This is shown in Table 7, which tabulates upper bounds on the expected project tardiness when the second moment of each arc is increased to 3. These results suggest that it is important to have a bound on the variance of each arc, even if the actual variance is not available. Example 3 This example is from Klein Haneveld [19861. According to Klein Haneveld, it is a slight modification of the Electronic Module Development Project described in Moder and Phillips [1964]. Figure 7 illustrates the project network for this project. Table 8 presents information on the mean, range, and second moment of each arc. We set the mean of each arc equal to the mode in Klein Haneveld's work. The standard deviation was derived assuming a triangular distribution. Thus, ai = (b-ai)/6, V i. Tables 9 and 10 record the bounds on the expected project tardiness under several due date levels. Upper bounds also appear in Figures 8 and 9. The smallest due date equals the completion 21

arc minimum maximum mean second moment 1 6.TU -.U 8.U 66.778 2 14.0 32.0 17.0 298.000 3 14.0 32.0 17.0 298.000 4 2.0 8.0 4.0 17.000 5 1.0 5.0 2.0 4.444 6 1.0 3.0 2.0 4.111 7 0.4 1.0 0.6 0.370 8 0.4 1.0 0.6 0.370 9 2.0 5.0 3.0 9.250 10 2.0 5.0 3.0 9.250 11 3.0 5.0 4.0 16.111 12 3.0 5.0 4.0 16.111 13 3.0 5.0 4.0 16.111 14 3.0 5.0 4.0 16.111 15 2.0 5.0 3.0 9.250 16 3.0 5.0 4.0 16.111 17 8.0 12.0 10.0 100.444 18 1.0 3.0 2.0 4.111 19 6.0 12.0 8.0 65.000 20 1.0 3.0 2.0 4.111 21 6.0 12.0 8.0 65.000 22 1.0 3.0 2.0 4.111 23 6.0 16.0 8.0 66.778 24 1.0 3.0 2.0 4.111 25 4.0 8.0 6.0 36.444 26 1.0 3.0 2.0 4.111 27 0.1 1.0 0.5 0.257 28 2.0 5.0 4.0 16.444 29 1.0 4.0 2.0 4.111 Table 8: Arc duration data for Example 3 Arc Information Due Date Available 45.10 55.00 65.00 75.00 85.00 upper bound range, mean 12.61 6.47 2.93 0.17 0.00 range, mean, second moment 6.46 1.78 0.53 0.02 0.00 lower bound range, mean 0.00 0.00 0.00 0.00 0.00 Table 9: Bounds On Expected Tardiness for Example 3 - bounded case Arc Information Due Date Available 45.10 55.00 65.00 75.00 85.00 upper bound range, mean 38.80 38.80 38.80 38.80 38.80 range, mean, second moment 6.77 2.51 1.72 1.04 0.73 lower bound range, mean 0.00 0.00 0.00 0.00 0.00 Table 10: Bounds On Expected Tardiness for Example 3 - unbounded case 22

l 10 Uj S a. ~o ~~~\- Range, Mn \ \ * Range, Mn. Sec 40 50 60 70 80 90 Due Date Figure 8: Upper Bounds On Expected Tardiness - Example 3, Bounded Case 40 30ILU ~0 20" -- Range. Mn Range, Mn, Sec i. 40 5o 60 70 80 90 Due Date Figure 9: Upper Bounds On Expected Tardiness - Example 3, Unbounded Case 23

Arc Information Due Date Available 0 200.00 420.00 510.00 600.00 upper bound range, mean 627.5 427.5 247.5 213.75 180.0 range, mean, second moment 569.2 369.2 163.9 108.5 83.4 lower bound range, mean 510.00 310.00 90.00 0.00 0.00 Table 11: Bounds On Expected Tardiness for Example 4 - bounded case Arc Information Due Date Available 0 200.00 420.00 510.00 600.00 upper bound range, mean 690.0 490.0 350.0 350.0 350.0 range, mean, second moment 569.6 369.6 164.3 110.4 86.7 Table 12: Bounds On Expected Tardiness for Example 4 - unbounded case time of the project when each arc duration is replaced by its expected value. The other due dates are set at intervals of ten. The results are similar to those of the previous two examples. Again, information on the second moment provides a tighter upper bound on the expected project tardiness, especially when the due date is loose. Bounding the arc length again makes a significant difference in expected tardiness. Example 4 The last example is from a manufacturing facility. Tardiness refers to the completion of an order which requires manufacturing and assembly of four components. The components also share common resources (machines and tools) so the full project network is highly interconnected. The network has 49 arcs and 35 nodes. The total number of paths is 25. Processing times had lower bounds of 20 minutes, means of 30 minutes and second moments of 1000 minutes2 (a standard deviation of 10 minutes). Tables 11 and 12 record the bounds on the expected project tardiness under several due date levels. The upper bounds appear in Figures 10 and 11. The times were chosen to represent an early value, the value with all processing times set to their means (510), and ninety minutes from the mean value. Note that second moment information more than halves the expected tardiness with a due date of 600, even when fixed upper bounds are given. These four examples demonstrate the value of additional arc information in determining upper 24

700 300 ~ \ Range, Mn 2 - Range, Mn, Sec * 600 - 100 - 400 C~ * 300 - Range, Mn jc~~~~~~~ \N. ^^^I~~~~~~~ -~*- Range, Mn, Sec 200 0 100 0 100 200 300 400 500 600 Due Oate Figure 11: Upper Bounds On Expected Tardiness - Example 4, Unbounded Case 25 200 100 20 300 400 Soo 60 0~ ~ ~ ~ ~~~2

bounds on the expected project tardiness. In every instance, knowledge of the arc duration means provided a tighter bound than could be obtained solely using the information on the range of each arc duration. For our bounds, if the maximum length of each arc is unknown, second moment information is always valuable. Acknowledgment The authors gratefully acknowledge the assistance of Sharon Fox in performing the computational tests. 26

Bibliography Anklesaria, K.P. and Z. Drezner (1986), "A Multivariate Approach to Estimating the Completion Time for PERT Networks," Journal of the Operational Research Society, Vol. 37, No. 8, pp. 811-815. Barlow, R.E. and F. Proschan (1975), Statistical Theory of Reliability and Life Testing, Holt, New York. Ben-Tal, A. and E. Hochman (1972), "More Bounds of the Expectation of a Convex Function of a Random Variable", Journal of Applied Probability, Vol. 9, pp. 803-812. Billingsley, P. (1968), Convergence of Probability Measures, Wiley, New York. Birge, J.R. and J. H. Dula (1991), "Bounding Separable Recourse Functions with Limited Distribution Information," Annals of Operations Research, Vol. 30, pp. 277-298. Birge, J.R. and R. J-B. Wets (1986), "Designing Approximation Schemes for Stochastic Optimization Problems, in particular, Stochastic Programs with Recourse," Mathematical Programming Study, Vol. 27, pp. 54-102. Birge, J.R. and R. J-B. Wets (1987), "Computing Bounds for Stochastic Programming Problems by Means of a Generalized Moment Problem," Mathematics of Operations Research, Vol. 12, No. 1, pp. 149-162. Clingen, C.T. (1964), "A Modification of Fulkerson's PERT Algorithm," Operations Research, Vol. 12, pp. 629-632. Dantzig, G. B. (1963), Linear Programming and Extensions, Princeton University Press, Princeton, NJ. Dantzig, G. B., and A. Wald (1951), "On the Fundamental Lemma of Neyman and Pearson," The Annals of Mathematical Statistics, Vol. 22, pp. 87-93. Devroye, L.P. (1979), "Inequalities for the Completion Times of Stochastic PERT Networks," Mathematics of Operations Research, Vol. 4, No. 4, pp. 441-447. Dodin, B.M. (1985), "Bounding the Project Completion Time Distribution in PERT Networks", Operations Research, Vol. 33, No. 4, pp. 862-881. DulA, J.H. (1986), "Bounds on the Expectation of Convex Functions," Ph.D. Dissertation, The University of Michigan, Ann Arbor, Michigan. Dupacov^, J. (1977), "Minimax stochastic programs iwth nonconvex nonseparable penalty functions," in: Progress in Operations Research, A. Pr6kopa (ed.), North-Holland, Amsterdam, pp. 303-316. Elmaghraby, S.E. (1967), "On the Expected Duration of PERT Type Networks," Management Science, Vol. 13, No. 5, pp. 299-306. 27

UNIVERSITY OF MICHIGAN 3 9015 04735 0304 Ermoliev, Y., A. Gaivoronski, and C. Nedeeva (1985), "Stochastic Optimization Problems with Partially Known Distribution Functions, SIAM J. Control Optim., Vol. 23, pp. 377-394. Fulkerson, D.R. (1962), "Expected Critical Path Lengths in PERT Networks," Operations Research, Vol. 10, pp. 808-817. Jagganathan, R. (1977), "A minimax provedure for a class of linear programs under uncertainty," Operations Research, Vol. 25, pp. 173-177. Kamburowski, J. (1985), "An Upper Bound on the Expected Completion Time of PERT Networks", European Journal of Operational Reseach, Vol. 21, pp. 206-212. Klein Haneveld, W.E. (1986), "Robustness against Dependence in PERT: An Application of Duality and Distributions with Known Marginals," Mathematical Programming Study, Vol. 27, pp. 153-182. Kleindorfer, G.B. (1971), "Bounding Distributions for A Stochastic Acyclic Network," Operations Research, Vol. 19, pp. 1586-1601. Krein, M. and A. Nudelman (1977), The Markov Moment Problem, Translations of Mathematical Monographs, Vol. 50, The American Mathematical Society, Providence, RI. Madansky, A. (1960), "Inequalities for Stochastic Linear Programming Problems", Management Science, Vol. 6, No. 1, pp. 197-204. Malcolm, D.G., J.H. Roseboom, C.E. Clark and W. Fazar (1959), "Application of a Technique for Research and Developement Program Evaluation," Operations Research, Vol. 7, No. 5, pp. 646-669. Meilijson, I. and A. Nadas (1979), "Convex Majorization with an Application to the Length of Critical Paths," Journal of Applied Probability, Vol. 16, pp. 671-677. Moder, J.J. and C. R. Phillips (1964), Project Management with CPM and PERT, Rheinhold, New York. Prekopa,A. (1988), "Boole-Bonferroni Inequalities and Linear Programming," Operations Research, Vol. 36, pp. 145-162. Robillard, P. and M. Trahan (1976), "Expected Completion Time in PERT Networks," Operations Research, Vol. 24, No. 1, pp. 177-182. Robillard, P. and M. Trahan (1977), "The Completion Time of PERT Networks," Operations Research, Vol. 25, No. 1, pp. 15-29. Riischendorf, L. (1982), "Random Variables with Maximum Sums," Advances in Applied Probability, Vol. 14, pp. 623-632. Scarf, H. (1958), "A minimax solution of an inventory problem," in: Studies in the Mathematical Theory of Inventory and Production, K.J. Arrow, S. Karlin, and H. Scarf (eds.), Stanford University Press, Stanford, CA. Shogan, A.W. (1977), "Bounding Distributions for a Stochastic PERT Network," Networks, Vol. 7, pp. 359-381. Weiss, G. (1986), "Stochastic Bounds on Distributions of Optimal Value Functions with Applications to PERT, Network Flows and Reliability", Operations Research, Vol. 34, No. 4, pp. 595-05. 28