Tradeoff idling and shutting down

Description
The report focuses on topic like Cost Implications of Translating Idle Periods to Reduced Production Rates, Production line tradeoffs, alternative production strategies, basic scheduling functionality

PRODUCTION

AND OPERATIONS MANAGEMENT Vol. 5. No. 4. Winter 1996 Prinfed in U.S.A.

EVALUATING THE TRADE-OFFS BETWEEN IDLING AND SHUTTING DOWN PRODUCTION LINES IN PROCESS INDUSTRIES *
RENATO DE MATTA AND TAN MILLER

Departmentof ManagementSciences, Collegeof Business Administration, University of Iowa, Iowa City, Iowa 52242, USA Warner Lambert Co., Morris Plains, New Jersey07950, USA
The costs of starting-up and shutting down production lines (and plants) in a process industry are often quite high. Therefore, when a plant’s capacity significantly exceeds its forecast demand over an annual planning horizon, a manufacturer must either plan temporary production line shutdowns during the year, or plan to temporarily idle production lines without formally shutting line(s) down. The trade-offs between these two strategies can be complex. In this paper, we propose a methodology to evaluate the impact of both strategies on a plant’s production costs by developing an analytical model based on the authors’ experience with several process industries. (PRODUCTION PLANNING WITH CHANGEOVER; MANUFACTURING OPERATIONS AND SCHEDULING; INTEGER ALGORITHMS)

1. Introduction

The costs of starting-up and shutting down production lines (and plants) in process industries are often quite high (e.g., the ceramic tile and chemical processing industries). Thus, in their tactical (annual) production planning activity, process industries tend to schedule capacity first and then materials (Taylor, Seward, and Bolander 198 1). This contrasts with material-oriented industries such as the fabrication and assembly industries. The substantial production line start-up and shutdown costs pose a particularly difficult dilemma for a process industry manufacturer when a plant’s capacity significantly exceeds its known and forecasted demands over an annual planning horizon. In this situation, the manufacturer must either plan to temporarily shut production lines down during the year, or idle the lines without formally shutting down, or run its plant at production rates lower than design capacity. Naturally, it can also choose a mix of these strategies. In this paper, we focus on modeling the trade-off between the shutdown and idle decision. The key difference between these alternatives is that by idling a line rather than shutting it down, one avoids the substantial shutdown and start-up costs. We also show how, in manufacturing environments such as the ceramic tile industry, we can implicitly address the production slowdown option by simply modeling the shutdown versus idle decision. The trade-offs between shutdown and idle strategies can be complex. For example, by temporarily idling a production line, a process manufacturer can save on shutdown and
* Received July 1995; revision received May 1996; accepted October 1996. 371 1059-~478/96/0504/371$1.25
Copyright 0 1996, Production and Operations Management Society

372

RENATO

DE

MATTA

AND

TAN

MILLER

start-up costs, perhaps reduce the loss of goodwill associated with temporary furloughs and rehiring, and so on. Additionally, by keeping a line idle, but ready to produce, a firm can maintain a higher degree of manufacturing flexibility in cases in which, for example, two production lines can make the same product and shutting one line down limits the capability to produce certain products to one line. However, below some level of demand for plant capacity, the cost inefficiencies of keeping a line available, but idle, more than outweigh any relative advantages of maintaining a line’s immediate availability. In this paper, we develop a methodology to evaluate the impact of these strategies on a plant’s production costs based upon our experience working with several process industries.
Background

We begin with a brief description of the production process, the manufacturing network, and the production planning activities of a ceramic tile manufacturer and distributor. This will provide the reader with an example of the type of manufacturing environment where one can best apply the production planning and scheduling methodology developed in this paper (refer to Matta and Miller 1993 and Miller and Liberatore 1989 for details). Our example firm manufactures standard and custom-decorated ceramic tiles for walls, floors, and swimming pools. The firm operates multiple manufacturing facilities across the United States and supplies in excessof 100 points of sale nationally. The manufacturing capabilities of the individual plants vary. Certain product lines are produced by several plants, while others are manufactured exclusively by only one plant. The firm’s manufacturing facilities use several different production processes, all of which begin with a crushing and milling procedure and end in the firing of glazed and unglazed tiles in large kilns. This company, similar to many process industry firms, faces a combination of known customer orders as well as uncertain future demands for which it must allocate capacity in advance. Thus, the annual forecast plays an important role in the firm’s ability to efficiently utilize its manufacturing capacity. A brief review of the firm’s annual production and distribution planning approach will help put into context the methodology that we propose to evaluate the trade-offs between shutting a line down and temporarily idling a production line. The example firm uses large-scale linear programming and mixed integer optimization models to create integrated annual production and distribution plans. These models represent the first stage in the firm’s hierarchical production planning process. The primary outputs from these models include annual production capacity and product mix allocations for the firm’s individual plants, distribution plans that establish sourcing patterns (i.e., plant/ product family/ sales region assignments), and aggregate inventory projections. The optimization models are multiperiod models that generate quarterly production plans for each plant. These cost minimization models typically evaluate variable production costs, freight costs, warehouse handling costs, and period-to-period inventory carrying costs. Mixed integer models are occasionally used to handle special constraints such as sole sourcing, and where necessary, minimum run quantities (see Matta and Miller 1993). For annual or tactical network-wide planning purposes, quarterly time buckets represent the smallest practical time increment. Besides such issues as model size, for distribution planning one needs consistent sourcing plans over time. For example, a sales region requires consistent plant sourcing because the same colored tiles manufactured in two different plants would actually appear slightly different from each other and could not be used together. For planning purposes at the plant level, the annual production plan must be disaggregated into weekly production requirements. It is at this point that if the production levels allocated to a plant in the annual planning model did not fully utilize the plant’s capacity over the planning horizon, then a decision is made whether to fully shut one or

PRODUCTION

LINE

TRADE-OFFS

373

more lines down for an extended period of time or to idle temporarily one or more production lines. This represents the decision point in the planning process where the model we propose can assist. The model presented in this paper represents an enhancement to some previous production scheduling models (see Liberatore and Miller 1985 and Matta and Guignard 1994), which we developed and tested for the tactical decision level in a hierarchical production planning system at our example firm. This system generally followed the classic hierarchical production planning approaches developed by Hax and Meal ( 1975 ) and Bitran and Hax ( 1977); however, it employed a simpler product aggregation scheme and used a mixed integer programming approach for production scheduling. The inability of the previous models to evaluate the shutdown versus idle tradeoff motivated the development of the model presented here.
2. Literature

