SETTING PLANNED LEADTIMES IN SERIAL PRODUCTION SYSTEMS WITH TARDINESS COSTS Candace Arai Yano Department of Industrial and Operations Engineering University of Michigan Ann Arbor, Michigan 48109-2117 %5-q February 1985 Revised August 1985, January 1986, and May 1986 This work was supported in part by NSF Grant ECS-8206499.

SETTING PLANNED LEADTIMES IN SERIAL PRODUCTION SYSTEMS WITH TARDINESS COSTS ABSTRACT We investigate the problem of determining optimal planned leadtimes in serial production systems in which the actual procurement and processing times may be stochastic. The objective is to minimize the sum of inventory holding costs and job tardiness costs given a customer specified due-date. We present a general solution procedure for two stage serial systems, which for most cost structures and leadtime distributions is a single-pass algorithm. We also indicate how the procedure can be extended to N-stage systems. We present computational results which provide some insight into the characteristics of optimal safety time policies.

SETTING PLANNED LEADTIMES IN SERIAL PRODUCTION SYSTEMS WITH TARDINESS COSTS 1.0 INTRODUCTION Uncertainty in production and delivery leadtimes is a major problem in production systems. It hampers effective coordination, resulting in parts shortages, workforce idle-time, and excessive expediting. Delivery leadtimes vary depending upon purchased product availability from vendors and transportation time. Production leadtimes vary due to many factors, including machine breakdowns, queueing resulting from capacity limitations and changes in the mix of products being produced, and rework. The effects of leadtime uncertainty are particularly problematic in multi-stage production systems, because late availability of an item may delay all subsequent stages of production. In simulation studies Whybark and Williams (1976) have found that safety time is a more effective and efficient buffer against leadtime uncertainty than safety stock. Weeks (1981) shows that the single stage problem with tardiness costs is a simple "newsboy" problem. Grasso and Taylor (1984) have found through simulation studies that leadtime variability, the quantity and type of buffers used, the lot-sizing rules, and the cost structure have statistically significant effects on system performance. We address the problem of optimizing planned leadtimes (and hence safety times) at each stage in the production process. We use the term safety time to refer to the excess of the planned leadtime above average leadtime. Two entirely different scenarios may give rise to this problem. The first involves situations in which efforts have been made to reduce leadtime uncertainty, and the issue at hand is how to deal with the remaining uncertainty. In such systems, transport time (for both inbound freight and internal material handling) and queueing are often the primary causes of leadtime variability. 1

The second scenario, unfortunately, occurs more frequently. Leadtime variability has not been reduced to a minimum; the question is where to focus the effort and how to quantify the economic benefits of reducing the leadtime or its variability through better scheduling or control, new equipment, or different operational policies. For instance, we may wish to examine "costdependability" tradeoffs that often exist for both suppliers and transporters. We may also want to quantify the benefits of employing additional resources (e.g., machines or labor) at production stages with highly variable leadtimes resulting from high traffic intensity (i.e., bottlenecks). The sources of leadtime variability are not examined in detail in this paper. Therefore, we do not address the effects of queueing or capacity explicitly in the model. There are also some behavioral phenomena —particularly "Murphy's law" of scheduling (everything takes at least as long as the planned leadtime) —that cannot be incorporated into our model. We are taking a planning perspective —a "macro" view —realizing that implementation of the policies that we prescribe may affect the actual leadtime distributions. We recognize that this is an important limitation of the analyses that follow. Nevertheless, this represents a first step toward gaining intuition into the optimal "location" and size of safety-time buffers. We also believe that iteratively using the algorithm to. determine planned leadtimes and simulating the resulting policy (or, where possible, using analytic results for tandem queues) to provide revised estimates of the leadtime distributions may converge rapidly to optimal policies which fully incorporate the queueing and scheduling effects. This belief is based upon results from recent work by Rees et al. (1985) where the problem was one of determining the number of kanbans for a single stage within a just-in-time inventory system. They used observed leadtime distributions to determine the number of kanbans 2

