STOCHASTIC LEADTIMES IN TWO-LEVEL ASSEMBLY SYSTEMS Candace Arai Yano Department of Industrial & Operations Engineering University of Michigan Ann Arbor, Michigan 48109-2117 April 1985 Revised April 1986 Technical Report 86-8

STOCHASTIC LEADTIMES IN TWO-LEVEL ASSEMBLY SYSTEMS Candace Arai Yano Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 April 1985 Revised April 1986 This work was supported in part by National Science Foundation Grant ECS-8206499.

STOCHASTIC LEADTIMES IN TWO-LEVEL ASSEMBLY SYSTEMS ABSTRACT Shortages of assembly parts often arise from late arrivals of one or more batches of components. We address the problem of determining planned leadtimes in two-level assembly systems with stochastic leadtimes, with the objective of minimizing the sum of inventory holding costs and tardiness costs. An algorithm is developed which exploits properties of the objective function to find optimal solutions. Computational results indicate that optimal solutions often have negative safety times for at least one of the components, as well as substantial safety times for the assembly stage.

STOCHASTIC LEADTIMES IN TWO-LEVEL ASSEMBLY SYSTEMS 1.0 INTRODUCTION The problem of parts shortages in assembly environments often results from variable timing of the arrival of a batch of component parts. The late arrival of a batch of a single component can delay an entire production run. Uncertainty in production or procurement leadtimes has a variety of causes. If the components are produced, the actual production leadtime will vary with because of queueing or transporation delays. Other reasons are variable setup times (particularly when calibrations are difficult) and variable processing times. The latter can arise when yields are variable and production continues until a specified number of acceptable parts has been completed. If the components are procured, availability at the vendor and transportation times may be uncertain. Earlier work on stochastic leadtimes includes simulation studies by Whybark and Williams (1976) and Grasso and Taylor (1984), models for single stage systems (Weeks, 1981), and approaches for serial systems (Yano, 1985). To the author's knowledge, no prior research has been done on safety times for multistage assembly systems with stochastic leadtimes. Yet, much of the coordination problem in assembly systems results from timing problems, not quantity variations. The general problem is quite complex. We therefore investigate a simple system under a strong set of assumptions with the expectation that the insights gained might be generalized to more realistic systems. In section 2 we describe and formulate the problem for the case with two components. Section 3 details the development of an algorithm which exploits properties of the objective function to find the optimal solution. Section 4 includes computational results which provide insight into characteristics of optimal solutions. Section 5 concludes with a summary and discussion. 1

2.0 PROBLEM DESCRIPTION AND FORMULATION We address the problem of determining optimal planned leadtimes in a twolevel assembly system with two components. These planned leadtimes are flow time allowances, and may include safety time, which is the difference between the planned leadtime and the average leadtime. The reason for investigating the use of safety time rather than safety stock is that prior research by Whybark and Williams (1976) indicates that safety time is preferred to safety stock when timing (rather than quantity) is uncertain. There are other assumptions in our model which also make safety time a more logical alternative. Related issues are discussed in conjunction with these assumptions. We assume that the two components are either produced or procured, and the times required to do so are permitted to be stochastic. We also permit the time required for the assembly process to be stochastic. Therefore, actual start (and completion) times may not be known with certainty. We further assume that these leadtimes are statistically independent, continuous, and twice differentiable. (Generalization to discrete leadtime distibutions is straightforward). A network representation of the system appears in Figure 1. We assume that there is a due date, d, for an order (or batch) of the finished product and that the order cannot be shipped before the due date. Systems with such "forbidden early departure" are described further in Kanet and Christy (1984). For simplicity, lot sizing is assumed to be done on a lot-forlot basis. If setup costs are of concern, lot-sizing can be done in advance using any applicable optimal or heuristic procedure (e.g., Blackburn and Millen (1982), Afentakis et al. (1984), or Roundy (1984)). Then, for each assembly run the problem is one of determining when to produce or procure the components which are not already available, and when to begin the assembly run. It is 2