A large body of literature in production scheduling focuses on economic lot sizing with constant demand rates (see survey in Elmaghraby 1978). The objective is to find schedules with fixed cycle times (e.g., Bomberger 1966; Stankard and Gupta 1969; Hodgson 1970; Doll and Whybark 1973; Jones and Inman 1989) or variable cycle times (e.g., Dobson 1987; Roundy 1989) such that holding and setup costs are minimized. Lotsizing problems with variable demand rates where products are produced in noncyclic patterns have also received considerable attention (see for example, Zangwill 1966; Sobel 1970; Karmarkar, Kekre, and Kekre 1987; and Karmarkar and Schrage 1985). One way to categorize production scheduling problems is by distinguishing the type of setup cost used. In some problems, the setup cost is a fixed charge incurred in every period with positive production. We usually observe this type of setup cost in discrete product manufacturing (see Manne 1958; Wagner and Whitin 1958; Veinott 1969; Schrage 1982; Wolsey 1989). When a product can occupy a production line over an extended period, however, the setup is generally carried over from one period to the next without incurring any additional setup cost. The setup costs observed in this case can include the following: a changeover cost when the line switches to producing a different product; a start-up cost when the line switches from off to on; a shutdown cost when the line switches from on to oe and the cost of an idle period or idling cost that is incurred when the production line is setup, but is not producing any positive quantity. We encounter these setup costs in continuous product manufacturing environments such as tile manufacturing. Production rates in many process industries are fixed; a line produces at a fixed rate or it does not produce at all. Often, manufacturing technology, quality, or economics dictate that a line must run at full capacity or not at all. Scheduling a single production line that produces at a fixed rate has been studied extensively in the past. For instance, Glassey ( 1968) proposed a dynamic programming method with unit changeover costs to solve a multiproduct, single production line scheduling problem. Gascon and Leachman ( 1988) extended Glassey’s study by considering nonsequence-dependent changeover and shutdown costs. Driscoll and Emmons ( 1977) considered the case with sequence-dependent changeover costs. Sobel ( 1969) formulated a single product problem where startup, shutdown, manufacturing and holding costs are minimized. The product demand in each period occurs in integral multiples of the production rate. Sobel developed a dynamic programming approach that finds the shortest route in an acylic network. Problems that have been successfully solved in the aforementioned studies are relatively small in size because the solution times of these dynamic programming-based algorithms increase exponentially with the number of products and periods. Other approaches also have been proposed to solve the single production line problem. For example, Magnanti and Vachani ( 1990) formulated a binary integer programming

374

RENATO

DE MATTA

AND

TAN

MILLER

model to determine the optimal trade-off among idling costs, changeover costs, and holding costs. By adding nontrivial facet inequalities to their model, they obtained near integer linear programming solutions. Matta ( 1994) developed a Lagrangian relaxation procedure to solve Magnanti and Vachani’s model and obtained near optimal solutions within a reasonable amount of time for much larger problems than those that had been solved previously. Few studies have treated the production scheduling of several products on multiple production lines. Liberatore and Miller ( 1985 ) were the first to address the problem with their formulation for a ceramic tile plant that had multiple, nonparallel production lines. Liberatore, Miller, and Guignard-Spielberg ( 1987) (see also Guignard and Liberatore 1992) enhanced this model by adapting preprocessing techniques from Bradley, Hammer, and Wolsey ( 1974) and Kianfar ( 197 1) to tighten the problem constraints. They conducted computational experiments using MPSX-MIP/ 370 that were based on data from the tile company. The method proved very effective in strengthening the linear programming bound, but took considerable time to preprocess even reasonably sized problems as the preprocessing method is itself a combinatorial problem. Matta and Guignard ( 1994) developed a Lagrangian relaxation-based method that outperforms earlier procedures and does not require any problem preprocessing to find good feasible schedules. In summary, a wealth of previous research and literature exists on production scheduling problems. The model that we now present contributes to this literature by evaluating line shutdown versus line idling strategies (when plant capacity exceeds demand) for multiproduct, multi-production line plants. To our knowledge, none of the production scheduling studies of multiproduct, multi-production line problems simultaneously evaluate these strategies. The following outlines the remainder of this paper. In section 3, we formulate a general model to evaluate the trade-offs between temporarily idling and shutting a line(s) down. This section also discusses our use of idle periods in the proposed model, and the equivalence in certain manufacturing environments between schedules with idle periods and schedules with reduced production rates. We will observe that this equivalence enhances the flexibility and value of our model for real world scheduling applications. Finally, we review in this section the impact of idle periods on the cost structure of the production process. In section 4, we consider two special cases of our general model and present some computational results. Section 5 concludes this paper with other applications of the general model and some remarks on the benefits of our scheduling approach.
3. Problem Statement

The following product family scheduling model minimizes the total of variable manufacturing costs, production line changeover/setup costs, inventory carrying costs, idling costs and shutdown costs. The cost of restarting a production line after it has been shutdown is included in the cost of a line shutdown to recognize that a shutdown decision also implies future start-up costs. This also prevents the model from generating solutions that shut down production lines near the end of planning horizons without considering that a start-up cost will be required in a future period beyond the current planning horizon. Additionally, whatever appropriate one time costs associated with the shutdown and start-up process should be included, for instance, the cost to repair a kiln if a shutdown typically damages the kiln. For purposes of the formulation, we also assume that production rates remain constant during each scheduling period. Note that in the manufacturing environments that we have based this model on, a major changeover under normal conditions does not reduce the output of a production line, and therefore, changeover time can be ignored. The products considered in our model have variable demand rates and different demand patterns. Finally, backlogging of demand is not allowed.

PRODUCTION LINE TRADE-OFFS

375

3.1. Product Family Scheduling Model
Our model makes use of the following notation: N is the number of products. L is the number of lines. T is the number of periods (in weeks). iistheindexontheproduct(i=O, l,..., N). Product zero is not a real product. If a production line j is assigned to product zero during period t, this means that j is shutdown during period t. j is the index on the production lines or processors (j = 1, . . . , L), t is the index on the production period (t = 1, . . . , T). Li is the set of lines that can produce product i. Mj is the set of products that can be produced on line j. cij is the unit variable manufacturing cost to produce product i on line j. r, is the cost per period of keeping line j temporarily idle while it is setup to produce i. hi is the unit carrying cost per period of product i. Soj is the fixed cost per period to keep a production line j shutdown, beginning with the first period in which the production line is shutdown. Qoj is the fixed cost to shut down production line j during the&St period of a line shutdown. The fixed cost to restart production line j at some future point is also included in qoj. Also, note that the value of qoj must exclude Soj to prevent doublecounting Soj during the first period. qUis the fixed cost to changeover to product i on line j, for i = 1, . . . , N. pii is the fixed production quantity per period of product i on line j. dj, is the demand of product i in period t. Zio is the starting inventory of product i. IMAXi, is the maximum inventory level allowed (or upper inventory limit) of product i at the end of period t. ZMZNi, is the minimum inventory level (or lower inventory target) planned for product i at the end of period t. Aj is the maximum number of consecutive periods that a production line j can be temporarily idle. Bj is the maximum number of periods of temporary idling allowed over the entire planning horizon on line j. B is the maximum number of periods in total of temporary idling allowed over the entire planning horizon over all lines j E L. As noted, in this formulation we adopt the convention that if a line j produces product zero during a period t, this indicates that the line is shutdown during that period. The decision variables in our formulation are as follows: WV, = 1, i 0,
Y/, =

if product i is produced on line j in period t; otherwise, if line j is setup to produce product i in period t; otherwise, if production otherwise. on line j changes to product i in period t;

1, i 0,

z,, =

1, 1 0,

Z/l = the end of period inventory of product i in period t. The problem formulation
PROBLEM(P)

is as follows:

376 minimize i
f=l

RENATO

DE

MATTA

AND

TAN

MILLER

2
i=l

C (ciipijWi,
jELf

+ rij( Yij - WUl) + qijzij,)

(1) f=I i=l

subject to:
Iil 2 ZMINily lil I IMAXi,, C
iEMj

i= i=
= 13
jELi,

1,2 9 . . . 7 N, 1,2 ,..., N, j = 1,2,. . . , L, i=O,1,2 i= 1,2 ,..., ,..., N,

t= t=

1,2,...,T 1,2,...,
t= T T

(2)

(3) (4) ,T
T

yijl +
-

YOjl

1,2,...,
t=

Zij,

2

Yol

Yijl-1 ,
jELi,

N, t=

1,2,..

(5)
(6)

