A COMPARISON OF SOLUTION APPROACHES FOR THE FIXED-SEQUENCE ECONOMIC LOT SCHEDULING PROBLEM Karla E. Bourland The Amos Tuck School of Business Administration Dartmouth College Hanover, NH 03755 Candace A. Yano Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 Technical Report 92-46 August 1992

ABSTRACT The economic lot scheduling problem (ELSP) has received much attention during the past few years. The general version of the problem has a non-convex objective function, so it is difficult to find truly optimal solutions for it. In this paper, we examine the three most popular heuristic approaches to the fixed-sequence ELSP. Each of these approaches imposes one or both of these simplifying constraints: the zero-switch constraint (production of a part is started only when its inventory level reaches zero), and the equal-lot constraint. We provide a formulation of the problem that helps to clarify the relationships among the general problem and the three constrained versions. In a computational study, we show that the three constrained formulations may lead to solutions with disparate costs when the better solutions have little or no idle time, but they lead to very similar or identical solutions when it is necessary or desirable to have even modest amounts of idle time. These results suggest that approaches based on more restrictive assumptions that are consistent with practical considerations, may provide very good solutions in practice.

1 Introduction The economic lot scheduling problem (ELSP) addresses production scheduling of several parts, each with known demand occurring at a constant rate, on a single machine. Several assumptions are made. Only one part can be produced on the machine at any time. Before producing a particular part, the machine must be set up for the new part. Each setup takes time, consumes production capacity, and may incur a setup cost. Setup costs and times are independent of the sequence and of the production quantity. Production rates are known and constant No backorders are allowed, and holding costs are charged on average inventory levels. The objective is to minimize the sum of the average inventory holding costs and setup costs per unit time. A solution to the ELSP must specify the sequence in which parts are to be produced; the production quantities, or, equivalently, the production-run durations; and the time at which each setup is to begin. This problem was first posed formally by Rogers [14]. Since then, a significant amount of research has been done on this problem, but to date, there is no known optimal solution procedure for the general version of the problem in which there are no restrictions on the sequence of production, the lot sizes, or the inventory at the start of a production run. Even if the production sequence is given, the problem has a non-convex objective function, and is therefore difficult to solve optimally. The ELSP derives its name from basic inventory theory. The optimal production policy for a particular part n, considered independently of other parts, is to produce Qn (the economic lot) every Tn units of time (the natural cycle). Tn and Qn are found by trading off setup and inventory holding costs. We call a schedule where each part follows its own optimal policy the independent solution. When several parts share a single facility, it is unlikely that the independent solution will be feasible, although the sum of costs of the independent solutions does provide a lower bound on the cost of the optimal schedule.

2 In the independent solution, each production run (after setup) begins when the inventory level drops to zero, and the same quantity is produced whenever production occurs. Production of a particular part is therefore periodic, and the corresponding cycle length is referred to as that part's natural cycle. Early research on the ELSP takes these properties as assumptions. The assumption that production is started only when inventory reaches zero is often referred to as the zero-switch assumption. The assumption of constant production quantities for a particular part is often referred to as the equal-lot-size assumption. A natural result of the zero-switch and equal-lot assumptions is the notion of a basic period, first introduced by Bomberger [1]. The basic-period assumption is that part n, n = 1,..., N is produced using a cycle equal to knw, for integer kn and basic period w. The most frequently produced part is produced once every basic period. The nth multiplier, kn, represents the number of basic periods between production runs of part n. Within the basic period framework, the problem is, first, to find the basic period and multipliers, which determine the production quantities and production cycles. Next, a feasible schedule (a production sequence and timing of production runs) that uses the resulting production cycles must be found. (See Elmaghraby [5] for an excellent review of this early research.) Although the zero-switch and equal-lot-size assumptions were originally considered simplifying assumptions, in fact the problem of finding a feasible schedule that satisfies these assumptions is quite difficult. Hsu [9] has shown that, given a basic period and set of multipliers, finding a feasible schedule is NP-hard. Basic-period approaches rely heavily on calculations similar to those for the economic order quantity, where setup costs are needed to calculate tradeoffs between holding and setup costs. Even when out-of-pocket setup costs are small, setup costs may be used as surrogates for setup times so that the capacity consumed by setups is considered in determining cycle durations. Parts with long setup times are assigned high setup costs, which then causes such parts to be produced less frequently than parts with short setup times. It is not clear, however, how to select setup costs

