PLANNED LEADTIMES FOR SERIAL PRODUCTION SYSTEMS Candace Arai Yano Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI Technical Report 86-20 September 1985 Revised May 1986 and September 1986

PLANNED LEADTIMES FOR SERIAL PRODUCTION SYSTEMS Candace Arai Yano Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 September 1985 Revised May 1986 and September 1986

PLANNED LEADTIMES FOR SERIAL PRODUCTION SYSTEMS ABSTRACT We investigate the problem of setting planned leadtimes in serial production systems when the actual leadtimes are stochastic. The objective is to minimize the sum of inventory holding costs, rescheduling costs arising from tardiness at intermediate stages of production, and tardiness of delivery to the customer. A single-pass algorithm is developed which finds optimal solutions. The analytical models underlying the algorithm and extensive computational experience indicate that it is never optimal to have planned leadtimes of zero when there are rescheduling costs at intermediate stages of production. This also implies that unconditional immediate dispatching is not optimal under these conditions.

PLANNED LEADTIMES FOR SERIAL PRODUCTION SYSTEMS INTRODUCTION Computerized manufacturing information and planning systems such as Material Requirements or Manufacturing Resource Planning (MRP) systems require several operating policy "rules." To specify production batch sizes, it is necessary to have a lot-sizing or production interval (lot-timing) policy. Planned leadtimes (times allowed for each stage of production) are required to determine when each batch should be started. It would be desirable to jointly optimize lot-sizing and planned leadtime decisions. Capacitated lot-sizing models, which attempt to deal with these decisions simultaneously, are addressed extensively in the literature (see references in Billington, et al. (1983)). These problems, however, are difficult to solve (particularly for multi-stage systems) and because only finite-horizon verions can be solved (except in special cases), the solutions may be "nervous" or unstable in a dynamic environment. Furthermore, these approaches cannot incorporate uncertainty of actual leadtimes at the various stages of production. Recent research by Karmarkar, et al. (1985a,b) has investigated the interaction between lot-sizes and leadtimes. Their analyses indicate that when there are positive setup times and lot sizes are too small, actual leadtimes increase exponentially (since the traffic intensity approaches or exceeds 1). As the lot sizes increase, the actual leadtimes asymptotically approach a linear function of the lot size. Considerable effort has already been directed toward solving lot-sizing problems, but very little attention has been given to determining planned leadtimes. Therefore, in this paper we focus on the latter problem. Most MRP systems use weekly planning periods, even though most production 1

processes require far less than one week, even for a "large" batch. Thus, while planned leadtimes are needed in weekly increments, they are also needed in more detail to provide local information on priorities and intermediate "due dates" where several processes may be completed in a week. In either case, the primary reason that planned leadtimes must be specified is that actual leadtimes may be stochastic because of queueing, variable material handling times, and uncertain procurement leadtimes. If the planned leadtimes are too short, certain stages of production may be completed "late," possibly requiring rescheduling to be done at one or more subsequent stages of production; also, delivery of finished product to the customer may be tardy, resulting in expediting or loss of customer goodwill. On the other hand, if the planned leadtimes are too long, work-in-process and even finished goods inventory may be larger than necessary. We investigate the problem of setting planned leadtimes in such an environment. We use the term "planned leadtime" to refer to the time allowed for production at a stage. Safety time refers to the difference between the planned leadtime and the average leadtime, where this value may be negative. Earlier work on planned leadtimes and related safety time issues includes simulation studies by Whybark and Williams (1976) and Grasso and Taylor (1984) which indicate that quantity and type of buffering are important decisions when leadtimes are variable. Weeks (1981) developed a one-stage model with tardiness costs, which is a standard "newsboy" problem. Yano (1985) developed an optimal solution procedure for serial systems with tardiness costs. Her experimental results indicate that safety time often should be negative for all but the final production process. Graves (1985) developed a model which characterizes the operational behavior of a job shop where a control rule is used which is consistent with the assignment of a planned leadtime. 2