(using the model of Weeks (1981)), simulated to find the new leadtime distributions, and repeated until convergence was obtained (within a few iterations at most). There is a direct correspondence between the planned leadtimes in our model and the number of kanbans in the Rees et al. paper. Thus, we would expect that the approach would be applicable and very workable in our scenario as well. A description and formulation of the two-stage problem are given in Section 2. In section 3 we discuss our approach to the problem and solution techniques. A discussion of extensions to N-stage systems is in Section 4. Computational results are reported in Section 5. We conclude with a summary and discussion in Section 6. 2.0 DESCRIPTION AND FORMULATION OF THE TWO-STAGE PROBLEM We first address the problem of determining optimal planned leadtimes in a two-stage serial system in which a fixed quantity (predetermined) batch is processed at each stage. The actual leadtime at each stage is stochastic but is assumed to have a known or estimated distribution. We assume that the actual leadtimes are mutually statistically independent and are twice differentiable. Each stage in the production or procurement process incurs a non-negative cost, increasing the "investment" in the production batch, and therefore inventory holding costs as well. The objective is to minimize the sum of inventory holding costs resulting from "early" completion and tardiness (or shortage) costs. We assume that each order has a specified due date. The decision variables are how much time to allow for each stage in the production or procurement process. These planned leadtimes, in turn, are used to determine planned dispatch times at each stage. The planned dispatch time at each stage is the due date less the cumulative planned leadtime (i.e., the sum of the planned leadtimes of that stage and all succeeding stages). The batch is dispatched at 3

the planned dispatch time for that stage if the previous stage of production has been completed on time. Otherwise, it is "tardy" and should be dispatched immediately. The primary reason for holding back a batch that finishes a stage "early" is that the cost of holding it at subsequent stages makes it uneconomical to dispatch it immediately to the next stage despite potential penalty costs for tardiness. Kanet and Christy (1984) provide an extensive discussion of systems with "forbidden early-order departure," and provide an analysis for a singlestage system. Our objective is not simply to solve the two-stage problem, but rather to develop a solution approach which may be useful for N-stage serial systems and more general systems. 2.1 Problem Objectives Organizations faced with the scenario described above may have differing objectives, including: (1) minimizing the sum of inventory holding costs and tardiness costs, where penalties may be charged for tardy delivery to the customer or to any intermediate stages, or (2) minimizing inventory holding costs subject to maintaining a specified on-time percentage for customers. Penalties may be of the binary type (positive if tardy, zero otherwise) or some other function of tardiness. We note that objective (2) above is equivalent to a problem with objective (1) in which an appropriate binary penalty is imposed. The reasons for imposing a penalty for tardy delivery to the customer are evident. Penalties are applicable at intermediate stages in the production process if, for instance, rescheduling, expediting, or an additional machine 4