assumed that if batching of orders is done, all units in the batch must be processed together (i.e., no lot splitting). Thus safety stock would need to be as large as the batch in order to provide any protection. We considered it uneconomical to use safety stock in such large quantities. Inventory holding costs (denoted hi for the item i batch) are charged for each period that a component waits for dispatching to assembly or that the finished product waits for shipment to the customer. If the batch is tardy, a penalty per period, p, is assessed, which reflects the additional cost of expediting and loss of goodwill. We assume that h2 + h3 < h1, since otherwise there would be little incentive for timing buffers (safety time) at the component level. We also assume that hi < p to provide some incentive for timely completion of the job, although this assumption is not critical to our model. The decisions to be made are (1) when to initiate production or procurement of each component, and (2) when to initiate the assembly process. Let Xi represent the planned leadtime for stage i. The system operates as follows. Assembly will commence at time d - X1 provided that both components are available. Otherwise, assembly will commence as soon as they are available. Production or procurement of component i, i = 2,3, is initiated at time d - X - Xi, where Xi is the planned leadtime for component i. We assume that d is sufficiently large so that d - X1 - Xi > O, i = 2,3 (i.e., it is not already too late to execute the desired plan). We assume that batches at any given stage are independent of one another. This strong assumption permits us to examine one batch at a time. Thus, we do not consider the effects of scheduling and queueing. The principal difficulty of incorporating detailed scheduling and queueing phenomena into the model is that we are attempting to develop normative policies in view of economic tradeoffs between inventory holding costs and tardiness costs. On the other 3

hand, nearly all scheduling and queueing models either only describe, or have the objective of minimizing one of the two. It would be reasonable to use empirically obtained distributions as inputs to our model to get an initial solution. Then, the initial solution can be implemented or simulated to obtain new distributions and a revised solution. Rees, et al. (1985) have used this type of technique (using simulation) for a single stage system with uncertain leadtimes, and have obtained rapid convergence. Thus, we expect that a similar approach would be viable for the assembly system. We use the following additional notation throughout the paper: Ti = actual leadtime for process i fi(x) = PE T- = x] Fi(x) =PE Ti < x] E( ) = expectation *')+ = positive part A formulation of the problem appears in Appendix A. It is a difficult nonlinear programming problem in which the decisions regarding planned leadtimes for the two components are not separable because (although not obvious from the formulation) much depends upon the maximum tardiness of the two components. There are no distributions for which the distribution of the maximum of two random variables (much less the maximum tardiness) can be represented as another standard distribution. Thus, it appears that the assembly problem cannot be collapsed into an equivalent serial problem. 3.0 SOLUTION METHODOLOGY It can be shown that the objective function for this problem is not convex for all leadtime distributions. However, the objective function does have two useful properties which are proved in Appendix C: 4

Property 1: For fixed X2 and X3, the objective function is convex in X1. Property 2: For fixed X1 < F1 [(h2+h3+p)/(h1+p)], the objective function is convex in X2 and X3 (jointly). Since the objective function has these properties, the first order necessary conditions can be useful, since they all must be satisfied at optimality. (The first order necessary conditions appear in Appendix B). It is clear (for the interested reader) from equation (B-1) and is intuitively obvious that given any X2, X3 pair, X1 can be determined quite easily using the appropriate first order necessary condition (namely, equation (B-1)). We note that if all first order conditions are satisfied, it must also be true that ~TC/X1 - dTC/TX2 - )TC/)X3 = 0. After simplification, this yields: F1(X1) = [p/(h1 + p)] + {h211 - [f2(t2)F3(X 3 + t2 - X2)dt2] X2 + h3 [1 - r f3(t3)F2(X2 + t3 - X3)dt3]}/(h1 + p) (1) X3 Thus, it is evident that given any X2 and X3 we can find X1. What is interesting about this equation is the fact that it indicates (reasonably) explicitly how X1 depends upon X2 and X3 Furthermore, since the integrals represent probabilities between zero and 1, it is evident that for any values of X2 and X3 satisfying first order conditions, F1(X1) > p/(p+h1) (2) which would be the "newsboy" solution to the single-stage problem. Also, F1(X1) < (h2+h3+p)/(p+h ). (3) Thus, the condition for convexity of the objective function with respect to X2 and X3 is always satisfied at points satisfying first order conditions. 5

