THE ECONOMIC LOT AND DELIVERY SCHEDULING PROBLEM: THE COMMON CYCLE CASE Juho I-hm Department of Industrial Engineering Seoul National University Seoul, Korea Candace Arai Yano Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 Technical Report 91-15 April 1991 Revised May and November 1991

THE ECONOMIC LOT AND DELIVERY SCHEDULING PROBLEM: THE COMMON CYCLE CASE Abstract We analyze the interface between a supplier and an assembly facility, where direct shipments are made from one to the other. The final manufacturing step at the supplier involves multiple components produced on a single machine or production line. The assembly facility uses these components at a constant rate. The supplier incurs a sequence-independent setup cost and/or setup time each time the production line is changed over from one component to another. On the other hand, setup costs and times for the assembly facility are negligible. We consider two types of delivery costs: a fixed charge for each delivery, and a fixed-charge-per-truck cost. We develop a heuristic procedure to find a "just-in-time" schedule in which one production run of each product and a subsequent delivery of these products to the assembly facility occur in each cycle. The objective is to find the cycle duration that minimizes the average cost per unit time of transportation, inventory at both the supplier and the assembly facility, and setup costs at the supplier. We also develop an error bound for this procedure, and use some of the insights gained from the analysis to explain how delivery schedules can influence the attractiveness of reductions in production setup costs.