Our study differs from earlier work in that both rescheduling costs at intermediate stages of production due to tardy completion of the previous stage and tardiness costs for the finished product are included. Although rescheduling costs are difficult to quantify, it would be useful to determine what existing safety time policies imply about the cost of rescheduling. If the implied cost exceeds any reasonable estimate of actual costs, this should provide some incentive for reducing safety times, and thereby reducing work-inprocess inventories. Of course, if the converse were to hold, more safety time would be warranted in view of the cost of rescheduling. The actual cost of "rescheduling" includes both the cost of revising the schedule (if necessary) and the effort involved in any expediting which may be done. Thus, while use of a simple dispatching policy may make the cost of revising the schedule negligible, the expediting effort is still likely to increase as the job becomes tardier. For instance, the expediting effort may affect more than just the tardy job. Other jobs may be started earlier than planned, which may necessitate expediting of material inputs or reallocation of resources. We would expect the leadtime distributions to reflect the "usual" expediting efforts, since expedited and non-expedited batches are not likely to be separated in historical data on leadtimes. Modeling the effect of tardiness and expediting on leadtime dynamics remains a difficult problem for future research. The primary reasons for this investigation was our observation that most MRP systems do not use planned leadtimes with the (significantly negative) safety times suggested by the study of Yano (1985). Rather than having negative safety times, it is customary for each stage to have a positive safety time. One of the questions that we want to address in this study is whether the presence of actual (or perceived) rescheduling costs at intermediate stages of production lead to planned leadtime policies with characteristics more similar 3

to those observed in practice. Later in the paper we present algorithms which can be used to determine optimal planned leadtimes. However, we view them as being much more useful as managerial tools for quantifying and analyzing some tradeoffs that are much too complex to study without the aid of such algorithms. Before continuing, we want to emphasize that queueing phenomena and detailed scheduling rules will not be modeled explicitly here. The arrival process and service rate distributions at the various stages will certainly affect the leadtime distributions. Further, the planned leadtimes will also affect the leadtime distributions by influencing the "arrival" process to successor stages. One way to incorporate more detailed queueing and scheduling effects is to use empirically observed leadtime distributions to determine initial planned leadtime policies. These policies can be simulated to provide updated leadtime distributions, which then can be used to find updated leadtime policies. This type of procedure has been used by Rees, et al. (1985) to address similar issues in a single stage system, and was found to converge rapidly. We present a formulation and a solution procedure for the two-stage problem to provide the reader with the basic foundations of the approach. We subsequently discuss extensions to N-stage systems briefly. This is followed by discussions of an experimental study of two- and three-stage systems from which we infer some general principles, and finally, a summary and conclusions. MODEL ASSUMPTIONS AND FORMULATION We investigate the problem of determining planned leadtimes in serial production systems where the objective is to minimize the sum of inventory holding, rescheduling, and job tardiness costs. Inventory holding costs are charged on all work-in-process inventory waiting to be dispatched to the next 4

stage of production, and on all finished goods inventory waiting to be sent to the customer. We assume, as in Kanet and Christy (1984), that "early order departures" are forbidden; one cannot send an order to the customer before the specified ship date. Similarly, we assume that semi-finished product cannot be dispatched to the subsequent stage prior to the dispatch time implied by the planned leadtimes. (These planned leadtimes may be zero or very small, giving a policy of immediate dispatching upon completion). Rules of "forbidden early departure" parallel (in concept) those used in just-in-time inventory systems, and MRP systems ostensibly use such rules (although practice often differs). The dispatching policy is described in more detail later in this section. Linear rescheduling costs are charged for tardiness (relative to the intermediate due dates implied by the planned leadtimes) at intermediate production stages. Note that rescheduling costs are charged only if a stage is tardy; if a stage is completed early, it is not necessary to reschedule any subsequent stage. Linear tardiness costs are charged for late delivery of the finished product to the customer. We have used linear costs here because the consequences usually become more severe as tardiness (at any stage) increases. Other functions could have been used, but in real applications it is difficult to estimate even a single parameter, so we chose to use this simple model. One other approach would be to have a fixed rescheduling cost at each stage which is independent of the degree of tardiness. Nevertheless, we believe that rescheduling-related costs (when they exist) do actually increase with tardiness over the ranges of tardiness normally observed. The rescheduling costs need not be large; we only require that they be positive. If all rescheduling costs are zero, the model of Yano (1985) would be applicable instead. For each stage, there is an implicit "earliest dispatch time" which is the customer due date less the sum of the planned leadtimes of that stage and all 5

