THE ECONOMIC LOT AND DELIVERY SCHEDULING PROBLEM: POWERS OF TWO POLICIES Juho Hahm Technology Research and Application Center Seoul National University Seoul, Korea Candace Arai Yano Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 December 1991

THE ECONOMIC LOT AND DELIVERY SCHEDULING PROBLEM: POWERS OF TWO POLICIES Abstract We investigate the problem of simultaneously scheduling the final production line of a captive supplier and the delivery of components produced on that line to an assembly facility that 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 cyclic production and delivery schedule with the power-of-two property. That is, in each cycle, each component is produced 2g times for some small integer Ai, where the value of gi may differ across components. In addition, several equally-spaced deliveries occur in each cycle, where the number of deliveries is equal to the least common multiple of the component production frequencies. 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. Computational results suggest that the heuristic performs well in an absolute sense, and that significant savings can be achieved by using coordinated production and delivery schedules rather than approaches in which they are decided sequentially. The results also indicate that in many situations, pure just-in-time policies (in which production and delivery frequencies are equal) are far from optimal. Our model provides a basis for determining the type and extent of improvements needed in the quest for just-in-time.

THE ECONOMIC LOT AND DELIVERY SCHEDULING PROBLEM: POWERS OF TWO POLICIES 1. INTRODUCTION Coordination of production and outbound delivery schedules has become more important with the adoption of "just-in-time" systems in major industry segments, including the automobile industry, which motivated our study. A recent survey of suppliers of automotive components (see Ward's Auto World, July 1990) shows that a majority of suppliers feel that they are being forced to hold inventory for their customers, which are typically assembly facilities. This suggests that suppliers may be producing components in batches that are larger than the delivery quantities, and then shipping the components to the assembly facilities as needed. This raises two important questions. First, what constitutes a good schedule (i.e., how much coordination is desirable) under the existing economics of transportation and production? Second, when should suppliers hold inventory, and when is "just-in-time" truly optimal? We investigate these issues by studying 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. We also assume that the supplier is captive and produces (multiple) components only for the assembly facility in question. Such situations are not uncommon in the automobile industry, and other examples exist in a wide variety of industries. From a technical viewpoint, our reason for considering this situation is that it allows us to investigate the just-in-time 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 1

direction. However, as we will see later, even this single-customer problem is difficult. We anticipate that the results obtained here will be helpful in solving more general problems. The next issue that needs to be addressed is the level of detail at which to model the manufacturing process at the supplier. We have observed that at most first-tier suppliers, the primary scheduling efforts are focused on the last stage of production at that facility, with the overriding concern being that of producing the components on time. At many of these suppliers, the last stage of production is a single production line where these components are assembled. Generally, the upstream stages of production (e.g., fabrication, subassembly) are expected to provide the necessary inputs as needed. We therefore include only the final production stage at the supplier in our model. Further research is needed to incorporate scheduling decisions upstream stages. We assume that rates of use of the components by the assembly facility are, for practical purposes, constant. Smoothing production is a very important prerequisite for making just-in-time workable (see Schonberger 1983 for related discussion), and automobile companies have made a concerted effort to smooth component usage rates as much as possible. Thus, this assumption is fairly realistic in our motivating examples. Considering a situation with constant demand also allows us to gain insight into general principles that are less apparent in more complicated models. We assume that there is a fixed charge for each delivery, but explain later in the paper how the model and solution procedure can be generalized to consider a fixed charge per truckload. Deliveries to the assembly facility occur at equal intervals (duration to be determined), and each shipment consists of exactly enough of each component to satisfy the requirements at the assembly facility until the subsequent delivery occurs. Since the deliveries are equally spaced in time and the demand rates are constant, each shipment has the same composition. The delivery lead time is assumed to be deterministic, and without loss of generality, equal to zero. 2

(Incorporating in-transit inventory requires a simple modification of the parameters in the objective function, but no change in the structure of the solution procedure.) Inventory holding costs are charged on time-weighted 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 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. In this paper, we address the problem of finding a cyclic production and delivery schedule with the power-of-two property. That is, in each cycle, each component is produced 2g times for some small integer ji, where the value of ji may differ across components. Powers-of-two policies are very useful because they facilitate the construction of good schedules with little loss of optimality. (For related references see Maxwell and Singh 1983, Maxwell and Muckstadt 1985, Roundy 1988, and references therein.) In addition, several equally-spaced deliveries occur in each cycle, where the number of deliveries is equal to the least common multiple of the component production frequencies. 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 duration of the overall cycle, the number of deliveries during the cycle (and consequently, the time between deliveries), the number of production runs of each component during the cycle, and the exact production quantities, sequence and timing of these production runs. We provide a review of related literature in the next section. Section 3 contains a formulation of the problem. We propose a hierarchical heuristic procedure in Section 4. 3

Computational results appear in Section 5, and we conclude with a summary and discussion in Section 6. 2. LITERATURE REVIEW Much research has been done on continuous-time, multi-stage production systems with known constant demands, but relatively little of it 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 likely 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 1988, Maxwell and Muckstadt 1985). Other papers incorporate capacity constraints but ignore some or 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). 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], and Moily [1986], among others, for a variety of results on continuous-time, multi-stage lot-sizing models. Transportation costs have been considered in a variety of procurement models, either as quantity discounts (e.g., Lee 1986) or fixed charge per shipment (e.g, Lippman 1971 and Lee 1989), but none of these models explicitly considers the impact of the selected delivery schedule on the inventory at the supplier. There are only a few papers that treat all of the issues that we consider in this paper, and these papers consider restricted versions of our problem. In the interest of brevity, we will review only those models most closely related to ours. Our problem might be viewed as an extension of the economic lot scheduling problem (ELSP) in which several items, each with a constant demand rate, are produced on one machine. Each item is produced one or more times in each cycle and the cycle is 4

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. See Elmaghraby (1978) for a review and Dobson (1987) and Zipkin (1991) for more recent references. Several results and solution procedures for restricted versions of the ELSP have proved to be useful in solving certain aspects of our problem. We will discuss these in more detail as we explain our solution procedure. In our model, the fact that deliveries occur only periodically imposes a structure that bears some resemblance to "basic period" approaches to solving the ELSP. In the basic period approach, the continuous time problem is transformed into a discrete time problem where the duration of the period is a decision variable. Each item has one or more production runs in a cycle. For any basic period duration, the problem is to assign each production run to one of a set of consecutive periods without allowing the production runs to span adjacent periods. This set of consecutive periods forms a repeating (cyclic) schedule. The number of basic periods is also treated as a decision variable. Some examples of basic-period approaches to the ELSP include Bomberger (1966), Madigan (1968), Stankard and Gupta (1969), Doll and Whybark (1973), Goyal (1973), and Haessler (1979). Other related papers are reviewed by Elmaghraby (1978). It is useful to note that given a basic period and a production frequency for each item, the problem of finding a feasible schedule is NP-hard (Hsu 1973). Thus, it is unlikely that an efficient optimal solution procedure can be developed for our problem, since it is even more complicated than the basic-period ELSP. In our problem, the delivery interval (time between deliveries) is, in essence, the basic period. However, our problem differs from the basic-period version of the ELSP in several 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. These accumulation inventories do not occur in the ELSP. Second, because of this inventory accumulation between deliveries, the sequence in which components are 5