wi, 5. Yjjt,
Z
iEMj

1,2,..., 1,

2+1 C
k=t-Aj+I

(Ytjk-

Ky/c)lAj,

t=A. J, * * * 9 T-

(7)
(8)

(9)
1 Iit = Z/O + C jELi C k=l Pijwijk 1 C k=l dik,

i= i=

1,2 ,..., 1,2 ,..., ,..., N,

N, N,

t= 1,2,...,T
t= t= t=

(10) (11) (12)

0 5 Wjl 5 1, integer, j E Li , 0 5 Ygl I 1, integer, j E Li , zij* 2 0,
jELi,

1,2,...,T 1,2,...,T
T.

i = 0, 1,2, . . . , N, i=O,1,2

(13) Constraints (2) prevent the backlogging of demand and ensure that the minimum inventory requirements are satisfied. Constraints (3) preclude solutions that produce excess inventory to avoid the potentially high costs of shutting down a line. Whether this would occur naturally depends on the comparative costs associated with shutting down a production line, idling a production line, and producing and carrying excess inventory. Note that one can set the maximum allowable level of inventory of product i through the parameter ZMAXit . Constraints (4) and ( 12) assure that any production line is setup to produce exactly one product (including product 0) during each period. They constrain each line j during period t to one of two conditions: the line is producing a product or the line is shutdown and requires start-up procedures before it can resume production. Constraints (5) relate the changeover variable (Z,,) to the production setup variables in the current and previous periods ( YUl and YVll-1, respectively). A changeover to product i on line j occurs during period t, if and only if Ytil = 1 and YUIP1 = 0. It is easily demonstrated that constraints ( 5) force Z,, to be one only if YUl = 1 and YVt-l = 0; in all other cases Z,, must be zero. Therefore, Z,, need not explicitly be specified as a binary variable. Constraints (6) assure that production takes place only when a production line j is setup to produce a product. However, when no production takes place on a line that is

1,2 ,...,

PRODUCTION

LINE

TRADE-OFFS

377

setup to produce a real product (i.e., any product but product zero), then we say the line is temporarily idle. To understand what we mean by saying that a production line is temporarily idle, we return briefly to the ceramic tile manufacturing example. While in operation, a kiln requires that unfired tile be moving through it constantly to absorb the heat generated by the kiln. If a kiln is lit and there is no tile moving through the kiln absorbing the heat, a fire will likely result. Thus, if a manufacturer wishes to idle a production line without turning off the kiln (i.e., without shutting the line down), it must push nonsaleable dummy or slug tile through the kiln to absorb the heat and prevent a fire. Manufacturers will do this in cases where they wish to stop or slow production temporarily without having to incur the costs and/or allocate the resources to turn off a kiln and then refire the kiln at some future time. To maintain a production line in this state typically has a direct cost and perhaps even an opportunity cost. For example, in the case of the ceramic tile manufacturer, one must still pay the fuel cost to keep the kiln burning, the labor and/or machine costs to set dummy tiles on kiln cars that move through the kiln, and so on. These costs are incorporated in the objective function as rti( YUL- wUt,), where YUt - Wi, is equal to one when line j is idle during period t and zero in all other cases. Quite often the shutdown of a production line (i.e., Y,, = 1) involves two types of costs and activities. One type consists of the set of fixed costs and activities required to shut a production line down (i.e., turn off a kiln) and restart a production line. These activities and costs may be thought of as one time actions and the binary variable Zoj, and its associated coefficient qoj reflect these actions. Constraints (5) assure that the model assessesthese costs only once (i.e., in one period) during a shutdown on a line j. The second type of costs and activities associated with the shutdown of a production line may be thought of as the fixed cost per period (Soj) incurred while the line is shutdown. For example, a down production line may still require periodic maintenance to assure its successful restart in some future period. Also, the shutdown of a production line may result in temporary furloughs and workmen’s compensation payments or some other directly related cost or opportunity cost. Typically, this type of cost is incurred each period in a relatively fixed amount. The binary variable Yo, and its associated coefficient Soj reflect this periodic cost. Constraints (7) establish a limit on the maximum number of consecutive periods that a model solution can allow a production line j to sit idle or nonproductive. Constraints (7) are optional management policy constraints. These constraints allow the scheduler to specify that a production line cannot indefinitely remain open, but nonproductive, even if cost relationships indicate that this represents a lower cost alternative to shutting a line down. These optional constraints allow the possibility that there may be other factors that are difficult to quantify which dictate that a production line cannot remain open, but nonproductive beyond some period of time. Constraints ( 8 ) and ( 9 ) represent additional optional management policy constraints designed to address the same issue as constraints ( 7 ) . Constraints ( 8 ) limit the total number of periods that any production linej can sit temporarily idle over the entire planning horizon, while constraints (9) limit the number of periods that all L lines of a plant collectively can remain idle, but not shutdown, over a planning horizon. Finally, constraints ( lo), in combination with the nonnegativity constraints (2) and the integrality constraints ( 11)) assure that demand for each product i in period t is satisfied. 3.2. The Equivalence Between Idle Periods and Reduced Production Rates The purpose of the production scheduling model [Problem (P)] is to assist a manufacturer in deciding whether to plan: ( 1) the temporary shutdown of production line(s), (2) the idling of production line(s), or ( 3) a combination of both strategies in response to forecast demand levels that do not fully utilize the plant’s available production capacity.

378

RENATO

DE MATTA

AND TAN MILLER

A solution to this model will clearly identify recommended periods to shutdown and/ or idle production lines. However, for our example tile manufacturer, a solution to this model also implicitly provides a recommended reduced production rate plan. How a scheduler would translate a solution from this model which recommends some idle production periods into planned reduced production rates requires an explanation. The scheduler can essentially follow a plan from this model without strictly adhering to a schedule that indicates that a line should sit idle, but should not be shut down. For example, suppose that a plan shows that a line should sit idle for 2 weeks and that the line should produce 3 weeks of a product at the regular production rate of 50,000 units per week. One can also interpret this as 5 weeks of production of a product with the 2 weeks of idle time (i.e., firing slug tiles for our example firm) interspersed over the 5 weeks. This could translate into 5 weeks of production at a reduced rate of 30,000 units per week rather than 3 weeks at 50,000 units each week. Table 1 illustrates how a production scheduler can convert a model solution (with idle periods) into a planned schedule with reduced rates. In practice, kilns would continue to fire 50,000 units each week (30,000 units of real tile and 20,000 units of slug tile) during the 5-week period. The costs of putting the slug tile through the kiln are still correctly captured by the model. Note that there would be a relatively minor change in the overall inventory carrying costs of the slightly modified production schedule. Specifically, the inventory carrying costs would increase slightly because the modified plan (with a reduced production rate) would produce inventory further in advance of demand than the original plan. However, for our example firm, this incremental inventory holding cost was minimal. Additionally, the individual period demands will also be satisfied by such an approach. (Obviously one must intersperse the idle period(s) over the periods with positive productionfiZZowing the idle periods to assure that demand constraints remain satisfied.) This represents one example of how to translate planned idle periods into production at reduced rates. Naturally, one also has the option to follow exactly the model’s solution. (The reader interested in modeling methods designed strictly to determine optimal reduced production rates is referred to Silver 1990). At a more general level, one can also take the total production of all real products (i = 1)...) N) scheduled by a model solution for a production line over a planning horizon and divide this by the number of periods in which the model schedules the production line up (i.e., producing or idle). This will yield an actual average production rate per period, which can be compared to the plant’s design capacity (based on the scheduled
TABLE 1 The Eauivalence Between Idle Periods and Reduced Production Schedule with Idle Periods Period 1 2 3 4 5 6 I Product 1 i Idle Idle 2 2 2 Production Rate 20,000 20,000 50,000 50,000 50,000 Product 1 1 2 2 2 2 2 Equivalent Schedule with Reduced Rates* Production Rate 20,000 20,000 30,000 30,000 30,000 30,000 30,000

.

. .

. .

. .

. .

5; * There would be a minor change in the overall inventory carrying cost of the translated solution.

PRODUCTION

LINE TRADE-OFFS

379

production mix), to determine the de facto reduced production rate if periods of production of slug tiles (i.e., idle periods) have been scheduled. An important benefit of the equivalence between idle (but not shutdown) periods and reduced production rates is that it prevents one from having to define a model with multiple production rates (or even a range of rates) to produce a product on a particular production line. Given that one would also have to define different costs associated with producing a product at different rates, this could clearly create an even more complex problem than the one formulated here. 3.3. Cost Implications
of Translating