successor stages. The earliest dispatch time for a stage can also be viewed as the "due date" for the preceding stage. If a stage is completed prior to its due date, the item waits until the due date. However, if a stage is completed after its due date, the item is dispatched to the subsequent stage immediately upon completion. The reader may be curious about why such a policy would be used. Why not dispatch everything immediately? Since the finished product cannot be shipped to the customer early, dispatching everything immediately could result in value being added to the product earlier than may be desirable, possibly increasing the average investment in work-in-process and finished goods inventories. Of course, in many situations the cost of labor is nearly fixed, and material procurement is not well synchronized with production. In these circumstances, the effect of the scheduling policy on cash flow (and therefore on inventory holding costs) is immaterial. It is, however, important to realize that there is generally a preference for holding product in a lesser stage of completion. One reason is that "raw" materials are easier to store (normally in centralized storage), whereas semifinished parts may occupy scarce space in the production area A second reason is that work-inprocess tends to become less versatile (in the sense of being suitable for inclusion in fewer finished products) as production progresses. In any event, if immediate dispatching is desirable, the optimal policy would simply have zero (or very small) planned leadtime at the relevant stages. Thus, the policy that we consider permits immediate dispatching but does not require it. We note that the procedure described later in the paper only requires that the inventory holding cost at each stage be non-negative. We do not require that echelon holding costs be positive. Thus, there are no conditions on the inventory holding costs which would prevent immediate dispatching as an alternative, a priori. The presence of positive rescheduling 6

costs will, however, tend to limit the use of immediate dispatching. We assume that demand is deterministic (i.e., the system is driven by customer orders), and that a lot-for-lot policy is used. If demand is uncertain, then a planned production quantity (e.g., demand forecast) can be specified instead of a customer order quantity and the problem remains unchanged. The leadtimes may be stochastic, and their distributions are assumed to be stationary in time. We also assume that they are mutually independent, continuous and twice differentiable (although extension to discrete leadtimes is straightforward). We next formulate the two-stage problem and then discuss a solution procedure for it in the following section. Our intent is to provide an in-depth study of a small but tangible problem before proceeding to an investigation of larger systems. Notation: hi - holding cost (per batch) per period at stage i Pi = penalty cost (per batch) per period at stage i i = actual leadtime at stage i Xi = planned leadtime for stage i (decision variable) fi(*) = density of leadtime at stage i Fi(') = leadtime distribution at stage i E(') = expectation ()+ = positive part F*G = convolution of two cumulative distribution functions (c.d.f.s) The stages are numbered so that i > j if stage i is done before stage j (i.e., stage 1 occurs last). 7

The two-stage problem can be stated as: X2 minimize h2 f (X2-u)f2(u)du 0 X + h1 {F2(X2) f (X1-t)fl(t)dt 0 X1 +X2 X1+X2-u + 1 2 X (X1+X2-t-u)f1(t) f2(u)dt du} X2 0 00 + P1 {F2(X2) f (t-X1) fl(t)dt X1 + f f (t+u-X1-X2) f1(t) f2(u)dt du} X2 X +X -u + p2 f (u-X2) f2(u)du (1) X2 subject to Xi> 0, i = 1,2. The six terms represent the expected costs of (i) holding inventory at stage 2, (ii) holding inventory at stage 1 when stage 2 is on time and stage 1 is early, (iii) holding inventory at stage 1 when stage 2 is tardy but stage 1 is completed before the due date, (iv) penalties at stage 1 when stage 2 is on time but stage 2 is tardy, (v) penalties at stage 1 when both stage 2 and stage 1 are tardy, and (vi) penalties at stage 2. 8