produced affects the solution, even when setup times and costs are sequence-independent. In basic-period approaches, the sequence within a basic period does not matter if setup times and costs are sequence-independent. Only a limited amount of research has been done to address sequence dependence in the ELSP (Dobson 1989, Sahinidis and Grossman 1991), but these results could be incorporated into our basic framework. If the setup times and costs are sequence independent, and if production costs per unit time are similar across components, the sequence within a delivery interval may not matter in practice, since the rate at which value is being added is relatively constant. Our point, however, is that unless the number of delivery intervals in the overall cycle is nearly as large as the number of components (in which case, few components would have to wait for very long prior to delivery), these inventories may be as substantial as the cost of holding inventories at the assembly facility. The magnitude of these inventories is influenced by the duration of the delivery interval and the number of intervals in the overall cycle, and thus should be considered in these decisions. Another somewhat related body of research pertains to the joint replenishment problem in which there is a (joint) setup cost per procurement (or a joint 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. Moreover, in a procurement setting, capacity is normally not a consideration, whereas we need to consider production capacity constraints at the supplier. We now turn a review of articles that explicitly consider both transportation and inventory costs in a continuous-time setting. Burns et al. (1985) develop a single-item 6

model with the objective of minimizing the sum of 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 a tradeoff analysis similar to the economic order quantity (EOQ) model. 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. This difficulty is corrected by Hahm and Yano (1991c) 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 7

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. Hahm and Yano (1991a) address a special case of our problem in which there is exactly one production run of each component and exactly one delivery per cycle. They develop properties of the optimal production sequence for a given cycle duration, and use these results in a heuristic procedure that iterates between finding the best cycle duration for a given production sequence, and finding the best production sequence for a given cycle duration. Their computational results indicate that the heuristic provides optimal or near-optimal solutions. This model is generalized in Hahm and Yano (1991b) to consider multiple deliveries per cycle, while retaining the assumption of one production run of each component in each cycle. They develop a heuristic procedure to determine the number of deliveries, the sequence of production runs, and the timing of deliveries relative to the production schedule (i.e., which production runs should occur between consecutive deliveries). The heuristic is shown to provide solutions close to the lower bounds, and to yield signficant savings over the more constrained problem with only one delivery per cycle in instances where the independently-determined economic production cycles are larger than the independently-determined economic delivery cycle. In the following, we generalize the Hahm and Yano (1991b) model to allow multiple deliveries and multiple production runs of each component in a cycle. 8

3. FORMULATION Recall that we must decide the time between deliveries, the number of deliveries per cycle, the number of production runs of each component during the cycle, and the exact production quantities, sequence and timing of these production runs. The last set of decisions generates a complex problem, even if the other decisions have already been made. Consider such a situation. We are still left with the problem of assigning components to delivery intervals while ensuring that each component has the proper number of production runs. We refer to this process as "grouping." For each assignment (or potential assignment), the sequence of production must be decided. We refer to this process as "sequencing." Finally, the allocation of the total cycle demand of each component among its production runs and the exact timing of the schedule need to be determined. We refer to this as the issue of "fit." As we will see later, the grouping, sequencing, and fit decisions are interrelated, and they all affect the cost of inventory in the system. For the sake of clarity, we begin with a formulation in which it is assumed that all production batches of a particular component are equal ("equal lot size assumption"). Later in the discussion, we relax this assumption to allow for unequal batch sizes. Notation: A: cost per delivery; ". setup cost for component j; sj: setup time for componentj; Dj: demand per unit time for componentj; pj: production time per unit for componentj; R: delivery interval (time between deliveries); M"j: ratio of production interval of componentj to the delivery interval; 9

Tj: production interval (time between production runs) for component j = MjR; M: ratio of scheduling horizon (overall cycle) to the delivery interval = least common multiple of the Mjs; T: overall cycle duration (= MR) Fj: number of setups (production frequency) of component j during the production cycle; bj: time (relative to the "beginning" of the cycle) at which the setup of componentj is begun; eji: earliness of the i-th production run of componentj during the production cycle (time between the start of this production run and the time of delivery); gji: index of the delivery in which components from the i-th production batch of component j are first shipped; [k]: index of component produced in the k-th position (k-th production run) in the sequence. The objective function has several elements. The first two elements are clear: the S. average setup cost per unit time is ~, and the average delivery cost per unit time is A. The inventory holding costs can be separated into two parts by noting that a portion of the inventory is that which would be incurred in the ELSP without deliveries. Under the equal lot size assumption, the associated average inventory cost per unit time is ajTj, where aj = PDj hj (l-pjDj)lFj. For convenience, we will refer to this inventory as "cycle inventory" since it is a direct consequence of the production cycle (production interval) of each component. (This portion of the inventory holding cost is identical to that in the economic production quantity (EPQ) problem when the time between production runs is Tj = M /Fj.) The remainder of the inventory cost is caused by the inventory accumulation necessary to ensure that the delivery quantities are available 10

when needed, and by inventory waiting while other components are being produced during the same delivery interval. We refer to all of this additional inventory collectively as "earliness" or "accumulation" inventory. The average inventory cost J f Djhjeji per unit time caused by earliness is X ~ JJi. Since the production batch size is j=1 i=1 Fj DjTIFj and this quantity is held for a duration eji at a cost of hj per unit per unit time, the earliness cost incurred by the i-th production run of component j is DjhjTejilFj. This cost is incurred only once during an interval of Tj time units, so the cost per unit time is DjhjTeji/FjTj. But FjTj = T, so this is equivalent to Djhjeji. This average cost rate is incurred during 1/Fj of the cycle. Taking a time-weighted average over all of the production runs of component j, then summing over all components, we obtain the expression given above. A formulation follows. (P) J S. J J: Djh ji A Minimize J + Ta + I +R (1) j=1 Tj f ji j- i=1 Fj R subject to Tj = Mj-R forj=l to J (2) Mj > 1 and integer forj= 1 to J (3) M = LCM(M1,..., Mj) (4) Fj M forj=ltoJ (5) J N= I Fj (6) j=1 eji 2pjDjR forj=l to J, i=1 to Fj (7) 11

b[k]> + s[k] + p[k]D[k]T[k] < b[k+l] fork= 1 to N (8) b[k] + S[k] + e[k] =g[k]R for k=1 to N (9) gji + Mj =gj(i+l) forj=l to J, i=1 to Fj -1 (10) g[k] < M (11) g[k] > 0 and integer for k=1 to N (12) b[k+l] = b<1> + M.R (13) b[k] > 0 for k=1 to N (14) J S. J -j < 1-,pjDj (15) j= -1 (15) Constraints (2) through (5) define the multipliers as discussed earlier. Constraint (6) defines the total number of production runs in the cycle. Constraints (7) ensure that production runs are started early enough prior to the first delivery of units out of that run so that the delivery quantity is available when needed. Constraints (8) ensure that the production runs do not overlap. Constraints (9) establish the timing of the start of each production run in relation to the time of the first shipment of components from that production run. Constraints (10) ensure that consecutive production runs of a given component are equally spaced in time. Constraints (11) and (12) are constraints on the indices of the delivery intervals. Constraint (13) ensures that the schedule is cyclic, while constraints (14) ensures that the starting times are non-negative. Constraint (15) is the aggregate capacity constraint and is similar to one first introduced by Bomberger (1966). In this formulation, constraint (15) is redundant because constraints (8) and (13) together imply constraint (15). 12

4. SOLUTION APPROACH Many solution procedures for the ELSP have used power-of-two policies. Such a policy restricts the value of Mj to be some power of two and thus, simplifies the problem because M is then the value of the largest Mj. Roundy (1988) shows that this policy has an error bound of less than 6% in the ELSP. In fact, it has been empirically observed that within the class of policies in which each component is produced in equal amounts and at equal time intervals, this policy is often optimal, and if not, it is near optimal (Elmaghraby 1978 and Haessler 1979). Therefore, we will employ powers-of-two policies here. Even with the power-of-two restriction, problem (P) is a large nonlinear mixedinteger program with general integer variables in addition to binary variables. As such, optimal procedures would be computationally intractable. We instead develop a hierarchical procedure which decomposes the problem into manageable subproblems. The general structure of the procedure can be described as follows. Step 1. Determine M, the Mjs and R using a power-of-two policy, ignoring the issues of "fit" and grouping. Step 2. Determine the production sequence for the overall cycle using the values of M, the Mjs and R from Step 1. Step 3. Resolve the issue of "fit" by relaxing the equal-lot-size assumption. Step 4. Determine the relative timing of the production schedule and the delivery schedule (i.e., which production runs should be in each delivery interval). Step 5. Select the value of R that minimizes the objective function in (P) with the other decisions from steps 1 through 4 held constant. The structure of this hierarchical procedure is based on insights gained in the process of solving a more restricted version of the problem (Hahm and Yano 1991b). In 13

particular, we observed that the largest elements of the total cost are the production setup, transportation, and cycle inventory costs. Consequently, it is logical to first determine the values of M, the Mjs and R because they are the decision variables that most strongly influence these costs. We also found it beneficial to develop a production schedule in which the total setup and processing duration in the various delivery cycles are approximately equal, which can be accomplished by appropriate grouping of the production runs. This helps to avoid unnecessary earliness costs, which we will explain in more detail later. After this is done, minor changes can be made to the batch sizes and delivery times to further reduce earliness costs. The last step in our procedure tries to achieve a reduction in the cycle duration if this is possible. Such a reduction will decrease cycle inventory and tends to reduce earliness costs, also. We now explain each step in more detail. Determination of M the Mjs and R If we ignore the issues of "fit" and grouping and use a power-of-two policy, (P) is reduced to the following problem. (P1) S. J J J J Djhjeji A Minimize ] +, Tjaj + F + R j= 1 j j=1 j=i 1=1 subject to (2), (4), (5), (7) and (15) Mj = 29i forj= 1 to J (16) yuj > 0 and integer forj= 1 to J (17) It is easily verified that (P1) has an optimal solution such that eji is equal to pjDjR for all i and j. In other words, if feasibility of the production schedule is not an issue, production runs should be started just in time for the delivery quantity to be available at the end of the delivery interval. Also, constraint (4) does not play a role when the issue 14