setup is necessary. In this paper we use a linear penalty for tardy delivery to the customer. We believe that using penalties only for tardy delivery closely represents the objectives of many manufacturing firms, since tardiness costs for the finished product generally dominate tardiness costs at intermediate stages. Throughout the remainder of the paper, stages of production are numbered so that stage i is a predecessor of stage j if i > j (i.e., the last process to be performed is stage 1). 2.2 Formulation of the Problem Let hi = holding cost (per batch) per period at stage i p = tardiness penalty (per batch) per period for the finished product Ti = actual leadtime at stage i Xi = planned leadtime for stage i (decision variable) fi(y) = density of leadtime at stage i Fi(y) = leadtime distribution at stage i E(') = expectation (-)+ = positive part F*G = convolution of two cumulative distribution functions (c.d.f.s) We assume that hi < hj if i > j, since otherwise it would always be more economical to dispatch immediately (i.e., Xi = 0). If hi > hj, i > j, stage i can be omitted from the analyses by letting the adjusted leadtime distribution at stage j be the convolution of the distributions of stages i and j. 5

The problem can be formulated as: X2 minimize h2 f (X2-u)f2(u)du (1) 0 X1 + h1{F2(X2) f (X1-t)f1(t)dt (2) 0 X1 +X2 X1+X2-u + I f (X1+X2-t-u)f2(u)f1(t)dtdul (3) X2 0 + p {F2(X2) f (t-X1)f1(t)dt X1 co co + f f (t+u-X1-X2)f2(u)f1(t)dtdu} (4) X2 X1+X2-u subject to Xi > 0, 1i1,2. The five terms represent: (1) expected holding costs incurred at stage 2, (2) expected holding costs incurred at stage 1 when stage 2 is on time and stage 1 is early, (3) expected holding costs incurred at stage 1 when stage 2 is tardy but the sum of the two leadtimes does not exceed the sum of the planned leadtimes, (4) expected penalty costs. This is a nonlinear optimization problem whose objective function may not be convex for some combinations of costs and leadtime probability density functions. The Hessian and sufficient conditions for convexity are presented in the Appendix. However, as in most real-world inventory-related problems, the principle of decreasing marginal returns generally holds, and the total cost function is reasonably well-behaved. For the two-stage problem, more specifically, given any value of X1 (the planned leadtime for stage 1) such that F1(X1) < (h2+p)/(h1+p), (5) the Hessian is positive semidefinite for all probability density functions. In 6

addition, the Hessian is positive definite if leadtime probability density function at stage 1 is such that fl(t) > 0 for -1 < t < T1 (6) where T1 is the minimum value of T1 and -1 is the maximum value of Ti (i.e., the support of T1 has no gaps). For larger values of X1, the total cost function may still be convex, but the conditions on costs and the probability density functions are much more restrictive. However, the optimal value of X1 does not fall into this range, as we will demonstrate in Section 3. We will return to the issue of convexity below. 3.0 SOLUTION APPROACH Dynamic programming or enumeration can be used to solve discrete versions of the two-stage problem, but more efficient procedures are needed for N-stage and continuous-time problems. We first numerically confirmed convexity of the total cost function since it might be ill-behaved in regions where convexity is not guaranteed by the results in Section 2.2. For a few combinations of costs (h2 < hI < p) and leadtime distributions (Poisson and negative binomial) the total cost as a function of the two decision variables had a trough-shaped response surface. One example is illustrated in Figure 1 for a case of leadtimes having negative binomial distributions. Contour-lines indicating level-sets have been included to highlight convexity of the surface. Also indicated is the region in which X1 < F1 1[(h2+p)/(h1+p)] where convexity is guaranteed for continuous problems. We observed that the objective function was quasi-convex even outside this region. With this added assurance that the response surfaces appeared to be well-behaved even for values of X1 > F1 1[(h2+p)/(hl+p)], we decided to proceed, assuming quasi-convexity of the cost functions. FIGURE 1 7

Taking first partial derivatives of the objective function with respect to the two decision variables and setting them equal to zero yields: X1+X2 (hl+p) f f2(u)F1(Xl+X2-u) + (hl+P)F2(X2)F1(X1) - p = 0 (7) X2 X1+X2 (hl+p) f f2(u)F1(X1+X2-u)du + (h2+p)F2(X2) - p 0 (8) X2 Since the first and third terms of these equations are equivalent, the second terms must be equal. Therefore, a necessary condition for a relative minimum is: F1(X1) = (h2 + p)/(h1 + p) if F2(X2) > 0 (9) It is interesting to note that this is simply the solution to a standard newsboy problem with adjusted costs. That is, if we set p' = p + h2 h' = h1 - h2 then F1(X1) = p'/(p'+h'). The penalty cost is adjusted upward to account for upstream ramifications while the adjusted holding cost is the echelon holding cost at stage 1. Setting X1 using equation (9), X2 can be found by a one-dimensional search using either (7) or (8). If the resulting X2 is such that F2(X2) > 0 then we are done. If, however, there is no solution to the equation such that F2(X2) > 0 then X2 can be set to any value in [0,T2) (i.e., stage 2 is always late) and X1 can be found using a one-dimensional search using (7) or (8). In fact, if X2 = 0 then X1 is found by solving a standard newsboy problem using the convolution of the two leadtime distributions. More formally G12(X1) = p/(P+h1) where G12 I F1*F2. Following is an algorithm for the procedure described above. 8

ALGORITHM 1. Find X1 = F-1 [(h2 + p)/(h1 + )] X i +y XI+Y 2. Find X2 = {y > 01 (h1+p) f f2(u)F1(Xl+y-u)du + (h2+p)F2(y) - p y if possible. Otherwise go to step 3. 3. Set X2=0. Find X1 G12 [p/(p+h1)] where 12 = F1 F2 Step 1 finds the optimal value of X1 assuming F2(X2) > O. Step 2 finds the optimal value of X2 given X1 from Step 1. If it is positive and F2(X2) > 0, we are done. Otherwise we set X2 = 0 (or any value less than the minimum possible leadtime at stage 2) and solve for X1 as if the two stage system were collapsed into one stage. Observe that there is another solution to the first-order necessary conditions, namely X1 - G12 [p/(h1+p)] and X2 0 O. It can be shown (see Appendix) that if a solution with X1 > 0 and F2(X2) > 0 exists, the alternate solution to the first-order conditions is non-optimal. (The determinant of the Hessian matrix is strictly negative at this point). Furthermore, if the solution with X2 - 0 is the only solution to the first-order conditions, X1 is strictly less than F11 [(h2 + P)/(h1 + P)]. Given X1 from either step 1 or step 3 of the algorithm, X2 satisfies (8), yielding a value which is strictly less than F2 1[p/(p + h2)] for any positive value of X1. Thus X1 is greater than the solution of the standard newsboy problem for Stage 1 alone, while X2 is less than if stage 2 were treated separately. In most situations p > h1 and h2 is fairly close to h1. Therefore, X1 is usually significantly larger than the median stage 1 leadtime. The allocation of the total planned leadtimes between the two stages is affected primarily by the relative magnitudes of ha and h2 and by the absolute magnitude of p. With large p, (i.e., p >> h1), there will be considerable 9

safety time at stage 1 regardless of the values of h1 and h2. On the other hand, when p is closer to the value of h1, h2 is the primary determinant of X1. A general conclusion is: the greater the values of p and h2, the greater the planned leadtime at stage 1. We can also put a bound on the sum of X1 and X2. Rewriting equation (7) we have X1 + X2 F1(X1)F2(X2) + f f2(u)F1(X1 + X2 - u)du = p/(p + h1) X2 But the left hand side of the equality is bounded above by G12(X1 + X2), so we ha ve G12(X1 + X2) > p/(p + h1) and the equality holds whenever F2(X2) = 0 3.1 Convexity Revisited Recall the conditions required for convexity discussed in Section 2.2. If F1(X1) < (h2+p)/(h1+p) then the objective function is positive semidefinite for all leadtime distributions. Notice, however, a first order necessary condition is F1(X1) = (h2+p)/(hl+p) if F2(X2) > O. Otherwise, F2(X2) = 0 and x = G12 1[p/(p+h1)] < F-1 (h2+p)/(h1+p)]. Therefore, the cost function is convex over the relevant range provided (6) holds. This condition is relatively mild and would be satisfied in most applications. Thus any solution procedure which keeps X1 and X2 within the relevant range and identifies a local minimum will provide the global optimal solution. 10

4.0 EXTENSIONS This basic approach can be applied to any N-stage serial system. The resulting first-order conditions have the general form: N N (h1+p) P [ T< Xj] - p = 0 (10) j=1 J =1 N N m-1 N N P[ E Tj < Z Xj] { z (hn + p) P C Z T+ < Z Xj, j m j =m n 1 j n j -n N N Z Tj > z Xj, k > n] j=k j=k - (hm+p) 0 m=2,3,...,N (11) where again the probability terms reflect the dispatching policy. Thus, the equations required for the algorithm can be written easily and need not be derived for each special case. Using the mth indexed equation sequentially for m = 2,..., N, one can solve for Xm_1 using the bracketed terms, assuming that given the dispatching policy, N N P[E Tj < ~ Xj] > 0 (12) j m J =m This assumption is quite innocuous in most cases. For instance, if Xi > Ti for all i (i.e., it is desirable to have the planned leadtime at least as large as the minimum possible leadtime at that stage), this assumption will always be satisfied. In the event that Xj 0 for some j, one may have to re-solve for the last positive value of Xj that was found, if a first-order condition which was originally satisfied assuming that Xj > 0 is now violated. (This generally is true whenever an Xj is set to zero). One then continues with Xj+1. The value of XN is determined using equation (8). A flowchart for the three-stage problem appears in Figure 3 to provide a flavor of the general approach. 11

We have discussed characteristics of optimal solutions for two stage systems in section 3.0. Analyses for N-stage systems reveals that for an Nstage system, Xi* = min {F1 1[(h2 + p)/(h1 + p)],G121 [(h3 + p)/(h1 + P)], G1231 [(h4 + p)/(h1 + p)], G1...N1 [p/(p + h1)]} Observe that as N increases, each element added to the set of values in brackets is at least as large as the minimum element in the previous set. For example, in going from three stages to four stages, the first two terms remain the same. However, G123[p/(p + h1)] is replaced by G123 1h + p)/(h1 + p)] which is clearly at least as large. The term G1234 1[p/(p + h1)] is at least as large as G123 [p/(p + h1)] for any stage 4 leadtime distribution with mass not all at zero. Thus X1 is non-decreasing with the number of stages. Let us now examine what happens to X2 as the number of stages increases. Suppose that F1(X1) = (h2 + p)/(h1 + p) in both the two-stage and three-stage problems. Then, for the two-stage problem, X2 satisfies X +X2 F1(X1)F2(X2) + f 2(u)FI(X1 + X u)du X2 = p/(p + hi) For the three-stage problem, X2 satisfies X1 +X2 Y12(X1 + X2) = F1(X1)F2(X2) + f f2(u)F1(X1 + X2 - u)du X2 (h3 + p)/(h1 + p) assuming F3(X3) > 0. It is evident that for fixed X1, X2 increases with the number of stages. If X1 increases, as indicated in the foregoing discussion, X2 may decrease, but the exact amount depends upon X1, the leadtime distributions, and the cost 12