We note that the second and third terms in (B-2) are non-negative for all Xi. Thus, for the first order condition to be satisfied, we must have (h2 + h3 + p) fj f2(t2)F3(X3 + t2 -X2)dt2 > h2 X2 But 1- F2(X2) > I f2(t2)F3(X3 + t2 - X2)dt2 Jx X2 Therefore F2(X2) < (h3 + p)/(p + h2 + h3) (4) Similarly, using the partial derivative with respect to X3, we have F3(X3) < (h2 + p)/(p + h2 + h3) (5) A workable procedure would be to find the optimal values of X2 and X3 (using any standard non-linear programming procedure) for each candidate value of X1. This, of course, is not very efficient, but since the objective function is not convex, there are few practical alternatives. We turn to a computational study which we hope will provide some information on the characteristics of optimal safety time policies. 4.0 COMPUTATIONAL RESULTS The objective of our computational work is to develop an understanding of characteristics of optimal solutions, particularly with regard to X1. We randomly generated 25 problems, choosing from among feasible combinations of parameters listed in Table 1. We have used Poisson leadtime distributions (with parameter Xi) for simplicity and normalize the value of hi to 1.0. The resulting problems are listed in Table 2. We used results in Section 3 to obtain bounds on the solution space, which are listed in Table 3. The lower bar denotes a lower bound 6

and the upper bar denotes an upper bound on the respective decision variable. In some case (particularly when p is small), the bounds are quite tight relative to the magnitude of the Xi. However, when p is large, the bounds for are improvements over (nearly infinite) enumeration, but really do not provide much help. The primary role of the bounds is to eliminate computations of gradients, etc., in directions that would be outside the "optimal" region. TABLES 1, 2, AND 3 Solutions for the problems are listed in Table 4 with safety times in parentheses. It was not surprising to find a significant amount of safety time at stage 1 in most cases. It was surprising, however, to find negative safety time for at least one of the two components in many instances. These situations appear to fall into two categories. The first category represents situations in which the component holding cost is relatively high (i.e., 0.40 or over) and the shortage cost is relatively low (i.e., 1 or 4). Problems 6, 8, 14, and 24 are examples of such situations. The second category comprises situations in which one component leadtime is much longer than the other (such as in problem 14). Here, negative safety time for the component with the longer leadtime is compensated for by a significant amount of safety time at stage 1. TABLE 4 One other result worth noting is that whenever hi >.65, i = 2,3, the optimal safety time is non-positive for stages 2 and 3 in these examples, except in instances with extremely high shortage costs (i.e., p = 49). While it makes sense intuitively that the larger the holding cost, the smaller the safety time, one might not expect so low a "cutoff" point. We cannot make a definitive statement on the position of X1 relative to its upper and lower limits. It appears that further research is necessary to 7

characterize the effect of the various costs and parameters on the optimal value of X1. We note that the relationships among the amount of safety time and the component holding cost and leadtime is not always as we would anticipate. For example, in problem 16, we have equal component holding costs, but different average leadtimes for the components. The component with the longer average leadtime has safety time while the component with the shorter planned leadtime does not. Thus, it appears that interactions between the components are quite complex, and "logical" solutions based on marginal analyses are not necessarily optimal. In addition, it appears that the variances of the leadtimes as well as their means may be responsible, in part, for these results. By using a Poisson distribution for the leadtimes, we have implicitly assumed a variance to mean ratio of 1. In practice, leadtimes with larger means generally have larger variances, but the relationship is not necessarily linear. To investigate the effects of the leadtime variance on the solutions, we constructed a small set of problems with negative binomial leadtimes. The parameters selected were i = 2, i = 1,2,3, i/i = 2,4,8, h = 1.0, h = h = 0.10, and p = 4. We selected Xi small enough to minimize the computational burden while still being large enough so that the different variances would have a noticeable effect. We chose h2, h3, and p so that safety time may be economical at all stages. The results are listed in Table 5. They indicate a sensitivity of the planned component leadtime values to the variance of the component leadtimes, and an amazing insensitivity of the planned assembly leadtime to the component leadtime variances. The reason for the latter result may be the relatively high safety times for the components. These large safety times ensure that the components will be on time a vast majority of the time, so that "extra" safety time at stage 1 is not necessary. 8