THE ECONOMIC LOT AND DELIVERY SCHEDULING PROBLEM: THE COMMON CYCLE CASE 1. INTRODUCTION The importance of coordinating the scheduling of production and outbound deliveries has been highlighted by the recent adoption of "just-in-time" systems in major industry segments, including the automobile industry, which is the motivation for our study. A recent survey of automotive industry suppliers (see Ward's Auto World, July 1990) indicates that a majority of suppliers feel that they are being forced to hold inventory for their customers, which are typically assembly facilities. These results, as well as our own conversations with some suppliers of major components, suggest that suppliers are producing components in batches that are larger than the delivery quantities, and gradually shipping the components to the assembly facilities. On the other hand, a "just-in-time" schedule would have the suppliers producing only what is required for the next shipment. In this paper, we investigate what characteristics such a schedule should have, taking into account system-wide costs. We investigate the linkage between a large assembly facility such as an automotive assembly plant and its immediate suppliers, often referred to as "first tier" suppliers. Because of the magnitude of their impact on total production and transportation costs, we focus on first tier suppliers that are large enough to justify direct shipments between the supplier and the assembly facility. Examples of such suppliers within the automobile industry include engine and transmission plants, bumper fabrication and assembly, and wheel fabrication plants. In this paper, we consider a situation where the supplier is captive and supplies multiple components to only one assembly plant. Such captive suppliers exist in the automobile industry, as well as in other industries. From a technical viewpoint, our reason for considering this situation is that it allows us to investigate the just-in-time 1

production/transportation problem unfettered by the complications of scheduling the production and deliveries of components for multiple customers. Such generalizations are natural extensions of this work and we encourage research in that direction. However, the more complex combinatorial nature of the multiple-customer problem tends to obscure the qualitative insights that are important in making strategic decisions regarding setup-related improvements. Under the aforementioned assumptions, the problem becomes separable by supplier. Because our focus is on the interface between a supplier and the assembly facility, we concern ourselves only with the scheduling of multiple components on one "machine" at the supplier. In the applications that motivated this work, the "machine" typically would be the final assembly line of the supplier. This represents the closest interface with both the transportation system and the assembly facility. Moreover, this stage tends to be the one where most of the production planning activities are focused in practice. Later in the paper, we discuss how our general approach might be extended to the cases of multiple customers with unique components, and multiple machines in parallel. In addition, we focus on situations where the usage rates of the components by the assembly facility is, for practical purposes, constant. In our motivating examples, and in other situations as well, the usage rates of component parts is smoothed considerably by a higher-level production smoothing procedure, or in a less sophisticated fashion, simply to make just-in-time workable. (See Schonberger 1983 for a discussion of the role of production smoothing within a just-in-time context.) Considering a situation with constant demand also allows us to gain insight into major tradeoffs that are less visible in more complicated models. The goal of this paper is to develop a procedure to find a common production and delivery interval that minimizes the average cost per unit time of transportation, inventory at both the supplier and the assembly facility, and setup costs at the supplier. The model also permits positive setup times. In the next section, we provide a formal 2

statement of the problem. The subsequent section contains a formulation. This is followed by the development of an iterative heuristic solution procedure based on properties of the optimal solution. We show that the procedure converges and provide an error bound for it. We report experimental results which indicate that the heuristic performs quite well. Since the initial model assumes a simple fixed-cost transportation cost structure, we extend the model to incorporate a more realistic fixed-charge-per truck transportation cost structure. Finally, we conclude with a summary and a discussion of the implications of this model on the attractiveness of setup cost reductions. 2. PROBLEM STATEMENT We analyze a system with a single supplier which produces multiple components on a single machine or production line. The components are delivered directly to an assembly facility which uses these components at a constant rate. The supplier incurs a sequence-independent setup cost and/or setup time each time the production line is changed over from one component to another. On the other hand, setup costs and times for the assembly facility are assumed to be negligible, which is reflective of many assembly environments. Initially, we assume that there is a fixed charge for each delivery, but relax this assumption later in the paper. Deliveries to the assembly facility occur at equal intervals (duration to be determined). The delivery lead time is assumed to be deterministic, and without loss of generality, equal to zero. (Incorporating in-transit inventory requires a simple modification of the cost parameters.) The supplier produces exactly one batch of each component between deliveries, where the batch sizes are exactly equal to the assembly facility's requirements until the subsequent delivery arrives. From an economic perspective, this restriction is most realistic when the unconstrained natural setup intervals (economic production cycles of the individual components) are similar in magnitude to the natural delivery interval 3

(economic delivery cycle of the assembly facility when considered separately). However, our intent in this paper is to characterize good schedules with such a "just-intime" requirement imposed exogeneously. As we will see later, the analysis of this constrained problem provides a basis for determining what improvements are necessary so that the "just-in-time" constraint is no longer problematic. Since the deliveries are equally spaced in time and the demand rates are constant, each shipment has the same composition. Inventory holding costs are charged on timeweighted average inventory levels, and the inventory holding cost of a component is assumed to be the same at the supplier as it is at the assembly facility. (Once again, relaxation of this assumption is fairly straightforward.) The objective is to minimize the average cost per unit time of setups, inventory, and transportation while ensuring that both demand and the supplier's capacity constraint are satisfied. We must decide the delivery interval and the (rotation) sequence in which to produce the components. Note that without the restriction of equal delivery and setup intervals, the problem involves determining (i) the delivery interval, (ii) which components are produced between consecutive deliveries, and (iii) the exact production schedule between consecutive deliveries —both quantities and sequence of components. We consider more general versions of our problem in sequels (Hahm and Yano 1991 a,b). The results that we obtain in this paper are useful in solving these more general problems. Although a considerable amount of work has been done on multi-stage production systems with known constant demands, little research has been done that considers both the cost of inventory accumulation prior to delivery and the cost of transportation in the determination of jointly optimal production and delivery schedules. One reason why the former has been ignored is that many models assume instantaneous production (e.g., Crowston et al. 1973, Blackburn and Millen 1982, Roundy 1985, Maxwell and Muckstadt 1985). Other papers that do incorporate capacity constraints ignore some or 4

all of the accumulation inventory (e.g., Caie and Maxwell 1981, Billington et al. 1983, Jackson et al. 1988), or treat transportation costs as fixed (Maxwell and Muckstadt 1981). Likewise, there is some research on procurement policies that include transportation costs, either as quantity discounts (e.g., Lee 1986) or fixed charge per shipment (e.g, Lippman 1971 and Lee 1989), but none explicitly considers the impact of the selected delivery schedule on the supplier's inventory levels. We are not aware of any papers that treat all of the issues in our problem. In the interest of brevity, we will review only those models most closely related to ours. The reader is referred to Schussel [1968], Taha and Skeith [1970], Jensen and Kahn [1972], Schwarz and Schrage [1975], Graves and Schwarz [1977], Bigham and Mogg [1979], Szendrovits [1981], Williams [1982], Blackburn and Millen [1982], and Moily [1986], among others, for a variety of results on continuoustime, multi-stage lot-sizing models. Our problem might be viewed as an extension of the "product cycling" problem first posed by Hanssmann (1962) in which several items, each with constant demand rates, are produced on one machine. Each item is produced once in each cycle and the cycle is repeated. Setup times and costs may be incurred in changeovers between items. The objective is to minimize average setup and inventory costs per unit time. Hanssmann shows that a closed form solution exists for this problem. Our problem differs from Hanssmann's in two ways. First, demand occurs at a location other than where the components are produced. Thus, inventory of the components must be accumulated prior to each delivery. Second, because of this inventory accumulation between deliveries, the sequence in which components are produced affects the solution, even when setup times and costs are sequence-independent. One might argue that if production costs per unit time are similar across products, the production sequence may not matter in practice, since the rate at which value is being added is relatively constant. The key issue, however, is that there is inventory accumulation at the supplier between deliveries, and the cost of holding these 5

inventories may be as substantial as the cost of holding inventories at the assembly facility. The magnitude of these inventories is influenced by the delivery frequency, and therefore should be included in this decision. A more distantly related body of research involves the joint replenishment problem in which there is a (joint) setup cost per procurement (or a joint setup cost per setup for a product family) plus an individual setup cost per item procured (or produced). The objective is to minimize the total setup and inventory cost per unit time. See the references in Jackson et al. (1985) for related literature. Although there is some similarity between the cost structure of this problem and that in ours, we have the additional costs associated with inventory accumulating prior to shipment, and the concomitant problem of sequencing between shipments. We now turn a review of articles that explicity consider both transportation and inventory costs in a continuous-time setting. Burns et al. (1985) develop a single-item model with the objective of minimizing transportation and inventory costs per unit time. Production-related costs are not included. The transportation cost consists of a fixed charge per truck movement. It is assumed that production is not synchronized with delivery, and the cost of inventory accumulating prior to delivery is estimated accordingly. The optimal delivery quantity is obtained by EOQ-type analysis. Benjamin (1989) investigates a single-item version of our problem, in which multiple deliveries may be made out of one production batch. He excludes from his objective function the cost of inventory accumulation prior to delivery and the additional inventories that would be required to avoid shortages when the production interval (or batch) is not an integer multiple of the delivery interval (batch). These two implicit assumptions lead Benjamin to the conclusion that the problem can be solved optimally by independent EOQ-type formulas for the production and delivery batches. Unfortunately, the independent solutions generally will not have the integer multiple property that is implicit in his formulation. 6

This difficulty is corrected by Hahm and Yano (1991a) who show that for the single-item problem, the optimal solution has the property that the production interval is an integer multiple of the delivery interval. They also provide a procedure to find the optimal solution, and derive conditions on setup costs and setup times for which a "justin-time" solution (production interval equal to delivery interval) is optimal. Blumenfeld et al. (1991) study a problem in which the supplier uses a single machine to produce several components, each of which is shipped to a unique destination. Setup times are not incorporated. Their model allows each component to be produced more than once in each production cycle. Unlike Benjamin's formulation, it does include accumulation inventories that accrue when production runs are equally spaced in time, and when production batch sizes are integer multiples of the respective delivery batches. However, it does not include accumulation inventories that must be held if either of these conditions is not satisfied. Consequently, when their results are specialized to the problem treated by Benjamin, they arrive at similar conclusions. They suggest rounding the ratio of the production batch to the delivery batch to obtain an integer multiple, but do not indicate how the rounding should be accomplished. For the case of N components with identical cost and demand characteristics, they present results for the special case in which the machine is 100% utilized. Unfortunately, because of this assumption, the results do not specialize to the case of N = 1. General results for the case of N components are not presented. Our model and results differs from earlier research in several ways. First, unlike most of the pure production lot sizing literature, we explicitly model the finite production rate at the supplier, and thereby also capture the impact of inventory that must be accumulated prior to each delivery. Second, we incorporate transportation costs for the movement of goods between the two facilities. Finally, we allow multiple components to be shipped to a single customer and deal with the related sequencing decisions. 7

3. FORMULATION It is useful to point out that in our problem, it is never beneficial to make multiple production runs of a given product between deliveries. (The proof is straightforward and therefore omitted.) Thus, under the "just-in-time" assumption, we need not make decisions about the number of production runs per delivery interval. Notation J: number of components. Dj: demand for component j per unit time. Sj: setup cost for componentj. pj: production time per unit of componentj. T: setup interval (time between setups); also equal to the delivery interval (time between deliveries). hj: inventory holding cost per unit of component j per unit time. Sj: setup time for componentj. We first develop the capacity constraint. During the delivery interval (T), components necessary for the next delivery are produced. The delivery quantity of component j is DjT, so the total setup and production time for component j is sj + pjDjT. Therefore, the time needed to produce all components is X(sj + pjDjT), which must be j less than T. Therefore, we must have J (sj + pjDjT) T, j=1 which is equivalent to T 2. T > ~~ 8

Inventory Holding Costs Inventory holding costs are incurred at both the supplier and the assembly facility. TD h The average inventory of component j at the assembly facility is 2, just as it is in the economic order quantity model. On the other hand, the average inventory of component j at the supplier depends upon the accumulation during the production time of component j itself and the amount of time the inventory must wait during production of other components produced after j but prior to delivery. For example, production sequences (1) 3-2-1 and (2) 1-2-3 in Figure 1 result in different inventory levels for the supplier. setup time for each component component 1 component 2 component 3 Let [i] be the index of the component produced in the i-th position in the sequence. Then the average inventory cost per unit time at the supplier is as follows: J 1 J+ l ~[i]h[il 2 TD[i][i] +.(_+DT [j]+ sU)] (1) 1=1 j=2i+ The first term in the outer summation is the inventory cost per unit time incurred during production of [i], while the second term reflects the cost per unit time of holding [i] until delivery takes place. The above expression can be rewritten as: 9

J J+1 J 1 |tih[i]..(TjIpW + sy) | + T D2pihi i=l J=t+l i=l - J 1 =Zl(q) + Z2 (q).T + T Di2pihi i=1 l where D[J+l] = h[J+l] = P[J+1] = 0, qe Q (Q is the set of all possible production sequences), J J+1 Z1(q)= Li]h~i] XsIl i=1 j=i+l J J+1 and Z2 (q)= D[i]h[i] iJi p[j] i=1 j=i+1 (2) Formulation (P1) The objective where Minimize + q T J A Minimize - + 1=TD hj-+ Zl(q) + Z2 (q).T +-J Dfpjh + j i + 2j JJ *r Pjh T subject to T > r Isj where = 1 -function in (M1) can be expressed in another form: JS 1 J TJ A XT + -JTDjhj + Zl(q) +Z2 (q).T + 2 Dpjhj + = +aT + Zl(q) + Z2 (q).T + PT + J S= Xsj, i=1 1 J a= Djhj (1-piDi), 2.= (3) 10