3 to reflect the impact of setup times on capacity utilization within the context of the basic period approach. A special case of the economic lot scheduling problem with both the zero-switch and equallot assumptions is modeled by Hanssmann [7]. He assumes, in addition, that all parts are produced exactly once in each cycle. This is called a common cycle schedule. Under this assumption, the optimal solution can be obtained in closed form. Consequently, it is always possible to find a common cycle solution, which provides an upper bound on the cost of the general problem. Jones and Inman [10] and Gallego [6] specify conditions under which common cycle schedules are optimal or near optimal. These schedules may be much more expensive than noncommon cycle schedules, however, when parts have significantly different natural cycles. In recent years, researchers have relaxed either the zero-switch or the equal-lot-size assumption and have developed solution procedures in which a cyclic schedule is found for a fixed production sequence where each part may be produced more than once. Although the optimal schedule may not be cyclic (Schweitzer and Silver [16]; Muckstadt and Singer [13]), virtually all the research on the ELSP assumes the schedule repeats every T units of time. Hodgson and Nuttle [8] solve the ELSP with the production sequence given and the zeroswitch assumption relaxed, while retaining the equal-lot assumption. They formulate the problem as a convex programming problem (convex objective function and linear constraints) and solve it with parametric linear programming techniques. Dobson [3] solves the complementary problem, retaining the zero-switch assumption and relaxing the equal-lot assumption. He develops a sequencing heuristic in which the determination of the number of batches per cycle for each part is based on the results of Roundy [15]. The heuristic is similar in nature to those suggested by Doll and Whybark [4] and Maxwell and Singh [12]. Dobson's model explicitly considers the effects of setup times so that surrogate setup costs are not needed. His formulation, which has a strictly quasiconvex objective function and a linear constraint set, can be solved with standard nonlinear programming techniques. Zipkin [17]

develops a more efficient computational solution procedure for the zero-switch problem, assuming the production sequence is given. He reports that in most of the problems in his computational study, his initial solution for the cycle duration is within 1% of the optimal solution for the zeroswitch version of the problem. All of the recent papers explicitly consider setup times, so surrogate setup costs are not necessary. In this paper we assume that the production sequence is given. We consider the equal-lot solution approach (as formulated by Hodgson and Nuttle), the zero-switch approach (as formulated by Dobson), as well as an equal-lot-zero-switch solution approach which incorporates both restrictions, and provide a formulation that helps to clarify the relationships among them and with the general problem. In a computational study we compare optimal solutions for these constrained versions of the problem with one another, and with a lower bound on the general problem, by solving a large set of problems with a wide range of parameters. We also provide analytical results for two classes of problems with simple production sequences to further explain when and why the zero-switch version of the problem provides better solutions. Computational comparisons of these solution approaches are very limited. Hodgson and Nuttle do not provide a computational study of their equal-lot solution approach. Dobson's computational study focuses on the sequencing aspect of the problem. For a few example problems, Delporte and Thomas [2] have found that the zero-switch version of the problem provides less costly solutions than the equal-lot version. The zero-switch version is the most popular in recent research on the ELSP, and is thought to provide good results. However, the equal-lot assumption is much more desirable in many practical situations, especially when material handling, inventory control, or procurement issues make unequal lots impractical. For these reasons, we also investigate the factors that influence the relative penalty of using the equal lot solution. We also investigate the penalty for including both the equal-lot and the zero-switch assumptions, which together can greatly simplify many aspects of system control. Since other more complex production planning problems are based on the ELSP