parameters. However, the combination of X1 and X2 change in such a way that Y12(X1,X2) which represents a measure of the aggregate level of leadtime protection is non-decreasing in the number of stages. Interpreting these results, we may conjecture that as the number of stages increases, the aggregate level of protection for any set of consecutive stages {1,..., i } increases. This is consistent with our intuition that greater uncertainty (by way of additional stages with uncertain leadtimes) necessitates greater levels of safety time in successor stages. There may be economic advantages in reducing the number of production stages (by enlarging each stage), which the procedure can help to quantify. Further research is needed to determine what types of cost parameters and leadtime distributions would encourage this and how it can be accomplished from a managerial viewpoint. The effect of the absolute magnitudes of leadtime variances on the optimal planned leadtimes is apparent at all stages in the system. However, the effects are most apparent at stage 1. The primary reason is that there is a portfolio effect as n increases. In most cases (i.e., when F(X2) > 0), X1 depends only upon the leadtime distribution at stage 1, whereas the value of XN depends upon on a distribution which is somewhat similar to the convolution of all the leadtime distributions. Xj, j- 2,...,N therefore provides a buffer only against the marginal effect of leadtime variance and has the added benefit of the portfolio effect, keeping safety time quantities relatively small, even when leadtime variances are high. Relative values of leadtime variances (among the stages) affect the "location" of safety time more significantly than do their absolute values. As an example, consider the case of a two stage system. If stage 1 has a low leadtime variance and the variance of the leadtime at stage 2 is high, it is likely that a solution with X2 > O will be optimal because X1 will be relatively 13