J and P= Dfpjhj j=1 Note that aT is the standard expression for the average inventory in the economic production quantity model, and Zl(q) + Z2 (q).T + fT is the cost of inventory that is induced by the delivery schedule (because inventory must accumulate at the supplier prior to each shipment). We can reexpress Zl(q) + Z2 (q).T + PT as shown below. Z,(q) + Z2 (q).T + PT = i D[i]h[i] TD[iP[i] + X(TDUjp[j+ s ]) I = ti]h]e[i] (4) where e[i] = TD[i]p[i] + X(TDIp]%+ s&']), which is the "earliness" of the component j=i+l produced in the i-th position in the sequence, and earliness is defined as the time between the start of production (after setup) of a component and the time of delivery. 4. HEURISTIC SOLUTION PROCEDURE We first consider the problem of finding the best production sequence for a given T. Since the second term in eq. (3) is constant for fixed T, the best sequence is that which minimizes X {ti]hi] -(TDjpU]]+ sj) }.;-1 7=4+1 This value is minimized by arranging components in non-increasing order of hD1 (Tpj Dj+ sj), that is, i precedes j if h TpiDi+ si) >2 jTpj Dj+ sj). (See Appendix hjDj hiDi hjDj 1 for a proof.) Thus, roughly speaking, components with long processing times and low holding costs are produced early in the sequence while components with short processing 11