Idle Periods to Reduced Production

Rates

Using our approach to plan and implement reduced production rates can have important ramifications for the (implicit) cost structure of the production process. By setting appropriate cost coefficients in the scheduling model for individual periods when a line is idle, the planner can effectively capture the costs of operating a plant at rates below the plant’s design capacity. The simple example shown in Table 2 can perhaps best illustrate this concept. Table 2 shows how the average variable cost (AVC) of production per unit changes depending on the number of idle periods scheduled (if any) in a planning horizon. In this hypothetical example of a plant with a single production line, the AVC per unit is $10.00 when the plant produces its design capacity of 52,000 units per year (or 52 weeks of production at a fixed rate of 1000 units per week with a variable cost of $10,000 per week). When the 52-week schedule includes one idle period, the AVC per unit increases to $10.157, and with two idle periods, the AVC rises to $10.32, and so on. The increase in the AVC results because in this example, we assume that there is a variable cost of $8,000 per week to keep a line idle, but not shut down. Again for our example firm, this $8,000 might represent the direct labor cost of producing the dummy product (e.g., workers must still feed nonsaleable slug tiles to absorb the kiln’s heat), the weekly fuel cost, etc. The raw material cost-let us assume it represents 20% of the variable cost of production-would not be incurred during an idle period because the line does not produce a real product. In this example then, each idle period will reduce the annual output by 100% of the weekly production rate, but reduce the annual variable costs by only 20% of the weekly rate. This results in an AVC per unit that will increase with each additional idle period scheduled. The effect of this approach is to create a curve-linear AVC cost curve (see Figure 1) moving upwards (to a higher cost per unit) and to the left (to a lower annual output) from a lowest cost point at annual design capacity. Finally, we should point out that there may exist limitations on the maximum number of scheduled idle periods and shutdown periods over which the model’s implicit cost

TABLE 2 Annual Production Costs.for Alternative Production Schedules No. of Periods Line Is Idle (i.e., producing a. dummy product) 1 2 3 4

No. of Periods of Real Production 52 51 50 49 48

Annual Variable cost ($) 520,000 5 18,000 5 16,000 5 14,000 5 12,000

Annual Production (real product) 52,000 5 1,000 50,000 49,000 48,000

Average Cost Per Unit (AW $10.000 $10.157 $10.320 $10.490 $10.667

Percentage Increase in AVC (%) 1.57 3.20 4.90 6.67

380

RENATO

DE MATTA

AND TAN MILLER

48

49

50 Production (000)

51

52

FIGURE 1. Average Variable Cost Per Unit for Alternative Production Schedules.

structure remains valid. For example, let’s consider the cost of a high volume raw material that a plant uses in its production process. Quite often, a plant’s (and/or a firm’s) unit purchase cost is determined by a vendor on the basis of annual purchase volume (i.e., a quantity based discount structure). Thus, a plant’s unit cost to purchase raw materials may assume some minimum annual purchase level. Below this minimum, the plant’s raw materials purchase cost per unit will increase, and therefore, so will the plant’s variable production cost per unit. In such a situation, this would imply that above some maximum number of idle plus shutdown periods in a solution to problem (P) , the variable production cost coefficients would become understated. From a real world perspective, this potential limitation does not represent a major problem, but rather an issue to remain aware of. We will now review two different approaches for solving model (P). 4. Solution Approach The production scheduling formulation presented in Section 3 represents a difficult model to solve directly. We have experimented with two different approaches to solve this model. Each of these approaches has particular advantages and limitations, and each is best applied to a specific manufacturing setting. In this section, we briefly review each solution approach and its application. We also provide some computational results obtained by solving problems created from historical demand and production data at three of the plants of our example tile manufacturing firm. The first approach generates cuts or valid inequalities to model (P) and solves the model using an exact solution procedure. The second approach uses a Lagrangian-based production scheduling heuristic. The following sections discuss these approaches in detail. 4.1. Strengthening Model (P) Using Cuts

This approach to solving model (P) extends the concept of partition inequality first developed by Magnanti and Vachani ( 1990) for the multiproduct, single production line problem. The approach is applicable to several manufacturing settings: 1. A plant with several production lines where each production line produces a unique set of products; 2. A plant which has several identical production lines that can produce the same products at the same production rates; and,

PRODUCTION LINE TRADE-OFFS

381

3. A plant where any product that can be produced on more than one production line is produced at the same rate by each line. We adapt model (P) to these manufacturing settings by making several minor modifications to the model. Denote
Pi = P” UT
.iELi,

i=

1,2 ,...,

N, pi ,

Di=

idik-IiO+IMINit
k=l I/

1

i
k=l

dik-Iio+IMAXil

)i 1
pi N, t= 1,2,...,T
(2’)

where r 1 implies the next highest integer. Expressing the inventory variables in terms of Wtil and Yijl, and replacing constraints (2 ) , ( 3 ) , and ( 10) with ;:
k=l

2 wij/crD;,
jELi

i=

I,2 ,...,

f: k=l

2 jELi

l’f’&lD$+,

i=

1,2 ,...,

N,

t=

1,2,...,

T

(3’)

we obtain the following formulation:
PROBLEM(P')

minimize

i
f=l

5 2 (cOtWul + siiYii + qiiZij,) + K
i=O jELi

subject to: (2’), (3’), (4), (5), (6), (7), (8), (9), (ll), (12), and (13), where Coj, = 0 andcii,=(Cijpi-rij+hipi(T-t+ l))fori= 1,2,...,N,andwhere K= -2
i=l

E f: hidik.
f=l

k=l

Since K is a constant, it can be eliminated from the objective function. Model (P’) with the exclusion of constraints (4)) ( 7 ), ( 8 ) , and ( 9)) decomposes into several independent single product, multi-production line problems. Each single product problem can be represented as a fixed charge network flow model. We can generate cut sets or valid inequalities from these network flow models and append the cut sets to the linear programming ( LP) relaxation of problem (P’) . The LP relaxation of problem (P’) is obtained by relaxing the integrality restrictions in constraints ( 11) and ( 12). This LP relaxation (with cuts appended) yields a strong lower bound to problem (P’), and in certain cases, near integer LP solutions. Using the cut sets derived from the network flow models to strengthen the LP bound, we can then solve problem (P’) directly by conventional branch-and-bound techniques. Note that we develop two different types of cuts from the network flow models to append to the LP relaxation of problem (P’). A type I cut establishes relationships among setup, changeover, production and inventory variables, while a type II cut relates the setup and changeover variables only. Appendix A details how we generate both types of cuts. 4.2. A Lagrangian-Based Approach The Lagrangian-based heuristic procedure discussed in this section can address multiproduct, multi-production line problems. Unlike the cut set approach reviewed in Section 4.1, we can apply the Lagrangian method to manufacturing plants where multiple pro-