small. On the other hand, if the variance at stage 1 is high and the variance at stage 2 is low, it is more likely that X2 = 0 will be optimal (i.e., G12-[p/(p+h )] < F-1 [(h2+p)/(h+p)]). 5.0 COMPUTATIONAL RESULTS The purpose of the computational study was to obtain some further insight into the optimal location and quantity of safety time. We constructed a large set of two- and three- stage problems (1780 two-stage problems and 2160 three-stage problems) with leadtimes having Poisson and negative binomial distributions. Although the Poisson and negative binomial distributions result in zero leadtimes with positive probability, the solution technique is unaffected for distributions without this characteristic. We used discrete leadtime values for computational simplicity and because many manufacturing control systems use discrete leadtime data. Typical numerical results for the two-stage problems gave positive safety time at stage 1 and negative safety times at stage 2. However, "degenerate" solutions with X2 = 0 occurred in very few instances. Thus, while the item would be dispatched immediately to stage 1 most of the time, it would be held back if stage 2 were completed very early. Similar results were obtained for the three-stage problems, with most of the safety time near the end of the production process, and frequent occurrences of negative safety time at the earlier stages. 6.0 CONCLUSIONS We have developed a procedure to determine optimal planned leadtimes (and therefore safety times) in two-stage production systems with stochastic leadtimes. When extended to the N-stage system, the solution procedure provides some insight into the character of the optimal solutions, and how solutions 14