OPTIMIZATION It can be shown that the objective function for the two-stage system is positive semi-definite for all probability density functions (p.d.f.s) and positive definite for all p.d.f.s for which the support of Ti has no gaps (i.e., PETi = t] > 0 for all t within the range of Ti). This has been demonstrated in Yano (1985) for systems without rescheduling costs and the proof here is similar. Therefore, first order necessary conditions are sufficient for optimality since the objective function is convex for most realistic leadtime distributions. In Appendix A, first order necessary and sufficient conditions are used to establish that the optimal solution has the following characteristics: (a) F11[p/(h1+p1)] < X < min {F 1[(h2+p1)/(h1+p1)], G121[p1/(h1+p1)]} (2) and (b) F2(X2) = P2/[(h2+P2+P1) - (hl+p1)F1(X1)], and (3) where G12 = F1 * F2 and Xi denotes the optimal value of Xi. One possible solution procedure is quite simple. Select any reasonable search procedure for X1 (e.g., bisection, Fibonacci search), and use equation (3) to find the corresponding X2. Check for satisfaction of one of the first order conditions. If it is satisfied, then we are done. Otherwise, X1 is adjusted in the appropriate direction and the procedure repeats. Since X1 and X2 increase or decrease together in equation (3) and one of the first derivaties of the objective function (i.e., equation (A-1)) is strictly increasing in both X1 and X2, the appropriate direction of adjustment is evident. A more expedient procedure is an adaptation of the generalized reduced gradient approach (discussed in Luenberger, 1973). One would begin with any value of X1 in the range indicated in (2) and solve for X2 using (3). Then, 9

using a first order necessary condition (i.e., equation (A-2)), one solves for X1 given X2. The procedure iterates between equations (3) and (A-2). Because we have permitted the leadtime distributions to be quite general, it is not possible to guarantee convergence of this algorithm. However, many similar approaches do indeed converge even without guarantees of convergence. We present experimental evidence of convergence later in the paper. We turn next to analyses of multi-stage problems. MULTI-STAGE PROBLEMS Analyses of a three-stage problem begin to reveal some general patterns. which extend to N-stage problems. Appendix B contains a formulation of the three stage problem. In Appendix C, first order conditions for the three-stage and N-stage problems are used to demonstrate that a general procedure would involve the following steps: (a) Start with a trial value of X1 satisfying F- [p1/(Pl+h1)] < X1 < mintF1 [(h2+p1+P2)/(h l+P )], G12 [(h3+3+p2+p1 )/(h1+P1 )1,.., Gi..N- Cp/(h1+p1 )]}. (4) (b) Sequentially solve for Xn, n = 2,...,N given the values of X1,.... Xn-1 (c) Use one of the first order conditions (i.e., equation (C-3)) and the values of X2,...,XN to obtain the next value of X1. The procedure repeats steps (b) and (c) until convergence is achieved. EXPERIMENTAL RESULTS There are two objectives of our computational study. The first is to determine whether the algorithm converges to optimal solutions even though convergence is not guaranteed. The second (but more important) objective is to 10

gain some insight into characteristics of optimal planned leadtimes. We used the algorithm to find optimal planned leadtimes for 1600 two-stage problems and over 3300 three-stage problems. The parameter sets are detailed in Tables 1 and 2, respectively. We used Poisson leadtime distributions because of their single parameter characteristic. Using two-parameter distributions would have necessitated larger sets of problems, but probably would have provided little additional insight. We restricted the solutions to integer values since the leadtime distributions under consideration are discrete and leadtimes generally are measured in terms of a multiple of some fixed time period (an hour, shift, or day, etc.). Thus, the solutions may not be optimal, but they represent the minimum cost integer solutions. If more accuracy is required, smaller time units can be used. TABLES 1 AND 2 We normalized h1 to 1.0 and set other cost parameters relative to this value. We used a wide range of rescheduling and tardiness costs, primarily to recognize the possibility of rescheduling costs far exceeding commonly used shortage cost values. Rescheduling often affects more than one product and the many resources required to produce those products. Of the 1600 two-stage problems, 1548 (about 97%) converged in three iterations. The remaining problems oscillated between two adjacent values of X1. Thus, it appears that non-convergence for these problems is an artifact of restricting solutions to integer values, not of the algorithm. We obtained similar results for the three-stage problem, with over 85% converging in three to five iterations and the remainder oscillating between two adjacent values of X1. Of the three-stage problems for which convergence was attained, the vast majority converged in three iterations. We initialized X1 to the integer nearest the average of its upper and lower limits in (4). This gave a value of 11