TABLE 5 In general, the results are similar to the results with Poisson leadtime distributions when the component holding costs are small (e.g., problems 18 and 21) in that safety time at all stages is non-negative. We also compared the results for the 9 symmetric systems from this set of problems with results for "similar" serial systems. For the serial systems, we set h2' = h2 + h3 and determined optimal planned leadtimes using the algorithm in (Yano, 1985). The solutions are listed in Table 6. It is evident that much more total safety time is required in the assembly systems (both X2 and X3 for the assembly system are larger than X2 for the serial system). Therefore, it appears that increasing the number of components increases the optimal safety times for components, and thereby the inventory holding costs associated with them. We might speculate, similarly, that a reduction in the number of components will reduce the inventory holding cost associated with safety time. TABLE 6 5.0 SUMMARY AND DISCUSSION We have developed a procedure which finds optimal planned leadtimes for two-level assembly systems. Computational results indicate that in some cases optimal solutions have the characteristic of negative safety time for at least one of the components and significant amounts of safety time for the assembly stage. We comment briefly that we have found similar patterns in two level production systems which have distribution-type arborescent network structures (see Yano, 1985b). Thus, the results appear to be more general than may be indicated by the results here. The increase from one component (i.e., a serial system) to a system with two components causes a significant increase in the optimal amount of safety 9

time for components. It would appear that additional components would further increase safety time for components. Operationally, having negative component safety times and large assembly safety times necessitates much more flexibility in scheduling at the assembly stage. The results also have important implications for supply decisions. If suppliers are perfectly reliable, then safety time is not needed. But if suppliers are even slightly unreliable, then having fewer parts to assemble, and/or using fewer suppliers to produce the same number of parts (assuming some coordination occurs at the supplier to ensure that parts to be mated arrive together), may result in significant inventory savings and shorter total leadtimes. On the basis of the results, managers would be advised to concentrate their efforts on "improving" leadtime characteristics of parts to be assembled (primarily by reducing the variances) and to reduce the number of parts, where possible. It may be better to have longer average, but less variable, leadtimes, and the procedure discussed here can be used to help quantify the economic effects of these factors. While some of these concepts are already well known, the magnitude of these effects probably has been underestimated in the past because techniques were not available to optimize each system before comparing alternatives. The results here represent an initial attempt to perform this optimization so that the magnitude of the savings can be estimated more accurately. Further analytical work is required to address situations with multiple components. The maximum tardiness of the components can be modeled using order statistics (for special cases), but two difficulties remain. The first involves modeling the component inventory costs in a tractable fashion (and the related first order conditions). The second difficulty relates to the irregularity of the objective function. For serial systems, the objective function is convex 10

for most leadtime distributions. For the simple assembly system studied here, it is less well-behaved. We might expect the objective function for the general n-component case to be somewhat less well-behaved, although it is conceivable that the objective function is convex in X1 with the other values fixed and jointly convex in the other decision variables with X1 fixed. Unfortunately, even writing the first order conditions for the n-component problem is not an easy task. It is likely that we must resort to (good) heuristics for more general problems. These problems may not be solved easily, but the economic benefits of understanding the major effects and tradeoffs may make further analyses worthwhile. Further research is also needed to incorporate the effects of queueing and various scheduling policies. 11

3~ S Stage 1, af Figure 1 Network Representation 12

TABLE 1 Problem Parameters Parameter Values xi 1, 3, 5, 10, i = 1, 2, 3 (Poisson parameter) hi.10,.25,.40,.65,.80, i = 2, 3 p 1, 4, 9, 19, 49 13

TABLE 2 Problem Data Problem 1 2 3 h2 h3 P 1 1 5 5.40.10 9 2 5 3 5.40.25 4 3 1 5 3.25 65 4 4 10 3 10.65.25 9 5 10 10 10.40.25 49 6 10 3 3.40.10 4 7 10 5 5.10.40 49 8 3 3 1.65.25 1 9 5 1 1 10 10.40 4 10 1 3 10.80.10 49 11 5 3 5 25.65 49 12 1 3 1.25.65 9 13 1 10 1.10.80 19 14 1 1 1.80.10 4 15 10 1 5.65.25 9 16 1 5 1 40.40 9 17 5 3 3.65.10 9 18 3 3 1.10 10 4 19 1 1 1.25.65 9 20 5 10 10.10.80 49 21 5 3 1.10.10 1 22 5 1 10.25.40 19 23 3 5 1.80.10 9 24 5 5 1.25.65 1 25 10 5 3.65.10 19 14