times and high holding costs are produced late in the sequence. This delays the accumulation of "expensive" inventory until close to the delivery time. (Observe that if the setup time is negligible compared to the production time, the best sequence is generally determined by the values of, which are independent of T.) Therefore, for hi any value of T, the best sequence is uniquely determined. Note that our problem is a variant of a single-machine weighted earliness problem in which there are positive setup times and earliness costs are accumulated on a unit-by unit basis. Thus, once appropriate transformations are made, our results are similar to those for the singlemachine weighted flow time problem (see Baker 1974). Note that Zl(q) and Z2 (q) are functions only of the sequence. As a result, if the sequence is given, the objective function is convex in T. Moreover, the best sequence can be found by the procedure discussed above. This leads us to the following heuristic algorithm which iterates between selecting the sequence and selecting T. Algorithm Al Step 1. (Initialization) Set n=0. Pi Sequence the components in non-increasing order of P. Let this sequence be q(O). Calculate Z2 (q(O)). Step 2. Set n = n+l. Let Tn) = max { r, + z(q(1 }(5) a + P + Z2(q(n-')) The second term in braces is the optimal unconstrained value of T (which minimizes (3)) for sequence n-1. 12

Step 3. Determine a new sequence by sorting all components in non-increasing order of jjT<1)p Dj+ sj). Let this sequence be q(n) hjDj j If q() is same as q(-l), stop. If Tn) =, stop. Otherwise, calculate the value of Z2 (q(nf ) for the new sequence; go to Step 2. Let us examine how Algorithm Al works. Let S A TC(T,q) = ST +aT + Zl(q) + Z2 (q).T + PT + -. By construction, algorithm Al has the property that TC(T(n),q(n)) > TC(T(n+l),q(n) ) > TC(TC(n+),q(n+) ) because T(n+l) is the optimal value of T given the sequence q(n), and q(f+l) is the best sequence given T(n+l). Algorithm Al is guaranteed to converge by Theorem 1 below. Theorem 1: Suppose algorithm Al terminates at the N-th iteration where N>2. Then, a. T('n+ < T<n) for all n such that 1 < n < N. b. TC(T(^), q(n)) < TC(T,q) for all T, q and n such that T>T("), qe Q, 1 < n < N. Proof. See Appendix 2. If 7Tn+1) = T(n), q(n+l) also must be the same as q(n) and Algorithm Al stops. Therefore, by Theorem 1, the same T will never repeat. Furthermore, the number of sequences is finite and the total cost is strictly decreasing at every iteration. Consequently, finite 13

convergence of Algorithm Al is guaranteed. The behavior of the algorithm is illustrated in Figure 2. TC(T,q) T1 T3 T2 T4 T5 qj: -th production sequence. Tj: optimal production interval under qj. Figure 2. Behavior of Algorithm A1 in Example 1. In Figure 2, the initial sequence is q5. Given sequence q5, the optimal production interval is Ts, and the cost is TC(T5, q5 ). See i in the figure. Given T5, optimal sequence is q4 with a cost of TC(T5,q4 ). See. The procedure continues and point W is the final solution found by Algorithm Al. In this example, Algorithm Al finds the global optimum. However, this does not always happen. For example, in Figure 3, Algorithm Al does not find a global optimum but it finds a local minimum. 14

T3 Figure 3. Behavior of Algorithm A1 in Example 2. As discussed above, Algorithm Al finds a local minimum. To evaluate the quality of the heuristic solutions, we developed a procedure to calculate an error bound. This procedure is described in Lemmas 1 and 2. Lemma 1. Suppose q(O) in Algorithm Al is the sequence in which the components are sorted in nonincreasing order of h-, and Algorithm Al (without the termination rule, "if T() = r, hij then stop," in Step 3) terminates at the N-th iteration where N>2. Then, a. T(n+l) > T() for all n such that 1 < n <N. b. TC(T(n), q(n) ) < TC(T, q) for all T, q and n such that T <T(n), q Q, 1 < n < N. Proof. See Appendix 3. Lemma 2: Error Bound on the solution from Algorithm A1. Let the values of T found by algorithm Al and Lemma 1 be T' and T", respectively. Also let q' and q" be the sequences found by algorithm A1 and Lemma 1, respectively. 15

Let T* be the optimal value of T and q* be the optimal sequence. Then, a. T" <T' b. If T"=T', T' is an optimal solution. c. If T'~T" and if an optimal solution exists at T* such that T"<T*<T', then TC(T',')- TC(T*,q*) (Zl(q')- Zl(q ))a+ + Z2(q) - a +Z2(q') cTC+ + Z2(q") + (+ 3 + + Z2(q') Proof. See Appendix 4. Remark. Lemma 2c can be shown to be true also for TC(T",q") - TC(T*,q*) if T" > >. 5. EXPERIMENTAL RESULTS We tested algorithm Al on a set of 72 problems which was designed to evaluate the impact of various problem parameters on the performance of the algorithm. Three major factors were considered. The first factor is the tightness of the capacity constraint. We consider two levels of tightness: pjDj drawn from a uniform J distribution on [0.3,0.5] (not tight) and from [0.7,0.9] (tight). The second factor is the spread of the natural production cycles among the components. We determined constrained natural productionand delivery cycles by solving the following problem: J Sj J A Minimize X ' + Xaf'Tj + PR + j=i Ti j=1 J S. J subject to 2 -- < 1-pjDj (6) =1 Tj R fj1 Tj > R forj=l toJ (7) 16

where Tj is the production cycle of component j, and R is the delivery cycle. We impose the constraint T > R here because our representation of inventory in the objective function is not accurate for the case of T <R. Moreover, our own discussions with component suppliers do not suggest that suppliers are being forced to produce undesirably large batches because shipments are too infrequent; indeed, the converse appears to be true. Let Tj and R be the optimal values of Tj and R for this problem, which we refer to as the natural production cycle and delivery cycle, respectively. These values can be expressed as: + S A + Sj Tj =j+- A, 1]<j J (8) and R'= A (9) p1 where AX is chosen so that constraint (6) is satisfied as an equality, or Ao = 0 if the constraint is not binding; and for each j, Aj is chosen so that constraint (7) is satisfied as an equality or Aj = 0 if it is not binding. We measure the spread of the natural production cycles using the ratio of the maximum to the minimum Tj. This ratio is generated from a uniform distribution on [1.5,2.5] for half of the problems (low variance) and on [4,8] for the other half (high variance). The third factor is the magnitude of the natural delivery cycle relative to the natural production cycles. We say that the natural delivery cycle is relatively small if it is similar to or less than the minimum Tj, medium if it is between the minimum Tj and maximum Tj, and large if it is similar to or greater than the maximum Tj. In the first case, we might expect T* to be constrained by the minimum Tj; in the second case, we might expect T* to be close to the unconstrained optimal R; and in the third case, economic tradeoffs may dictate the solution. 17

The two levels of capacity tightness, two levels of natural cycle spreads, and three levels of natural delivery cycles give twelve (2x2x3) different combinations of levels. For each combination, we generated a set of six problems: two problems with three components, another two with six components, and two with nine components. For all 72 problems, algorithm Al found an optimal solution. Earlier, we gave a graphical representation of a case in which Algorithm Al would not find an optimal solution, but despite numerous attempts, we were unable to generate problem data for which algorithm Al would not produce an optimal solution. 6. EXTENSION TO A FIXED-CHARGE-PER-TRUCK TRANSPORTATION COST In this section, we generalize the results to incorporate a fixed-charge-per-truck transportation cost. Such transportation costs arise when good are being shipped at fulltruckload rates, or under a contract with point-to-point charages. The truck capacity is defined as the maximum quantity a truck can deliver at a time. Because we assume that the composition of each shipment is the same, there is a delivery interval corresponding to the truck capacity and we define p to be this interval. Therefore, the T delivery cost for each delivery is A( p 1) where F x 1 is the smallest integer greater than p or equal to x. The problem becomes: (P2) Minimize + + ( + + Z2 (q))T + (AT r 1) + Zl(q) subject to T > T For simplicity, let a + /3 + Z2 (q). Also let TC(T) - T + T + (A.F P 1)+ ZI(q) S A and TC'(T) + qT + - + Zl(q). P 18

Then TC(T) > TC'(T) ~since1 rTi 1 since - I - I> [ -. Tp p TC'(T) achieves its minimum when T= =I. Theorem 2. Let T* be an optimal solution of (P2). Then, T1 < T* < T2 where T' =max( r, ), T1 = max(, L -p }, p T' T2 =r lp p and L x J is the largest integer less than or equal to x. Proof. See Appendix 5. A graphical representation of Theorem 2 is illustrated in Figure 4. T1 is the T' minimum productioninterval (r)or L-J times the delivery interval corresponding to p the truck capacity, whichever is larger. T2 is r[ 1 times the delivery interval corresponding to the truck capacity. Therefore, we must consider, at most, the values between durations corresponding to two consecutive integer multiples of the truck capacity. Then the value of T* is easily calculated because TC(T) is a convex function of T. 19

\. ---- TC(T) \ * -- - TC.(T) T I SI I 1 TiV - T2 Figure 4. Total costs of extended model. Thus far, we have discussed a procedure to find the best value of T when the production sequence is given. By replacing Step 2 of Algorithm Al with the above solution procedure, we have an algorithm for this extension. 7. CONCLUSIONS We have developed an iterative heuristic procedure to determine the frequency of deliveries from a supplier to an assembly facility when the supplier produces several components on a single production line. The goal is to minimize the average cost per unit time of setup costs at the supplier, inventory costs at the supplier and the assembly facility, and transportation between the two locations. The model also allows positive production setup costs. An easy-to-determine lower bound is also developed. The heuristic is shown to perform extremely well in computational experiments. We mentioned earlier that in practice, the sequence of production may not have a significant influence on the cost of accumulating inventory prior to delivery. This may be one reason why the heuristic performs so well. If we believe that the production sequence is not critical, then it may be adequate to use a "good" production sequence (e.g., our initial sequence in which components are arranged in non-increasing order 20

of their processing time to holding cost ratios). With this simplification, it is relatively easy to see the influence of accumulation inventory in the specification of the delivery interval. If the assembly facility were to decide the delivery interval independently, we would have: A R We might expect the supplier to adopt a production interval close to its independently selected production interval S a+ Z 2(q(~)) possibly rounding to the nearest multiple of the delivery interval. On the other hand, in the simple, integrated heuristic solution, we would have T=~ A+S T = A + S a + p + Z 2(q(~)) which might be viewed as a compromise between the two. A variety of different tradeoff analyses can be performed quickly with these formulas. We discuss one briefly. Suppose the supplier is considering an improvement that would reduce setup costs. (There is an analogous argument for setup times.) With the decoupled decisions, a reduction in the setup cost will not affect the delivery interval, so there will be no reduction in the supplier's inventories (although total setup costs will decrease). Consequently, there is limited incentive for the supplier to reduce setup costs. With the integrated approach, a setup cost reduction will lead to a smaller value of T than before the reduction. The impact of this change on the total cost (inventory and transportation) at the assembly facility depends on the parameters. (Inventory costs will decrease and transportation costs will increase.) The supplier can now reap the benefits 21

of a reduction in inventory as well as a reduction in setup costs, and therefore has greater incentive to make the improvements. This "quick and dirty" analysis may partly explain why Japanese manufacturers have made a greater effort to reduce setup costs (and times). There, travel distances are shorter and hence transportation costs are generally smaller and deliveries are more frequent. In these circumstances, any reductions in setup costs up to the point where each component can be produced once in each delivery interval result in inventory cost savings to the supplier. Many U.S. manufacturers still use weekly shipments, creating significant disincentives for setup cost reduction. Models such as the one described in this paper can be useful in understanding these issues more fully. Further research is needed to incorporate more complex manufacturing environments. The approach developed here can be applied to problems with multiple customers with unique components. Within each cycle, each customer would have one delivery, and the same rules would apply to sequencing that customer's components prior to the delivery. It might also be possible to incorporate a few common components if each were produced once during the cycle. A solution procedure would entail selecting the customer to whom to "assign" the component, and sequencing the customer deliveries, since the delivery sequence would have an impact on the inventory levels of the common component. The procedure could also be generalized to consider a supplier that has several subassembly lines in parallel. If components are already assigned to production lines, production sequences on each line and the common production and delivery interval for all of the lines would need to be decided. However, if some of the components can be produced on more than one line, the best assignment of components to production lines might depend on the delivery interval. For example, cost savings may be achieved by assigning components so that their natural production cycles are similar to one another, 22

or so that their collective natural production cycle is close to the natural delivery interval. Acknowledgement This work has been supported in part by a gift to the University of Michigan from Ford Motor Company. 23

REFERENCES BAKER, K. R., 1974, Introduction to Sequencing and Scheduling, John Wiley and Sons, New York, New York, pp. 20-22. BENJAMIN, J., 1989, "An Analysis of Inventory and Transportation Costs in a Constrained Network," Transportation Science, Vol. 23, 177-183. BIGHAM, P.E. AND MOGG, J.M., 1979, "Converging Branch Multi-Stage Production Schedules with Finite Production Rates and Start-up Delays," J. of Opl. Res. Soc., Vol. 30, 737-745. BILLINGTON, P., MCCLAIN, J.O., AND THOMAS, L.J., 1983, "Mathematical Programming Approaches to Capacity-Constrained MRP Systems: Review, Formulation and Problem Reduction," Management Science, Vol. 29, 1126-1141. BLUMENFELD, D.E., BURNS, L.D. AND DAGANZO, C.F., 1991, "Synchronizing Production and Transportation Schedules," Transportation Research, Vol. 25B, 23-37. BURNS, L.D., HALL, R.W., BLUMENFELD, D.E., AND DAGANZO, C.F., 1985, "Distribution Strategies that Minimize Transportation and Inventory Costs," Operations Research, Vol. 33, 469-490. BLACKBURN, J. D. AND MILLEN, R. A., 1982, "Improved Heuristics for Multi-Stage Requirements Planning Systems," Management Science, Vol. 28, 44-56. CAIE, J.P. AND MAXWELL, W.L., "Hierarchical Machine Load Planning," in Multilevel Production/Inventory Control Systems: Theory and Practice, L.B. Schwarz (Ed.), North Holland, New York, 1981. CROWSTON, W. B., WAGNER, H. M. AND WILLIAMS, J.F., 1973, "Economic Lot Size Determination in Multi-Stage Assembly Systems," Management Science, Vol. 19, 517-527. GRAVES, S.C. AND SCHWARZ, L.B., 1977, "Single Cycle Continuous Review Policies for Arborescent Production/Inventory Systems," Management Science, Vol. 23, 529 -540. HAHM, J. AND YANO, C.A., 1991a, "Economic Lot and Delivery Scheduling Problem: The Nested Schedule Case," Working Paper, Department of Industrial & Operations Engineering, University of Michigan, Ann Arbor, MI. HAHM, J. AND YANO, C.A., 1991b, "Economic Lot and Delivery Scheduling Problem: Powers of Two Policies," Working Paper, Department of Industrial & Operations Engineering, University of Michigan, Ann Arbor, MI. HAHM, J. AND YANO, C.A., 1991c, "The Economic Lot and Delivery Scheduling Problem: The Single Item Case," Journal of Manufacturing and Operations Management (to appear). HANSSMANN, F., 1962, Operations Research in Production and Inventory Control, John Wiley & Sons, New York. 158-160. 24

JACKSON, P.L., MAXWELL, W., AND MUCKSTADT, J.A., 1985, "The Joint Replenishment Problem with a Powers-of-Two Restriction," IIE Transactions, Vol. 17, No. 1, 25-32. JACKSON, P.L., MAXWELL, W., AND MUCKSTADT, J.A, 1988, "Determining Optimal Reorder Intervals in Capacitated Production-Distribution Systems," Management Science, Vol. 34, No. 8, 938-958. JENSEN P. A. AND KHAN, H. A., 1972, "Scheduling in a Multistage Production System with Set-up and Inventory Costs," AIIE Transactions, Vol. 4, 126-133. LEE, C.Y., 1986, "The Economic Order Quantity for Freight Discounts," IIE Transactions, Vol. 18, 318-320. LEE, C.Y., 1989, "A Solution to the Multiple Setup Problem with Dynamic Demand," lIE Transactions, Vol. 21, 266-270. LIPPMAN, S.A., 1971, "Economic Order Quantities and Multiple Setup Costs," Management Science, Vol. 18, 39-47. MAXWELL, W. AND MUCKSTADT, J.A. 1981, "Coordination of Production Schedules and Shipping Schedules, " in Multilevel Production/Inventory Control Systems: Theory and Practice, L.B. Schwarz (Ed.), North Holland, New York, 1981. MAXWELL, W. AND MUCKSTADT, J.A., 1985, "Establishing Consistent and Realistic Reorder Intervals in Production-Distribution Systems," Operations Research, Vol. 33, No. 6, 1316-1341. MOILY, J.P., 1986, "Optimal and Heuristic Procedures for Component Lot-Splitting in Multi-Stage Manufacturing Systems," Management Science, Vol. 32, 113-125. ROUNDY, R., "A 98%-Effective Lot-Sizing Rule for a Multi-Product, Multi-Stage Production/Inventory System," Math. of OR, Vol. 11, No. 4, 699-727. SCHONBERGER, R., 1983, Japanese Manufacturing Techniques, The Free Press, New York, New York. SCHUSSEL, G., 1968, "Job-Shop Lot Release Sizes," Management Science, Vol. 14, B449-B472. SCHWARZ, L.G. AND SCHRAGE, L., 1975, "Optimal and System Myopic Policies for Multi-Echelon Production/Inventory Assembly Systems," Management Science, Vol. 21, 1285-1294. SZENDROVITS, A., 1981, "Comments on the Optimality in 'Optimal and System Myopic Policies for Multi-Echelon Production/Inventory Assembly Systems'," Management Science, Vol. 27, 1081-1087. TAHA, H. A. AND SKEITH R.W., 1970, "The Economic Lot Sizes in Multistage Production Systems," IIE Transactions, Vol. 2, 157-162. WILLIAMS, J. F., 1982, "On the Optimality of Integer Lot Size Ratios in 'Economic Lot Size Determination in Multi-Stage Systems,"' Management Science, Vol.28, 1341 -1349. "1990 Supplier Survey," Ward's Auto World, Vol. 26, No. 7, 37-39, July 1990. 25

APPENDIX 1 BEST PRODUCTION SEQUENCE Let q* be the sequence in which the components are sorted in non-increasing order of 4(TpjDj + sj). Also let V(q) = j {D[]h[j].S(TDJpU]+ s]). J=1 J=i+l Then, V(q*) < V(q) for all qe Q. Proof: Suppose there is an optimal sequence q' with j preceding i when hj(TpjDj + sj) < (TpiDi + si). Let us interchange j and i and let the resulting sequence be q" Then Then V(q') - V(q") = hjDjITpiDi + si) - hiDi(TpjDj + sj).1.1 ~ ~ +s = hjDjhiDi ( h DTpiDi + si) - jjTpjDj + sj) ) > O. Therefore, V(q') > V(q") and q" must be also optimal. Repeating this argument will result in the conclusion that the sequence in which the components are sorted in nonincreasing order of hj(TpjDj + sj) is an optimal sequence. hjDj 26

APPENDIX 2 PROOF OF THEOREM 1 Theorem 1: Suppose algorithm Al terminates at the N-th iteration where N>2. Then, a. T(n+1 < T(" for all n such that 1 n < N. b. TC(T(n), q() ) < TC(T, q) for all T, q and n such that T > T(n, qe Q, 1<n <N. Proof: We will prove Theorem 1 by induction. a. T(+l) < T( for all n such that 1 < n < N. In algorithm Al, T() = A + +Z(q(iS)) Case 1: n=l. We want to show T<2) < T). =T()-= +/3+ ZA(q ). The sequence q(O) satisfies Z2(q( ) < Z2(q) for all q e Q a+ p + Z2(q( )) (the proof of this is very similar to that of Best Production Sequence and is omitted here). Therefore T'(1 is the largest among the T(i values for i>l. As a result, T(2) < T(M) and the equality holds only when q(l) = q(). This implies N=1 and contradicts the assumption that N > 2. Therefore, T(2) < T1. 27

Case 2: 2 < n < N. We will show that, if T(n) < T(n-1), then T(n+l) < T(n) contradiction. By definition,. We will show this by T+n+I A +a= S A + S a + - i + Z2(q~()) and + + Z2q-1) Suppose T(n+1) > T(n), i.e., Z2(q(n)) < Z2(q(n-)). The equality holds only when q(n) = q(n-l), which implies that N=n, thereby contradicting the assumption. Therefore Z2(qn) ) < Z(q(n-l) ) By the construction of algorithm Al, at T = Tcn-1), Z2(q(n-1)).T(-l) + Zl(q(n-l)) < Z2(q(n) )).Tn-) + Z(q(n)) which is equivalent to Zl(q(n)) - Zl(q(n-1 ) Z2(q(n-) )- Z2(q(n)) because Z2(q(n) < Z2(q(n-). Similarly, n)> Zl(q(n) ) - Zl(q(n-l)) T(n) > Z2(q(n-l) ) - Z2(q(n) ) As a result, T(n) > T(n-1). This result contradict the hypothesis that T(n) < T(n-1). As a result, T(n+l) > T(n) cannot be true and we must haveTX"+l) < T). By Cases 1 and 2, T(n+l) < T(n) for all 1 ~ n <N. 28

b. TC(T(), q(n) ) < TC(T, q) for all T, q and n such that T>T"), qe Q, 1 < n < N. Case 1: n=l. We want to show TC(T(1), q(l) ) < TC(T, q) for all T and q such that T>T(1), qe Q. For all given q E Q, TC(T, q) is a convex function of T. Also from the proof of part (a), for all q, the optimal value of T is less than or equal to T(V). Therefore TC(T, q) is an increasing function of T for T > T(1) and all qe Q. Moreover, TC(T(1), q(1) = min ( TC(T1), q) ). qeQ As a result, TC(T(1, q(1) ) < TC(T, q) for all T and q such that T > T(), qe Q. Case 2: 2 < n <N. We will show that, if TC(T(n-), q(n-l) ) < TC(T, q) for all T, q such that T > T(n-), qe Q, then TC(T(n), q(n) ) < TC(T, q) for all T and q such that T > T(, qe Q. We will show this by contradiction. Suppose there exist some T' and q' such that TC(T', q') < TC(T(T), q(n) ) and T' > T(, q'e Q where T' is the optimal value of T for the sequence q'. ( If T' is not the optimal value of T for the given sequence q', the proof is trivial and is omitted here). Then T' must be less than or equal to T(n-l) by hypothesis. Also, since T' > T(), we have Z2(q') < Z2(q(n-1)). At T= T(n-1, by construction, TC(T(-1), q(n-)) < TC(T(n-), q'), i.e., Z2(q(n'- ).T(n-l) + Zl(q('n-1) < Z2(q).T(n-1) + Zl(q'). (A2-1) 29

Suppose that at T = T(n), TC(T(), q(n-1)) < TC(Tn), q'), i.e., Z2(q(n-1) ).T(") + Zl(q(n-1)) ) Z2(q').T(r) + Zl(q'). (A2-2) By (A2-1) and (A2-2), for all T such that T(n) < T < T(c-1), Z2(q(nl) ).T + Zl(q(n-1) ) < Z2(q').T + Zl(q') which means TC(T, q(n-l) ) < TC(T, q') for all T such that T() <- T < T(n-1) and this contradicts the assumption that TC(T', q') < TC(T(<), q(n) ). Therefore, at T = T-n, TC(T(n), q(n-l)) > TC(T(n) q'), i.e., Z2(q(n-) ).T(n) + Zl(q(n-l) ) > Z2(q')-T(n) + Zl(q'). (A2-3) Then, by (A2-1) and (A2-3), Z2(q') > Z2(q(n-)) which indicates that Tn) > T' and this contradicts the assumption that T'>T(7). Consequently, TC(T(n), q(n) ) < TC(T, q) for all T and q such that T>T(n), qe Q. By Cases 1 and 2, TC(T(Qn, q(n) ) < TC(T, q) for all T, q and n such that T>T(), qe Q, 1 < n < N. 30

APPENDIX 3 PROOF OF LEMMA 1 Suppose q(O) is the sequence in which the components are sorted in non-increasing order of i, and Algorithm Al (without the termination rule, "if T() = r, then stop," in hi, Step 3) terminates at the N-th iteration where N>2. Then, a. T7n+l > Tn) for all n such that 1 < n <N. b. TC(T(n), q(n) ) < TC(T, q) for all T, q and n such that T>T(, qe Q, 1 < n < N. Proof If q(~) is the sequence in which the components are sorted in non-increasing order of &, for all q, the optimal value of T is greater than or equal to T). If Algorithm Al hj' starts with the new qcO), the algorithm will search the points in the opposite direction as it would have searched with the original q(O). The remainder of the proof is similar that of Theorem 3 and is omitted here. 31