X1 less than X1 in most instances. With this initial value, convergence in three iterations means that the optimal solution was identified on the second iteration and confirmed on the third despite an arbitrary starting point. Since the two-stage problem has a convex objective function, optimality is guaranteed, since the algorithm simply finds a set of Xi which satisfy the first order conditions. W.e selected a few three-stage problems to confirm that the solutions were optimal. One problem was selected for each of the 27 possible leadtime parameter combinations. Each of these leadtime parameter combinations was paired randomly with one of the 27 Pi/hi combinations in such a way that each pi/hi combination was used only once (random bipartite matchings). We used h2 = 0.5 and h3 = 0.25 for each of the 27 problems. To evaluate the performance of the algorithm, we performed a grid search around the solutions obtained from the algorithm and extended the search far enough to locate a local optimum. Since we have bounds on the optimal value of X1, it would have been possible (in some cases) to enumerate all "reasonable" solutions. However, because of the high Pi/hi ratios, small changes in each decision variable produced large changes in the objective function, so an extensive search was deemed unnecessary. The observed optimal solution had the same value of X1 as determined by the algorithm in 26 of the 27 problems. The optimal values of X2 and X3 were no more than one unit from the values obtained from the algorithm. This may indicate minor difficulties cause by limiting decision variables to integer values or round-off errors in computation, but no apparent fundamental problems with the algorithm itself. In fact, even for those problem for which the procedure did not converge, the optimal solution values were not more than one unit from the ranges of values for X1, X2, and X3 indicated by the two alternate solutions from the algorithm. 12

In the one case where the X1 values differed, the algorithm located a local optimum with cost only 0.25 of 1% greater than the global optimum. If one is concerned with locating the exact optimum, it may be advisable to perform a very limited search in the neighborhood of the solution obtained from the algorithm. On the basis of our experimental results, it appears that the algorithm performs extremely well, both in terms of convergence and in terms of identifying the neighborhood of the optimal solution, even though convexity of the cost function and convergence of the algorithm are not guaranteed. The solutions obtained from the algorithm had some striking characteristics. First, in all two-stage problems (except for those problems on which the algorithm did not converge), the values of Xsatisfied i= max {x I F(x) < (h2+Pl)/(h1+p1)} This would indicate that a single-pass procedure starting with this value of X! could provide optimal solutions. Similar results were observed for the threestage problems. The values of X, were amazingly insensitive to the costs at stages 2 and 3. Similarly, the values of X9 were insensitive to costs at stage 3. It is also evident from equations (C-6) and (C-7) (also from equations (C1) and (C-2)) as well as from the computational results that Fn(Xn) > 0 for n = 2,....,N. Specifically, the first order necessary condition to be satisfied by Xn requires that Fn(Xn) be positive whenever Pn is positive. Therefore, it is impossible for Xn to equal 0 for n=2,...,N. (Relevant technical details appear in Appendix C). Thus, with any positive rescheduling penalty, planned leadtimes are strictly positive and the stages do not "collapse" as they might when p2=.'=PN=O. In other words, unconditional immediate dispatching is not optimal when there are rescheduling penalties at intermediate stages. Instead, each stage "fends for itself" in view of planned leadtime at successor stages, and 13