TABLE 3 Bounds on Decision Variables PROBLEM 1 x1 X 3 1 2 3 9 11 2 7 8 5 9 3 2 3 9 5 4 14 18 6 17 5 17 18 18 19 6 13 14 5 7 7 17 18 12 11 8 3 6 3 2 9 7 8 4 14 10 3 5 7 20 11 10 12 8 11 12 3 4 7 3 13 3 4 19 3 4 2 3 2 3 15 14 18 3 10 16 2 3 9 3 17 8 10 6 8 18 4 5 7 3 19 2 4 3 3 20 10 12 20 17 21 5 56'2 22 9 9 4 17 23 5 8 8 4 24 5 9 8 1 25 16 18 9 8 15

TABLE 4 Optimal Solutions Values and Safety Times Problem X X* X 1 3 (2) 7 (2) 9 (4) 2 8 (3) 3 (0) 6 (1) 3 3 (2) 7 (3) 3 (0) 4 16 (6) 2 (-1) 12 (2) 5 18 (8) 13 (3) 14 (4) 6 14 (4) 2 (-1) 4 (1) 7 18 (8) 8 (3) 6 (1) 8 4 (1) 2 (-1) 1 (0) 9 8 (3) 1 (0) 11 (1) 10 5 (4) 4 (1) 17 (7) 11 12 (7) 4 (1) 5 (0) 12 3 (2) 5 (2) 1 (0) 13 4 (3) 16 (6) 1 (0) 14 3 (2) 0 (-1) 2 (1) 15 16 (6) 0 (-1) 6 (1) 16 3 (2) 7 (2) 1 (0) 17 9 (4) 3 (0) 5 (2) 18 5 (2) 5 (2) 2 (1) 19 3 (2) 2 (1) 1 (0) 20 12 (7) 15 (5) 12 (2) 21 5 (0) 4 (1) 2 (1) 22 10 (5) 1 (0) 13 (3) 23 7 (4) 5 (0) 2 (1) 24 6 (1) 6 (1) 0 (-1 25 17 (7) 5 (0) 5 (0) 16

TABLE 5 Negative Binomial Results for Assembly Systems CY2 2 2 2 x* o12 o22 o32 X1 X2 X3 4 4 4 4 5 5 8 4 5 8 16 4 5 11 8 8 4 8 8 16 4 8 11 16 16 4 11 11 8 4 4 4 5 5 8 4 5 7 16 4 5 11 8 8 4 7 7 16 4 7 11 16 16 4 11 11 16 4 4 4 4 4 8 4 4 7 16 4 4 11 8 8 4 7 7 16 4 7 11 16 16 4 11 11 All safety times are two units less than the respective Xi values. 17

TABLE 6 Negative Binomial Results for Serial Systems o1 2 X1 X2 4 4 4 2 8 4 2 16 4 2 8 4 4 2 8 4 3 16 4 3 16 4 4 2 8 4 3 16 4 3 All safety times are two units less than the respective Xi values. 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. 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, Department of Management Science, Virgina Polytechnic Institute and State University. Weeks, J.K. (1981), "Optimizing Planned Lead Times and Delivery Dates", American Production and Inventory Control Society 21st Annual Conference Proceedings, 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), "Setting Planned Leadtimes in Serial Production Systems with Tardiness Costs", Technical Report 85-7, University of Michigan, Department of Industrial and Operations Engineering. Yano, C.A. (1985), "Stochastic Leadtimes in a Two-Level Distribution Type Network," Technical Report 85-17, Department of Industrial and Operations Eng ineer ing. 19