APPENDIX 4 PROOF OF LEMMA 2 Lemma 2: Let the values of T found by algorithm Al and Lemma 1 be T' and T", respectively. Let q' and q" be the sequences found by algorithm Al and Lemma 1, respectively. Let T* be the optimal value of T, and q* be the optimal sequence. Then a. T" < T'. b. If T'=T", T' is an optimal solution for Model 1. c. If T'~T" and if an optimal solution exists at T* such that T"<T*<T', then -a+ + Z2(q") + a + + Z2(q') Proof a. and b. The proofs are trivial and are omitted here. c. We know that T" > T and thus, both T* and T' must be greater than T. From (5), A+S A+S a + + Z2(q*) andT'= a + 3 + Z2(q') We have that TC(T*, q*) = 2 (A + S)(a + P + Z2(q*)) + Zl(q*) (A4-1) 32

and TC(T', q') = 2 (A + S)(a + P + Z2(q')) + Z(q'). (A4-2) From the fact that T" < T* < T', we know that Z2(q') < Z2(q*) < Z2(q"). (A4-3) Furthermore, Z1(q') > Zl(q*) > Zl(q"). (A4-4) (Suppose Zl(q') < Zl(q*). Then TC(T', q') <TC(T*, q*) because Z2(q') < Z2(q*). This contradicts the fact that T* and q* are optimal solutions. For a similar reason, Zi(q*) > Zl(q").) Let t be the value of T which satisfies TC(t, q*) = TC(t, q'). Then there exists a t such that t Zl(q') - Zl(q*) Z2(q*) - Z2(q') by (A4-3) and (A4-4). Also, it can be easily verified that t < T', i.e., Zl(q') - Zl(q*) < A+S Z2(q*) - Z2(q') a + + Z2(q') Since Z2(q') < Z2(q*), the above inequality can be rearranged as follows. (Z2(q*) - Z2(q'))A + S > (Z(q') - Z (q*)) a + + Z2(q'). (A4-5) Moreover, (Z2(q*) - Z2(q'))A + S = ((a + p + Z2(q*)) - (a + P + Z2(q')))A +S 33