compensates very little for possible tardiness of its predecessors. Translating these results into implications for safety time policies, we find that the safety time at each stage is affected primarily by its own pi/hi ratio. The rescheduling/tardiness costs at successor stages have only secondary effects, while holding costs at successor stages have only marginal effects in most cases. These results have implications for possible myopic heuristics, but the optimal procedure is fast, taking less than 10 seconds an IBM PC/XT using Advanced BASIC for an average three-stage problem in our parameter set. Hence, in most instances, use of heuristics may not be necessary. SUMMARY AND CONCLUSIONS We have developed solution methodologies for determining planned leadtimes in two- and three-stage systems with rescheduling and tardiness costs and have indicated how the procedures can be applied to N-stage systems. The resulting procedure is a single-pass sequential algorithm in which the planned leadtime for stage i, i=1,...,N is determined in sequence as a (nearly) closed form function of the planned leadtimes at successor stages, and of the various costs. The model underlying the algorithm indicates (and experimental results confirm) that it is not optimal to have unconditional immediate dispatching when rescheduling costs are positive. The planned leadtimes at all stages are positive and are influenced most heavily by the respective pi/hi ratios, secondarily by the penalty costs at successor stages, and only marginally by inventory holding costs at successor stages. It is interesting to note that the presence of rescheduling costs leads to optimal policies which are much closer to those used in practice than those derived from the model with no rescheduling costs. This may suggest that shop floor controllers perceive that there are positive rescheduling costs (even if 14

they are not easily quantified) —or that intermediate due dates result in a similar response. Application of the algorithm somewhat in reverse (using current planned leadtimes to estimate the perceived rescheduling costs) could cause many firms to reduce their planned leadtimes! Although the algorithms can be used for setting planned leadtimes, they are likely to be more useful as managerial tools for quantifying and analyzing tradeoffs among inventory, rescheduling, and tardiness penalties. These issues traditionally have been investigated through simulation. The new method presented here can be used to optimize and to perform sensitivity analyses much more efficiently than can be done by simulation alone. One specific use of the algorithm in this context would be to find planned leadtimes using a variety of leadtime distributions reflecting different levels of shop congestion. These planned leadtimes could be used as a basis for establishing more flexible, loadsensitive, dispatching policies. Much more work needs to be done to incorporate scheduling and queueing considerations into planned leadtime decisions. This paper represents a first step in understanding complex issues related to leadtimes. ACKNOWLEDGEMENT The author is grateful to two anonymous referees for their helpful suggestions on an earlier version of this paper. 15

TABLE 1 Parameters for Two-Stage Problems (h1 = 1.0) Parameter Values Ai (i=1,2) 2,4,6,8,10 h2 0.2,0.4,0.6,0.8 P1 4,36,100,196 P2 4h2,36h2, 100h2,196h2 16

TABLE 2 Parameters for Three-Stage Problem Parameter Values Ai (i=1,2,3) 2,6,10 h2 0.2,0.5,0.8 h3 00.2h3,0.5h3,0.8h3 P1 4,36,100 P2 4h2,36h2,100h2 p3 4hh3,36h3, 100h3 17

APPENDIX A First order necessary and sufficient conditions for the two-stage problem are: X1+X2 (h1+p1) [F2(X2)F1(X1) + f f2(u) F1(X1+X2-u)du] - p1 = 0 (A-1) X2 X1+X2 and (h2+P2+pl)F2(X2) + (h1+p1) I f2(X2)F1(X1+X2-u)du - P1 - P2 = 0 (A-2) X2 Observe that the respective second and third terms of these equations are equivalent. Thus, the remaining terms must also equate. So we have F2(X2) [ (h2+P2+Pl) - (h1+P1)F1(X1) ] = P2 Since we have assumed p2 > 0, both terms on the left hand side of the equation must be positive, or F2(X2) > 0 (A-3) and F1(X1) < (h2+P2+Pl)/(h1+pl) (A-4) Also, given X1, X2 satisfies F2(X2) = P2/[(h2+P2+p1) - (h1+P1)F1(X)] (A-5) Since X2 can be expressed (almost) as a closed from function of X1, solving for both simultaneously only requires essentially a one-dimensional search for X1. We also can take advantage of some of the results from Yano (1985) to limit the search. For the case of p2 = 0 (no rescheduling costs), it was shown that 1 = min{F11[(h2+p1)/(h1+P1)], G121 [/(h+P1)] } 18