APPENDIX A The problem can be formulated as: minimize: X3 h3 [F2(X2) f (X3-t3)f3(t3) dt3 Jo X3+t -X2 + f f' (X3 +t2-X2-t3) f3(t3) f2(t2) dt3 dt2 X2 0 +f0 f (t2-X2-t3+X3) f2 (t2)f3(t3) dt2 dt3 J J X3 X2+t3-X3 X2 + h2 [F3 (X3) f (X2-t2) f2 (t2) dt2 Jo X2+t -X3 r+ f 3 (X2+t3-X3-t2) f2 (t2) f3 (t3) dt2 dt3 Xp 0 J2 + f f(t3-X3-t2+X2) f3 (t3) f2 (t2) dt3 dt2] X2 X3+t2-X2 + h1 [F2 (X2) F3 (X3) F i (X-t1) fl (tl) dt1 Jo X1+X3 X1+X3-t3 + F2 (X2) f 3 1 (X1+X3-tl-t3) fl (tl) f3 (t3) dt1 dt3 J, J0 X1+X2 X2+X3-t2 + F3 (X3) f f (X1+X2-t1-t2) f2 (t) f (t2) l ) dtldt2 J J X2 X1 +X3 Xi +X2 Xi +X2-t2 +f r I3 xf Xf+X F+(Xl+X2-tl-t2) fl (tl) f2 (t2) f3 (t3) dtl dt2 dt3 X3 X2+t3-X3 0 20

X1 +X2 X1 +X3 X +X3-t ~+ f ff.~ f(X1+X -tl-t3) fl (tl) f3 (t3) f2 (t2)dtl dt3 dt2] X2 X3+t2-X2 0 x2 0X2) +P [F2 (X2) F3 (X3) If (tl-X1) fl (t) dtl X1 (X i +X2 I + F3 (X3) 2. f(tl+t2-X1-X2) fl (tl) f2 (t2) dtl dt2 J J X2 X1 +X2-t2 X1+X3 + F2(X2) f (tl+t3-X1-X3) fl (tl) f3 (t3) dtl dt3 J J 3 X1 X3-t3 Xi +X3 Xi +X2 + fX+X3 f 2 f (tl+t2-Xl-X2) fl (tl) f2 (t2) f3 (t3) dtl dt2 dt3 J J J -x3 X2+t3-X3 X1+X2-t2 + F3 (X +X ) f (l1+t2-X1-X2) f2 (t2) dt2 X1+X2 X.1+X2 X1 +X3 c x+ rft X +2 l (t1+t -Xi-X3) fl (tl) f2 (t2) f3 (t3) dt dt3 dt2 2 X3+t 2-X2 X1+X3-t3 + F2 (X1+X2) r (pl+t3-X1-X3) f3 (t3) dt3 Xl +X3 + f f00 (P1+t3-X1-X3) f3 (t3) f2 (t2) dt3 dt2 J J X1 +X2 t2-2+X3 + f'" fr (P1+t2-X1-X2) f2 (t2) f3 (t3) dt2 dt3] J J XI+X3 t3-X3-X2 subject to Xi, i 21

APPENDIX B The first order conditions are as follows: TC --- = (h1 + p) {F1(X1)F2(X2)F3(X3) + Xi X1 + X2 F3(X3) j f2(t2)F1(X1 + X2 - t2)dt2 + X2 X2 X1 + X3 F2(X2) j f3(t3)F1(X1 + X3 - t3)dt3 + X3 X1 + X X + X 2 rfl 3 f3(t3)f2(t2)F (X1 + X2 - t2)dt2dt3+ X3 X2 + t3 -X3 X1 + X2 X1 + X3 r + f2(t2)f3(t3)F1(X1 + X3 - t3)dt3dt2} i j 3 X2 X3 + t2 -X2 -p = 0 (B-1) A TC = - (h2 + h3 + p) f2(t2)F3(X3 + t2 - X2)dt2] X2 2 X2 X1 + X + (h1 + p)[F3(X3) r f2(t2)F1(X1 + X2 - t2)dt2 X2 X + X3 X + X2 + +3 2 f3(t3)f2(t2)F1(X1 + X2 - t2)dt2dt 3] X3 X2+t3-X3 + h2 = 0 (B-2) The partial derivative with respect to X3 is the same as equation (B-2) with subscripts 2 and 3 interchanged. 22

APPENDIX C The elements of the Hessian matrix are: H1 = (h1+P) {f1(X1)F2(X 2)F3(X3) X1+X2 + F3(X3) r f2(t2)f (X1 + X2 - t2)dt2 J X2 X1+X3 + F2(X2) f f3(t3)f1(X1 + X3 -t3)dt3 X3 x3 X1+X3 X1+X2 I'+ fl X3 XfX2 f3(t3)f2(t2)f (X1 + X2 - t2)dt2 dt3 J J X3 X2+t3-X3 X 1+X2 X1+X + 3 f2(t2)f3(t3)f (X1 + X3 - t3) dt3 dt2} J,, J X2 X3+t2-X2 >0 X1 +X H12 = (h+P) {F3(X3) f f2(t2) fl (X1 + X2 - t2)dt2 X X2 XI+X3 XI+X2 + Xi+3 f3(t3)f2(t2)f1(X1 + X2 - t2)dt2 dt3 J X3 X2+t3-X3 X+X3 + ( f3(t3)f2(X2 + t3 - X3) F1 (X1 + X3 - t3)dt3 X3 x3 X1+X2 + r f2(t2)f3(X3 + t2 - X2) F1 (X1 + X2 - t2)dt2} X2 > 0 23

H22 (h2+h3+p) [ r f2(t2)f3(X3 + t - X2)dt2 + f2(X2) F3 (X3) ] X2 X1+X2 + (h+P) [ F3(X3) f2(t2)fl(X1 + X2 - t2)dt2 X2 - F3(X3)f2(X2)F1(X1) X 1+X3 X1 +X2 + f I rfr3(t3)f2(t2)fl(X1 + X2 - t2)dt2 dt3 J J X3 X2+t3-X3 XI+X3 - f3(t3)f2(X2 + t3 - X3) F1 (X1 + X - t3)dt3 ] -;u~x 23 = -(h2+h3+p) r f2(t2)f3(X3 + t2 - X2)dt2 2X2 XI+X3 +(h1+p) [ f f3(t3) f2(X2 + t3 - X3) F1 (X1 + X - t)dt3 ] x3 IH13 is the same as H12 with subscripts 2 and 3 reversed and H33 is the same as H22 with subscripts 2 and 3 reversed. 24

We prove several properties of the objective function in the remainder of this appendix. PROPERTY 1: For fixed X2 and X3, the objective function is convex in X1 for X1 > 0. PROOF: This follows directly from H11 > 0. o PROPERTY 2: A sufficient condition for convexity of the objective function with respect to X2 and X3 for fixed X1 is X1 F1 [(h2 + h3 + p)/(hl + p)]. PROOF: We must show that H22 > 0,H33 > 0 and H22 H33 H2 for F1(X1) < (h2 + h3 + p)/(h1 + p). We note that (h2+h3+p) I f2(t2)f3(X3 + t2 - X2)dt2 X2 X1 +X = (h2+h3+p) [ 2 f2(t2)f3(X3+t2-X2)dt + D f2(t2)3)f3(X3+t-X2)dt2 ] X2 x1+x2 and X1 +X2 X1+X3 r f2(t2)f3 (X3+t2-X2)dt2 = f f3(t3)f2(X2+t3-X3)dt3. J J 2 X3 Therefore, X +X (h1+P) f f3(t3)f2(X2+t3-X3) F1 (X1+X3-t3)dt3 JX x3 X1+X < (h +p) F1(X1) f f3(t3)f2(X2+t3-X 3)dt3 x3 25

x +X3 < (h2+h3+P) f f3(t3)f2(X2+t3-X3)dt3 X3 x3 X1+X2 = (h2+h3+p) I f2(t2)f3(X3+t2-X2)dt2 X2 where the second inequality holds because FI(X1) < (h2+h3+p)/(hl+p). So the first term in H22 is larger than the absolute value of the last term. It is also evident that (h2+h3+p)f2(X2)F3(X3) > (hl+p)F3(X3)f2(X2)F1(X1 ) if F1(X1) < (h2+h3+p)/(hl+p). Thus, the second term of H22 is larger than the absolute value of the fourth term. Hence, H22 > 0 if F1(X1) < (h2+h3+p)/(hl+pl). The proof for H33 is identical (except for the reversal of subscripts). To show that H22 * H33 - H23> > 0 it is necessary to show that the fifth and sixth terms, respectively, of H22 and H33 are identical. Then, using the fact that the first terms are also identical, the result follows directly. We omit the details here. o 26