382

RENATO

DE MATTA

AND TAN MILLER

duction lines can produce the same product or products, but at different rates. For this reason, the Lagrangian approach represents a more generally applicable method than does the cut set approach. To summarize, the range of manufacturing settings where the Lagrangian approach is applicable includes the following: i. A plant in settings ( I), (2)) and (3) described in Section 4.1 that the cut set approach can address, or ii. A plant that can produce multiple products on multiple lines at multiple production rates. The Lagrangian approach is a four-staged procedure. The four stages are as follows: 1. Determine an initial solution to a subcase of model (P) using the Lagrangian relaxation approach. (Note that in general the Lagrangian solution obtained is infeasible.) 2. Apply a heuristic (auction) procedure to the Lagrangian solution developed in stage 1 to find a feasible solution to the subcase of model (P) and model (P) itself. 3. Improve the solution found in stage 2 by rearranging product assignments over the entire planning horizon on individual production lines. (Opportunities to lower overall costs by trading off inventory carrying costs and changeover costs, while holding other costs constant, are evaluated at this stage.) 4. Improve the stage 3 solution by evaluating the trade-offs between incurring temporary idling costs and shutdown costs during periods when there is no production on a line. Table 3 provides an overview of what decisions are determined and what costs are evaluated at each of the four stages of our algorithm. The algorithm we propose here is an iterative one in which a sequential pass through all four stages represents one full iteration of the algorithm. As we detail later, in solving test problems, we simply ran this algorithm for 200 iterations and selected the best solution obtained. Our heuristic approach is an extension of the solution procedure for what we will term the capacity-oriented scheduling problem ( CSP) . The CSP is a subcase of model (P), i.e., the CSP is model (P) with the production variables ( Wi,) strictly equal to the setup variables (Y,,). As such, CSP models do not allow a line to have temporary idle periods. Rather, during each period, CSP models force a line either to produce a product or to shutdown. Additionally, CSP models do not have minimum and maximum limits on

TABLE 3 Decisions and Costs Evaluated by Stages Costs Evaluated Stage
1

Variable Production
X X

Inventory Carrying
X X

Changeover
X X

Shutdown
X

Idling

Final Decisions Determined None Number of periods of production of each product on each line. Production periods when each line will produce its previously assigned product mix. Shutdown or idle a line during periods when it is not producing any product.

2 3 4

X
X*

X* X*

X

X X

X'

X

X

* Remain constant, not affected by the procedure in this stage.

PRODUCTION

LINE

TRADE-OFFS

383

end-of-period inventories. Liberatore and Miller ( 1985) formulated the CSP as a mixed integer linear programming model that Matta and Guignard ( 1994) modified and solved successfully using a Lagrangian relaxation approach. We will modify Matta and Guignard’s approach to find good feasible schedules to model (P) . Briefly, Matta and Guignard solved an equivalent but slightly different formulation of the CSP where demand and capacity constraints with a linear programming transportation problem structure are used in lieu of constraints ( 10) in model (P) . In particular, Matta and Guignard relaxed the complicating constraints, i.e., the demand constraints, and replaced them with a penalty term in the objective function. The Lagrangian problem then decomposes into several single-line scheduling problems that are solved independently. These are shortest path problems. Matta and Guignard obtained feasible schedules from the Lagrangian solutions using a product-to-production line assignment heuristic that eliminates product shortages period-by-period by reassigning production lines from overproduced products to underproduced products. The Lagrangian problem and assignment heuristic provide solution values that are lower and upper bounds, respectively. Matta and Guignard iteratively solved the Lagrangian problem and applied the heuristic to every Lagrangian solution. The lower and upper bounds are brought closer together by optimizing the penalty coefficients (Lagrangian multipliers) in the Lagrangian dual problem using the subgradient method. The process terminates when the gap between the bounds is smaller than a given tolerance or when the number of iterations exceeds a specified limit. In test runs on a VAX 8700 computer, Matta and Guignard obtained good bounds in less than 1 f CPU minutes for problems with five to eight production lines, five to eight product families, and with up to 52 time periods. Model (P) has more complicating constraints than the CSP and relaxing all of them to obtain the CSP’S Lagrangian problem yields a Lagrangian dual problem that is much harder to optimize. The difficulty arises from the large number of Lagrangian multipliers. Alternatively, relaxing a smaller subset of complicating constraints yields Lagrangian problems that are difficult to solve. Therefore, as previously introduced, we utilize the Lagrangian relaxation approach to CSP as the first step toward obtaining feasible solutions to model (P). In particular, we solve CSP’s Lagrangian problem in the first stage and find a feasible schedule for model (P) in the second stage. We refer to this second stage procedure as the auction procedure. The auction procedure, similar to Matta and Guignard’s product-to-production line assignment heuristic, uses the CSP’S Lagrangian solution as a starting point. The auction procedure has several advantages over the productto-production line assignment heuristic. First, the auction procedure avoids making myopic scheduling decisions. Namely, to eliminate a product shortage, each product assignment on any given production line is made only after examining all the periods when the line is not producing. Second, our approach utilizes the dual price information, which is not used in Matta and Guignard’s heuristic procedure, to prioritize the assignment of products with shortages to production lines. Third, the auction procedure constrains the end-of-period inventories in the model solution from exceeding their maximum limits. Finally, the auction procedure is suitable for parallel implementation. Appendix B offers a detailed description of the auction procedure and also describes how stages 3 and 4 of our algorithm improve the solution yielded by the auction procedure in stage 2.
4.3. Computatinal Study

We now present computational results using the approaches just described. As noted, we obtained the results by solving problems created from historical demand and production data at three of the plants of our example tile manufacturing firm. These plants

384

RENATO

DE MATTA

AND

TAN

MILLER

each produced 5 product families and have 2, 4, and 5 production The production possibilities at these plants are as follows:
Plant Product A B C D E I X 1 II X X X X I II Plant 2 III X X X X X IV X I X X II

lines, respectively.
Plant III 3 IV X X X V X X X

X X X

X

X X X