where G12(') = F1 * F2. It also was shown that X = G-1 p1/(h1+p)] only when F2(X2) = 0. We have a similar condition here when P2 > 0. If it were possible to set F2(X2) = 0, we would have X = G12-[p/(hl+p)] since if F2(X2) = 0, all the (rescheduling) costs at stage 2 are sunk and the decision at stage 1 is the solution to a standard newsboy problem using the convolution of the two leadtime distributions. Consider setting X1 = G121 p1/(h+p1)]. Clearly F2(X) cannot equal zero from equation (A-3). Now the sum of terms in brackets in equation (A-1) (which equals G12(X1) when X2 = 0) is increasing in both X1 and X2, so if X2 increases from zero (as required by equation (A-3)) then X1 must decrease from G-1 [p1/(p1+hl)]. Thus, in addition to equation (A-4), we also have -1 X < G12 [p1/(h1+p )]. Stated intuitively, one would never provide more protection at stage 1 than would be desirable when X2 = 0. We also know that if stage 2 could be guaranteed to be on time, we would set X= F-1 [p/(h+p )], but since this cannot be guaranteed, this value setX1 -F[Pl 1 represents a lower limit on X1. We now have F1 [p /(h1+p)] < X < min I{F1[(h2+p1)/(h++p1)], G12 [pl/(hl+P )} (A-6) This condition, in turn, ensures that condition (A-4) is satisfied, which then guarantees that F2(X2) > 0 (from equation (A-5)). Observe also that if the left equality were to hold, from equation (A-5) we have F2(X2)=P2/(P2+h2) and the solutions for the two stages would be like solutions to independent newsboy problems. 19

APPENDIX B The three stage problem can be formulated as: x3 minimize h3 f (X3-v)f3(v)dv 0 X2 + h2 [F3(X3) f (X2-u)f2(u)du 0 X2+X3 X2+X3-v + f f (X2+X3-u-v)f2(u)f3(v)du dv] X3 0 X +X3 X1 h [F3(X3)F2(X2) + f f3(vV)2(X2+X3-V) dv] f (X1-t)f1(t)dt X1 +X2 X1 +X2-u + h1 F3(X3) f f (X1+X2-t-u)f (t)f2(u)dt du X2 0 co X1 +X 3+X u-V + h1 If f f (X1+X2+X3-t-u-v) f1(t)f2(u)f3(v)dt du dv X, X2+X3-v 0 X +X + P1 [F2(X2) F3(X3) + f 3 f(v) F2(X2+X3-v) dv] f (t-X1) f1(t)dt X3 X1 + P1 F3(X3) f f (t+u-X1-X2) fl(t) f2(u)dt du X2 X1 +X2-u co00 00 00 + P1f f f (t+u+K-X1-X2-X3) fl(t)f2(u)f3(v)dt du dv X3 X2+X3-v X +X2+X3-u-v 00 + P2 F3(X3) f (u-X2) f2(u)du X2 20

+P2 I X (u+v-X2-X3) f2(u)f3(v)du dv X3 X2+X3-v + p3 f (v3X3) f3(v)dv x3 subject to Xi > O0 V i 21

APPENDIX C Taking first partial derivatives and two of the three pairwise differences for the three-stage problem yields: F2(X2) [(h2+P1+P2) - F1(X1)(h1+p1)] - P2 = (C-1) X1+X2 F3(X3){(h3+P3+P2+Pl) - (hl+p1) f f2(u)Fl(Xl+X2-u)du X2 - (h2+P+P2)F2(X2)} - P3 0(C-2) Y123 (X1, X2, X3) = pl/(hl+P1) (C-3) where Y123 (X1, X2, X3) = probability that the batch is completed on time given the dispatching policy. This is not a true convolution except when X2=X3=0. It is already evident that given a value of X1, we can find X2 using equation (C-1), and then proceed to find X3 given X1 and X2 using equation (C-2). Then we can update X, using equation (C-3) given X2 and X3, and repeat the process. We have not demonstrated convexity of the objective function, nor have we proved convergence of an iterative procedure. It is not possible to obtain simply-stated conditions for convexity and therefore, we do not present the conditions here. (It is not possible to prove convexity of any n-stage objective function by induction, so for each n, this must be demonstrated by brute force). However, most problems involving inventory and shortage cost tradeoffs have a fairly well-behaved objective function. We therefore proceed on the assumption that it is well-behaved, if not convex. As in the two-stage problem, convergence is not guaranteed, but may be expected for most costs and leadtime distributions. It is evident that X1 > F1 [p1/(Pl+hl)] as explained previously for the two-stage problem. From equations (C-1), (C-2), and (C-3), we are able to 22

obtain an upper bound on X1 as we did for the two-stage problem. So we have F1-[P1/(pl+h )] < X1 < min{F 1[(h2+p +p2)/(h +pl)], G121 [(h3+p3+p2+p1 )/(h+pl)], G123 -1[p/(hh+pl)]} (C-4) where G123(') - F1 * F2 * F3. The first term in brackets comes from equation (C-1). The second and third terms result from assuming X2= 0 in equation (C-2) and X2 = X3 = 0 in equation (C-3), respectively. The algorithm is started using X1 equal to the integer nearest the midpoint of the range. Using a similar approach as above for N-stage systems results in a set of first partial derivatives which have the general form: 1...N(X) = Pl/(hl+p1) (C-5) where Y1 N(X) = probability that the batch is completed on time given the dispatching policy, and Fn(Xn) {gn(X,..., n )} - n = 0, n=2,...,N (C-6) where gn(X1 *.*,Xn-_) = n n'1 hn + Pn - (hn-1 + Z Pj) Fn1 (Xn-1) n-1 n-m n-1 n-1 n- n-1. I n-{(hm + j) P [ j <j < Z j =n j > Xj, k<mn (C-7) m=2 n j = j1 Jn-m j=n-m j - j=n-m k We also have: F1-l[P1/(Pl+h1)] < X1 < min{F1-1[(h2+P1+P 2)/(h1+P1)] G12 [(h3+p3+p2+P 1)/(h+p11)],..., G1..N1[P1/(hl+p 1)]} (C-8) 23

Again, starting with a trial value of X1 chosen according to (C-8), we iteratively solve for Xn, n=2,...,N in sequence and then use equation (C-5) to obtain the next value of X1. We have not yet proved that the gn(') functions above are positive, but since Pn > O, n=1,...,N, it would be impossible to satisfy the first order conditions if they were non-positive. The proof can be obtained indirectly, and we provide a sketch of it here. It can be shown that gn(') is monotone decreasing in X1,...,Xn_1. Thus, planned leadtimes satisfying the first order conditions have the characteristic that if X1 is increased, X2,...,XN also increase (from equation (C-6)). Thus, preventing gn from becoming negative is the same as preventing X1 from becoming "too large." The upper limit on X1 in (C-8) essentially prevents this from occurring. This, in turn, guarantees Fn(Xn) > 0 for all n. 24

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. Graves, S.C. (1985), "A Tactial Planning Model for a Job Shop," Sloan School of Management Working Paper 1552-84, Massachusetts Institute of Technology. Karmarkar, U.S., S. Kekre and S. Kekre (1985), "Lotsizing in Multi-Item MultiMachine Job Shops," IIE Transactions 17(3), 290-298. Karmarkar, U.S., S. Kekre, S. Kekre, and S. Freeman (1985), "Lot Sizing and Lead Time Performance in a Manufacturing Cell," Interfaces 15(1), 1-9. Kanet, J. and D.P. Christy (1984), "Manufacturing Systems with Forbidden Early Order Departure," International Journal of Production Research 22(1), 4150. Luenberger, D.G., Introduction to Linear and Non-Linear Programming. Reading, Massachusetts: Add4Wesley Publishing Company, 1973. 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, Virginia Polytechnic 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), "Setting Planned Leadtimes in Serial Production Systems with Tardiness Costs," Technical Report 85-7, Department of Industrial and Operations Engineering, University of Michigan. 25