would be expected to change as the number of stages increases. This represents a first step in the study of leadtime uncertainty in multi-stage production systems, and is general enough to include most leadtime distributions. One interesting result from these analyses and the computational study is that immediate dispatching is usually not optimal. While it would be possible to make a comparison of the optimal policy and immediate dispatching, the shape of the cost function suggests that the cost of the system may be fairly sensitive to even small deviations from the optimal policy. This is evident for X1 and much less so for X2 in Figure 2, but one would expect decisions at intermediate stages of production to be much more critical as N grows larger. There are, of course, situations where immediate dispatching would be optimal or nearly so. Such systems would have inventory holding costs almost constant across stages (i.e., small echelon holding costs), and/or leadtimes at the initial stages of production which have low variances. However, typical production systems have higher leadtime variances (attributable to longer average leadtimes and larger batch sizes) at the earlier stages of production, so one might expect the echelon holding costs to play the most important role in determining whether or not immediate dispatching is desirable. In any event, the proposed algorithm can aid in clarifying these issues. One important benefit from this approach is quantification of the savings resulting from reducing the mean, variance, and/or skewness of the leadtime distribution at each stage. The savings can be measured in terms of either reduced planned leadtimes (and hence, the corresponding reduction in safety time and work-in-process inventory) or reductions in total cost. Until now, it was necessary to use simulation (or even real systems!) to set planned leadtimes by trial and error. Our approach will permit both optimization and sensitivity analysis to be done much more efficiently. 15

Incorporation of uncertainty into the selection of planned leadtimes represents an important step toward increasing robustness of manufacturing planning and information systems. An area for further research is an investigation of the robustness of solutions and system cost to errors in estimation of cost and leadtime distribution parameters. Nevertheless, rudimentary sensitivity analyses can be done by varying the relevant parameters and using the algorithm to determine corresponding solutions. The insight obtained from the solution procedure may permit more complete inclusion of queueing phenomena, and extension of the basic approach to more complex systems. We are investigating generalization to such systems as well (see Yano, 1985a, b, c). This research was partially supported by National Science Foundation grant ECS-8206499. The author gratefully ackowledges the helpful comments of the referees and the Associate Editor. 16

4.957 4.684 7 4.9 22 4.622 41808 6 ('* 4.62 4. 22 4590 \ 4.715 4.1 595.71 4 4.z o. \ i I9 3 -t \ \Y.65 / 711 5.074.771 4.766 5.067 ~.., 4.8;1 5.101 1 4y convexity _ guaranteed 0 L, J, _ 0 1 2 3 4 Xl Figure 1 Response Surface 2 2 p11=, 1=3,.U2=1, C 2=9, hi=l, h7=.2, p=4 17

F1(X1) = (h2+p)/(h1+p) X2 determined using (11) X2 = 0 X2 > 0 G12(X1) = (h3+P)/(h1+P) X3 determined using (10) X determined using (10) 3 X3 0 X3 > 0 0 X3 > 0 G123(X ) = p/(hl+p) X2 determined using (10) DONE with X3 = 0 DONE DONE DONE Figure 2 Flowchart for Three-Stage Problem 18

REFERENCES Grasso, E.T. and B.W. Taylor, III (1984), "A Simulation-based Experimental Investigation of Supply/Timing Uncertainty in MRP Systems." International Journal of Production Research 22(3), 485-497. Kanet, J. and D.P. Christy (1984), "Manufacturing Systems with Forbidden Early Order Departure," Internation Journal of Production Research. 22(1),- 41-50. Rees, L.P., P.R. Philipoom, B.W. Taylor III, and P.Y. Huang (1985), "Dynamically Adjusting the Number of Kanbans in a Just-In-Time Production System Using Estimated Values of Leadtime," Working paper, Virginia Polytechnic Institute and State University. Weeks, J.K. (1981), "Optimizing Planned Lead Times and Delivery Dates." 21st Annual Conference Proceedings, American Production and Inventory Control Society, 177-188. Whybark, D.C. and J.G. Williams (1976), "Material Requirements Planning Under Uncertainty." Decision Sciences 7(4), 595-606. Yano, C.A. (1985), "Planned Leadtimes for Serial Production Systems with Rescheduling and Tardiness Costs," Technical Report 85-27, Department of Industrial and Operations Engineering, University of Michigan. (1985), "Stochastic Leadtimes in Two-Level Assembly Systems." Technical Report 85-16, Department of Industrial and Operations Engineering, University of Michigan. -------- (1985), "Stochastic Leadtimes in Two-level Distribution Type Networks." Technical Report 85-17, Department of Industrial and Operations Engineering, University of Michigan. 19

APPENDIX The Hessian for the two-stage problem has the following components: X1 +X2 H11 = (h1 + p) [ f f2(u)f1(X1 + X2 - u)du] X2 + (h1 + p)F2(X2)fl(X1) X1 +X2 H12 = H21 = (h1 + ) [f f2(u) f1(X1 + X2 - u)du] X2 X1+X2 H22 = (h1 + p) If f2(u) f1(X1 + X2 - u)du] X2 - (h1 + p) f2(X2) F1(X1) + (h2 + p) f2(X2) Observe that H, > 0 for all X1 and X2. In addition, X1+X2 det H - [(h1 + p) f f2(u)fl(X1 + X2 - u)du] X2 {(h1 + P)F2(X2)fl(X1) + f2(X2)[h2 + p - (h1 + P)F1(X1)]} +(hI+p)F2(X2)fl(X1)f2(X2)[h2+p - (hl+p)F1(X1)] which is clearly non-negative for all X1 < F1 1[(h2+p)/(h +p)]. One simplystated sufficient (but not necessary) set of conditions for positive definiteness is: X1 > 0, f (X1), and F2(X2) > 0. The first condition is always satisfied for any reasonable cost structure and the second condition leads to (6) in section 2.2. The third condition is the most interesting and we discuss it in more detail below. 20