At plant 1, both production lines Z and ZZproduced product family A at the same weekly rate and cost. However, for any given product family at plants 2 and 3, all the production lines that produced the product family operated at different weekly production rates and costs. Therefore, the cut set approach detailed in Section 4.1 could only be applied to problems at plant 1. We generated a number of different test problems by scaling actual historical demand down by a fixed percentage (e.g., IO%, 15%, and so on). This preserved the actual variation in the demand. The ratio of demand to total plant capacity ranged from a low of 63% to a high of 86% for our test problems. For all the test problems, the average coefficient of variation of demand (i.e., the standard deviation divided by the mean) for the five product families was 22% and the demand patterns of individual products varied widely. We assumed that the maximum number of consecutive idle periods allowed per production line, the maximum number of idle periods allowed over the entire planning horizon per line, and the maximum number of total idle periods allowed plant-wide were 3, 6, and 9 periods, respectively. The minimum end-of-period inventory limit was twice the average weekly demand. The maximum end-of-period inventory limit was 10 weeks worth of production (i.e., 10 times the average weekly production rate), while the initial product inventories equaled 6 times the average weekly demand. We assumed that the annual product holding cost was 26% of the average unit variable manufacturing cost. In four of the problems, we doubled the actual changeover, idle period and shutdown costs to determine how this would affect the computation time and the solution quality. We solved the test problems using the optimization subroutine library (OSL) on an IBM 3090 computer (refer to the OSL Users Guide and Reference 1992 ) . A FORTRAN program generated the problems and valid inequalities in MPS format. We solved each problem at plant 1 with and without the cuts appended to model (P’) and each problem at plants 2 and 3, without the cuts, for 1,200 CPU seconds. Including the cuts, the average total number of constraints for the 13, 26, and 52 period problems at plant 1 were 293, 592, and 1,396, respectively. The number of cuts generated averaged IO%, 13%, and 14.5% of the number of regular constraints for the 13, 26, and 52 period problems, respectively, a modest increase in the problem size. Columns (4)-( 9) of Table 4 present the results. Appending cuts to model (P’) to solve the problems at plant I produced 20%, 7%, and 3.6% average increases in the LP values for the 13, 26, and 52 period problems, respectively. None of the problems yielded an optimal integer solution. Nevertheless, the strong LP values reduced the integerality gaps by an average of 86%, 63%, and 57% for the 13,26, and 52 period problems, respectively. Setting the changeover, idle period, and shutdown costs to two times the actual costs did not produce a significant change in the solution quality. Also, the wide variations in the ratio of demand to the total plant capacity did not affect the solution quality. Without using any cuts, the integrality gaps of problems at plants 2 and 3 were surprisingly not as large as those obtained from problems at plant 1.

TABLE

4

Computational Results for the Tile Manufacturing Plant Producing 5 Products on 2. 4 and 5 Production Lines at Plants I, 2 and 3, Respectivelv

(5) (12)
V(H) W-U (%I 14.0 10.2 5.7 4.2 4.4 4.5 - V(LP2) V(IP) WP) (“ro) VW (%) Value VW) Cl4 VW) (%) (8) - V(LPI) V(IP) (10) Heuristic V(H) (9) - V(LP2) (11) - V(LP1)

(6)

(2)

(1)

Plant Number

Number of Periods

(3) Demand Over Capacity (%I

(4) LP Value Without cuts VLPI ) 6)

LP Value With cuts* V(LP2) 6) (7) Value of Integer Solution+ ww (8

Proportion of Cuts in the Problem (“Jo)

(13) CPU Seconds+ 3 3 3 3 3 3 2 8 g z c 3 cl

1

13

8

26

52

604,82 1 689,56 1 743,968 757,479 826,646 837,039 1,393,352 I,40 1,047 1,642,918 1,690,556 3,429,700 3,388,678 9 11 10 10 12 13 12 13 13 14 15 3.7 2.8 2.4 2.1 2.5 2.1 2.9 3.7 3.9 3.4 4.1 3.3 -

2

26 52

3

13 26 52

64 718 77 80 86# 86 67 67 82 83 748 78 68 52 69 50 62 60 708

492,478 564,163 611,993 638,157 712,881 716,061 1,298,200 1,308,49 1 1,551,134 1,582,984 3,309,290 3,272,248 3,841,470 6,108,492 8,538,462 5,122,693 12,317,396 26,5 18,960 27,047,746

at plant problems

-

628,120 709,475 762,156 773,587 847,572 854,918 1,435,092 1,455,516 1,709,064 1,756,568 3,577,5 15 3,504,699 4,133,452 7,103,388 10,163,342 5,699, I59 12,960,459 27,414,494 28,960,944 702,476 767,748 789,020 790,698 864,320 876,365 1,479,131 1,467,07 I 1,690,969 1,724,045 3,474,339 3,484,627 4,029,765 6,803,004 9,068,650 5,582,465 12.589.116 26,927,086 27,954,400 I were 293, 592, and 1,396, respectively. 30.0 26.5 22.4 19.3 17.5 18.3 12.2 10.8 8.3 8.2 4.8 6.1 4.7 10.4 5.8 8.2 2.2 1.5 3.2

21.6 20.5 19.7 17.5 15.9 16.2 9.5 10.1 9.3 9.9 7.5 6.6 7.1 14.0 16.0 10.1 5.0 3.3 6.6

5.8 4.5 2.9 1.9 1.3 6.1 4.7 10.2 5.8 8.2 2.2 1.5 3.2

9 8 9 9 28 28 11 41 33 4 16 67 68

* The + The * The r The

average total number of constraints (including the cuts) for the 13, 26, and 52 period value of the best integer solution found in 1,200 CPU seconds (IBM 3090). length of time the heuristic spent to obtain V(H) on an IBM 3090. problems have double the actual setup, changeover, idle period, and shutdown costs.

386

RENATO

DE

MATTA

AND

TAN

MILLER

We coded the Lagrangian-based heuristic in FORTRAN and ran the program on an IBM 3090. We again solved problems from the three plants with planning horizons of 13, 26, and 52 periods. We measured the gap between the value of the best solution obtained by the heuristic procedure and the LP value. Columns ( lo)-( 13) of Table 4 show the results. In step 1 of the Lagrangian procedure, we optimized the CSP’S Lagrangian dual problem using the subgradient method (Held, Wolfe and Crowder 1974). We set the maximum number of iterations to 200. The starting stepsize constant that worked best was one. We halved the stepsize constant whenever the Lagrangian dual failed to increase for 27 consecutive iterations. Our heuristic procedure produced rather mixed results for the 13 period problems. Namely, the 13 period problems at plant 1 with demand to capacity ratios between 64% and 70% yielded significant gaps, while those with ratios of 77% or more yielded gaps which were less than 6%. For the majority of the test problems of 26 and 52 periods, the heuristic procedure yielded integer solutions with gaps ranging from 2% to 6% (column 12 of Table 4). We did not observe any significant change in solution quality and computational time in problems where the changeover, idle period and shutdown costs were twice as large as the actual costs. The heuristic procedure required less than 70 CPU seconds to obtain solutions comparable to the first approach. This constituted a significant saving in the computation time. The largest end-of-period inventory quantity in the feasible integer solutions we obtained was 6 weeks of demand. At plants 2 and 3, some production lines were totally dedicated to producing certain products. We also observed in all the solutions that the production lines did not produce any excess units to avoid incurring the shutdown costs even for the problems where we doubled the shutdown costs. To simulate a manufacturing setting where one would want to avoid shutting a line down by overproducing certain products, we modified the data from our example firm by setting the shutdown cost, qoj, to maxi (cii + hi)pu. Also, we reduced the maximum end-of-period inventory from 10 to 6 weeks worth of production and doubled the actual changeover, idling and weekly shutdown costs. Again test results did not show any degradation of the heuristic’s performance under these conditions when compared to the results shown in Table 4. In summary, our tests indicated that the methods we proposed, i.e., adding cut sets to strengthen model (P) and solving model (P) using an exact solution method and directly solving model (P) via a heuristic, are promising. Because the first method ultimately solves scheduling problems by a direct branch-and-bound technique, large problems can still present a major challenge (e.g., problems with more complex production possibilities). Overall, the Lagrangian heuristic approach is robust and more efficient than the first method in that tests have demonstrated that it can quickly solve more complex problems with up to 52 production periods. 5. Conclusion The scheduling approach developed in this paper offers flexibility in the sense that it can support both annual plant production planning activities and short-run scheduling decisions. Although we formulated model (P) specifically to address the trade-offs between shutting a production line down temporarily and idling a production line, this model clearly can serve as a decision support tool to schedule normal short-run operations. It considers the cost factors generally found in a traditional scheduling model for process industries (changeover costs, inventory carrying costs, and variable production costs), and it creates a schedule for producing product families, by production line for a plant. The constraints in the model designed to evaluate alternative production strategies for periods of weak demand do not detract from the basic “scheduling” functionality of the model, and in fact, enhance the insights that this model can provide. In periods of strong

PRODUCTION

LINE TRADE-OFFS

387

demand where a plant must operate at full capacity, these constraints will simply not influence the scheduling solution obtained. The two solution approaches that we have developed for solving model (P) both display potential. The cut set methodology, which employs the concept of partition inequality (Magnanti and Vachani 1990)) and the Lagrangian-based auction procedure, which builds upon previous research by Matta and Guignard ( 1994)) both produced promising results. The auction procedure also has some intuitive appeal in that it captures aspects of how managers make trade-offs in assigning products to production lines and how they decide whether to leave a line idle or shutdown. In conclusion, we believe that the general modeling approach proposed in this paper offers an enhanced methodology for evaluating the trade-offs between temporarily shutting down or idling production lines during periods when demand does not fully utilize the plant capacity.
Appendix A. Strengthening Model (P’) Using Cuts