= a + + Z2(q*) - a + 3 + Z2(q'))( a++Z + + Z*) +a + + Z2(q'))A + S > (Zl(q') - Zl(q*))/ a + / + Z2(q') by (A4-5). As a result, 2IA+S (a + 3+Z2(q*) -a + f3 + Z2(q)) >2(Zl(q') - Zl(q*)) TZ/3 + +Z2(q') - a + P+ Z2(q*) + + i+ Z2(q') From (A4-1) and (A4-2), TC(T', q') - TC(T*, q*) - Zl(q') + Zl(q*) =2TIA+S (/a+ 3+Z2(q')- a+ + Z2(q*)). ( From (A4-6) and (A4-7), the next result follows. TC(T', q') - TC(T*, q*) < (Zl(q') - Z(q*))[ 1 - 2a t P+ Z2(q') a+f3+Z2(q*) +a + P + Z2(q') = (Zl(q') Z(q*)) 4a + /P + Z2(q*) - a + / + Z2(q') = (Zl(q')- Zl(q*)) Nr/a+ +z-V + +j+Z2(q') < (Zl(q') - Z,(q")) a +/ + Z2(q") -a + p + Z2(q') ~/a + i 3+Z2(q")+ +/a +3+Z2(q') The last inequality in (A4-8) follows from the facts that Z2(q*) < Z2(q") and Zl(q*) > Zl(q"). Consequently, Lemma 2c is true. ~ A4-6) A4-7) (A4-8) 34

APPENDIX 5 PROOF OF THEOREM 2 We provide a result which limits the region in which the optimal value of T lies in the extension to the fixed-charge-per-truck transportation cost structure. Recall the problem is to: (P2) Minimize subject to S 1 T +rT + + (A.Fr 1)+Zl(q) T > T T>r LetS 1 T Let TC(T) = S T + 1T + (A. r 1)+ Zl(q) S A and TC'(T) S + pT + - + Zl(q). T P Then TC(T) > TC'(T) since 1 r -I. T p p TC'(T) achieves its minimum at T =. Theorem 2: Let T* be an optimal solution of (P2). Then, T1 < T* < T2 where T'= max( T, ) }, T1 = max( T,L LJp}, p (A5-1) (A5-2) (A5-3) (A5-4) (A5-5) (A5-6) 35

TT2rIp T2 =:I, (A5-7) and L x J is the largest integer not greater than x. Proof. We want to show that 1) TC(t) > TC(T2) for t > T2 and 2) TC(t) > TC(T1) for T < t < T1. Case 1. t > T2. By (A5-3), TC(t) > TC'(t) > TC'(T2) = TC(T2) since TC'(t) is convex in t and t >T' since T2 is an integer multiple of p. Case 2. r <t < T1. Subcase 1. T < T1. By (A5-3) TC(t) > TC'(t) 2 TC'(Ti) = TC(T1) since TC'(t) is convex in t and t <T' since T1 is an integer multiple of p. Subcase 2. T = T1. In this case, any t < T1 is infeasible. As a result, an optimal value of T exists in the interval [TI, T2].' 36