Observe that there are two possible solutions to the first order conditions in (7) and (8): (1) X1 = F -1[(h2+p)/(hl+p)] and X2 satisfying (7) or (8) given this value of X1 such that F2(X2) > 0 (essentially X2 > 0), and (2) X1 = G12- [p/(p+h1)] and X2 = 0. We next demonstrate that if a solution of the first type exists, a solution of the second type cannot be optimal. We use some graphical "proofs" because they provide insight that an analytic proof cannot. PROPOSITION: If a solution to (7) and (8) with X1 = F1 [(h2+p)/(h +p)] and X2 > 0 exists, it is optimal. PROOF: We first note that both (7) and (8) are monotonically increasing in both X1 and X2. Furthermore, since H12 > 0, the slopes of the curves representing the sets of points satisfying (7) and (8), respectively, are negative (but finite) over their entire range. Let us examine a case where both types of solutions exist. Figure A-1 depicts some representative curves composed of points satisfying (7) and (8). Observe that they intersect in two points. Since the slopes of both curves are negative (but not infinite), the intersection at X2 = 0 necessarily has X1 strictly greater than F1 -[(h2+p)/(h1+p)]. At this intersection point, H11 > 0 but it is easily shown that det H < 0, so this point cannot even be a local minimum. [2 We next demonstrate that if the only solution is of the second type, the optimal value of X1 is strictly less than F1 1[(h2+p)/(h +p)]. 21

PROPOSITION: If a solution of the first type does not exist, X < F-1 (h2+p)/(h +p)]. X1 < F1 [ (h2 1 PROOF: Since a solution of the first type does not exist, the set of points satisfying (7) and (8) intersect in only one point (depicted in Figure A-2), and at X1 = F1 [(h2+p)/(h1+p)], there is no point on either curve where X2 > 0. For (8), a solution exists when X1 is as small as zero. Thus, (8) extends from X1 = 0 to the point of intersection of the two curves, and at all points has X2 > O. Thus, F1 [(h2+p)/(hl+p)] must be strictly larger than the value of X1 at the point of intersection and we must have 0 < X1 < F 1[(h2+p)/(hl+p)]. a FIGURE A-2 The only point that remains to be clarified is that the solution in which X2 = 0 is not unique, since when F2(X2) = 0 the Hessian is only positive semidefinite. This point is discussed more fully in Section 3. 22

X2 points satisfying (7) points satisfying (8) 1 F1 [(h2+P)/(h1+p)] X1 Figure A-i Situation where Solution with X2>0 Exists 23 23

X2 oints satisfying(7) points satisfying(S) G012 p/p+h1)] X1 Figure A-2 Situation where Solution with X2>0 Does not Exist 24