As noted, we can tighten the LP relaxation of model P’ by appending type I and type II cuts to this problem. Recall that type I cuts establish relationships among setup, changeover, production and inventory variables, while type II cuts establish relationships between setup and changeover variables. We generate these cuts by decomposing problem (P’) into independent single product, multi-production line problems and creating network flow model representations of these individual problems. Consider the fixed charge network flow graph shown in Figure A I. It represents a single product, two production line scheduling problem with 3 periods and 2 units of demand. The network has I6 nodes. The I2 nodes in the center, which are labeled with the production line numberj and the production period t” or t’, are transhipment nodes. The 3 nodes on the right are demand periods t with I unit of demand each at t = I and t = 3. The single node S on the left is a source node with 2 units of supply. The variable I+‘, is a flow variable that is I if the solution sends a flow from [j, t’] to [t]. This arc has a unit capacity and the cost of a unit flow on this arc is cc,. The flow on arc ([t], [t + I]) is 4, the ending inventory in period t, and the cost is 0 since cV1includes the holding cost. The variables Z, and Ytil are indicator variables where each variable is equal to I if the solution

z12

1

\
FIGURE A I. The Network Corresponding to a Single Product, Two Production Line Problem.

388

RENATO

DE

MATTA

AND

TAN

MILLER

sends a positive flow from S to node [j, t”] and nodes [j, t”] to [j, t’], respectively. Thus a flow on arc ([I, 2”], [ 1, 2’1) implies Yin = 1. This could mean that Y,,, = 1 or Z i i2 = 1, i.e., sending a flow on arc ( [ 1, I “1, [I, I’]) or (S, [I, 2”]). A type I cut is obtained, for example, by a cutset (Q, Q’) with Q’ = { [l, 3”], [I, 2’1, [1,3’],[2, 3”], [2,2’], [2, 3’1, [2], [3]}andQ= U\Q’where Uisthenodeset.Sincethesetp’hasoneunit of demand that must be met by a flow from Q to Q’, the following inequality is valid for all solutions to the problem: I, + Y,,, + Z,,, + Y,,, + ZizX + 1 2 2. But I, = IV,,, + IV,,, - 1; therefore, IV,,, + Y1i2 + Z1,3 + IV,,, + Y,,, + Z123 2 2. Notice that variable Z may exceed 1 when we append this inequality to model (P’) . Thus,weneedtoaddO<Zij,<l,jELj,i=1,2,.. .,N,t=l,2 ,..., Ttomodel(P’). A type II cut pertains to setup and changeover. To satisfy a unit requirement at a particular period requires a setup (i.e., Y,, = 1) and possibly a changeover (i.e., Z,, = 1) either during that period or during a previous period. Examples of a type II cut are as follows:

yl,,

+

yl22

+

&,3

+

z,23

2 1.

Appendix

B.

The Auction

Procedure

This appendix describes the auction procedure (stage 2) and stages 3 and 4 of the Lagrangian approach that we use to find feasible solutions to model (P). In the first stage of our algorithm, recall that we solve a Lagrangian relaxation of the CSP model. At this stage, and during the auction procedure in stage 2, we minimize the sum of variable manufacturing, inventory carrying, changeover, and shutdown costs. The Lagrangian solution yields a production schedule for each production line that typically is infeasible because of product shortages (i.e., the products with unsatisfied demands and minimum inventory requirements). We shall refer to product shortages in the Lagrangian solution as jobs. At this point, the algorithm proceeds to stage 2, the auction procedure, which perturbs the Lagrangian solution to obtain feasible production line schedules. This automated auction heuristic can be thought of as a bidding process that we describe as follows. Initially, production lines that have overproduced products during certain periods are shut down during these periods. We say a line has overproduced a product in a certain period when its end-of-period inventory exceeds the maximum. If it has been exceeded, we reduce the inventory by arbitrarily selecting a production line to shut down. Next a job rist is drawn where jobs are listed in chronologicai order. This job list includes job due dates and imputed values. The imputed values are measures of relative importance of accomplishing the jobs. We utilize the Lagrangian multipliers yielded by the Lagrangian dual solution as the imputed values. A production or bidproposal for each production line is then prepared which contains the production quantities and production costs ofjobs that can be produced on the production line. Note that a proposal may contain a fraction of a job. It is natural for jobs with large imputed values to be given higher production priority on a production line. That is, our procedure will allocate these jobs to periods where the least expensive production capacity is still available, thereby moving these jobs to the top of the list on our bid proposal. However, from experience, when drawing up a bid proposal, we found it necessary to schedule the first k percent of the jobs on the top of the job list (i.e., those at the beginning of the chronological list). This prevents jobs with high imputed values, which are due in the middle or at the end of the planning horizon, from using up the capacity of a production line in earlier periods. This can occur when jobs due in early periods have lower imputed values than jobs due in the middle and the end of the planning horizon. Empirically, we observed that the value of k that worked best for the range of problems we solved is 30%. For the remaining 70% of the jobs, we then determine for each production line when to produce each job such that we maximize the difference between the imputed value and the production cost of the job. Next, upon completing the bid proposals for the different production lines, we assign the jobs to production lines as follows. For each item on the job list, we find the single production line that can perform the job with the least cost. We also find several production lines that can perform the job as a group. The job is then assigned either to the single production line or the group of production lines, whichever has the lower cost and yields an end-of-period product inventory which does not exceed the maximum inventory limit. In some cases,two or more rounds of bidding may be necessary to assign all jobs. However, once all jobs have been assigned, that is, all product shortages have been eliminated, then the auction procedure has successfully found a feasible schedule. Our algorithm then proceeds to its third and fourth stages where it generates further improvements to the feasible solution found by the auction procedure in stage 2. In the third stage, our algorithm attempts to move forward the production of any product scheduled later in the planning horizon to periods contiguous to earlier periods where that product is also scheduled to be produced without exceeding the product’s maximum inventory limit. (This is done for all products.) The algorithm will change an existing schedule on a line, if and only if the change will lower the total solution cost and still provide a feasible solution. This stage 3 procedure has two benefits. First, it can develop lower cost solutions by determining those “forward moves,” which will lower changeover costs by more than they will increase inventory carrying costs. (Note that “forward moves” do not affect the other costs considered through stage 3, namely, variable

PRODUCTION

LINE TRADE-OFFS

389

production costs and shutdown costs.) Secondly, as a by-product of the forward moves, this procedure also will often increase the consecutive periods without production on each line over the planning horizon. As we will explain shortly, this facilitates more opportunities in stage 4 to potentially substitute temporary idle periods for shutdown periods. At the close of its third stage, our algorithm has determined the period when each production line will produce its assigned product mix. It then remains in stage 4 to determine for each period that a production line does not have an assigned product to produce, whether the line should be temporarily idled or shutdown. The stage 4 procedure which makes the idle versus shutdown decisions begins by calculating the indifference point (i.e., the number of consecutive periods of nonproduction) at which the costs to shut down a line are equal to the costs to temporarily idle a line. The algorithm then evaluates all the periods of nonproduction assigned to each line in stage 3 and determines how to treat these periods. When the number of consecutive periods is less (larger) than the indifference point, the algorithm will idle (shut down) the production line. Note that the number of idle periods must satisfy the limits imposed on the number of consecutive idle periods per line, the number of total idle periods per line, and the total number of idle periods plant-wide. Also note that we have implicitly assumed that one period of temporary idling has a lower cost than the first period of a shutdown. If this were not the case, then one would not consider temporary idling as an option.

References
BITRAN, G. R. AND A. C. HAX ( 1977), “On The Design of Hierarchical Production Planning Systems,” Decisions Sciences, 8, 1, 28-55. BOMBERGER,E. E. ( 1966), “Dynamic Programming Approach to a Lot Size Scheduling Problem” Management Science, 12, 1I, 778-784. BRADLEY, G. H., P. L. HAMMER, AND L. WOL~EY ( 1974), “Coefficient Reduction for Inequalities in O-l Variables,” Mathematical Programming Study, 7, 3, 263-282. DOBSON, G. ( 1987), “The Economic Lot Scheduling Problem: Achieving Feasibility Using Time Varying Lot Sizes,” Operations Research, 35, 5, 764-77 1. DOLL, C. L. AND D. C. WHYBARK ( 1973), “An Iterative Procedure for the Single-Machine, Multi-Product Lot scheduling Problem” Management Science, 20, 1, 50-55. DRISCOLL, W. C. AND H. EMMONS ( 1977), “Scheduling Production on One Machine With Changeover Costs,” AIIE, 9,4, 388-395. ELMAGHRABY, S. E. ( 1978), “The Economic Lot Scheduling Problem (ELSP): Review and Extension,” Management Science, 24,6, 587-598. GASCON, A. AND R. C. LEACHMAN ( 1988), “A Dynamic Programming Solution of the Dynamic, Multi-Item, Single Machine Scheduling Problem,” Operations Research, 36, I, 50-56. GLASSEY,C. R. ( 1968), “Minimum Changeover Scheduling of Several Products on One Machine,” Operations Research, 16,2, 342-352. GUIGNARD, M. AND M. LIBERATORE ( 1992), “Applying a Modified Coefficient reduction Method to a Dynamic Production Scheduling Model,” European Journal of Operations Research, 56, 1, 119- 130. HAX, A. C. AND H. C. MEAL ( 1975) “Hierarchical Integration Of Production Planning And Scheduling” in Studies In the Management Sciences, Vol. 1, M. A. Geisler (ed.), Logistics, North Holland, Amsterdam. HELD, M., P. WOLFE AND H. D. CROWDER (1974), “Validation of Subgradient Optimization,” Mathematical Programming, 6, 1,62-88. HODGSON, T. J. ( 1970), “Addendum to Stankard and Gupta’s Note on Lot Size Scheduling” +znugement Science, 16, 7, 514-517. JONES,P. AND R. R. INMAN ( 1989), “When is the Economic Lot Scheduling Problem Easy?’ ZIE Transactions, 21, I, 1 I-20. KARMARKAR, U. S., S. KEKRE, AND S. KEKRE ( 1987) “The Dynamic Lotsizing Problem With Startup and Reservation Costs,” Operations Research, 35, 3, 389-398. AND L. SCHRAGE ( 1985), “The Deterministic Product Cyclic Problem,” Operations Research, 33, 2, 326-345. KIANFAR, F. ( 197 I ), “Stronger Inequalities for 0, I Integer Knapsack Functions,” Operations Research, 19, 6, 1374-1392. LIBERATORE, M. J. AND T. MILLER ( 1985), “A Hierarchical Production Planning System,” Interfaces, 15, 4, 1-11. T. MILLER, AND M. GUIGNARD-SPIELBERG ( 1987), “A Dynamic Production Scheduling System for ;he Process Industries,” Working Paper in Decision Sciences, Wharton School, University of Pennsylvania, Philadelphia. MAGNANTI, T. L. AND R. VACHANI ( 1990), “A Strong Cutting Plane Algorithm for Production Scheduling with Changeover Costs,” Operations Research, 38, 3, 456-473. MANNE, A. S. ( 1958), “Programming of Economic Lotsizes,” Management Science, 4, 2, 115-135. MATTA, R. DE ( 1994), “A Lagrangian Decomposition Solution to a Single Line, Multiproduct Scheduling Problem,” European Journal of Operations Research, 79, 1, 25-37.

390
-

RENATO

DE MATTA

AND TAN MILLER

AND M. GUIGNARD ( 1994), “Dynamic Production Scheduling for a Process Industry,” Operations Research, 42,3,492-503. AND T. C. MILLER ( 1993). “A Note on the Growth of a Production Planning System: A Case Study in Evolution,” Interfaces, 23,4, 116-122. MILLER, T. C. AND M. L. LIBERATORE ( 1989), “Production and Distribution Planning in a Process Firm,” Production and Inventory Management Journal, 30, I, 44-48. Optimization Subroutine Library ( 1992), (SC23-05 19-03), IBM Corp., Kingston, NY. ROUNDY, R. ( 1989), “Rounding off to Powers of Two in Continuous Relaxations of Capacitated Lot Sizing Problems” Management Science, 35, 12, 1433-1442. SCHRAGE,L. ( 1982), “The Multi-Product Lot Scheduling Problem” in Deterministic and Stochastic Scheduling, M. A. H. Dempster, J. K. Lenstra, and A. H. G. Rinnooy Khan (eds.). NATO Advanced Study Institute Series, D. Reidei, Holland, 233-244. SILVER E. ( 1990), ‘Deliberately Slowing Down Output in a Family Production Context,” International Journal of Production Research, 28, 1, 1l-27. SOBEL, M. ( 1969), “Smoothing Start-Up and Shut-Down Costs in Sequential Production” Operations Research, 17, 1, 133-144. ( 1970), “Smoothing Start-Up and Shut-Down Costs: Concave Case” Management Science, 17, 1,7891. STANKARD, M. F. AND K. GUPTA ( 1969), “A Note to Bombergers Approach to Lot Size Scheduling: Heuristic Proposed” Management Science, 15,7,449-452. TAYLOR, S. G., S. M. SEWARD, AND S. F. BOLANDER ( 1981). “Why the Process Industries are Different,” Production And Inventory Management Journal, 22,4,9-24. VEINOTT, A. F. ( 1964) “Production Planning with Convex Costs: A Parametric Study” Management Science, 10,3,441-460. WAGNER, H. M. AND T. M. WHITIN ( 1958), “A Dynamic Version of the Economic Lot Size Model,” Management Science, 5, I, 89-96. WOLSEY, L. ( 1989), “Uncapacitated Lotsizing Problem With Start-Up Costs,” Operations Research, 37, 5, 141-747. ZANGWILL, W. I. ( 1966). “A Deterministic Multi-Period Production Scheduling Model with Backlogging” Management Science, 13, 1, 105-I 19.



doc_406287374.pdf