J of "fit" is not considered. Therefore, removing (4) and replacing eji by pjDjR, EDjhj j=1 M by 13, and Fj by My in (P1) leads to the following formulation. J S. J A Minimize + 7J + 1ajTj + + (18) j=l Tj j=1 subject to (2), (15), (16) and (17) Problem (P1) has several general integer variables, which makes this problem difficult to solve. Let us, instead, consider a problem where Mj is any real number greater than or equal to 1 instead of a power-of-two. Let (P2) refer to this problem, as shown below. (P2) J S- J A Minimize I A + faiTj + fR + j=T - aj j'= I+subject to (15) Tj >R forj= 1 to J (19) Let 7j'*and R* be the optimal values of Tj and R in (P2). These values can be expressed as: r~ =,xj ' 1<j <J (20) and R*=.A (21) where;o is chosen so that constraint (15) is satisfied as an equality, or Jo = 0 if constraint (15) is not binding, and Xj is chosen so that constraint (19) is satisfied as an equality or Xj = 0 if constraint (19) is not binding for a given j. 15

Let TC* be the optimal objective function value for (P2). Then TC* is a lower bound on the optimal objective value for (P1) as well as (P). We now proceed to describe an algorithm for (P1) which is similar to one that Roundy (1988) has proposed for finding production frequencies for the ELSP. This algorithm finds a set of feasible R and Tjs for (P1) in the neighborhood of R* and Tj*,j=l,..,J, and then selects the one with the lowest total cost. For all j, let Rj and integer uj be defined by J* - Rj 2uj, R2 < R*<. (22) We assume that the components are reindexed so that Rj < Rj+i for allj. For each k, 1 < k < J, we consider a solution of the form Tk { TJ^, 1 <j < J where Tj Rk2vJ (23) vJ u1 j k (24) V j j>k and Rk is a positive scalar. Let TC(T, R) be the objective value of (P1) when T and R are given. We wish to choose Rk so as to minimize TC(Tk, Rk). Let Sk = (25) SR = Sj 2'UJ and a -- J__ajiJ (25) j=1 j=1 Then Sk A TC(Tk, Rk) = -- + akRk + pRk + (26) The value of Rk which minimizes TC(Tk, Rk) is clearly Rk = < +A( Rk ak +. (27) 16

However, (15) implies that Rk is greater than or equal to iz J r=kisj8 2- (28) J where w = l-pjDj. (29) j=1 Since TC(Tk, Rk) is a convex function of Rk, the optimal solution of Rk is given by Rk max[ a+, T. (30) In our procedure, we choose the (Tk*, Rk*) which minimizes TC(Tk, Rk) over all k. We now suggest algorithm (Al) to solve (P1). Algorithm Al Step 1. Determine Rj and uj for allj using (22). Step 2. Re-index the components so that Rj < Rj,+ for allj. Step 3. For each k, 1 < k < J, apply (24) through (30) to compute TC(Tk, Rk). Step 4. Select the vector (Tk*, Rk*) with the minimum cost. The following theorem provides a worst case error bound for our procedure. Theorem 1. TC(Tk*, Rk*) -< — TC* = 1.06TC*. (31) e ln2 Proof. See Appendix 1. We now have a procedure to compute both a delivery interval and production intervals that are power-of-two multiples of the delivery interval. This solutions has an 17

error bound of less than 6% if production schedule feasibility is ignored. In our problem, the combination of periodic deliveries and schedule feasibility considerations give rise to earliness costs. In the next step, using the values from Step 1, we determine a production sequence while placing more attention on schedule feasibility and earliness costs. Determination of the Production SeCuence. Dobson (1987) develops a procedure to determine production frequencies and a sequence for the standard ELSP. He finds relative production frequencies ignoring the issue of "fit" and integrality of frequencies. Then, he uses a variation of the Longest Processing Time heuristic (cf. Graham 1969) to determine a sequence. A feasible schedule is found for the selected sequence by relaxing the equal-lot-size assumption. He shows that if the lot size deviates by at most 100a percent from the lot size in the relaxed solution in which fit is ignored, then the increase in the total cost caused by this error is no more than 100a2 percent. In our problem, the presence of delivery intervals complicates the sequencing decision. One major consideration in constructing the production sequence is to ensure that demand is satisfied on time by restricting production runs of a particular component, say j, to be assigned to delivery intervals that are Mj delivery intervals apart. (In the remainder of this paper, we will use the term 'production run' to refer to a setup and the processing time immediately following it.) For example, if M=4 and Mj=2, there are two choices: assign production runs to the 1st and 3rd delivery intervals, or alternatively, to the 2nd and 4th delivery intervals. Not only does this ensure that demand is satisfied, but it also allows us to avoid the excess inventory carrying costs that would be incurred if the production runs are not assigned to equally spaced delivery intervals. 18

The second consideration pertains to the subset of production runs assigned to a particular delivery interval. If the total setup and processing time for these runs is too long, the earliest production run in the subset may start prior to the beginning of the delivery interval. In this case, additional earliness costs will be incurred for all components in the preceding delivery interval. If there are "domino" effects into yet earlier delivery intervals, the impact may be far worse. There are other interactions that need to be considered. The last production run started in a delivery interval may not be complete at the end of the interval. Generally, only the delivery quantity is produced prior to delivery and the remainder of the production batch, if any, is produced at the beginning of the next delivery interval. The time required for this "overflow" in the succeeding delivery interval may make it impossible to finish all of the required production (for that delivery interval) prior to the corresponding delivery. Thus, it would be advantageous to construct groups with approximately the same total setup and processing time so as to reduce the frequency and extent of the domino and overflow effects. It is well-known from the scheduling literature that the Longest Processing Time (LPT) rule is fairly effective in equalizing the workload among several machines for realistic problems (French 1982) Stated simply, under the LPT rule, the production runs are sequenced in non-increasing order of their total (setup and processing) time requirements. The production runs are considered in this sequence, and are assigned to the machine for which the resulting assignment has the "most equal" machine loads. Because we also have to ensure that production runs of a given component are assigned to equally spaced delivery intervals, we make a minor modification to the LPT rule to account for this difference. In Algorithm A2, we assign all production runs of a given component simultaneously, taking into account their impact on all relevant delivery intervals. 19

Algorithm A2 Step 1. Let tj = sj + pjDjMjR for all j. Let M be the number of groups. Let Li = 0, 1 < i < M. (Li is the total setup and processing time assigned thus far to delivery interval i.) Order the components in (non-decreasing) lexicographic order of (Mj, tj). Step 2. Select the first component not yet assigned. Let it be component j. Let i* = argmin(max(LI I 1 = k, k+Mj,..., k+(Fj -1)Mj ). (32) Assign the Fj production runs of component j to delivery intervals i*, i*+Mj,..., and i*+(Fj -1)Mj. Let Lk - Lk + tj for k = i*, i*+Mj,..., i*+(Fj -1)M. Repeat until all components are assigned. Step 3. Arrange the components in each group in non-increasing order of jhj. Steps 1 and 2 have been suggested by many researchers (e.g., Dobson 1989, Doll and Whybark 1982, etc.) in the context of solving the ELSP. Step 3 has been added to consider the effects of earliness. Observe that each component has at most one production run assigned to any delivery interval. Thus, in determining the sequence of production within a delivery interval, we can refer to components (rather than production runs) in specifying the sequence. We have shown elsewhere (Hahm and Yano 1991b) that for a given assignment of production runs to delivery intervals, the total earliness cost for a particular group (ignoring possible interactions with other groups) are minimized by sequencing all components, except possibly the last 20

component in the group, in the sequence given in Step 3. (Since the last component in the group may complete only a portion of its production run prior to the end of the delivery interval, its earliness may be less than the full processing time of the batch.) Qualitatively, we want to process the components with high inventory holding costs and short production runs late in the delivery interval, while components with low inventory holding costs and long production runs should be processed early in the delivery interval. Note that the duration of the production run affects the waiting time of all components produced earlier in the interval. Thus, both the holding cost and the duration of the production run affect earliness costs. Thus far we have assumed that all lot sizes of a particular component are equal. However, because of the issue of "fit", this is not always possible, as explained in the next subsection. Resolution of the 'fit" issue. The issue of "fit" is best explained by an example. Suppose there are three components, A, B and C, and the policy is to produce components A and B every two delivery intervals and component C every four delivery intervals. Also, suppose that the production sequence is A, B, C, A, B. Components A and B consume half a delivery interval for each production run and component C consumes 1.5 delivery intervals. In this example, M is 4. Therefore, this schedule satisfies the aggregate capacity constraint. The Gantt charts for the components are shown in Figure 1. 21

1 4 component A in! lln 1111111M 2 n 2 5 component B, 3 component C lI I i I 0 1 2 3 4 t Numbers on charts indicate the sequence of production runs Figure 1. Gantt Charts for the Components. It is not possible to fit these three production patterns together. Hodgson and Nuttle (1986) resolve this difficulty by relaxing the zero-switch rule but retaining the equal-lot-size assumption. They show that the resulting problem can be solved optimally by using parametric linear programming. In the above example, the resulting solution involves pushing back production runs 1 and 2 by half a delivery interval each (see Figure 2). In this case, production runs 1 and 2 start before the components produced in production runs 4 and 5, respectively, are consumed. Thus, the equal-lot-size policy may have an unnecessarily large amount of inventory in some cases. 4 1 component A 11llllll 111111111111111111 2 5 component B,,,, 3 component C i I I I I 0 1 2 3 4 Figure 2. Gantt Charts with relaxation of the zero-switch rule. Another approach is to relax the equal-lot-size assumption but retain the zero-switch rule (e.g., Delporte and Thomas 1977 and Dobson 1987). In our example, this can be done by increasing the lot sizes of production runs 1 and 2, and decreasing the lot sizes of production runs 4 and 5 (see Figure 3). 22

1 4 component A In_!m =1i11 2 5 component B 2 5. component C 0 1 2 3 4 Figure 3. Gantt Charts with relaxation of the equal-lot-size assumption. Matthews (1988) derives conditions in which the zero-switch policy is optimal in the ELSP. In a computational study of various ELSP policies, Bourland and Yano (1991) show that the zero-switch policy outperforms the equal-lot policy in nearly all instances. We therefore use the zero-switch policy here. Before we describe a procedure to address the issue of fit, let us define some additional notation. k': index of the first production run after the k-th production run in which [k] is produced, 1 < k < N. mk: number of delivery intervals between the starts of the k-th and k'-th production runs, 1 < k < N = (bk] - b[k / R. Ij: set of production runs in which component j is produced, i.e., {k I component j is produced in the k-th production run), 1 < j < J. For ease of presentation, we will use k rather than [k ] when the meaning is clear from the context. Because we are relaxing the equal-lot-size assumption, the mk values for ke Ij, are not necessarily equal. With this relaxation, the issue of "fit" can be resolved by finding a solution satisfying the following constraints. k'-I mkR > pkDkmkR + (si + piDimiR ) + sk', 1< k < N. (33) i=k+l 23

The k-th production run requires pkDkmkR time units. Also, during the time between the k-th production run and the k'-th production run (mkR), production runs k+l,...,k'-l k'-I must be completed and these runs require Y(si + piDimiR) time units. The number of i=k+l units produced during the k-th production run must be large enough to satisfy demand until the the next production run of the same component. Therefore, the setup for the k'th production run also must be done during mkR. Constraint (33) incorporates all these factors to ensure feasibility. Note that sk' is the same as sk because k and k' are the same component. Therefore, constraint (33) can be simplified to: k'-i mkR > I(si + piDimiR) 1< k <N. (34) i'k We also need to ensure that the total production of each component is enough to satisfy demand during the production cycle. That is, we require that 7mk =M, 1<j < J. (35) k Ij For any value of mk, the average inventory cost per unit time incurred by the k-th akmk2R production run is. (The average cost per unit time during the production interval is akmkR, and the aggregate average cost per unit time is obtained by mk multiplying this value by M-, the proportion of the overall cycle during which this cost is incurred.) As a result, if we do not consider grouping, and if M, R and the sequence are given, the best mk values can be found by solving the following problem. (P3) R N Minimize M lak2 subject to Xmk =M 1 <j< J ke Ij k'-i mkR >,(si + piDimiR) 1< k < N i=k 24

Problem (P3) is a simple convex quadratic program. We use linear complementary programming to solve this problem, but any appropriate technique can be used. If we ignore the the issue of "fit" (i.e., the last set of constraints in the above formulation), the problem is separable by component. The optimal solutions to the invidual subproblems have mk = M[k] for all k, and the sum of the costs of these solutions provides a lower bound on problem (P3). Suppose the solution to the relaxed version of (P3) is not feasible. Let mk be defined as M[k] + 8k. Then, M = Imk = (M[k] + 8k) (36) kE Ij ke Ij = EM + Ak kE Ij k'li =M+ >a8k k Ij As a result, for all j, A 8k is zero. The following proposition is due to Dobson (1987). kE Ij Proposition. If I 8k I < o5M[k] for all k, then the total additional error caused by the issue of "fit" is at most 100o2 %. Proof. See Dobson (1987). Thus we see that the additional error (i.e., in addition to the potential 6% error caused by the power-of-two policy) due to the issue of "fit" will be small if the lot sizes are not far from being equal. For example, a 20% adjustment of all lot sizes would cause an additional error of 4%. We have now resolved almost every issue except grouping, which we discuss next. 25

In this step, we take as given the production sequence from Algorithm A2 and the mk values resulting from (P3), which collectively define the entire production schedule. The problem is to determine when the M equally-spaced deliveries should occur. Since a group is defined as the set of production runs assigned to the same delivery interval, the grouping decision is equivalent to the delivery-timing decision. Note that the mk values are generally non-integer so determining the best relative timing of production and deliveries is not a straightforward matter. One important consequence of non-integer values of mk is that the delivery of a component may occur before the assembly facility has depleted its supply of that component. Therefore, to be more precise, let us redefine the earliness of the k-th production run (ek) as the time between the start of the k-th production run and the time when the units produced in the previous production run of the same component are depleted. Let yk denote the time between the start of the k-th production run and the first delivery of units from that batch. Thus, we have bk + Sk +Yk =gkR, 1 < k <N (37) where gk is positive integer, 1 < k < N. Since the units cannot be depleted prior to delivery, ek must be greater than or equal to yk for all k. Figure 4 shows the notation graphically. 26

I c C) E O co D R - ----- k: Sk YkI Rek+Yk b bk gkR I< ek' ek I mkR t: delivery points Figure 4. Graphical representation of notation ek and Yk. At time gkR, the delivery quantity (DkR) must be available. If no additional production of k were completed between (gk -1)R and gkR, the inventory in the system at time gkR would be Dk(ek - Yk). Thus, is it necessary to complete at least Dk(R -ek + yk) additional units in the k-th production run prior to time gkR. That is, the k-th production run must start pkDk(R -ek + Yk) time units before gkR, or bk + Sk + PkDk(R -ek + k) < gkR, 1 < k < N. (38) Other constraints are as follows. bk + Sk + pkDkmkR < bk+l, 1 k < N. (39) bk + sk + ek + mkR = bk' + sk' + ek', 1 k < N. (40) Constraints (39) prevents the production runs from overlapping. Constraints (40) prevents component shortages. Note that bk + Sk + ek and bk' + Sk' + ek' are points in time when the units produced in the k-th and k'-th production runs, respectively, begin to 27

be consumed. Therefore, the time between these two points must be mkR, the duration whose demand is covered by the k-th production run. The objective of grouping is to minimize costs caused by the earliness of all production runs. The inventory caused by the earliness of the k-th production run is illustrated by the shaded area in Figure 5. The average cost per unit time caused by this mkDkhk inventory is M ek. A formulation for the grouping problem follows. (P4) N mkDkhk Minimize - M ek k=l1 subject to bk+l -bk - Sk > pkDkmkR 1 < k < N bk' + ek' - b -ek = mkR 1 <k <N bk+sk+yk =gkR <k <N PkDkek + (1 - pkDk )k kDkR < k < N ek >Yk k <N gk positive integer 1 < k < N. In (P4), constraints (40) have been simplified by subtracting Sk (= Sk' ) from both sides of the inequality. Constraints (38) have been simplified by substituting for gkR using equality (37). Problem (P4) can be solved using any mixed integer programming technique. 28

Adjustment ofR At this point, a feasible solution has been constructed. Sometimes it is possible to further reduce costs by adjusting the value of R, with all of the other decisions held constant. With R as the only decision variable, problem (P3) is a parametric linear program whose whose right-hand-side parameter is R. It is well known that the objective function value of such a problem is convex in the parameter. Furthermore, the original objective function (of problem (P)) can be expressed as 1 N RN N kDkhk A A MR mkSk +- lakmk2 + k1 M k+ (41) MR k=1 M k=l k=l M R This objective function is convex in R since the third term of (41) is convex in R (from the discussion above) and the other terms are obviously convex in R. Therefore, using a parametric linear programming technique, we can find the optimal value of R when the values of all other decision variables are given. Algorithm to solve (P) Algorithm A3 Step 1. Find M, the Mj*s and R* using (20) and (21). Then find the corresponding power-of-two policy using algorithm (Al). Step 2. Determine the production sequence using algorithm (A2). Step 3. Solve problem (P3) to find the values of mk, 1 < k < N. Step 4. Solve problem (P4) to find the values of gk, 1 < k < N. Step 5. Minimize (41) with R as the decision variable, holding the other decision variables fixed. 29

5. EXPERIMENTAL RESULTS We generated a set of 72 problems to test the algorithm. Several factors were varied in generating the problems. The first factor is the tightness of the capacity constraint. We generated the value of.pjDj from a uniform distribution on [0.3,0.5] J for half of the problems (not tight) and on [0.7,0.9] for the other half (tight). The second factor is the variance of the natural setup cycles among the components. We use the term 'natural setup cycle' of component j to refer to Tj* in equation (20) and the term 'natural delivery cycle' to refer to R* in equation (21). We measure the variance of the natural setup cycles using the ratio of the maximum Tj* 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. We say that the natural delivery cycle is relatively small if it is similar to or less than the minimum T7*, medium if it is strictly between the minimum Tj* and maximum Tj*, and large if it is equal to the maximum Tj*. The two levels of capacity tightness, two levels of natural cycle variances, and three levels of natural delivery cycles give twelve (2x2x3) different combinations of levels. For each combination, a set of six problems is generated: two problems with three components, another two with six components, and two with nine components. Since it is not possible to find optimal solutions for these problems in a reasonable amount of computing time, we compare the solutions from the algorithm with lower bounds obtained from Algorithm Al. Recall that Algorithm Al determines power-of-two policies, but ignores all of the detailed scheduling issues, and does not include any earliness costs. Thus, in most cases, it provides a very loose bound. However, because of the complexity of the problem, finding tighter bounds is not easy. 30

Results are shown in Table 1. The average deviation is approximately 16% and the maximum is roughly 37%. More detailed analysis indicates the deviations increase as the problem becomes more complicated. It appears that this is the result of the lower bound becoming looser as the details of scheduling and the effects of earliness have a greater impact on the solution. The solutions are likely to be much closer to optimal than the bounds indicate. Although we could not obtain optimal solution for all problems, we solved one problem to optimality to get a better assessment of how well the heuristic performs. For this problem, our heuristic provides a solution that is about 1.3% greater than the optimal solution, even though the deviation from the lower bound is nearly 12%. This demonstrates the looseness of the bounds, and suggests the need for tighter bounding procedures. To provide an assessment of the practical benefits of the procedure, in Table 1, we also compare the solutions to optimal (or very near optimal) "just-in-time" policies (the constrained case in which M = Mj = 1). Solutions for the just-in-time case were obtained using the algorithm of Hahm and Yano (1991a) which was described earlier in the paper. The average savings is over 13%, with savings of up to 46% in some problems. In only 4 of the problems was our heuristic solution worse than the just-in-time solution, and in 3 of these 4 problems the difference was less than 1%. Thus, in many instances, pure just-in-time policies may not perform well, and considerable savings may be achieved by using policies in which the production intervals are greater than the delivery interval. We also compared our heuristic with two sequential approaches that capture more decentralized decision-making policies. They are described below. 31

Sequential Decision Approach 1: Step 1. Determine the best production cycle for each component using a power-of-two policy without considering deliveries. (Refer to Roundy 1988.) Step 2. Set the delivery interval equal to the minimum production interval among all the components. (This ensures that there is at most one production run of each component during each delivery interval and that unnecessary deliveries are avoided.) Step 3. Resolve the issue of "fit" by solving the quadratic program (P3). Step 4. Solve the grouping problem using the mixed integer program (P4). Sequential Decision Approach 2: Step 1. Determine the delivery interval considering only the delivery cost and the inventory at the assembly facility. Step 2. Determine the best production cycle for each component using algorithm Al with the initial value of R as determined in Step 1. Step 3. Resolve the issue of "fit" by solving the quadratic program P3. Step 4. Solve the grouping problem using the mixed integer program P4. Note that Steps 3 and 4 of these sequential decision approaches are the same as the corresponding steps in our heuristic. Thus, the primary distinction is that the delivery and production scheduling decisions are decoupled in these sequential decision approaches. It is also important to point out that these are relatively sophisticated heuristics that rely heavily on optimization procedures, and are not simply rule-ofthumb procedures. We randomly selected 15 of the 72 test problems and applied these sequential decision approaches to each. The results (not reported in detail here) show that costs 32

from the sequential decision approaches are approximately 18% larger than the corresponding costs from our heuristic, on the average. The range for SD1 is approximately 40% less to 0.5% greater, and the range for SD2 is approximately 30% less to 5% greater. In the few cases where the sequential decision approach outperformed our heuristic, we found that the production and delivery frequency decisions in our heuristic were largely responsible for the discrepancy. In these problem instances, the difficulties of scheduling and the extent of earliness costs made it ultimately less costly to have Mj = 1 for all j, or even Mj = = = 1 for all j. Our heuristic does not modify the Mj values after the scheduling and earliness issues have been considered, and consequently, may not identify such solutions even if they are less costly. We should note that 11 of these 15 problems have parameters for which Mj = 1 or Mj = M = 1 would be logical (i.e., unconstrained optimal production intervals, or both production and delivery intervals, that are similar in magnitude). Thus, this turned out to be a rather challenging set of problems for our heuristic. Nevertheless, even for these difficult problems, it is clear that there are benefits from coordinating production and delivery schedules. Additional details can be found in Hahm 1990. 6. SUMMARY AND DISCUSSION We have developed a hierarchical heuristic procedure to find coordinated production and delivery schedules with power-of-two policies. This complements algorithms developed for the more restricted cases in which either there is exactly one production run of each component and one delivery in each cycle (Hahm and Yano 1991a) or exactly one production run of each component and multiple deliveries in each cycle (Hahm and Yano 1991b). The heuristic decomposes a large mixed integer nonlinear program into a set of manageable subproblems that can be solved more easily. Computational results suggest that the heuristic performs relatively well in an absolute sense, and generally much better than some relatively sophisticated 33

alternatives that do not determine the production and delivery intervals simultaneously. It also provides solutions that, in general, are much better than pure just-in-time policies where production and delivery intervals are equal. Our model can be used to investigate what types of improvements in setup times and costs, production rates, etc., would be needed for pure just-in-time policies to be optimal. The model in this paper can be extended to consider a fixed cost per truck, under the assumption that all trucks have the same capacity. Because 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. It is easy to show that an optimum value of R less than or equal to p exists, and incorporating this fact into the algorithms is straightforward. The proof parallels that in Hahm and Yano (1991b) and is not given here. Further research may be warranted to provide feedback from the scheduling aspects of the problem to reconsider the choices of the delivery interval and production frequencies. Research is also needed to consider more complex and realistic models with multiple customers and more detailed models of the manufacturing system. In addition, the impact of time-varying and uncertain demand, machine down time, and other random events need to be incorporated into these models. Acknowledgement This work was supported in part by a gift from Ford Motor Company to the University of Michigan. 34

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. BOMBERGER, E., 1966, "A Dynamic Programming Approach to a Lot Size Scheduling Problem," Management Science, Vol. 12, 778-784. BOURLAND, K.E. AND YANO,C.A., 1991, "A Comparison of Solution Approaches for the Fixed-Sequence Economic Lot Scheduling Problem," Working Paper, Amos Tuck School of Business Administration, Darmouth College, Hanover, NH. 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. DELPORTE, C.M. AND THOMAS, L.J., 1977, "Lot Sizing and Sequencing for N Products on One Facility," Management Science, Vol. 23, 764-771. DOBSON, G., 1987, "The Economic Lot-Scheduling Problem: Achieving Feasibility using Time-Varying Lot Sizes," Operations Research, Vol. 35, 764-771. DOBSON, G., 1989, "The Cyclic Lot Scheduling Problem with Sequence-Dependent Setups," Working Paper Series No. QM88-16, Simon Graduate School of Business, University of Rochester, Rochester, New York. DOLL, C.L. AND WHYBARK, D.C., 1973, "An Iterative Procedure for the SingleMachine Multi-Product Lot Scheduling Problem," Management Science, Vol. 20, 50 -55. ELMAGHRABY, S.E., 1978, "The Economic Lot-Scheduling Problem (ELSP): Review and Extensions," Mangement Science, Vol. 24, 587-598. 35

FRENCH S., 1982, Sequencing and Scheduling, New York: John Wiley & Sons. GOYAL, S.K., 1973, "Scheduling a Multi-Product, Single-Machine System," Operational Research Quarterly, Vol 24, 261-266. GRAHAM, R.L., 1969, "Bounds on Multiprocessing Timing Anomalies," SIAM J. Applied Math., Vol. 17, 416-429. GRAVES, S.C. AND SCHWARZ, L.B., 1977, "Single Cycle Continuous Review Policies for Arborescent Production/Inventory Systems," Management Science, Vol. 23, 529 -540. HAESSLER, R., 1979, "An Improved Extended Basic Period Procedure for Solving the Economic Lot Scheduling Problem," AIIE Transactions, Vol. 11, 336-340. HAHM, J., 1990, The Economic Lot Production and Delivery Scheduling Problem, Unpublished Ph.D. Dissertation, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan. HAHM, J. AND YANO, C.A., 1991a, "Economic Lot and Delivery Scheduling Problem: The Common Cycle 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: The Nested Schedule Case," 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. HODGSON, T. AND NUTTLE, H., 1986, "A Note on Linear Programming and the Single Machine Lot Size Scheduling Problem," International J. of Production Research, Vol. 24, 939-943. HSU, W. (1983), "On the General Feasibility Test for Scheduling Lot Sizes for Several Products on One Machine," Management Science, Vol. 29, 93-105. 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," IIE Transactions, Vol. 21, 266-270. 36

LIPPMAN, S.A., 1971, "Economic Order Quantities and Multiple Setup Costs," Management Science, Vol. 18, 39-47. MADIGAN, J.G., 1968, "Scheduling a Multi-Product Single Machine System for an Infinite Planning Period," Management Science, Vol. 14, 713-719. MATTHEWS, J.P., 1988, "The Optimality of the 'Zero-Switch' Rule for a Class of Economic Lot-Scheduling Problems," J. Operational Research Society, Vol. 39, 1155 -11.61. 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. MAXWELL, W. AND SINGH, H., 1983, "The Effect of Restricting Cycle Times in the Economic Lot Scheduling Problem," IIE Transactions, Vol. 15, 235-241. 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., 1988, "A 98%-Effective Lot-Sizing Rule for a Multi-Product, Multi-Stage Production/Inventory System," Math. of OR, Vol. 11, No. 4, 699-727. SAHINIDIS, N.V. AND GROSSMAN, I.E., 1991, "MINLP Model for Cyclic Multiproduct Scheduling on Continuous Parallel Lines," Computers and Chemical Engineering, Vol. 15, 85-103. 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. STANKARD, J.F. AND GUPTA, S.K., 1969, "A Note on Bomberger's Approach to Lot Size Scheduling: Heuristic Proposed," Management Science, Vol. 15, 449-452. 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. 37

ZIPKIN, P., 1991, "Computing Optimal Lot Sizes in the Economic Lot Scheduling Problem," Operations Research, Vol. 39, 56-63. "1990 Supplier Survey," Ward's Auto World, Vol. 26, No. 7, 37-39, July 1990. 38

Table 1. Summary of Experimental Results J:Number of Components. C: 1 if capacity is not tight and 2 if capacity is tight V: 1 if low variance of natural production cycle, 2 if high. D: 1 if delivery interval is small, 2 if medium, 3 if large. TC: Total Cost from Heuristic LB: Lower Bound JIT: Cost with Mj = M = 1 J C V D TC / JIT TC / LB J V D TC/JIT TC/LB 3 1 1 1 93.22% 107.79% 3 1 2 1 82.66% 117.56% 3 1 1 1 92.10% 104.12% 3 1 2 1 76.06% 108.75% 3 1 1 2 93.02% 103.21% 3 1 2 2 93.25% 110.07% 3 1 1 2 94.18% 107.48% 3 1 2 2 94.16% 111.92% 3 1 1 3 100.00% 113.58% 3 1 2 3 99.64% 113.94% 3 1 1 3 100.00% 116.60% 3 1 2 3 98.00% 111.19% 3 2 1 1 80.45% 127.73% 3 2 2 1 68.23% 115.49% 3 2 1 1 80.40% 115.35% 3 2 2 1 71.91% 118.10% 3 2 1 2 77.88% 111.45% 3 2 2 2 98.76% 113.38% 3 2 1 2 74.96% 104.53% 3 2 2 2 94.28% 114.98% 3 2 1 3 100.00% 118.96% 3 2 2 3 100.00% 115.70% 3 2 1 3 100.00% 122.73% 3 2 2 3 93.82% 111.49% 6 1 1 1 85.27% 115.54% 6 1 2 1 75.23% 109.72% 6 1 1 1 84.50% 118.10% 6 1 2 1 77.34% 109.67% 6 1 1 2 100.00% 118.91% 6 1 2 2 91.04% 118.78% 6 1 1 2 100.41% 121.55% 6 1 2 2 100.31% 127.79% 6 1 1 3 97.14% 118.61% 6 1 2 3 100.00% 117.22% 6 1 1 3 109.75% 133.33% 6 1 2 3 96.08% 115.96% 6 2 1 1 55.53% 110.87% 6 2 2 1 79.48% 122.29% 6 2 1 1 64.86% 111.67% 6 2 2 1 66.56% 110.32% 6 2 1 2 73.84% 121.24% 6 2 2 2 93.28% 127.20% 6 2 1 2 74.19% 123.78% 6 2 2 2 92.20% 123.98% 6 2 1 3 100.00% 133.81% 6 2 2 3 98.23% 136.78% 6 2 1 3 91.19% 136.58% 6 2 2 3 100.52% 132.71% 9 1 1 1 88.63% 127.29% 9 1 2 1 83.19% 125.12% 9 1 1 1 92.17% 130.71% 9 1 2 1 80.33% 108.50% 9 1 1 2 100.00% 133.03% 9 1 2 2 89.82% 120.31% 9 1 1 2 100.00% 143.28% 9 1 2 2 92.17% 119.62% 9 1 1 3 100.00% 134.82% 9 1 2 3 94.34% 123.18% 9 1 1 3 100.00% 132.24% 9 1 2 3 100.00% 119.21% 9 2 1 1 53.29% 105.82% 9 2 2 1 75.09% 117.11% 9 2 1 1 62.61% 108.68% 9 2 2 1 59.36% 109.56% 9 2 1 2 57.90% 110.56% 9 2 2 2 73.59% 124.03% 9 2 1 2 79.21% 127.84% 9 2 2 2 64.18% 123.58% 9 2 1 3 80.40% 132.33% 9 2 2 3 94.36% 138.83% 9 2 1 3 85.15% 153.08% 9 2 2 3 76.75% 129.28% 39

APPENDIX 1 PROOF OF THEOREM 1 Portions of the proof of Theorem 1 are similar to that of Theorem 6 in Roundy [1988]. Before proving the theorem we need to introduce some notation and preliminary results. Recall that the value k* has been selected so that TC(Tk*, Rk*) = min (TC(Tk, Rk). (A-l) Therefore, J TC(Tk*, Rk*) < wkTC(Tk, Rk) (A-2) k=1 J where YWk = 1 and Wk > 0 for all k. (A-3) k=l Let wk be defined as follows. w- log2( Rk^ ), lk < J-1 2R1 and wJ-log2(RJ ). (A-4) Let Rjk R j > k (A-5) ~~~JLetj j> Let J TCw = wkTC(Tk, Rk). (A-6) k=l 40

The following lemmas are used in the proof. Lemma 1: k Rk J R. R r 1 If i <j then YWk [iR + ] < 42 + k=l Rj.iR 2 Proof. By (A-4) and (A-5) J R. R. Ri k=l Rj Ri J where f(x) (X +-) log2(2x) + (2x +1 ) where f(x)-(x + -)log2(2x)+ (2x + 1)log2 (-). x t (A-7) (A-8) (A-9) 1 Ri Since i <j, (22) implies that < < < 1. On the interval and attains its maximum value of + 1 at x = 2L a 2 Lemmna 2: C, 1], the function f is concave 2' J 2 k=l.-i e ln2 J Proof. Case 1. i <j. By (A-4) and (A-5) J R Ri Ywk [I ]= t(y) 1 k=l R j Ax) = x log2(2x) + 2x log2 (-). X (A-10) (A-1l) where 41

1 Ri 1 Since i <j, (22) implies that 1 < < 1. On the interval [, 1], the function f is concave 2 2 and attains its maximum value of 2 at x = e ln2 e Case 2. i>j. By (A-4) and (A-5) J Rk. Ri Iwk [R ]= fI j ) (A-12) k=l R' x j2 where f(x. x 2 where f(x) =- log2(x) + x log2 (2). (A-13) Since i > j, (22) implies that 1 < R < 2. On the interval [1,2], the function f is concave 2 4 and attains its maximum value of 2 at x =-. e ln2 e Theorem 1: TC(T*, Rk ) < 2TC* 1.06TC*. Proof. S. J Case 1. < w, where w = l-pj-Dj. J J j=l Suppose we were to decrease the value of w from its current value to 1 The J J cost of TC(T*, R*) would be unaffected because (T*, R*) is still feasible for (P2). However, the cost TC(Tk, Rk) would either increase or remain unchanged. Therefore the relative cost for Case 1 is bounded by the relative cost for Case 2. Case 2. 2T, = -w. j I 42

We will show that TC(Tk, Rk*) < e TC* by showing TCW< 2 *. e In2 C ysown C~e ln2C* Note that (A-5), (24) and (22) imply that k 2v 2~j R. x2V= Rj x 2j =Tj*. SI a, SLet[j =, Yj i T*' and Zj- Then by (25) we have et j-Sk Tj* J adT* Sk= Zj and ak=X *fi. 3 (A-14) (A-15) Let:xj-. Note that xj 20 and.xj = 1. By assumption w iJL J J j J = YXj, so (28) J implies k zXjRk JX = - = xjRj. j J (A-16) We can write TC(Tk, Rk) as TC(Tk, Rk) = S + ^kI + r + A. (A-17) By (20) we have Y = Zj + zaoj + jTj*. J- j;di~;~T (A-18) So, TC(T*, R*) = 2AZj + Xo2 +.jTj + [ PR* + ] J J J (A-19) and 43

TC, = LIWk f +[ z][ ] ) JR + ko XWk [XxjRj] I X' ] k jJR. + wLk [xR] [Y I k J iJ aR 3 k 1 + P Plwk[LxjRj] + A Xwk[1] k. k i k Zxk~J j (A-20) The remainder of the proof is divided into four parts. We show term by term that each 2 term in (A-20) is at most e ln2 times the corresponding term of (A-19). Part 1. Let zj -. -. Then zj > 0 and, zj = 1. We need to show that Z < 4I where Letz~~~ jJ - J e ln2 J J zjRZ — Wk ( J +[.xRj]][ ]} ). i R (A-21) By Jensen's inequality and by Lemma 1, Z < Xwk([ { I j][X4] k J Jj Rj 3 + [.xnjR] [~ ] 1 j~~~ J R.k Rk = I [Xjzi + xizj] lwk [-: + -1l ]+ 2xi i<> k*=l Ri Ri j 44

< (F- + ) (Y[xzi +xizj] + xijZj ) V2 i< J s (~ ~<1 1 4 <_ (5 + ) [][]: (J +.) < e n2 J 4s e ln2 Part 2. 2 We need to show that X < in2 where e ln2 X =Iwk [>jRi Ij R,]. k j - j 3 (A-22) By Lemma 1, J R. R. A - I xi X w [Rk +. ] ) + I.j2 y - 1 ^k=.l " RK ji i I <I (2 + - i 2 2x + -F2 i< j j2 - = i^ (4-t + ) < 2 -J 2: F+ eln2 ' Part 3. 2 We need to show that L < n2 where e 1n2 L wk [I k j and l -jT-j = I;jTj J Note that lj > 0 and.lj = 1. By Lemma 2, J xjR^] [ ]I r Ji R 7cR3 C^i (A-23) (A-24), l<j<J. 45

L J R. = I ( xjli Ywk [;- ] ) iandj k=l R J < 2 Xli - 2 e ln2 iandJi - eln2 Part 4. We need to show that G1 +G2 2 H1 +H2 e ln2 where G1 = PR*, G2- R*, H = wk [>R] and H2 A kwk [- k]. k k Let Let (A-25) k pji 1,jJ. (A-26) Then by Jensen's inequality and Lemma 1, G1 +G2 G1 G2 Hl+HJ2 -H1 H2 k 1JX 1jpj k ji xjiPp k k =ka p k ]pkI + Ixmi Yw Ik p '1) + l '} x = i wk=l + Pi J 46

XRh. Rk: =XjXi W[IT_ + R__k ]} + ].T2)+ 2 i<j k=l Rj Ri J 1 1 1 WE 2xrv2 2,2 < 2 (2 j e ln2 As a result of Parts 1 through 4, TCw e n2TC*. Also, because TC(Tk* Rk*) < TCw, TC(Tk* Rk*) < en2TC*. 47