5 (see, for example, Gallego [6]), inclusion of both assumptions may also help to simplify approaches to these (and other) larger problems. 2. Formulations First we formulate the fixed-sequence ELSP, relaxing both the equal-lot and the zero-switch assumptions. This formulation is a generalization of the one given in Dobson [3]. Other authors (Maxwell [11]; Delporte and Thomas [2]) have also formulated the general problem. Our formulation is distinctive in that it clarifies the relationships between the general and the restricted versions of the problem. Notation is defined in Table 1. The cycle length T is partitioned into H (unequal) intervals. The numbering of the intervals is circular, that is, interval 1 follows interval H. In each of the intervals there is idle time (perhaps zero), a setup, and a production run. After we formulate the problem, we show how each of the variations is obtained by constraining the general problem in a particular way. The zero-switch schedule is defined by the decision variablesfi, Tv,i, and T. An example of such a schedule is shown in Figure 1. The average inventory holding and setup costs per unit time of the zero-switch schedule are given by T H[if 2 + A/T. i Observe that the summation is over the intervals, rather than the parts, because the fraction -- and hence, the contribution to the average inventory -- is reflected for each interval. The time between the start of production run k (after setup) and the start of the next production run for part [k] is equal to (fiTp[i] + Ts,i + Xv,i) - v,k + Nk. (1) ie Mk The time to deplete the quantity of part [k] produced in production run k isfkT. One requirement for feasibility of a zero-switch schedule is that (1) must be equal tofkT for all k.

6 Table 1 Notation n index of parts, n = 1, 2,..., N i,j,k indices of intervals [i] index of the part produced in interval i Jn the set of intervals in which part n is produced Ni the index of the interval in which part [i] is next produced Mi set of indices from i up to, but not including, the index of the interval in which part [i] is next produced Ts,n setup time for part n Dn demand rate for part n Pn production rate for part n Pn Dn/Pn P,Pn n hn inventory holding cost per unit per unit time for part n Hn hn Dn (1 - pn)/2 A total setup cost for the sequence T length of overall cycle fi fraction of cycle demand for part [i] produced during interval i Tv,i idle time in interval i To relax the zero-switch assumption, we include the decision variable 0,j, which represents the overlap time in interval i. That is, production in interval i begins 0oj units of time before the inventory of part [i] reaches zero. An example of a schedule with positive overlap is given in Figure 2. The additional inventory holding cost during interval i is given by h[I/fi D[l Txo (see Figures 3a and 3b). The time between the start of production run k and the start of the next production run for part [k] is still given by (1). This must be equal to the time to deplete the

7 quantity of part [k] produced in production run k, plus any overlap in interval k, and less any overlap in interval Nk. That is, (fiTplil+ Ts,i + Tv,i) =fkT + o,k - o,Nk + Tv,k - TvNk k = 1,..., H. i fMk The variables fi, tv,i, Toi, and T define a schedule where production runs may start when inventory is positive and where production lots of the same part may be unequal. We refer to the general problem in which both the zero-switch and equal-lot constraints are relaxed as GP (general problem). The complete formulation is given below. Problem GP: min T E fi2H[i + + hlilfi Dl] goi i i subject to fi = 1, n = 1,...,N; (2) i EJn (fiTP[i]+ s,i + v,i) = ieMk fkT + To,k - ok + Xv,k - vYNk k= 1,..., H (3) H (fiTP[i]+'s,i + v,i) = T;(4) i= 1 fi, T, xv,i, Xo,i < O i = l,..., H. The objective function, which is nonconvex, represents the average inventory holding and setup costs per unit time. Constraints (2) guarantee that there are no shortages, constraints (3) ensure that the timing of the various events in the schedule are feasible, and constraint (4) defines the overall cycle length. Constraints (3) and (4) are also nonconvex. By letting xp,i =fiTp[,i represent the time spent producing in interval i and replacingfi by tp,i/(Tp[i]) in the formulation, the constraints become linear. The objective function remains nonconvex.

8 Let 1rn be the number of times part n is produced in the given sequence. Then, setting the T0r to zero for all i and settingfi equal to the reciprocal of ~[i ] in the general problem GP gives a formulation for the fixed-sequence ELSP with both the equal-lot and zero-switch assumptions. We refer to our formulation of this problem as ELZSP (equal-lot-zero-switch problem). Although both the ELZSP and the basic-period formulations mentioned earlier include the equal-lot and the zero-switch assumptions, the two formulations differ significantly from one another. In the ELZSP we do not require the production runs to fit into the discrete time constraints imposed by the basic periods. In essence, we allow a production run to begin in one basic period and end in the next. Basic-period solution approaches use heuristics to determine a sequence for a given basic period. These approaches are often iterative, with the relative frequency and sequence of production changing as the basic period changes. In the ELZSP, the production sequence is given and fixed. When the production sequence is given, ELZSP provides a lower bound on the cost of a basic-period solution for that sequence. Note that settingsf = 1 / rl[i ] for all i gives a formulation for the ELSP with only the equallot assumption. We will refer to this as the ELP (equal-lot problem). A formulation for the ELSP with the zero-switch assumption is given by once again replacing fiT by tp,i / (Tp[11), and then fixing Tj at zero for all i in the general problem formulation. The objective function for this problem is strictly quasiconvex and the constraints are linear, so it can be easily solved with standard nonlinear programming techniques. We refer to this as the ZSP (zeroswitch problem). (This version of the problem is formulated in a similar manner by Dobson [3].) A variation of GP also gives a lower bound on the cost of the optimal solutionfor a given sequence. First, linearize the constraints by replacing the fiT by tp / (Tp[1l) for all i. Then remove the terms associated with the overlap, h[1fiD[i]ojr, from the objective function. A solution to this problem is feasible for the general problem. The objective function value, which does not incorporate the overlap costs, provides a lower bound on the cost of the optimal solutionfor the general problem for that sequence. We refer to this problem as LBP (lower bound problem).

9 In the computational study that follows, we solve the ELP, ZSP, ELZSP, and LBP optimally and compare the corresponding objective values. 3. Computational Comparison Experimental Design We designed a set of over 4000 problems representing a wide variety of different combinations of production rates, demand rates, setup times, setup costs, and unit costs. While these problems are quite varied, we have not included extreme cases where, for example, one part represents only 1% of the total demand or has a setup cost or time hundreds of times larger than that of another. This choice was motivated by our observation that in many practical single machine scheduling problems, and in the vast majority of the problems that motivated this research (injection molding and metal stamping) the parts assigned to a particular machine are fairly similar with regard to most parameters. We use a 30% inventory carrying cost rate, and assume 2,000 hours of production time per year. For each problem, the other problem parameters are randomly generated from a specified range, and we use two or more range levels for each parameter, as shown in Table 2. Considering all possibilities gives 192 (22 x 3 x 42) combinations of parameter ranges. For each combination of parameter ranges, we generate 26 parameter vectors (problems), where each parameter is generated uniformly from the given range. Thus, we have a total of 4,992 (26x 192) problems. (Because the parameters are randomly generated, the probability of generating equivalent problems after scaling is infinitesimal.) For each of these problems, new parts are generated and added to a problem until utilization without accounting for setups (p) falls to between 0.65 and 0.95. Using Dobson's sequencing algorithm, we generate sequences for each of the problems, discarding the 676 problems for which Dobson's procedure generates a common-cycle sequence. There are between 3 and 16 parts and between 4 and 41 positions in the remaining production sequences. Then we find optimal

10 solutions to ELZSP, ZSP, ELP, and LBP, and the costs of the common-cycle solution for the remaining 4,316 problems. Zero-Switch and Equal-Lot Results In every case the ZSP solution is less costly than the ELP solution, and on the average, its cost is less than 2% above the lower bound. In many cases the ELP and ZSP solutions have similar costs, and the ELP costs are only 4% above the ZSP costs on average. The maximum difference in our problem set, however, is over 18%. We observed that the difference is largest when the parts have unit costs (and hence holding cost rates) that differ widely (unit costs from $5 to $25), and relatively slow production rates (from 300 to 400 parts per hour). Table 2 Ranges for Randomly Generated Problem Parameters Range Parameter Dimension level Low High Production Rate Parts Per Hour 1 300 400 2 800 1,000 3 1,600 2,000 Demand Rate Parts Per Hour 1 90 100 2 20 100 Unit Cost Dollars Per Part 1 0.75 1 2 7.50 10 3 75 100 4 5 25 Setup Time Hours 1 0.50 2 2 4.00 16 Setup Cost Dollars 1 10 100 2 7.50 10 3 75 100 4 750 1,000 Although the ZSP always outperformed the ELP in our problem set, it is difficult to show that ELP solutions are dominated by ZSP solutions in general. We can obtain results for some special cases that help to illustrate why ZSP solutions are less costly. Consider a simple example involving three parts-A, B, and C. Part A is produced twice in the sequence, and parts B and C are produced once. (Parts B and C might actually represent several parts each, all produced only

11 once in the sequence.) So, the schedule has four intervals, and we assign part A to intervals 2 and 4, and parts B and C to intervals 1 and 3, respectively. In a schedule satisfying both the equal-lot and zero-switch assumptions, the time between successive production runs of part A is equal to T/2. During each of these intervening time durations, part A must be produced, consuming PA T/2 time units. The rest of the time is available to produce other parts that must be produced according to the fixed production sequence. Thus, in our simple example, neither the time required to produce part B, PB T, nor the time required to produce part C, PC T, can exceed T(1 - PA) / 2. Assume part B violates this constraint, that is PB > (1 - pA)/2, as shown in Figure 4. In this figure, T is equal to the smallest T for which a feasible solution exists. (There is no idle time in a solution to this problem for this value of T.) To resolve the infeasibility without violating the zeroswitch constraint in this example, the fraction of demand for part A satisfied by production in the second interval must be f2 = PBI/( - PA). This is shown graphically in Figure 5. To resolve the infeasibility without violating the equal-lot constraint, the overlap in interval 2 must be o,2 = T(2pB + PA - 1) / 2. This is shown graphically in Figure 6. The difference between the costs of the equal-lot and the zero-switch schedule is ThA(l-pA)DA ThA( - PA) D 2 4 + hAD2 o,2 - 2- ) ThA(1-pA)DA ThDA(1 -PA) ThA(1 -PA)DA + (1 -f)2) -= - -4 + 2T(l - PA) ~o2 2 f+(l-f)) ThA(l- PA) DA [1 l -f2)- 2' T(1 - PA) Since T is unchanged and only T affects the cost of parts A and B, expressions involving intervals 1 and 3 do not appear in this cost difference. Substituting for to,2, we have ThA(1- PA) DA 12pB +pA -l 2 2 [ 2 2(l-PA) - -(-2). Now,

12 (1 + PA - PB)2 +(1 -f2)2=B- +(1- PA p)2 (1- PA)2 After substituting, the difference between the two schedules becomes ThADA(1 - PA - PB)(2PB - 1 + PA) 2(1 - PA) which is strictly greater than zero since PA > 1 - 2PB by assumption (which caused the original infeasibility), and PB + PA < 1 is a condition for the existence of a feasible solution. Therefore, given the choice between a zero-switch and an equal-lot solution, the zeroswitch solution will be less costly. Increasing the overlap in interval i increases the holding cost in interval i, but without a reduction in costs elsewhere. On the other hand, violating the zero-switch assumption by makingf2 > 1/2 andf4 < 1/2 increases the holding cost in interval 2, but decreases it in interval 4. Now consider a problem where part A is produced more than once in the sequence, and all other parts are produced only once. We assume that a feasible solution exists, possibly violating the zero-switch and/or the equal-lot constraints, for a sufficiently long cycle length (i.e., we are attempting to solve a feasible problem). Suppose that we start with an infeasible schedule in which part A is produced in interval i, and consider reducing a machine conflict by e by increasing the time between the completion of production in interval i and the start of the next production run for part A. We investigate the costs of two alternatives: either increasingfi and decreasingfj for somej (i i) in JA by Af= T(1 - A) or increasing the overlap in interval i by e. Under these assumptions the difference between the cost of increasing to,i and the cost of increasingfi is given by hADAT(1 - PA) Af (f - Af) - hAD,i Af. (5)

13 Thus, the cost of increasing o.,i exceeds the cost of increasingfl if &f > Af+ T(l -pA) If the current overlap, TOi, is zero, then this condition is always satisfied, but if the current overlap is quite large (which may not be feasible in the first place), it may be less costly to increase the overlap. Also observe that the cost difference in (5) increases as the production rate decreases. This is consistent with our earlier observation that the difference between the ELP and ZSP solutions is highest when the production rates are low. In our problem set, the difference between the ELP and ZSP solutions virtually disappears when the idle time in the solutions reaches about 4% of the cycle duration. Production systems are rarely scheduled so that the machines are so highly utilized. If there are reasons, such as planned maintenance, for including planned idle time in excess of, say, 5% the production planner can choose either the equal-lot or the zero-switch assumption and obtain similar results. Equal-Lot-Zero-Switch Results The ELZSP approach performed very poorly on average. The costs of the ELZSP solutions average over 18% higher than the corresponding ZSP solutions. In some cases, the ELZSP solutions yield costs that are many times that of the corresponding ZSP solutions. This discrepancy occurs even though we use Dobson's sequencing algorithm, which should provide sequences favorable to the ELZSP because it is based on a formulation with the zero-switch and equal-lot assumptions. The poor performance of the ELZSP is directly related to the issue of feasibility. Overall, 4% of the ELZSPs in our set are infeasible, but for certain combinations of parameter ranges, over half the ELZSPs solutions are infeasible. This illustrates the potential difficulty of finding feasible solutions under equal-lot and zero-switch restrictions. In basic-period approaches, where both restrictions are imposed, this problem is overcome by iteratively considering differences sequences and by (perhaps simultaneously) changing the number of times a part is produced in a cycle.

14 In a fixed-sequence problem, the only way to move toward feasibility is to increase the cycle duration. In those problems where the ELZSP costs are extremely high, the idle time is also quite high, whereas in the corresponding ZSP and ELP solutions, there is little or no idle time. Since the cycle stock holding costs per unit time are roughly proportional to the cycle duration, the ELZSP solution incurs a significant penalty due to this effect. We observed that optimal ZSP schedules rarely include idle time. The average idle time across all problems is only about 1% of the cycle duration. Using arguments similar to those given in our discussion of the dominance of ZSP solutions over ELP solutions, it is possible to obtain limited analytical results (not reported here) on conditions for the optimality of zero idle time. While zero idle time may be theoretically optimal in many cases, it is rarely feasible in practice. Uncertainties inherent in most production facilities require that some idle time be planned into the system. When the facility operates three shifts per day, idle time must be planned for maintenance of equipment. In these situations, it may be impossible to plan production so that there is no idle time in the schedule. As we add idle time and increase the cycle length, it becomes more likely that the solution will satisfy both the equal-lot and zero-switch assumptions. We can bound the increase in the cost of the schedule that results from increasing the cycle length by assuming that the equal-lot and zero-switch assumptions are satisfied before the increase. (Once these assumptions are satisfied, any increase in the cycle duration leads to a proportional increase in cycle stock. For shorter cycle durations, increases in the cycle duration may cause allow more equal batch sizes and more equally spaced production runs, both of which help to decrease inventory holding costs. Consequently, less-than-proportional increases in cycle stock costs may occur.) From this, we can determine an upper bound on the rate of increase in the cycle stock cost as the cycle duration increases. This may be partially offset by a reduction in the setup cost per unit time if setup costs are positive. In the worst case, when setup costs are zero, we obtain no additional advantage from amortizing the setup costs over a longer cycle. Under this assumption, the cost penalty percentage from

15 increasing T so that there is 100k% idle time is bounded above by k / (1 - p - k). For large p, this penalty may be high. We found that when idle time is 6% of the total cycle duration, virtually all the ELP, ZSP and ELZSP solutions are equivalent. For a problem with p = 0.75, 6% idle time may result in a cost penalty as high as 32%. This is quite large, but may be unavoidable because of considerations discussed earlier. When it is unavoidable, then the simplifying assumptions of the ELZSP may be useful in simplifying other related problems. Limitations of the Sequencing Procedure One result of our study is somewhat surprising: the common cycle (CC) solution is less costly than the corresponding ZSP solution in 29% of the problems. This generally occurs when a part is produced in two successive intervals, as in the sequence A-B-C-A (although not all sequences of this form lead to this result). We also observed CC solutions that are less costly than the ZSP solutions even when there are no apparent anomalies in the sequence generated by Dobson's procedure. We have not been able discern any patterns that would allow us to characterize when the CC solution would cost less than the corresponding ZSP solution. More surprising is the fact that in 2,419 of the 4,316 problems, the cost of the CC is less than the cost of the LBP, which means that no solution with the given sequence could outperform the CC solution. This raises questions concerning the use of Dobson's sequencing algorithm. Dobson's algorithm is intuitively appealing and accommodates more general conditions than earlier approaches to the sequencing problem, most of which are for the basic period approach. Many basic period approaches guarantee that the common cycle solution will be found, if it is less costly than other sequences considered, whereas Dobson's algorithm may not consider the CC solution. As it is easy to calculate the CC solution, one could evaluate it before choosing a solution to implement Table 3 presents results from the 1897 problems that remain after eliminating those problems where the CC solutions give lower costs than the ELP and ZSP solutions. Replacing the ZSP and

16 ELP solutions with the CC solutions whenever the CC is less does not change the qualitative results of our comparison, but it does change the magnitude of the differences reported. Table 3 Summary of Results From Reduced Problem Set Averages of the Ratio of Optimal Costs* ELP CC ELZSP LBP ZSP 0.969 0.963 0.848 1.009 ELP 0.992 0.863 1.036 CC 0.875 1.043 ELZSP 1.244 *Each entry is the average ratio of the optimal cost of the solution in the corresponding row to the cost of the solution in the corresponding column. Ratios are included only where both problems are feasible. Local Minima for the General Problem Thus far we have reported results from our study of different versions of the general fixedsequence ELSP. As mentioned earlier, the objective function of the general problem is nonconvex. This led us to investigate the possibility of finding improved solutions in the region of either the ELP or the ZSP solutions. The general problem was solved for one hundred and fifty problem vectors. Solutions were found with standard descent procedures using the ELP and ZSP solutions as starting points. In all cases, when the ZSP solution is used as a starting point, the minimization returns the same solution. When the ELP solution is used as a starting point, the minimization returns either the same solution or the ZSP solution. Consequently, it appears that solutions to the ZSP and ELP may represent local minima for GP, and that more sophisticated procedures are needed to improve on the better of the two solutions.

17 4. Summary In this paper, we formulate a fixed-sequence ELSP that helps to clarify relationships among three popular versions of the problem. A variation of the formulation provides a lower bound on the cost of any solution for the corresponding fixed sequence. Our computational study demonstrates and suggests why the zero-switch may be superior to the equal-lot approach. When there is about 4% idle time in the schedule, however, the ELP and ZSP approaches yield quite similar solutions. Moreover, when the idle time in the schedule rises to 6%, the costs of the equal-lot, zero-switch, and equal-lot-zero-switch solutions are identical in virtually all the problems in our data set. We develop an upper bound on the penalty for adding idle time to the schedule, and use a simple example to show that it can be very high. This is demonstrated further by the generally weak (and occasionally very poor) performance of the ELZSP, where significant idle time must be added to the schedule in order to achieve feasibility. On the other hand, idle time is often necessary, either as a buffer against uncertainty or to perform preventive maintenance. When idle time must be included in the production plan, one can justify choosing the solution approach that best fits the operational patterns and needs of the facility. In some cases, this may allow inclusion of simplifying assumptions that facilitate modeling larger problems related to the ELSP. Finally, our computational study suggests that solving the ELSP once, with a fixed sequence, may be an inappropriate approach. Although Dobson's sequencing algorithm is intuitively appealing, often common-cycle solutions turn out to be less costly than the corresponding zero-switch solutions for the sequence given by Dobson's procedure. This observation suggests the need for further investigation of the sequencing issue.

18 REFERENCES [1] Bomberger, E. 1966. "A Dynamic Programming Approach to a Lot Size Scheduling Problem." Management Science. 12:778-784. [2] Delporte, C.M., and L.J. Thomas. 1977. "Lot Sizing and Sequencing for N Products on One Facility." Management Science. 23:1070-1079. [3] Dobson, G. 1987. "The Economic Lot-scheduling Problem —Achieving Feasibility Using Time-varying Lot Sizes." Operations Research. 5:764-771. [4] Doll, C.L., and D.C. Whybark. 1973. "An Iterative Procedure for the Single-machine Multi-product Lot Scheduling Problem." Management Science. 20:50-55. [5] Elmaghraby, S.E. 1978. "The Economic Lot Scheduling Problem (ELSP): Review and Extensions." Management Science. 24:587-598. [6] Gallego, G. 1990. "Scheduling the Production of Several Items with Random Demands in a Single Facility." Management Science. 36:1579-1592. [7] Hanssmann, F. 1962. Operations Research in Production and Inventory Control. New York: John Wiley & Sons: 158-160. [8] Hodgson, T.J., and H.L.W. Nuttle. 1986. "A Note on Linear Programming and the Single Machine Lot Size Scheduling Problem." International Journal of Production Research. 24:939-943. [9] Hsu, W.L. 1983. "On the General Feasibility Test of Scheduling Lot Sizes for Several Products on One Machine." Management Science. 29:93-105. [10] Jones, P.C., and R. R. Inman. 1989. "When is the Economic Lot Scheduling Problem Easy?" IE Transactions. 21:11-20. [11] Maxwell, W.L. 1964. "The Scheduling of Economic Lot Sizes." Naval Research Logistics Quarterly. 11:89-124. [12] Maxwell, W.L., and H. Singh. 1986. "Scheduling Cyclic Production on Several Identical Machines." Operations Research. 34:460-463.

19 [13] Muckstadt, J.A., and H.M. Singer. 1978. "Comments on'Single Cycle Continuous Review Policies for Arborescent Production/Inventory Systems."' Management Science. 24:1766-1768. [14] Rogers, J. 1958. "A Computational Approach to the Lot Scheduling Problem." Management Science. 3:264-291. [15] Roundy, R. 1989. "Rounding off to Powers of Two in Continuous Relaxations of Capacitated Lot Sizing Problems." Management Science. 35:1433-1442. [16] Schweitzer, P.J. and E.A. Silver. 1983. "Mathematical Pitfalls in the One Machine Multiproduct Economic Lot Scheduling Problem." Operations Research. 31:401-405. [17] Zipkin, P. H. 1991. "Computing Optimal Lot Sizes in the Economic Lot Scheduling Problem." Operations Research. 39:56-64.

20 - interval 3 run Q)* I /' I'',. /: ^ * r'./ /'x Time 3 idle ks setup WM run Figure 1. Example of zero-switch schedule.

21 interval 3 ame 1_ idle ramr setup r- un I% IN run

22 4') ^ - -- ------------— l — [ii I, I Thie -- TsOs^! Time __'.0_ i,? o i Dil -"' II^~P Pfi- D[i] Figure 3a. Additional holding costs from overlap To,i in the ith interval, where To,i <fiT(1 - P[i]). By construction, the area of the parallelogram is equal to the area of the rectangle (defined by the dashed lines), and is given byfiTxoD[i].

23 fi T ~o,i D[i]: < -- oi f, < 3i T l in Figure 3b. Additional holding costs from overlap Xo,i in the ith interval, where,o.i >fiT(l - P[i]). By construnction, the area of the parallelogram is equal to the area of the rectangle (defined by the dashed lines), and is given byfiTToD[i].

24 1< ~~~~~~T~PBe~ -time P --- -p~ —--- /2 -1 Ir -Tp^/2 T A/ _ — - machine conflict production for part B, interval 1 production for part A, intervals 2 and 4 rI production for part C, interval 3 Figure. Ae 4. An example of an ELZSP solution where there is a machine conflict. The time required to produce each part is represented by a filled box. The horizon shown represents T time units. Note that interval 1 does not begin at the origin.

25 time - II' f2TpA I I production for part A, intervals 2 and 4.rn production for part C, interval 3 Figure 5. Resolving the infeasibility by violating the equal-lot requirement. The dotted line is the inventory trajectory of part A under the equal-lot-zero-switch schedule. The time required to produce each part is shown by a filled box. The upper set of boxes shows the equal-lot-zero-switch requirements, and the lower set shows the requirements under the revised, zero-switch schedule.

i 0 391 15o47 35 3571 TpA/2 + TpB T- T/2 I.A Eite Tp^/ 2 PTPTPA --- T/2 -B > —------ l production for part B, interval 1 k production for part A, intervals 2 and 4 - production for part C, interval 3 Figure 6. Resolving the infeasibility by violating the zero-switch rule in interval 2, but maintaining equal lots. The dotted line is the inventory trajectory of part A under the equallot-zero-switch schedule. The time required to produce each part is shown by a filled box. The upper set of boxes shows the equal-lot-zero-switch requirements, and the lower set shows the requirements under the revised, equal-lot schedule.