£35}; .
. xx... .51.“.

<4

\, Ii, ,
>b:a o

u. .3...

.. $.13 I.

91!)?! “I.

.54..st

VA ..

'a‘K.
v.7”: 51’!“
r I!” ‘

3.

.I ‘
r'OLDJ’

.
I; i.
knead Up... p.)
“(.1 8: 6 1w]. Kr!
‘ . 319'
v . v $2) .1}?

.‘nfiu :MA.

. . .. : i .. . .
5...... . 235 9W.
. n; .

TH!)
I. 2.3.5
‘ 1'. Edd.

9L4 3....
£1! 23: ..

1 13.. rd”

1 ¢ I

vlo . r¢btvnv1DJV
.ttl votaf VIII, "no.
V; (
.?.:tl..I-: .e
lozraa:.hrt:r

..v .
MI!

I

s.
‘V

‘ I. 141 Iv»:

:

.I‘nv\el

9

._.
.33. ”22”»...
5:2..‘2 v.
-. ..w.....h,.%u in, .
. u . , . .I. z. 4459‘
v ‘1 ,5l? .?
UH." ”Hora . .5
If;

\59! .

 

55.qu. (
v. 89:19.:
. A a a???”
ta ufififigfig , i figg 2E3

D).
A 3.3! . | 2:?

‘(!I .|

 

iii/iii?" IM/I/ /I/17"‘7f'//'/7/7/7i//‘/fi//7/7i

114538358

(1 4-?» "

This is to certify that the

dissertation entitled

A PRODUCTION SCHEDULING MODEL FOR
REPETITIVE MANUFACTURING SYSTEMS

presented by
Bret Joseph Wagner
has been accepted towards fulfillment

of the requirements for

Ph. D. degree in Business Administration

 

 

[is flagge—

jO!‘ p106“) SOTOV

Date November 7, 1995

 

MSU is an Affirmative Action/Equal Opportunity Institution 0-127"

_.‘7- _._~._-

 

 

LIBRARY
Mlchigan State
University

 

 

 

PLACE N RETURN BOX to romovo this checkout from your rocord.
TO AVOID FINES rotum on or butoro doto duo.

DATE DUE DATE DUE DATE DUE

 

    

 

 

 

 

 

 

 

[—I _I I

WE
:QE
II I I

MSU II An Atflnnottvo Adm/Equal Opportunity lrltttuion

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

M..

A PRODUCTION SCHEDULING MODEL FOR
REPETITIVE MANUFACTURING SYSTEMS

By

Bret Joseph Wagner

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Management

1995

ABSTRACT

A PRODUCTION SCHEDULING MODEL FOR
REPETITIVE MANUFACTURING SYSTEMS

By

Bret Joseph Wagner

This dissertation presents the Machine State Scheduling (MS S) model, a
production planning and scheduling model for repetitive manufacturing systems. The
MSS model was evaluated using data from an actual production facility.

Although production planning and scheduling has received a great deal of attention
in the past 40 years, surprisingly few models or techniques have been applied in actual
manufacturing environments. In varying degrees, three problems have plagued most
models:

1. The models make simplifying assumptions or constrain the problem so that it
has limited applicability in real world environments.

2. The models are difficult to solve.

3. The models are hard for the typical practitioner to understand.

The MSS model addresses real-world production problems, including labor and
machine constraints, sequence-dependent setups, component part commonality and
transfer batches. It is a zero-one integer programming model that does not involve the
large number of integer variables typical of most models. While the model itself is not
simple, the underlying logic is easily explained. Further, the results of the model can be
directly translated into shop floor instructions. Thus, the model lends itself to

implementation in real production environments.

The computer program MSS Plan was developed to implement the M88 model
and demonstrate how the model could be used in an actual production environment. Two
solution methods--integer programming using GAMS/OSL and a single-pass finite loading
(SPFL) heuristic--were evaluated using production data from Walker Manufacturing’s
Newark, Ohio exhaust system production facility. While it proved difficult to find optimal
solutions to the M88 model for real-world sized problems, both the integer programming
and SPFL heuristic solutions compared favorably to the scheduling decisions of Walker
Manufacturing.

The MSS Model provides a means to schedule production in a repetitive
manufacturing environment that currently does not exist. Future research that finds
solution techniques that quickly find better solutions will enhance the usefulness of the

M88 model.

Copynghtby
BRET JOSEPH WAGNER

1995

To Cindy, Emily and Robert, who gave up

so much for me to complete this work

ACKNOWLEDGMENTS

I would like to thank the chairman of my committee, Professor Gary Ragatz, for
all of his support throughout my doctoral program. I would like to thank Professor Paul
Rubin for his diligence in reviewing this dissertation and my other committee members,
Professor Shawnee Vickery and Professor Phillip Carter, for their help and support.

I owe much to my fellow graduate students who have helped me in numerous ways
throughout my graduate program: Dave Mendez, Mike D’Itri, Byung-Kyu Sohn, Keah-
Choon Tan, Larry Fredendall, Jack Williams, Joel Litchfield, Scott O’Leary-Kelly, Bob
Marsh, Greg Magnan and Hyun-Gyu Kim. I would also like to thank Adrian Carl, Faye
Janowiak and Rick Miller.

I received a tremendous amount of support from Walker Manufacturing’s Newark,
Ohio, plant and would like to thank Bill Kames and Mike Blake for providing me with the
data to evaluate the M88 model.

I would like to thank Dick Sacher and Howard Garland of the University of
Delaware for providing the computer support to finish this work, and Pete Steacy of
GAMS Development Corp. for modelling support.

Finally, I would like to thank my parents and my mother- and father-in-law for

helping me in so many ways.

vi

TABLE OF CONTENTS

LIST OF TABLES .......................................................................................................... x
LIST OF FIGURES ......................................................................................................... x
1.0 INTRODUCTION .................................................................................................... 1
1.1 CLASSIFICATION OF PRODUCTION-INVENTORY SYSTEMS ........................ 1
1.2 TRADITIONAL APPROACHES TO PRODUCTION PLANNING AND

SCHEDULING IN REPETITIVE MANUFACTURING SYSTEMS ....................... 4
1.3 THE MACI-HNE STATE SCHEDULING APPROACH ........................................... 7
1.4 FORMAT OF THE DISSERTATION ...................................................................... 9
2.0 LITERATURE REVIEW ....................................................................................... 10
2.1 PRODUCTION PLANNING AND SCHEDULING MODELS

AND METHODS ................................................................................................... 10
2.1.1 LOT SIZING MODELS ...................................................................................... 12
3.0 THE MACHINE STATE SCHEDULING (MSS) MODEL .................................... 21
3.1 AN EXAMPLE PROBLEM ................................................................................... 22

3.2 THE MACHINE STATE SCHEDULING INTEGER

PROGRAMMING MODEL ................................................................................... 25
4.0 FINITE LOADING HEURISTIC ........................................................................... 34
5.0 PRODUCTION SYSTEM FOR MODEL EVALUATION ..................................... 49
5.1 THE WALKER MANUFACTURING ENVIRONMENT ...................................... 52

vii

5.2 WALKER PRODUCTION DATA ......................................................................... 63

5.3 HIGH AND LOW CAPACITY DEMAND SCHEDULES ..................................... 70
5.4 LABOR COSTS AND SCHEDULES ..................................................................... 72
6. 0 EVALUATION OF THE MODEL ........................................................................ 77
6.1 WALKER MANUFACTURING COMPARISON .................................................. 79
6.1.1 WALKER MANUFACTURING COST ESTIMATES ........................................ 79
6.1.2 LOWER BOUND ON COSTS ............................................................................ 80
6.2 SOLUTION OF MSS INTEGER PROGRAMMING MODELS ............................. 81
6.3 EXHAUST SYSTEM ASSEMBLY COMPARISON ............................................. 81
6.4 MUFFLER ASSEMBLY COMPARISON .............................................................. 88
6.5 PIPE AREA RESULTS .......................................................................................... 96
6.6 PRESS AREA RESULTS .................................................................................... 102
6.7 ENTIRE MODEL RESULTS ............................................................................... 102
6.8 EFFECT OF CAPACITY UTILIZATION ON SOLUTION PROCEDURES ....... 106
7.0 DISCUSSION ...................................................................................................... l 15
7.1 SOLUTION OF THE MODEL ............................................................................. 1 15
7.2 THE COMPARISON TO WALKER MANUFACTURING ................................. 1 18
7.3 OTHER BENEFITS OF THE MSS MODEL ....................................................... l 19
7.3.1 SIMPLIFIED SHOP FLOOR MANAGEMENT ................................................ 1 19
7.3.2 REDUCED LEAD TIMES COMPARED TO MRP ........................................... 1 19
7.3.3 PROACTIVE RESPONSE TO CHANGING DEMAND ................................... 120
7.3.4 ONE SHOP FLOOR PERFORMANCE MEASURE ......................................... 121

viii

7.3.5 BETTER MANAGEMENT OF LABOR AND MAINTENANCE ..................... 123

7.3.6 POTENTIAL FOR INCREASED DISCIPLINE ................................................ 124
7.4 MODIFICATION OF THE MODEL TO ALLOW SETUP CHANGES AT THE
END OF A PERIOD ............................................................................................ 125
8.0 CONCLUSIONS .................................................................................................. 126
LIST OF REFERENCES ............................................................................................. 127
APPENDIX
COMPUTER PROGRAM DEVELOPED FOR THE MSS MODEL .................... 130

ix

LIST OF TABLES

TABLE 2.1 CONIPARISON OF MODEL CAPABHJTIES ........................................ 19
TABLE 5.1 MUFFLER BILL OF MATERIAL DATA ................................................ 51
TABLE 5.2 WORKERS REQUIREMENTS FOR MUFFLER ASSEMBLY ................ 52
TABLE 5.3 SINGLE DIAMETER BUSHINGS ........................................................... 57
TABLE 5.4 DUAL DIAMETER BUSHING WORKCENTERS .................................. 59
TABLE 5.5 LOUVER TUBE WORKCENTERS ......................................................... 63
TABLE 5.6 SETUP TIMES FOR THE HEAD PRESS IN MINUTES ......................... 65
TABLE 5.7 SETUP TIMES FOR THE PARTITION PRESS IN MINUTES ............... 66
TABLE 5.8 SUMMARY OF 7-INCH MUFFLER PRODUCTION AREAS ................ 67
TABLE 5.9 WALKER EXHAUST SYSTEM DEMAND SCHEDULE ....................... 68
TABLE 5.9 (CONT’D) ................................................................................................. 69
TABLE 5.10 COMPONENT COST AND BEGINNING INVENTORY DATA .......... 71

TABLE 5.1 1 LOT SIZES USED FOR HIGH CAPACITY DEMAND SCHEDULE... 72

TABLE 5.12 HIGH CAPACITY DEMAND SCHEDULE ........................................... 73
TABLE 5.12 (CONT’D) ................................................................................................ 74
TABLE 5.13 WAGE RATES ....................................................................................... 75
TABLE 5.14 LABOR AVAILABILITY ....................................................................... 75
TABLE 5.15 DAYS WITH SECOND SHIFT HEAD PRODUCTION ......................... 76
TABLE 6.1 EXPERIMENTAL DESIGN ..................................................................... 78
TABLE 6.2 SOLUTIONS FOR EXHAUST SYSTEM ASSEMBLY ............................ 83

TABLE 6.3 COMPARISON OF COSTS FOR EXHAUST SYSTEM ASSEMBLY ..... 84

TABLE 6.3 (CONT'D) ................................................................................................. 85
TABLE 6.4 SOLUTIONS FOR MUFFLER ASSEMBLY ............................................ 89
TABLE 6.5 COMPARISON OF COSTS FOR MUFFLER ASSEMBLY ..................... 90
TABLE 6.5 (CONT'D) ................................................................................................. 91
TABLE 6.6 MUFFLER EOOS ..................................................................................... 96
TABLE 6.7 SOLUTIONS FOR PIPE AREA ............................................................... 99
TABLE 6.8 COMPARISON OF COSTS FOR PIPE AREA ....................................... 100
TABLE 6.8 (CONT'D) ............................................................................................... 101
TABLE 6.9 SOLUTIONS FOR PRESS AREA .......................................................... 103
TABLE 6.10 COMPARISON OF COSTS FOR PRESS AREA .................................. 104
TABLE 6.10 (CONT'D) ............................................................................................. 105

TABLE 6.11 MODEL COMPLEXITY FOR MUFFLER AND PIPE PROBLEMS... 106

TABLE 6.12 SOLUTIONS FOR TOTAL SYSTEM .................................................. 107
TABLE 6.13 COMPARISON OF COSTS FOR TOTAL SYSTEM ............................ 108
TABLE 6.13 (CONT'D) ............................................................................................. 109
TABLE 6.14 MACHINE AND LABOR CAPACITY ................................................. 1 10

TABLE 6.15 CAPACITY EXPERIMENT WITH 30 DAY PLANNING
HORIZON ............................................................................................................ l 1 1

TABLE 6.16 CAPACITY EXPERIMENT WITH 50 DAY PLANNING
HORIZON ............................................................................................................ l 12

xi

LIST OF FIGURES

FIGURE 1.1 TRADITIONAL PRODUCTION PLANNING AND SCHEDULING ....... 5
FIGURE 2.1 CONIPONENTS OF AN MRP SYSTEM ................................................ l 1
FIGURE 2.2 LOT SIZING MODEL CLASSIFICATION SCHEME ............................ 13
FIGURE 3.1 MACHINE STATE SCHEDULING EXAMPLE PROBLEM ................. 23
FIGURE 3.2 GRAPHICAL REPRESENTATION OF THE MSS SOLUTION ............ 24
FIGURE 3.3 GRAPHIC REPRESENTATION OF THE TRANSFER LIMIT
CONSTRAINT ...................................................................................................... 31
FIGURE 4.] LOW LEVEL CODING .......................................................................... 37
FIGURE 4.2 SPFL HEURISTIC - OVERVIEW OF ROUTINES ................................ 38
FIGURE 4.3 SPFL HEURISTIC - INITIALIZE ROUTINE .......................................... 40
FIGURE 4.4 SPFL HEURISTIC - INCREMENT ROUTINE ....................................... 41
FIGURE 4.5 SPFL HEURISTIC - PRODUCTION ROUTINE ..................................... 42
FIGURE 4.6 SPFL HEURISTIC - SCHEDULE ROUTINE .......................................... 43
FIGURE 4.7 SPFL HEURISTIC - ADJUST ROUTINE ................................................ 44
FIGURE 4.8 SPFL HEURISTIC - SETUP ADJUST ROUTINE ................................... 45
FIGURE 5.1 TYPICAL 7-INCH EXHAUST SYSTEM ............................................... 50
FIGURE 5.2 TYPICAL 7-INCH MUFFLER ................................................................ 50
FIGURE 5.3 THE 7-INCH EXHAUST SYSTEM PRODUCTION STRUCTURE ...... 53

FIGURE 5.4 7-INCH EXHAUST SYSTEM ASSEMBLY AREA ARRANGEMENT .54

FIGURE 5.5 ASSEMBLY CELL FOR EXHAUST SYSTEM #8289 ........................... 55

xii

FIGURE 5.6 MUFFLER ASSEMBLY LINE WORKSTATIONS ................................ 56

FIGURE 5.7 PIPE AREA LAYOUT ............................................................................ 58
FIGURE 5.8 A DUAL DIAMETER BUSHING WORKSTATION .............................. 60
FIGURE 5.9 PRESS AREA LAYOUT ......................................................................... 61
FIGURE 5.10 STOLP MACHINES ............................................................................. 62
FIGURE 5.11 PARTITION DIAL PRESS ................................................................... 64
FIGURE A1 MSS PLAN MAIN SCREEN ................................................................. 131
FIGURE A2 COMPONENT DATA INPUT SCREEN ............................................... 132
FIGURE A3 LABOR DIVISION SCREEN ............................................................... 134
FIGURE A4 WORKCENTER DEFINITION SCREEN ............................................. 135
FIGURE A6 PLANNING HORIZON SCREEN ......................................................... 138
FIGURE A7 DEMAND SCHEDULE SCREEN ......................................................... 140
FIGURE A8 LABOR SCHEDULE SCREEN ............................................................. 141
FIGURE A9 WORKCENTER AVAILABILITY SCREEN ........................................ 142
FIGURE A10 SPFL HEURISTIC RESULTS SCREENS ........................................... 144
FIGURE A11 GAMS MODEL SCREENS ................................................................. 145

xiii

1.0 INTRODUCTION

A repetitive manufacturing system intermittently produces a fixed set of relatively
high volume products and is a common and important type of manufacturing system. The
production scheduling problem in this environment is complex and effective scheduling
techniques do not exist. Numerous models and techniques have been proposed for this
problem, all of which have weaknesses and limitations. This dissertation presents the
Machine State Scheduling (MSS) model, a comprehensive production planning and
scheduling model that provides an improved capability to schedule production in repetitive
manufacturing environments. The MSS model was evaluated by applying it to the
scheduling problem faced by Walker Manufacturing, a major automotive supplier that
provides an assembled product according to the customer's demand schedule.

To define the production planning and scheduling problem, it is necessary to
classify the production environment and describe the traditional approach to the problem,

then describe how this model differs from the traditional approach.

1.1 CLASSIFICATION OF PRODUCTION-INVENTORY SYSTEMS
A number Of researchers (Bufi‘a and Taubert [1972], Buffa and Miller [1979] and
Johnson and Montgomery [1974]) suggest that production-inventory systems be classified

into four categories:

2

Pure inventory systems
Continuous production systems
Intermittent production systems
Project management

PPN?‘

Intermittent production systems are characterized by batch production of many
products using shared production equipment. A repetitive manufacturing system is a
special case of the intermittent production system in which a fixed and usually limited set
of products is produced. Repetitive production systems may be composed of a
combination of machines, workcenters, assembly stations or assembly lines and usually
exhibit a flow-shop-like work flow as opposed to the random flow of the general job shop.
Since product demand typically varies, production batches may vary in size or timing,
equipment may be operated intermittently, dedicated machines may be idled and labor may
be transferred among different pieces of equipment.

Intermittent production systems are the least understood category of production
system. Inventory theory was well developed by the 1960's, and many practical
techniques have been applied by industry and the military. Continuous production systems
have also been studied extensively, and again research has resulted in tools for industry.
Many of the factors in successful project management are hard to quantify, but PERT and
CPM have simplified the coordination of tasks and resources in a project. Research on
intermittent production systems, while voluminous, has produced few practical tools and
techniques.

Intermittent production of unique products has been the domain of job shop
research, which now is typically conducted using computer simulation. Most of this

research has centered around the evaluation of dispatching rules. Researchers have

3
developed a surprisingly large number of ways to select jobs for processing. Blackstone,
Phillips and Hogg (1982) provided a state-of-the-art evaluation of 34 dispatching rules
while Panwalker and Iskander (1977) provided a survey of over 100 dispatching rules
from the literature. A number of researchers have studied the dual resource constrained
problem (see F redendall, 1991) in which both machines and labor constrain production
options. This research has used dual dispatching rules (labor assignment and job
selection) to solve the problem. McKay, Safayeni and Buzacott (1988) point out that little
job shop research has been applied, stating that in job shop research "the problem
definition is so far removed from job-shop reality that perhaps a different name for the
research should be considered."

Material Requirements Planning (MRP) is a practical, practitioner-developed
approach to order launching and due date maintenance that requires skilled planners for
successfial implementation. In 1982, Anderson, Schroeder, Tupy and White estimated that
62% of manufacturing firms used MRP systems and in 1989 MRP systems accounted for
almost one-third of the total market for computer services.‘ Yet MRP systems have not
been very successfiIl in scheduling repetitive manufacturing systems. According to the
APICS Repetitive Manufacturing Group:

The history of floor control for repetitive manufacturing has been very
different from that of job shops. Very few companies have successfully adapted an

MRP system designed to generate shop orders to operate a repetitive

manufacturing floor. When they did, they buried themselves in transactions and
paperwork. Consequently, most repetitive manufacturing companies have

 

lNewscope Column, "Competition in Manufacturing Leads to MRP 11", Industrial
Engineering, 1991, Vol. 23, No. 7, p. 10.

4

developed their own planning and control systems. Their need is to provide
visibility and control of a flow of parts.2

The Japanese have developed Kanban systems to be used in conjunction with the
Just-In-Time (JIT) approach to manufacturing. A Kanban system is essentially an
advanced reorder-point inventory system that works well if production equipment requires
minimal setups and production managers are willing to set level production schedules, two
factors that appear to be in short supply in US. manufacturing firms.

In conclusion, repetitive manufacturing systems are an important form of
production systems for which effective production planning and scheduling techniques do
not exist. By taking a different approach to the problem, the MSS model provides a
means for converting an end-item production schedule into detailed shop floor
instructions. Because the MSS model considers the critical parameters of the real-world
repetitive manufacturing problem (sequence-dependent setups, machine capacity, labor
assignments, assembly, component commonality, etc), this research is of importance to
the repetitive manufacturing practitioner. The next two sections describe how the MSS
model differs from the traditional modeling approach to production planning and

scheduling for repetitive manufacturing systems.

1.2 TRADITIONAL APPROACHES TO PRODUCTION PLANNING AND
SCHEDULING IN REPETITIVE MANUFACTURING SYSTEMS

The traditional approach to production planning and scheduling in repetitive

manufacturing systems is to treat the problem in a hierarchical fashion. Figure 1.1

 

2APICS Repetitive Manufacturing Group, "Repetitive Manufacturing", Production and
Inventory Management, Second Quarter, 1982, p. 81.

5

Strategic

 

  
   

  

Resource
Planning

Long Range
Forecasts

 

 

 

 

Tactical

 
     
 

 

Short Term
Demand

Master Production
Scheduling

 

 

Lot Sizing

 

 

Lot Scheduling

Labor &
Machine
Capacity

 

 

 

 

____________________

 

Operational

 

Machine
Sequencing

 

 

 

 

Labor Scheduling :
and 1
Assignment I

 

 

 

FIGURE 1.1 TRADITIONAL PRODUCTION PLANNING AND SCHEDULING

6

illustrates this traditional view. Long range production planning involves determining
labor and machine capacity requirements to meet long range product demand. These
strategic decisions are typically made for a one- to two-year planning horizon and
constrain lower level decisions.

The first tactical problem is master production scheduling, which is determining
which finished products to manufacture to best meet short term demand, given labor and
machine capacity constraints. In many environments, there is no master production
scheduling decision. For example, automotive suppliers must meet dictated schedules or
face severe penalties. General Motor's Saturn division charges suppliers $500 per minute
of assembly line production delay due to tardy shipments.3

Given a master production schedule, the next problem in the traditional approach
is deciding how big production lots should be (lot sizing) and when these lots should be
released to the shop floor (lot scheduling). Ideally, these decisions should be made
simultaneously for all components. In MRP systems, lot sizing and scheduling decisions
are made separately for each component and constrain the decision for components at
lower levels in the bill of material. The lot sizing and sequencing decisions should be
made recognizing labor and machine constraints and many planning models incorporate at
least one constraint. MRP systems incorporate capacity planning as a separate process

that must be used iteratively with the MRP lot sizing and scheduling logic.

 

3Raia, Ernest, "Saturn: Rising Star", Purchasing, Vol. 115, NO. 3, September 9, 1993, p.
45.

7

With production lots sized and scheduled, the shop floor supervisor must
determine how to manage machines and workers to process production lots so that
demand is satisfied at minimum cost. The shop floor supervisor decides which production
lot to process next (the sequencing or dispatching decision) and where to assign workers
(the labor assignment decision). Although the sequencing problem has been studied
extensively, in practice this decision is made using dispatching rules. In some cases,
dispatching heuristics include behavioral parameters, e. g., which supervisor is most
convincing in his demand that his batch of parts be produced next.

While the traditional hierarchical approach attempts to simplify the production
planning and scheduling problem by sacrificing global optimality, the resulting tactical and
operational problems are still complex, and integrated solutions are not available. Von
Lanzenauer (1970) observed that "The production scheduling and the job-lot sequencing
problem remain separate in theory while being closely interrelated in practice."4 More
recently, Sum and Hill (1993) "take the position that order sizing and scheduling should be
considered simultaneously (or at least iteratively) because they are tightly

interdependent. " 5

1.3 THE MACHINE STATE SCHEDULING APPROACH
The MSS model is a zero-one integer programming model that integrates tactical

and operational decisions by focusing on the state of production equipment, i.e., which

 

4Von Lanzenauer, Christoph Haehling, "A Production Scheduling Model by Bivalent
Linear Programming", Management Science, Vol. 17, No. 1, 1970, p. 105.

5Sum, Chee-Chuong and Arthur V. Hill, "A New Framework for Manufacturing Planning
and Control Systems", Decision Sciences, Vol. 24, No. 4, July/August 1993, p. 740.

8

component are machines, workcenters and assembly lines producing in a given time
period. By constraining production to fixed time intervals, the model can determine
schedules for machines and labor in a dependent demand repetitive manufacturing system
with sequence-dependent setups. The model formulation requires a reasonable number of

integer variables. If Ci is the number of components produced on workcenter i and T is

the number of periods in the planning horizon, then the number of zero-one integer

variables in the problem (N2) is:
N z = 72 C.- (1-1)

This model takes a desired end item demand schedule and converts it into a set of
shop floor production decisions that can be easily implemented by shop floor supervisors.
The shop floor supervisor, freed from the intractable shop floor scheduling problem, can
concentrate on ensuring that labor and equipment are performing to plan.

Constraining production to a single component at a workcenter in a period is
consistent with management practice in repetitive manufacturing firms. According to the
APICS Repetitive Manufacturing Group, repetitive manufacturers use "daily run
schedules, not work orders, for control of production. Master schedules culminate in
serialized control of production which covers specific lengths of time, which is the

development Of schedules, not orders."6

 

6APICS Repetitive Manufacturing Group, "Repetitive Manufacturing", Production and
Inventory Management, Second Quarter, 1982, p. 81.

1.4 FORMAT OF THE DISSERTATION

Section 2 reviews the literature on production planning and scheduling models.
Section 3 presents the Machine State Scheduling (MSS) model. Section 4 presents the
single-pass finite loading (SPFL) heuristic that gives good solutions to MSS problems.
Section 5 presents the production environment at Walker Manufacturing, the firm that was
used to evaluate the MSS model. In Section 6, the quality of the integer programming and
SPFL heuristic solutions is evaluated and the MSS model solutions are compared to the
production scheduling decisions made at the Walker Manufacturing. Section 7 presents a
discussion of the results and Section 8 gives conclusions and recommendations for fiJture
research. Appendix A describes the methods and computer programs used to generate

solutions to the MSS model.

2.0 LITERATURE REVIEW

2.1 PRODUCTION PLANNING AND SCHEDULING MODELS AND METHODS
Most production planning and scheduling models/methods make use of at least one

of the following techniques to make the problem tractable:

1. Hierarchical Structure: The problem is solved in a hierarchical fashion, with
each solution in the hierarchy providing restrictions on the lower level
problems.

2. Aggregation/Disaggregation: The products are aggregated to reduce the size
Of the problem. The solution to the aggregate problem must then be
disaggregated to provide detailed production plans.

3. Limited Scope: A limited portion of the production planning and scheduling
problem is addressed or some of the factors of production are ignored. For
example, machine capacity constraints may be considered but labor capacity
ignored.

4. Simplifying assumptions/restrictions: For example, component part
commonality may not be allowed or production lot sizes may be restricted to
be integer multiples of the parent component lot size.

5. Local logic: Heuristics may be applied using a limited set of information in
isolation from other decisions in the production facility. Local logic produces
solutions to the scheduling problem which are locally optimal at best.
Dispatching rules and Kanban systems are examples of local logic.

MRP is the most common production planning and scheduling technique in use
today. MRP systems develop production schedules for component parts based on a time-
phased "parts explosion" using the bill of material. Figure 2.1 shows the main components
of an MRP system. The MRP lot sizing logic requires a master production schedule as an

input. Capacity requirements can be approximated at the master production schedule level

using rough-cut capacity planning techniques, or more accurately after the parts explosion

10

 

Resource
Planning

 

 

 

Rough-Cut
Capacity
Planning

 

 

   
      
 

 

Detailed
Capacity
Planning

 

 

ll

 

 

 
 
   

Aggregate
Production
Planning

 

   
   
 

 

 

    
 

Master
Production
Scheduling

 

       

Demand
Forecasting

 

 

   

 

Material
~ Requirements
Planning

 

 

 

Purchasing

  

 

      

 

 

Feedback

 

 

 

Shop
Floor

Control

 

 

FIGURE 2.1 COMPONENTS OF AN MRP SYSTEM

12

process using capacity requirements planning techniques. MRP systems use a hierarchical
structure (the bill of material) with simplifying assumptions and a limited scope to generate
production plans. MRP systems have a number of weaknesses as a result Of the

techniques used to make the production planning and scheduling problem tractable:

1) The production planning decisions are made independent of the shop floor.
MRP systems only provide batch sizes, release dates, due dates and priority
information to the shop floor, but they do not provide shop floor
production schedules.

2) The time phasing process assumes a known and constant lead time for
component part production--usually with significant slack.

3) The MRP logic assumes infinite capacity (capacity planning techniques are
separate from the explosion process).

4) Lot sizing decisions are performed level by level according to the BOM.

Lot sizing decisions at one level constrain the decisions at a lower level,
producing less than Optimal lot sizes.

2.1.1 Lot Sizing Models

A number of lot sizing models have been developed since F .W. Harris proposed
the EOQ model. Bahl, Ritzman and Gupta (1987) evaluate lot sizing models and provide
the classification scheme shown in Figure 2.2. To solve practical problems in a repetitive
production system, a lot sizing model must consider dependent demand and constraints, so
this discussion will focus primarily on MLCR models.

A second means of classifying lot sizing models is to consider the nature of
demand. Many of the earlier models were developed in the inventory theory field, and
considered demand as stochastic. Others are extensions of the EOQ model and consider

demand known and constant. More recent models use the concept of a master production

13

 

 

Production
Planning
Problems

 

 

l

 

 

 

 

Single Level
(Independent
Demand)

 

 

 

l

 

I

 

l

 

 

 

Multiple Level
(Dependent
Demand)

 

 

l

 

 

 

Unconstrained

Resources
(SLUR)

 

 

 

Constrained

Resources
(SLCR)

 

 

 

Unconstrained

Resources
(MLUR)

 

 

 

Constrained

Resources
(MLCR)

 

FIGURE 2.2 LOT SIZING MODEL CLASSIFICATION SCHEME

 

14

schedule--a varying but known production schedule for end items. The MSS model
assumes demand is known and fixed but that it may vary from period to period.

The single—level constrained resource (SLCR) problem has received considerable
attention. Elmaghraby (1978) provides a survey of the research on the economic lot
scheduling problem (ELSP), which allows multiple items but assumes only one
constrained resource and constant demand. Many heuristics have been developed for the
ELSP problem when the constant demand constraint is relaxed (Eisenhut (1975),
Vanderveken (1978), Kami and Roll (1982) among them), but these methods assume that
setups result in a cost but not in reduced capacity. In the repetitive manufacturing
environment, the setup costs are typically the labor costs associated with performing the
setup, but the loss in production capacity may be more important. A second problem with
these models is that they assume that production of an item in a period requires a setup. It
is possible that an item may be the last one produced in one period and the first one
produced in the next period, eliminating the need for a setup.

Manne (195 8), in his seminal piece, defined a zero-one integer variable for each
possible production sequence. Although this approach resulted in a large number of zero-
one integer variables, Manne showed that the large majority of these variables would be
integer when the problem was solved as a linear program. Thus, good solutions could be
achieved by rounding LP relaxations. A disadvantage of the model is that by defining
production sequences, variable lot sizes are not allowed.

The multiple-level unconstrained resource (MLUR) problem has been studied, but

a number of assumptions are usually made in addition to the assumption that resources are

15

unlimited. Component commonality is usually not allowed, constant end-item demand
rates are typically assumed and production is assumed to be instantaneous. Crowston,
Wagner and Williams (1973) proved that in this environment component lot sizes should
be integer multiples of the parent component's lot size, a proof that was later shown to be
incorrect (Williams, 1982). Unfortunately, the Crowston, Wagner and Williams paper is
frequently quoted and used to justify the assumption of integer multiple lot sizes.

As Bahl, Ritzman and Gupta point out, "A casual look at practitioner-oriented
literature such as the Production and Inventory Management journal and APICS
Conference Proceedings strongly suggests that most real-life environments are MLCR
problems. "7

Von Lanzenauer (1970) formulated a zero-one integer programming model that
considered machine capacity in the multi-level production environment. Like the Von
Lanzenauer model, the MSS model divides the production horizon into periods. Von
Lanzenauer’s model considers setups, but only as a fixed cost independent of the
production sequence. The production environment is considered to be a flowshop, with
no assembly operations. Von Lanzenauer's model contains the basic structure used in this
proposal to address a less constrained, more realistic environment. Surprisingly little has
been done with this approach since Von Lanzenauer's original paper. Bruvold and Evans
(1985) use the fixed time period concept in the single level problem to consider

sequencing multiple products on multiple production lines where setups are sequence-

 

7Bahl, Harish C., Larry P. Ritzman and Jatinder N. D. Gupta, "Determining Lot Sizes and
Resource Requirements: A Review", Operations Research, Vol. 35, No. 3, May-June
1987.

l6

dependent. Setups are considered to result in both a fixed cost and a capacity loss. A
disadvantage of their model is the number of variables required. Bruvold and Evans define

the zero-one integer variable 5,1). to determine if product i is produced on production line

j in period k. If there are N products produced on J machines in T time periods, then NJT
zero-one integer variables are required to define the production schedule. To determine
which setups occur, Bruvold and Evans define the continuous variables

¢uk , 61,11.— and 7,1,], , which are continuous variables but only take on binary values due to

constraint relationships with the variable (SJ/5' Since the subscript i and l in 7ka refer tO

product, there are 2NJT + NZJT added variables in the problem. In the MSS model

presented in Section 3, a production variable 5,], is defined similarly to Bruvold and

Evans, except the sequence-dependent setups are determined using only one continuous

variable 7,1,, resulting in NJT additional continuous variables with a corresponding

reduction in added constraints.

Smith-Daniels and Smith-Daniels (1986) developed a mixed integer programming
model for lot sizing and sequencing in packaging lines which include both major and minor
setups. A major setup may be required for changing products, while a minor setup may be
required to change package size (or vice-versa). Their model only allows major setups to
occur between fixed time periods (over the weekend, for example), and restricts
production in a period to one product family. Item production in a period can have
sequence-dependent setups, and not all items need to be produced. Item sequencing is

handled via a traveling-salesman binary variable V,-,,,, which equals one if item i is an

l7

immediate predecessor Of item m in period t. Thus, the number of zero-one variables is
proportional to the square of the number of items.

A variety of other approaches have been used to model MLUR and MLCR
problems. Prabhakar (1974) modeled a two-stage chemical processing problem using
traveling salesman binary variables. His continuous time model allowed for sequence-
dependent setups, but no assembly. While his model constrains aggregate production and
inventory in the first stage to be at least as great as aggregate production in the second
stage, his model does not require first stage production to rm: second stage
production. Thus, the model could produce a schedule where the second stage production
of a product is scheduled before the first stage production is started.

Gabbay (1979) formulated a discrete time, multi-stage, multi-item planning model
with one constraint per stage. He presented a one-pass algorithm and a hierarchical
solution procedure, however, the problem could be solved with a linear program since the
model does not consider setups.

Steinberg and Napier (1980) proposed a model that considers commonality. While
it is presented as having a network structure, the problem is solved with a mixed integer
linear programming code.

A number of researchers have considered the multi-stage problem assuming
constant end item demand as in Crowston, Wagner and Williams (1973). Blackburn and
Millen (1982) considered the multistage problem assuming child component lot sizes to be
integer multiples of the parent lot size in the context of a lot sizing procedure for an MRP

system. They developed a single pass heuristic that considers the impact of lot sizing

18

decisions at one level of the bill of material on lower level components. Moily (1986)
considered the same problem assuming lot splitting (an integer number of child component
lots is required to satisfy the demand created by a parent component lot) and provides
both an Optimal and a heuristic solution procedure.

Billington, McClain and Thomas (1983) present an integer programming model
that considers sequence-independent setups. The contribution Of their paper is product
structure compression--an optimized production technology (OPT) concept by which the
problem size is reduced by solving the problem for the few capacity-constrained facilities
and lot-for—lot lot sizing is used at unconstrained facilities.

Bahl and Ritzman (1984) present a model that combines the Manne concept of
production sequences with an integer programming lot sizing model. They develop a
solution heuristic that iterates between a production sequencing problem with fixed lot
sizes and a lot sizing model with fixed production sequences. The model only considers 2
levels-~component and end-item--and assumes that assemblies are produced lot-for-lot and
have no capacity constraints. Sum and Hill (1993) propose the integrated manufacturing
planning in continuous time (IMPICT) fi'amework, which is a late-start, capacity
constrained operation scheduling network, similar to a project scheduling network. They
present three heuristics based on order merging, order splitting and order merging and
splitting.

The production planning and scheduling literature is broad and varied. Table 2.1
provides an analysis of the more relevant models described above. This comparison

clearly shows that all of these models have significant limitations that make them

l9

 

 

 

 

 

 

 

 

 

 

 

 

 

Ed 6386.. v v 22 838623 .5.»

v v v 6386.. v v v v 82 a: 28 53m

.80 v 6356.2 7 v v v v 82 8.92 as 935%

v v v Bees. 26.6. N v E: 861%“...

.80 v v v 82 as:

v v v 2.2 .Azfio

28%? as

.80 v v 63.88 2.2 has? .8855

v v v v 32 asé 23 233m

38 6388; v v v $2 552 2a 62:85

«Sue—E. use

> v v v v v v v 82 5666: Susan

» v v v v v 52 5.58 ea 26m

3:3 as} .33 38:8 253 .355: .5530 £582 2.55.. 2.3. a; 3.2.3.

AER—o: 2.332 noun-Eh. .5330 .3359: v.8

85:5 153. i232

 

 

 

 

 

 

 

 

 

 

 

 

mE—dm<m<0 Anna—OE ho ZOm—Mafi—ZOU _.N Hum—<8

 

20
unsuitable as a general modeling approach for repetitive manufacturing systems.
Commonality frequently has been excluded from model formulations. Machine capacity is
frequently modeled, but labor constraints (constraints based on the actual workers and not
aggregate labor levels) have been excluded. Only Von Lanzenauer's model could be easily
extended to consider labor. Many models consider setups as a cost and ignore the
capacity loss. Sequence-dependent setups have only been considered in the single level
case (Bruvold and Evans) and the two level case of Prabhakar, although Prabhakar's
model incorrectly relates the timing of production quantities at each level.

The MSS model includes all of the model capabilities given in Table 2.].
Furthermore, it includes these capabilities while only making three simplifying
assumptions:

1. Only one component is produced at a workcenter in a period

2. Labor cannot be transferred between workcenters in a period.

3. Setups are performed either during a period when the workcenter is idle or at

the beginning of a period in which there is production.

The next section presents the MSS model.

3.0 THE MACHINE STATE SCHEDULING (MSS) MODEL

In the following description, component refers to components, subassemblies,
assemblies or end items. A workcenter is a collection of tools, a machine or a group of
machines Operated by one or more workers that produces one or more components using
purchased components or components produced by other workcenters. A workcenter is
buffered by inventory; that is, components used and produced by a workcenter can be
stored in work-in-process (WIP).

The fundamental concept behind the MSS model is that the production planning
and scheduling problem for repetitive manufacturing systems can be made manageable by

dividing the planning horizon into periods, then producing no more than one component at

each workcenter in the period. The zero-one integer production variable 51]: is used to
determine whether component i is being produced at workcenter j in period 1. Knowing
which components are being produced at each workcenter, it is possible to detennine

production quantities and labor requirements. By assuming setups are performed either

during periods when the workcenter is idle or at the beginning of a production period, it is
possible to include sequence-dependent setups in the model. A machine state variable Yijt

is used to keep track of which component a workcenter is set up to produce. This
variable takes on a value of one when a workcenter is set up to produce component i in
workcenter j in period t and zero if not. The machine state variable is continuous and can
take on fractional values when the workcenter is idle to represent a setup that is performed
over more than one (idle) period. The following example demonstrates the logic behind

the MSS model.

21

22

3.1 AN EXAMPLE PROBLEM

Figure 3.1 presents the data for the example problem and Figure 3.2 presents the
MSS solution. The problem requires 300 units of component A by the end of period 4.
Component A is assembled using one unit of component B and two units of component C,
where components B and C are produced in the same workcenter. Production of
components A and C require one worker, while production of component B requires two.
Two workers are available each period; thus, labor limits production to either component
B or components A and C in any period. Production periods are two hours long, resulting
in four periods in a standard eight hour day. If component C is produced in a period, up
to 150 units can be transferred in the same period to workcenter 1 for use in assembling
component A. If a setup is required to produce component C in a period, the maximum
units that can be transferred is reduced from 150 to 100 due to the production loss from
the setup.

Units of component B cannot be transferred to workcenter 1 in the same period
they are produced-~the entire quantity becomes available in the next period. Workcenter 2
starts period 1 set up to produce component B and a setup is required to switch from
production of component B to component C. These setups are sequence-dependent,
expressed in terms of the units of production lost at the beginning of a period.

The MSS solution in Figure 3.2 shows that component B is produced in the first
period, components A and C are produced in periods 2 and 3 and component A is
produced in period 4. The initial inventory of 25 units of component B, plus 50 of the

units produced in the first period are used in the assembly of component A in period 2.

23

| Bill of Material I

A

 

 

 

 

 

 

 

B C
(2)

 

 

 

 

 

 

 

Production
Information

     

Period Length Inventou Holding Cost
2 Hrs 20%lunit/yr
Demand
300 units of end item A by the end
of Period 4
Available Workers Initial Setu Workcenter 2
2

Component B

Component Data

Prod. Periods Max Number Initial Unit Cost
Coma. Center (your) Delay Transfer Workers Inventofl [S]
A l 50 0 - I 25 $30
B 2 125 l - 2 25 $20
C 2 150 - 150 l 50 $10

Production Loss from Setups
(production loss in units of the component
switched to.) T0

 

B
Switching
From

 

 

 

 

 

FIGURE 3.1 MACHINE STATE SCHEDULING EXAMPLE PROBLEM

24

v cow—om

ZO—th—Om mm: HIP .mO ZO—hflwlflmgma A<U—mm§0 N

 

N 3......— _

 

 

— eaten—

n nay—DU:

_
_
_
_
_

EN

em

N 3233235
U E28955

N $253.33
m EoEEEoU

fl $283.33
< «5:22.50

25

Units of component B used to assemble component A in periods 3 and 4 are satisfied from
inventory.

In period 2, workcenter 2 is switched from production Of component B to
production Of component C. The setup of workcenter 2 in period 2 means that only 250
units Of component C can be produced in period 2 and the maximum number of units of
period 2 production that can be transferred to workcenter 1 in period 2 is 100 units. The
transfer of 100 units of period 2 production plus the initial inventory Of 50 units is
sufficient to support the assembly of component A in period 2. Workcenter 2 produces
250 units of component C in period 3, 50 of these units are used in period 3 for assembly
of component A. Afler period 3, sufficient inventory of component C is available to
support assembly of component A in period 4.

The example Of Figures 3.1 and 3.2 illustrate the logic behind the MSS model,

which is presented in the next section.

3.2 THE MACHINE STATE SCHEDULING INTEGER PROGRAMMING
MODEL

In the following model, production periods are assumed to be of equal length with

no loss in generality.

SUBSCRIPTS:

i,i - component
j - workcenter
t - time period
(1 - labor division

VARIABLES:
Binary:
5i]!

2,];

Continuous:

7:]:

X8

Parameters:

26

1 if workcenter j is producing component i in time period t.

0 if not.
1 if an intraperiod transfer of component i can occur from

workcenter j in period t.
0 if not.

1 if workcenter j is set up to produce component i in time period t
Oifnot

Number of units of production of component i at workcenterj in
period t available after period t.

number of units of production of component i at workcenter j in
period 1 available for intraperiod transfer.

Units of component i in inventory at the end Of period t.

Production loss (in units) of component i in a workcenter j in period 1
due to a setup (assumed to be less than the period production rate
Pg)-

Wage rate for a worker in labor division d ($lperiod).
Per period holding costs for a unit of component i.
External demand for component i during period t.

The maximum number of units of component i produced at

workcenter j that can be transferred to and used at another
workcenter in the period in which they are produced.
Number of periods of delay between production of component i at

workcenter j and its availability at another workcenter. If 1,-1- > 0,
then f” = 0.

mi'ij

”dt
pi]
‘lii '

uj'y'

Uij

vi'ij

Wijd

OBJECTIVE:

CONSTRAINTS:

27

max(f,j , u”). ) where uiqj is defined below. This is only required if

setups are sequence-dependent and some but not all ”i'ij are greater
than fij-

Number of workers in labor division d in period 1.
Production rate of component i at workcenter j (units/period).

Number of units of component i used to produce a unit of component

I .

Production loss (in units) when changing production from component
i' to component i at workcenter j if setups are sequence-dependent.
max(u,.,j) = maximum production loss (in units) in switching to

product i at workcenter j if setups are sequence-dependent.
U I” - ”i'lj-

Number Of workers in labor division d required to staff workcenterj
when producing component i.

Production loss (in units) when changing the setup at workcenterj if
setups are n_ot sequence-dependent.

Minimize 2 20,!” + Z Z Z Zbdwy‘dag,
r’ t i j d t

Production/Inventory Balance:

(1)

[1.1—1+Zth,t—I,,ZYzjt - 111 = du +ZZqii'Xi'jt Vi!

J J I I

28

Labor Capacity:

(2) zzwij‘d51jt S "dt
I I

Intraperiod transfer limit:

If fij 2 all setup losses ("i'ifla then:

(3) ’71! + Z1): 3 fit

If fij < any ui'ij» then:

(3a) 11,-, + 2,], + 114(2), — 1) s f,~,-
(3b) X'jt S fij/ijt

Definition of the setup state variable 7,1,:

71]: 2- 5g“:

(4)
(5) Zr... =1

Vd,t

Vi,t where 1,}. = O

Vi,j,t where [:1 = O

\7’i,j,t where I” = 0

Vi,j,t

VIJ

If setups are not allowed during idle periods, then constraint (6) is included:

(6) 7w 2 7031-1 - Z56.

Define setup production loss ijti

(7) ert 2 ([1161]! — Z vi'ijyr'jJ-l

"

Define period production Xijt

(8)

X11: + Yin S P0511! - Zifl

Vi,_/',t

Vi,j,t

Vi,j,t

29

The objective function of the MSS model minimizes the sum of inventory holding
and labor costs. If a workcenter is producing a component in a period, then the labor
required to operate the workcenter for the entire period is charged even if only one part is
produced.

The first constraint in the model is the production/inventory balance equation. In

any period, the beginning inventory plus the production available in the period

(both Xy,;_10 and Yij!) minus the ending inventory must equal the external demand for

the component plus the dependent demand for the component from workcenters that use
the component. The parameter q,»,» can be set to allow for scrap losses, but this does result
in fractional production quantities.

A workcenter may require more than one worker. For example, an assembly line
may require a number of workers from different labor divisions (e. g. welders, assemblers,
etc). The second constraint is the labor capacity constraint which limits the number of
workers assigned to workcenters in a period.

The model allows two types of delay in the transfer and use of components. If
components produced at a workcenter are not available for use by another workcenter in

the same period they are produced, then parameter 1,-1- is the number of periods of delay

before they are available. This delay might be due to material handling restrictions (parts
transferred by forklifi, time for paint to dry or steel to cool) or it may be due to an external
process like electroplating by a supplier. Components delayed in this fashion are not
included in the inventory variable for the periods of the delay and the entire period’s

production is available 1,] periods later.

30

If components can be transferred to a workcenter during the same period in which
they are produced, it is unlikely that all components can be transferred and used within the

period. The parameter fij is the maximum number Of components that can be effectively
transferred in the period. If the intraperiod transfer limit is always greater than or equal to

the setup loss (fil- 2 um) Vi'), then the intraperiod material transfer is handled by

constraint (3). If the setup loss can be greater than the intraperiod transfer limit

(fij < any llj'jj) then an addition binary variable ,1}, is required and constraints (3 a) and

(3b) are used. These constraints are illustrated graphically in Figure 3.3.
To determine when setups occur, it is necessary to know the state of each
workcenter in every period (i.e., what component a workcenter is set up to produce). The

production variable 5,-1- indicates the state Of a workcenter when it is operating but not

when it is idle. The machine state variable 7,], is defined in terms Of the production
variable 50'" Constraint (4) requires the state variable to be one when the production

variable is one. Constraint (5) requires the sum of the state variables for a workcenter in a
period to be one. Together, constraints (4) and (5) limit a workcenter to production of

only one component in a period, making a constraint on the production variable 617'!

unnecessary. If there are no setups, then 26,-], s 1 Vi,t replaces constraints (4) and
j

(5).
If the workcenter setup can be changed only during an operating period, then
constraint (6) is added. Constraint (6) requires the state variable for state i in period t to

be one if the workcenter was in state i in period t-I unless there is production of a

31

 

 

 

 

 

 

Setup production loss is less than maximum intraperiod transfer

 

 

Setup production loss is greater than maximum intraperiod transfer

FIGURE 3.3 GRAPHIC REPRESENTATION OF THE TRANSFER LIMIT
CONSTRAINT

32

different component i' in period t. Constraints (4), (5) and (6) will force the machine state

variable 7,], to be binary even though it is defined as a continuous variable.

If n components can be produced in a workcenter, then n(n-1) state changes are
possible each period. Rather than defining a variable for each of the n(n-l) possible state

changes, constraint (7) defines the setup loss Zijt in terms of the production variable 6,},
and the machine state variable y”, . Since Vi'i' = Uij - ui'ijv the sequence-dependent setup
loss “i'ij can be expressed as (1,-1- - Vi'ij» so constraint (7) requires the setup production loss
Zijt to be greater than or equal to um]- when there is production in a period and at least a

nonpositive number when there is no production. Note that sequence-independent setup
losses are a special case of the sequence-dependent setup loss.

Constraint (8) defines the period production X ,j, + Y t'jt in terms of the production

variable 6..

y, , production rate parameter Pij and setup loss variable Zijt-

The MSS model addresses two of the seven needs of repetitive manufacturing

cited by the APIC S Repetitive Manufacturing Group:

1. Conversion of MRP Explosions to Run Schedules for Repetitive
Manufacturing.

Most companies control repetitive manufacturing by daily schedules,
but schedules covering other lengths of time are more appropriate for some
products. Floor control of repetitive manufacturing has not been addressed
in a systematic way in the United States. Every company has developed its
own in-house system. More detailed systems of planning are needed for
repetitive manufacturing. Planning should lead to improved control Of a
flow of material through a sequence of Operations. This would result in
obvious savings by reducing parts banks between Operations.

2. Planning Capacity During Production Planning and Master Scheduling.

33

This seems to be much more a problem with some companies than
others, and is most severe in multi-plant planning. If production is planned
through several stages and into final assembly, the assembly rates and parts
fabrication rates must be balanced to avoid shortfalls or excessive parts
banks between operations. A shortfall of parts is most serious, and it
should be revealed as early as possible in the planning process.8

 

8APICS Repetitive Manufacturing Group, "Repetitive Manufacturing", Production and
Inventory Management, Second Quarter, 1982, p. 85.

4.0 FINITE LOADING HEURISTIC

Although the MSS model does not require the large number of zero-one integer
variables of typical production planning and scheduling models with sequence-dependent
setups, the model is difficult to solve. Even for problems with good solutions, the time
required to find solutions with integer programming software prevents using the model
iteratively. Thus, a simple heuristic solution procedure, the single-pass finite loading
heuristic (SPFL), was developed to provide an effective solution technique so that
production planners could use the model in a trial-and-error manner.

The SPFL heuristic does not schedule setups during idle periods. Scheduling
setups during an idle period in the heuristic could result in a significant loss of capacity
since it is not possible to determine a priori which periods are idle. Allowing for setups
during an idle period requires a multiple-pass or iterative approach. The heuristic
procedure ignores cost or productivity differences at workcenters that can produce the
same component.

The following parameters are used in the SPFL heuristic and are identical to the
parameters of the MSS model in Section 3. The parameters and subscripts are not

presented in italics in this section (except for the parameter Iij and the subscript l) to

clearly distinguish the heuristic procedure from the MSS model.

Parameters
di. = External demand for component i during period t.
fij = The maximum number of units of component i produced at

workcenter j that can be transferred to and used at another
workcenter in the period in which they are produced.

34

35

15,- = Number of periods of delay between production of component i at
workcenter j and its availability at another workcenter.

nd. = Number of workers in labor division d in period t.

Pij = Production rate of component i at workcenter j (units/period).

q:;» = Number of units of component i used to produce a unit of component
i'.

um,- = Production loss (in units) when changing production from component
i' to component i at workcenter j.

Uij = m.ax(u,.,j) = maximum production loss (in units) in switching to
product i at workcenter j.

Vi'ij = Uij - Ui’ij

wiJ-d = Number of workers in labor division (1 required to staff workcenterj

when producing component i.

The variables used in the heuristic are defined below.

Variables

STATEG, t)

PROD(i, j, t)

P0T(i. i, t)

WORK(t, d)

BAL(i, t)

i if workcenter j is producing component i in period t.
= 0 if not.

Production of component i scheduled at workcenterj in
period t.

Best known upper bound on the units of component i that can
be produced at workcenter j in period t. If STATEG, M) is
not known, then POTG, j, I) = Pij - Uij V1.

# of workers in labor division d in period t who are not yet
assigned to a workcenter.

Units of component i available in period t. BAL(i, t) will take
on negative values during processing of the heuristic to
represent the need for production. If a feasible solution is
found by the heuristic all BAL(i, t) must be 2 O.

36

The subscript i represents the component and ranges from 1 to I. The subscript j
represents the workcenter and ranges from 1 to J. The time periods t are numbered from
1 to T. The component indices are assigned first in order of ascending low-level code,
then in order of descending inventory holding cost. Figure 4.1 illustrates the low-level
code concept, which was developed for MRP record processing. For example,
component B is a level 2 component because it appears at level 1 for end item A but also
appears at level 2 as a component of item H in end item G. Numbering components in
low level code order allows the SPFL heuristic to schedule production in a single pass
while considering dependent demand relationships. Numbering components in order of
descending inventory holding costs should result in relatively low inventory costs since the
SPFL heuristic will schedule production of higher holding cost components closer to the
period in which they are used. It Should be noted that low-level codes are generally
negatively correlated to inventory holding costs because components with lower low-level
codes have had more processing and are frequently assembled from components with
numerically higher low-level codes.

Figure 4.2 shows how the major routines in the heuristic are related. The initial

variable values are set in the Initialize routine. The Increment routine uses the BAL(i,t)

 

variable to determine when component production is needed. When the Increment routine
finds a period that requires component production, control is passed to the Production
routine which determines when the components should be produced. The Production
routine passes control to the Schedule routine, which updates the variables STATE(j,t),

PROD(i,j,t) and POT(i,j,t). The routine Adjust updates the BAL(i,t) variable to reflect the

37

Level

 

 

0
(ca—<9
6

G

0 G 6 9

Unit Low Level Index
Component Cost Code [i]

A $10 0 2
B 4 2 7
C 3 3 10
D 1 1 6
E 2 2 9
F 1 4 12
G 15 O 1
H 5 1 3
l 3 1 5
J 4 1 4
K 3 2 8
L 2 3 11

FIGURE 4.1 LOW LEVEL CODING

38

 

1_nit_ia_li_z_.:c_
Initializes Heuristic Variables

 

 

 

 

Increment

Controls single pass
incrementing

 

 

 

 

 

Production

 

 

 

> Determines when production Infeasrble
capacity is available

 

 

 

 

Schedule

Sets production
Updates production potential

 

 

 

 

Adjust
Determines dependent demand for scheduled production

Adjusts production potential if workcenter idle in next period
Determines if production should be updated in next period due to setup

l

Setup Adjust

 

 

 

 

 

Adds production due to setup and
corresponding dependent demand

 

 

 

FIGURE 4.2 SPF L HEURISTIC - OVERVIEW OF ROUTIN ES

39
dependent demand for the component production that was just scheduled. Since the
decision to schedule production in period t determines the state of the workcenter,
adjustments may need to be made in period t+l. If the workcenter is idle in period t+ l ,
the production potential can be adjusted since the workcenter's state is now known in
period t. If the workcenter was scheduled to produce component i in period t and was
already scheduled to produce component i in period t+l, a setup is not required in period
t+1. Since the heuristic assumed the worst-case production potential when scheduling
production in period t+1, production in period t+1 can be increased (if needed). This is
accomplished in the Setup Adjust routine. Control returns to the Production routine
either from the A_djust or Setup Adjust routine. The Production routine then checks if the
scheduled production is sufficient to cover the need identified in the Increment routine. If
not, additional production is scheduled. Otherwise, control is passed back to the
Increment routine, which continues the single pass search for periods requiring component
production. The heuristic either ends successfirlly if all component requirements are
satisfied in the Increment routine, or unsuccessfiilly if the production routine cannot
schedule sufficient production to satisfy the demand for a component.

The six SPFL heuristic routines are presented in detail in Figures 4.3 to 4.8.
Important steps are identified by circled numbers to facilitate the following discussion. In
Step 1, the Initialize routine (Figure 4.3) sets the variables STATEG,t) and PROD(i,j,t) to
zero. The POT(i,j,t) variable is set to the minimum production potential for periods t > 1
since the previous production states are not known. The initial state for each workcenter

is known for period 0, so the exact production potential for t = l is known and set

40

 

Initialize
Initializes Heuristic Variables

 

 

 

 

STATE(j, 0) = Component number (i)

for initial setup

I
E
Vi: t¢0 ®

STATEO, t) = 0
PROD(i,j. t) = 0 V1.“

 

 

 

 

 

 

POT(i, j. r) = P”- - U”- V1.11: 1.. 1
. . v. .
POT(1,j, 1) = P1] ' "STATEtj. 01.1,; "1
WORK(t, d) = 11,, VI. .1
BAL(i, r) = 110 V1.1

 

 

Set

 

 

 

 

 

 

_S_e__t

IE:
i=i+1

 

 

 

 

 

 

 

 

 

 

 

 

BAL(i,t) = BAL(i,t) - d.,., 4

 

 

 

 

 

 

 

 

FIGURE 4.3 SPF L HEURISTIC - INITIALIZE ROUTINE

41

 

Increment

Controls single pass
incrementing

 

 

 

 

 

 

 

 

  
  

Go to
Production

Return from \
Production /

 

 

 

H=q+l

 

 

 

Is N0
td> T

 

 

 

 

 

 

 

 

 

FIGURE 4.4 SPFL HEURISTIC - INCREMENT ROUTINE

42

 

Production

Determines when production
capacity is available

 

 

 

 

   

 

 
     
   
  

 
  

 

 

 

 

From Set etum from
Increment j:l Adj”! or
’ etup Adjust

 

 

   
 
 
 
 
  

      
  
   
 
   

 

 

 

 

w- ~ 8 S
[i‘.]. - (Fig.1. — POT(Id,j.,td )) wdmud d) YCS gel.
.' —(BAL(rd.td )) V i (s — tI - td
? d
7
Go to

 

Schedule

 

 

§_e_t

 

 

 

 

 

 

 

 

 

 

 

Set IflidJs > 0

-:1 Set t1 = t, - Ito-l.

Js‘ -—>

ts_td lflidajs = 0
SCII|=Is-I

 

 

 

 

 

l

 

 

 

 

 

 

 

 

 

 

 

FIGURE 4.5 SPFL HEURISTIC - PRODUCTION ROUTINE

‘ Go to
Schedule

 

 

1n feasible

43

 

Schedule

Sets production
Updates production potential

 

 

 

From
Productio

 

 

1f-(BAL(id,T)) < POT(id, j,, 1,) Then PROD(id, j,, 1,) = -(BAL(id,T)) Q)
Otherwise PROD(id, j,, 1,) = POT(id, j,, 1,)

t

§c_t
B=S

’t

BAL(id, 18) = BAL(ii, ta) + PROD(id’ 1., ‘1)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Sgt

STATE (j,,t,) = id ®
WORK(1,,d) = WORK(1,,d) -w Vd

V

§e_t
18:1

—*1

POT(iBj,,t,) = 0 ®

I

iB=iB+l

N0 Yes Go to
Adjust

'd-JSv d

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

FIGURE 4.6 SPF L HEURISTIC - SCHEDULE ROUTINE

 

 

44

Adjust
Determines dependent demand for scheduled production
Adjusts production potential if workcenter idle in next period

Determines if production should be updated in next period due to setup

 

 

From
Schedule

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
   

 

   
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

S_et
I = Id
1 No
0 0 "°
No Yes
Yes
Return to
. +1 No Production
11)
Return to
Production
S_et_ .
t. = 1,
I Yes
. ls N
B , t = . 0
AMP P) BAL(Id. T) 0
BAL(ip. 1.0—(11.,.,)(PROD(ii.1..1i>) 1
* Yes
$=$+l h
p“ \. No
PROD(i..1..1. +1)
Yes IS No 7
?

® Yes

Go to
Setup Adjus

 

FIGURE 4.7 SPF L HEURISTIC - ADJUST ROUTINE

45

 

Setup Adjust

Adds production due to setup and
corresponding dependent demand

 

 

 

From
Adjust

 

 

_S_e;
g=g+l

 

 

 

 

1 @

 

 

If -(BAL(id, T)) > P.,_,, -PROD(id.j,.1, +1)Thcn
D = n,_,, -PROD(id.I..11+1)

 

 

 

Else
D = - (BAL(id. 1))

 

 

 

 

*1

mm... )=BAL(1,.1,)+ D
PROD(id, j,, 1,+ ) = PROD(id, j,, 1,+1) + D

 

 

 

 

    
 

 

 

Return to
Production

 

 

 

 

 

 

 

 

 

 

 

BAL(Ip. 1p) =
BAL(ip, 1.0-(<11. i.)(D)

 

 

i

 

 

9=$+1

 

 

 

 

 

 

FIGURE 4.8 SPFL HEURISTIC - SETUP ADJUST ROUTINE

46

accordingly. The WORK(t,d) variable keeps track Of the number Of workers available for
assignment to a workcenter, so it is initialized to be m.) for all t. The BAL(i,t) variable
keeps track of the number of components at the end of each period. 'In Step 1 it is set

equal to the initial inventory balance 1:0. The rest of the Initialize routine subtracts

 

external component demand (d;.) from BAL(i,t) for the period in which it occurs and all
following periods. A negative value for BAL(i,t) represents the need for component
production.

Figure 4.4 shows the Increment routine. This routine increments id and td to
determine when components are needed, which is indicated by a negative value of
BAL(id,td) in Step 2. Because the components are numbered in order of ascending low
level code, the BAL(i,t) array can be checked in a single pass.

Figure 4.5 shows the Production routine, which determines when production
should be scheduled to eliminate a negative value in the BAL(id,td) variable. The
production routine tries to schedule production as close to the period in which it is needed
to minimize inventory holding costs. The routine first checks if the entire demand in
period td can be satisfied using intraperiod transfer (Step 3). If it can and there are
suflicient workers available then control is passed to the Schedule routine. If not, the
routine searches for the workcenter that can produce the desired component closest to the
period needed (Step 5) and if there are sufficient workers to man the workcenter (Step 6)
then control is passed to the Schedule routine. Afier production is scheduled, BAL(id,td)

may still be negative and additional production may need to be scheduled.

47

The Schedule routine (Figure 4.6) first checks the ending component balance (Step
7) and sets the production quantity in the PROD(i,j,t) variable so that the ending inventory
balance will be zero. If a nonzero ending balance were desired, the desired ending
inventory could be subtracted fi’om the last period of BAL(i,t) in the initialize routine. In
Step 8 the scheduled production is added to the BAL(i,t) variable for the period in which
it is available (t.) and all later periods. Step 9 sets the STATE(j,t) variable to the
component number id and adjusts the WORK(t,d) variable for the workers needed to staff
the workcenter. With production assigned at workcenter j, in period t), the workcenter is
not available to produce other components and the POT(i,j,t) variable is set to zero for all

components at workcenter jS in period t. (Step 10).

If the component that has just been scheduled for production (id) is an assembly
that requires other components in its production, then BAL(i,t) must be adjusted to reflect
the need for these components. This is done in the Adjust routine (Figure 4.7). If a
component is used in the production of component id (Step 11), then the BAL(i,t) variable
is adjusted to reflect this dependent demand.

The state of workcenter js is known in period t, because production was just
scheduled. If the workcenter js has not been scheduled for production in period ti+l (Step

12) then the production potential will be adjusted for period tl+l at workcenter js (Step

13) since the setup losses are now known.

If workcenter j, is producing component id in period tl+l, then the production
scheduled can be increased in period tI + 1 Since no setup will be required. Step 14 sends

control to the routine Setup Adjust if additional production is needed and available. Note

48

that if production has been scheduled for a component other than id in period ts+ l , then
due to the single pass approach of the SPFL heuristic, sufficient production has already
been scheduled to meet demand and there is no need to increase output.

The Setup Adjust routine sets the additional production D (due to the setup being
performed in period t.) as Minimum{Potential Production, Component Deficit} in Step 15.
If additional production is scheduled, then dependent demand for subcomponents must be
reflected in the BAL(i,t) variable (Step 16). When all dependent demand has been
accounted for, control returns to the Production routine.

The SPFL heuristic provides a simple means to generate good solutions to the

MSS model. The quality of the SPFL heuristic solutions is evaluated in Section 6.

5.0 PRODUCTION SYSTEM FOR MODEL EVALUATION

The MSS model was evaluated using Walker Manufacturing's 7-inch light truck
exhaust system production line at its manufacturing facility in Newark, Ohio. Eight
versions of the 7-inch exhaust system are produced at the facility. A drawing of a typical
7-inch exhaust system is shown in Figure 5.1. The typical exhaust system consists Of a
muffler, inlet and outlet pipes, a heat shield and hangers. Since hangers and heat shields
are purchased components, they were not considered in the evaluation of the model. It
would be easy, however, to incorporate a purchased material ordering capability in an
implementation of the MSS model. Inlet and outlet pipes also were excluded from the
model as they are produced on pipe benders that service a number of different products.

The 7-inch exhaust system mufflers are produced using a number of components--
heads, partitions, bushings, louver tubes and tuning tubes--as illustrated in Figure 5.2.
These components are produced in the pipe and press area of the Walker plant and are
combined with a stamped steel sheet to produce a finished muffler on the muffler assembly
line. Table 5.1 provides bill of material data for the 7-inch mufflers.

Production of 7-inch exhaust systems involves additional manufacturing processes
including: the production of steel tubing sheet steel, bending of steel tubing, stamping of
steel blanks for heads and partitions, stamping of perforated steel blanks for louver tubes
and stamping muffler shell blanks. Since products from these processes are used in the
production of other exhaust systems and components, they were not included in the

evaluation.

49

50

Muffler P,
8286 'Pe

Pipe

 

 

11 \

 

 

 

Heat Shield

FIGURE 5.1 TYPICAL 7-INCH EXHAUST SYSTEM

Muffler #8286

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Tuning Tube
‘ 539133
Inlet Bushin Louver Tube 2" 4
#324862 a \ #324162 Louver Tube 1.75" /
. ‘\\ #3241 52 /
\\ {I \ I” \“7*.\ I ‘ f. ‘
\l \ ' ' / 0\
1.1 f /
8 T l A I x I X
I W“ x
1 J" ,
i l A I , I
Wet Head /// Outlet Head
#324462 \ p #324202
- / i 1 G). 11 i T
- 7 // \\ 1..
/ Partition / \
Shell #3241 22
Partition Louver Tube 2.25"
#3241 32 #3241 42

Outlet Bushing
#324182

FIGURE 5.2 TYPICAL 7-INCH MUFFLER

51

TABLE 5.1 MUFFLER BILL OF MATERIAL DATA

Mufflers

8298

1
Louver Tubes

Inlet Heads

1 1
Outlet Heads

8329

 

52

5.1 THE WALKER MANUFACTURING ENVIRONMENT

The 7-inch exhaust manufacturing system has a hierarchical structure which is
illustrated in Figure 5.3. Exhaust system assembly is performed in dedicated work cells.
The arrangement of the exhaust system work cells is shown in Figure 5.4. Eight different
7-inch exhaust systems are produced on seven dedicated workcenters, primarily by
welders, although two C-classification machine operators are required for production of
exhaust system #8297. A negligible setup is required to switch between the #8290 and
#8291 exhaust systems; all other products are produced in dedicated assembly cells which
do not require setups. The assembly cell for exhaust system #8289 is shown in Figure 5.5.

All 7-inch mufflers are produced on a single muffler line which is staffed with C-
classification operators. Normally the muffler line produces 125 mufflers per hour and
Operates for two 8-hour shifls each day. A l-hour setup (sequence-independent) is
required to switch between different mufflers. The number of C-Operators required to

operate the muffler line depends on the muffler being produced as shown in Table 5.2.

TABLE 5.2 WORKERS REQUIREMENTS FOR MUFFLER ASSEMBLY

Muffler # C-Operators

 

8285 13
8286 l l
8289 13
8290/91 1 l
8297 1 l
8298 14
8329 13

Some Of the workstations on the muffler assembly line are shown in Figure 5.6

53

 

7-inch Exhaust System Assembly

Assemble exhaust system from
mufflers, pipes*, heat shields*
and hangers*

 

 

 

7-inch Muffler Assembly

Assemble mufflers from shell blank“,

heads, partitons, bushings, louver
tubes and tuning tubes*

 

 

 

 

 

Pipe Area Press Area

Produce heads, partitons Produce bushings and tuning tubes*
and louver tubes

 

 

   

*not included in evaluation.

FIGURE 5.3 THE 7-INCH EXHAUST SYSTEM PRODUCTION STRUCTURE

 

54

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

8298 8286
3 Welders 54 parts/hr. 3 Welders 56 parts/hr.
8297 8285
3 Welders 47.5 parts/hr. Open 2 Welders
2 C-Operators 52.5 parts/hr.

 

 

 

 

 

 

 

8290 8329 8289

 

 

 

 

 

 

 

 

Pipe Service
Bender Parts 829 I

/
/

3 Welders
40.5 parts/hr.

2 Welders 2 Welders
25 parts/hr. 60 parts/hr.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

FIGURE 5.4 7-INCH EXHAUST SYSTEM ASSEMBLY AREA ARRANGEMENT

55

 

First workstation and conveyor to second workstation

FIGURE 5.5 ASSEMBLY CELL FOR EXHAUST SYSTEM #8289

56

 

View of workstations where components are inserted

FIGURE 5.6 MUFFLER ASSEMBLY LINE WORKSTATIONS

57

Pipe components used in muffler production--inlet tubes, outlet tubes and
bushings--are produced in the pipe area. The arrangement of the pipe area is shown in
Figure 5.7. Production of these components begins by cutting steel tubing to length on
one of two cutoff machines. The cutoff machines were not included in the problem since
they produce components for products other than the 7-inch exhaust system. Since tuning
tubes do not require additional processing, they were not included in the evaluation.
Single diameter bushings (no diameter changes over the length Of the bushing) require
processing on both ends by a riesener machine, a metal forming machine that ensures that
the end of the pipe is exactly round. The single diameter bushings listed below are
produced in two diameters (2-3/8-inch and 2-5/8-inch) at one of two single-riesener

workcenters as shown in Table 5.3.

TABLE 5.3 SINGLE DIAMETER BUSHINGS

Inlet Bushings
324912
325792

Outlet Bushing§_
324182
324292

 

 

Dual diameter bushings are produced by taking tubing that has been cut to length and
reducing the diameter of one end with a swage machine. Each end must be processed on a
riesener to ensure roundness, and since the pipe now has a different diameter on each end,
a riesener is dedicated to each diameter. A swage with two riesener machines is set up in

one workcenter dedicated to 2-3/8-inch dual diameter bushings, while another workcenter

58

 

2 3/8” Dual Diameter Bushings
2 C-Operators

333 parts/hr.

1 hr. setup

 

 

Riesener

 

 

Single Diameter Bushings
l C-Operator

250 parts/hr.

1 hr. setup

/

 

 

Riesener

 

 

 

2 3/8” Dual Diameter Bushings
2 C-Operators

333 parts/hr.

1 hr. setup

 

 

 

Riesener

 

 

Riesener

 

 

 

 

 

 

Riesener

 

 

Riesener

 

 

 

 

FIGURE 5.7 PIPE AREA LAYOUT

 

59

composed of a swage with two rieseners is dedicated to 2-5/8-inch dual diameter
bushings.
The bushings produced at each dual diameter bushing workcenter are listed in

Table 5.4.

TABLE 5.4 DUAL DIAMETER BUSHING WORKCENTERS

2-3/8" Dual Diameter Bushings

Inlet Bushings—
324102
324862

 

2-5/8” Dual Diameter Bushings

Inlet Bushing—
324282
324782

Outlet Bushing_
325802
326672

 

 

A workstation at the 2 5/8” dual diameter bushing workcenter is shown in Figure 5.8.
The other muffler components-~louver tubes, partitions and heads--are produced
in the press area. The layout of the press area is shown in Figure 5.9. Louver tubes are
formed from perforated steel blanks on three stolp machines (one for each louver tube
diameter). See Figure 5.10. The louver tubes produced on each stolp machine are listed

in Table 5.5.

60

 

Close-up view of a riesener

FIGURE 5.8 A DUAL DIAMETER BUSHING WORKSTATION

61

.....................
IIIII
g D
\ 0
‘ I
e U,
a‘ 1

 

 

 

saqn .1.
JaAnO'I “z

 

 

 

 

1 3/4” Louver
Tubes

 

 

 

 

 

2-1/4” Louver

 

 

Q
U
.....
' ‘
I. .‘
s, s‘
.........
IIIIIIIIIIIII

 

 

Head

1 B-Operator
550 parts/hour
1 hour Setups

1 B-Operator
__ 1000 parts/hr.

 

Press

 

 

 

 

Partition
Press

 

 

Sequence-dependent
setups

1 B-Operator

750 parts/hr.
Sequence-dependent
setups

i\

 

 

FIGURE 5.9 PRESS AREA LAYOUT

 

Close up view of completed louver tubes on stolp machine

FIGURE 5.10 STOLP MACHINES

63

TABLE 5.5 LOUVER TUBE WORKCENTERS

1-3/4" Stolp 2-1/4" Stolp

 

 

324152 324142

330032 324372

2” Stolp 324722
324162 324732

324392 324742

324442 324952

330022 325852

325862

325872

Partitions and heads are produced on dedicated dial presses(Figure 5.1 1). Many
heads and partitions are similar, requiring only a change in a die insert to switch from one
to the other. Others require a complete die change, so setups for the head and partition
dial presses are sequence-dependent. Setup times for the head and partition presses are
shown in Tables 5.6 and 5.7, respectively. The characteristics of the four production areas

are summarized in Table 5.8.

5.2 WALKER PRODUCTION DATA

Walker Manufacturing production schedule data was obtained for the period from
November 15, 1993 to February 3, 1994. Daily reports of exhaust system and muffler
production were obtained, as well as copies of the shipment schedule, which recorded
daily exhaust system production, shipments and inventory balances. Table 5.9 summarizes
daily exhaust system demand.

Special records were made in the pipe and press area by the area supervisor to

record daily production quantities and their sequence on a workcenter. The plant’s

64

 

Close-up view of dial press tool

FIGURE 5.11 PARTITION DIAL PRESS

65

TABLE 5.6 SETUP TIMES FOR THE HEAD PRESS IN MINUTES

FTUDDI

 

TI)

 

11741

324202

324302

324462

324702

325782

 

117417

..........................

30

15

 

324202

10

30

 

324302

......................

,. ....

.11.

10

 

324462

. :{ifj-‘E; - 7 3O

30

 

324702

............................

 

 

325782

 

 

 

 

 

 

.10.. . . _.

 

 

665

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

mm—HDZHE Z— mmm—zm ZOE—EMA‘A Huh. KGB mag mDHHw 5m Hum—«Q.

eemmm we we oe ow co 96 ON Noooww
oe NNLDH oe we we we we we Neeer
co co __wamw we we we we we Nweer
06 we we ow 06 co ow oe NwwwNw
so we we co co co co co NNwwNw
ow we we ow co co co cw N_NwNw
06 we we so ow co co co NweVNw
ow we we co co co ow o6 NeewNw
oe we we co co co co co NNeVNw
ow we we ow co co co cw NeeVNw
ow we we co 06 co co ow NweVNw
ow we we .- co co co co co NwwVNw
ow we we ..-_mN oe ow co ow ow NVNVNw
oe we we B...we co co NwwVNw
co we we so aw mam oe NNNVNw
O6 we we co so mean», Ne_VNw
ow we we we we ow Nw_4Nw
cw we we co co co .wue NN_VNN
N N N N N N N N eawznu
a w a N N e n N
e e e w w _ u _
c e e v v v v e
N N N N N N N N
w w w w w n N w

Nye

 

67

TABLE 5.8 SUMMARY OF 7-INCH MUFFLER PRODUCTION AREAS

 

 

 

 

 

 

# of # of

Production Area Wctr Comp Setups Other
Exhaust Systems 7 8 None
Assembly
Muffler Assembly 1 8 .Sequence- 2 shifts/day

Independent

. Sequence-
4 16
Pipe Area independent
Press Area 5 38 Sequence- Some Overtime
dependent Used

 

 

 

 

 

 

68

TABLE 5.9 WALKER EXHAUST SYSTEM DEMAND SCHEDULE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Exhaust 1 2 3 4 5 6 7 8 9 10
SyStcm 11/15/93 11/16/93 1 1/17/93 11/18/93 ll/l9/93 11/22/93 11/23/93 ll/24/93 11/29/93 11/30/93
8285 180 300 180 270 420 120 330 61 510
8286 390 270 390 300 570 240 451 270 570
8289 175 175 150 150 175 175
8290 270 270 360 300 270
8291 25 120 30 120 180 60 90 60 180
8297 120 120 121 120 160 160 160
8298 300 300 300 300 300 300 200
8329 25 25 50 25 25
Exhaust 11 12 l3 14 15 l6 17 18 19 20
Symem 12/1/93 12/2/93 12/3/93 12/6/93 12/7/93 12/8/93 12/9/93 12/10/93 12/13/93 12/14/93
8285 210 60 360 270 240 210 210 240 300 210
8286 60 270 360 270 600 30 570 330 1050 30
8289 150 150 150 150 175 125
8290 270 240 270 30 270 60 300 90 300
8291 60 90 180 150 150 60 120 120 210 30
8297 160 160 160 160 120 120 120
8298 300 300 300 300 350 350 350
8329 25 25 25 25 25
Exhaust 21 22 23 24 25 26 27 28 29 30
System 12/15/93 12/16/93 12/17/93 12/20/93 12/21/93 12/2 2/93 12/23/93 1/4/94 1/5/94 1/6/94
8285 270 480 300 180 525 270 210 360 330 90
8286 630 690 270 330 1140 600 300 390 570 210
8289 150 175 150 175 150 175 125 150
8290 300 330 360 420 330 30
8291 120 210 90 30 210 150 60 90 120 90
8297 120 120 200 200 240 160 200 320
8298 350 351 200 200 100 400 600
8329 25 25 25 25

 

 

 

 

 

 

69

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

TABLE 5.9 (CONT’ D)
Exhaust 31 32 33 34 35 36 37 38 39 40
Syaem 1/7/94 1/10/94 1/11/94 1/12/94 1/13/94 1/14/94 1/17/94 l/18/94 1/19/94 1/20/94
8285 330 300 180 270 210 330 510 90 420
8286 30 630 30 600 360 630 840 300 405
8289 150 151 150 125 150
8290 180 30 300 30 270 30 330 30 405
8291 30 30 60 90 90 60 90 30 180
8297 160 160 160 160 200 160 200
8298 300 300 300 300 200 300 200
8329 25 25 25 50 25
Exhaust 41 42 43 44 45 46 47 48 49 50
SyStcm 1/21/94 1/24/94 1/25/94 1/26/94 1/27/94 1/28/94 1/31/94 2/1/94 2/2/94 2/3/94
8285 90 600 60 390 210 390 90 390 90
8286 300 690 300 360 240 990 210 450 330
8289 100 150 125 150 100 100 125
8290 30 180 270 330 60 330 90
8291 60 120 30 120 90 120 60 90 30
8297 200 160 200 160 160 200 200 160 160
8298 200 300 200 300 300 200 200 300 300
8329 25 25 25

 

 

 

 

 

 

 

 

 

 

 

 

 

70

accounting department provided cost data for all components. Accurate inventory data
for November 15, 1993 (the beginning inventory for the planning period) for components
other than finished exhaust systems was unavailable. Since the goal was to compare MSS
model schedules to actual production decisions, the initial inventory levels were assumed
to be the lowest value that would result in a non-negative inventory balance over the
period of data availability. This resulted in a conservative (minimum cost) estimate Of the
scheduling decisions made by the company. Table 5.10 summarizes the component cost

and beginning inventory data.

5.3 HIGH AND LOW CAPACITY DEMAND SCHEDULES

A high-capacity utilization test problem was developed based on the Walker
Manufacturing environment by keeping all parameters the same as the Walker problem
and increasing the demand. Exhaust system demand over the period November 15, 1993
to February 3, 1994 occurred in the proportions shown in column two of Table 5.1 1
(relative to the lowest demand exhaust system #8329). These proportions were used to
develop the lot sizes shown in column three of Table 5.11. Demand was randomly added
to the Walker demand schedule of Table 5.9 using the following procedure. Beginning
with the first day of the schedule, an exhaust system was randomly selected and demand
was increased by the lot size in the table above. The SPFL heuristic with an 8-hour period
length was used to determine if the demand schedule was still feasible. If it was, then the
additional demand was kept in the high capacity demand schedule. If not, it was removed

and another exhaust system was randomly selected. This process continued until either all

71

TABLE 5.10 COMPONENT COST AND BEGINNING INVENTORY DATA

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Exhaust Systems Partitions
Part8 Unit Cost Initial lnv.‘ Partl Unit Cost Initial Inv.’
8285 $27.27 1710 324122 $0.55 7238
8286 $33.09 2310 324132 $0.42 9840
8289 $33.14 475 324172 $0.55 5813
8290 $29.38 240 324322 $0.42 4520
8291 $33.62 25 324332 $0.55 5076
8297 $51.50 1560 324342 $0.55 3238
8298 $33.35 650 324352 $0.55 6596
8329 $40.59 0 324752 $0.42 2187
Mufflers 324762 $0.55 1579
8285 $17.31 2048 324922 $0.59 1493
8286 $16.56 0 324972 $0.59 1753
8289 $17.76 125 324982 $0.55 503
8290/91 $16.30 696 325812 $0.42 1551
8297 $17.54 54 325822 $0.42 1551
8298 $18.00 1538 325832 $0.55 1551
8329 $18.93 47 327782 $0.55 1007
Inlet Bushings 327792 $0.59 61 I
324102 $1.59 987 330002 $0.59 703
324282 $1.23 1685 Louver Tubes
324782 $1.62 769 324142 $0.79 16561
324862 $1.35 4968 324152 $0.66 4161
324912 $1.80 0 324162 $0.82 6952
325792 $1.52 551 324372 $1.38 1611
Outlet Bushings 324392 $0.66 4452
324182 $0.80 I 8032 324442 $0.63 4089
324292 $1.34 | 1011 324722 $0.68 3068
325802 $0.97 I 1844 324732 $0.64 1824
326672 $0.97 I 882 324742 $0.80 3557
Inlet Heads 324952 $0.76 1841
324302] $0.82 | 2663 325852 $0.76 2666
324462] $0.82 | 13704 325862 $0.64 2064
Outlet Heads 325872 $0.64 4984
117417 $0.94 228 330022 $0.57 228
324202 $0.82 20229 330032 $1.26 405
324702 $0.94 2275
325782 $0.82 4993

 

 

 

*Initial inventory was known for exhaust systems.
set at the minimum feasible level.

For all other components it was

 

72

TABLE 5.11 LOT SIZES USED FOR HIGH CAPACITY DEMAND SCHEDULE

Exhaust Proportion Lot Size

 

System
8285 20.3 200
8286 32.1 320
8289 7.1 70
8290 12.1 120
8291 6.7 70
8297 9.8 100
8298 16.7 170
8329 1.0 10

components during a day had been evaluated for additional capacity or three exhaust
systems had been selected with the result being an infeasible schedule, whereupon the
process was repeated for the next day in the schedule. The result was the development of
a demand schedule that used a high percentage of the available capacity, yet remained
feasible and had a demand pattern that was roughly proportional to that typically
experienced by Walker Manufacturing. The resulting demand schedule is shown in Table
5.12.

A low capacity problem was also developed by taking the Walker Manufacturing

demand schedule of Table 5.9 and reducing the demand by one half.

5.4 LABOR COSTS AND SCHEDULES

Three job classifications were used in the production of 7-inch exhaust systems.
Welders were used solely in the assembly of exhaust systems. C-classification machine
operators were used in the assembly of #8297 exhaust systems, muffler assembly and the

pipe production areas. B-classification machine operators are a higher classification of

73

TABLE 5.12 HIGH CAPACITY DEMAND SCHEDULE

 

Exhaust 1 2 3 4 5 6 7 8 9 10

 

Syflem ll/15/93 11/16/93 11/17/93 ll/l8/93 ll/l9/93 11/22/93 11/23/93 11/24/93 11/29/93 11/30/93

 

8285 380 500 380 470 200 620 320 530 61 510

 

8286 710 590 710 300 320 890 560 771 270 570

 

8289 70 175 70 245 70 220 220 70 175 175

 

8290 120 270 120 270 360 300 120 270

 

8291 95 190 200 120 70 250 130 160 60 180

 

8297 220 120 121 120 260 160 260

 

8298 470 470 470 300 470 470 370 170 170

 

 

 

 

 

 

 

 

 

 

 

 

8329 35 10 25 10 60 10 35 25

 

 

Exhaust 11 12 I3 14 15 16 17 18 19 20

 

 

Syflem 12/1/93 12/2/93 12/3/93 12/6/93 12/7/93 12/8/93 12/9/93 12/10/93 12/13/93 12/14/93

 

8285 210 60 360 270 240 210 210 240 300 210

 

8286 60 270 360 270 600 30 570 330 1050 30

 

 

 

 

 

 

 

 

 

 

8289 150 150 150 150 175 125

8290 270 240 270 30 270 60 300 90 300
8291 60 90 180 150 150 60 120 120 210 30
8297 160 160 160 160 120 120 120
8298 300 300 300 300 350 350 350
8329 25 25 25 25 25

 

 

 

 

 

 

 

 

 

Exhaust 21 22 23 24 25 26 27 28 29 30

 

 

SyStem 12/15/93 12/16/93 12/17/93 12/20/93 12/21/93 12/22/93 12/23/93 1/4/94 1/5/94 1/6/94

 

8285 270 480 300 180 525 270 210 360 330 90

 

8286 630 690 270 330 1140 600 300 390 570 210

 

 

 

 

 

8289 150 175 150 175 150 175 125 150
8290 300 330 360 420 330 30
8291 120 210 90 30 210 150 60 90 120 90
8297 120 120 200 200 240 160 200 320
8298 350 351 200 200 100 400 600

 

 

 

 

 

 

 

 

 

 

 

 

8329 25 25 25 25

 

 

74

TABLE 5.12 (CONT’D)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Exhaust 31 32 33 34 35 36 37 38 39 40
53'3““ 1/7/94 1/10/94 1/1 1194 1/12/94 1/13/94 1/14/94 1/17/94 1/18/94 1/19/94 room
8285 330 300 180 270 210 330 510 90 420
8286 30 630 30 600 360 630 840 300 405
8289 150 151 150 125 150
8290 180 30 300 30 270 30 330 30 405
8291 30 30 60 9O 9O 6O 90 30 180
8297 160 160 160 160 200 160 200
8298 300 300 300 300 200 300 200
8329 25 25 25 50 25
Exhaust 41 42 43 44 45 46 47 48 49 50
System 1/21/94 1/24/94 1/25/94 1/26/94 1/27/94 1/28/94 1/31/94 2/1/94 2/2/94 2/3/94
8285 90 600 60 390 210 390 90 390 90
8286 300 690 300 360 240 990 210 450 330
8289 100 150 125 150 100 100 125
8290 30 180 270 330 60 330 90
8291 60 120 30 120 90 120 60 90 30
8297 200 160 200 160 160 200 200 160 160
8298 200 300 200 300 300 200 200 300 300
8329 25 25 25

 

 

 

 

 

 

 

 

 

 

 

 

 

75

operator who can perform machine setups entirely on their own. They were used in the
press area to produce louver tubes, partitions and heads. Wage rates for the job

classifications are given in Table 5.13.

TABLE 5.13 WAGE RATES

Job Classification Houflywlge Rate (Slhr)

 

Welder 12.00
C operator 11.16
B operator 12.00

For the MSS model of the production facility, the number of workers available was

assumed to be the same each day according to the schedule in Table 5.14.

TABLE 5.14 LABOR AVAILABILITY

 

 

 

 

 

 

 

Number of
Model Shift Classification Workers
Exhaust 1 Welder 12
Assembly
C Operator 2
Muffler 1&2 C Operator 14
Assembly
Pipe Area 1 C Operator 4
Press Area l B operator 3
2 B operator ZQ“)
All Areas 1 Welder 12
l B operator 3
1 C operator 20
All Areas 2 Welder 0
2 B operator 2(3*)
2 C operator l4

 

*During some days a second shift was used for head
production with a second B classification Operator.

76

A second shifi for head production was assumed to be available on the days shown in

Table 5.15.

TABLE 5.15 DAYS WITH SECOND SHIFT HEAD PRODUCTION

11/16/93 11/23/93 11/30/93 12/7/93
12/14/93 12/21/93 1/5/94 l/l 1/94

1/18/94 1/25/94 2/1/94

The next section discusses the results of the MSS model evaluation.

6.0 EVALUATION OF THE MODEL

Two experiments were run using models of the Walker Manufacturing production
facility. In the first experiment, models were developed for each of the four production
areas (exhaust system assembly, muffler assembly line, pipe area and press area) and for
the entire production process. Three period lengths--eight, four and two hours--were
evaluated for planning horizons ranging from 10 to 50 days. The first experiment allowed
for the comparison of the MSS model results to actual production schedules used at
Walker Manufacturing.

A second experiment evaluated the impact of production system capacity
utilization on the solution procedures. This experiment was run using the Walker
Manufacturing environment with three demand schedules: Walker Manufacturing’s
demand schedule and the high and low capacity demand schedules described in Section
5.3. This experiment also evaluated hierarchical decomposition Of the problem. In
hierarchical decomposition, the scheduling problem is solved one level at a time. In the
Walker Manufacturing environment, hierarchical decomposition means that the exhaust
system assembly problem is solved first, with the resulting exhaust system assembly
schedule used to generate demand for the muffler assembly problem. The solution to the
muffler assembly problem then can be used to generate demand for the pipe and press
areas, which in turn are solved in isolation. In the second experiment, models were
evaluated using 30 and 50 day planning horizons with 8 hour periods. Table 6.1

summarizes the two experiments used to analyze the MSS model.

77

KEY

 

Assembly:

Muffler:
Pipe:
Press:

10-50:
10, 30, 50:
30, 50:

78

TABLE 6.1 EXPERIIVIENTAL DESIGN

Walker Manufacturing Comparison

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Production 8-hr. Days 4-hr. Days 2-hr. Days
System
Assembly 10-50 10, 30, 50 10, 30, 50
Muffler 10-50 10, 30, 50 10, 30, 50
Pipe 10-50 10, 30, 50 10, 30, 50
Press 10-50 10, 30, 50 10, 30, 50
Entire System 10-50 10, 30, 50 10, 30, 50
Capacity Evaluation
High Low
Production Capacity Walker Capacity
System Demand Demand Demand
Assembly 30, 50 30, 50 30, 50
Muffler 30, 50 30, 50 30, 50
Pipe 30, 50 30, 50 30, 50
Press 30, 50 30, 50 30, 50
Entire System 30, 50 30, 50 30, 50

 

 

 

 

 

 

Exhaust system assembly area, 7 workcenters, 8 components, no setups
Muffler assembly line, 1 workcenter, 7 components, seq. ind. setups, 2 shifts
Inlet and outlet bushings, 4 workcenters, 16 components, seq. ind. setups
Partitions and louver tubes, 5 workcenters, 38 components, seq. dep. setups

Model evaluated for 10, 20, 30, 40 and 50 day planning horizons
Model evaluated for 10, 30 and 50 day planning horizons
Model evaluated for 30 and 50 day planning horizons

79

6.1 WALKER MANUFACTURING COMPARISON

6.1.1 Walker Manufacturing Cost Estimates

The first experiment compared the performance of the integer programming and
the SPFL heuristic solutions to the actual schedules used at Walker Manufacturing. A
number of real-life factors (machine breakdowns, worker absences, setup difficulties, low
employee performance, etc.) can affect the implementation of a production schedule and
are difficult to include in the evaluation of the model. The approach used here was to
calculate costs for Walker Manufacturing based on production quantities, inventory levels
and setup decisions assuming the same parameters used in the MSS model.

To calculate costs for Walker Manufacturing, a spreadsheet was developed to
calculate the daily production-inventory balances based on the production data described

in Section 5.2. Daily inventory levels were calculated and inventory costs assessed

accordingly. In the MSS model, when a workcenter is activated (6)-11:1), labor costs are

charged for the entire period whether parts are being made, a setup is being changed or
the workcenter is idle for part of the period. For Walker Manufacturing, production costs
were calculated in two parts: direct production costs and setup costs. Letting X ,~,, be the
units of component i produced at workcenter j in period t, the direct production cost (..'P,,,

was calculated as:

X.
C8,». = glam —-——’-’-—
P11

where:

bd = Wage rate for a worker in labor division d (S/period)

80

pi]- = Production rate of component i at workcenter j (units/period).

wU-d = Number of workers in labor division d required to staff
workcenter j when producing component i

as defined in Section 3.2. Based on the production data gathered at Walker
Manufacturing it was possible to determine when setups occurred. The cost for a setup at
a workcenter with sequence-independent setups CS, was calculated using:
(78,-, = Zbdww fl
11 PI]
where y, is the production loss (in units) when changing the setup at workcenter j. If the
setups are sequence-dependent, then the cost for changing the setup from component i to

component i’, CS”, was calculated as:

u...
Cs,--,-,- = Zbdwjjd '—f{
d PU

where u,«,,~ is the production loss (in units) when changing production from component i’ to

component i at workcenter j. Note that calculating labor costs in this fashion assumes no

idle labor.

6.1.2 Lower Bound on Costs

A lower bound on production costs was calculated to aid in the comparisons. A
perfect schedule would carry zero inventory while minimizing setups. Although it is
impossible to determine the minimum number of setups required for a particular demand
schedule, a lower bound is zero. Thus, a zero-setup, zero inventory (ZSZI) bound on

production costs can be calculated assuming zero inventory levels (once the initial

81

inventory is “consumed” by the demand schedule) and including only direct production
costs. This bound is quite good when there are no setups involved (e. g. exhaust system
assembly) and not as good when setups are significant (e. g. muffler assembly), but in
either case it can aid in comparing the MSS model results with Walker Manufacturing’s
production decisions.

6.2 SOLUTION OF MSS INTEGER PROGRAMMING MODELS

The integer programming models were solved using IBMs Optimization
Subroutine Library (OSL) release 2 on a Sun Microsystems SPARCcenter 2000 consisting
Of eight 50mhz TI SuperSPARC CPUs with 2 MB of Supercache. Problems were
submitted to OSL using GAMS version 2.25.073 requesting 300 MB of core memory.

The branching strategy used in evaluating models was the standard OSL strategy
with the addition of supemode processing and the SPFL heuristic solution (if available) as
an incumbent. The OSL branching strategy first estimates two values for the solution
degradation (rounding up and rounding down) in satisfying integrality for each 0-]
variable that does not take on an integer value in LP relaxation at the current node. It

then branches on the variable with the worst of the best solution degradation estimates.

6.3 EXHAUST SYSTEM ASSEMBLY COMPARISON

For the exhaust system assembly problem, the GAMS/OSL integer programming
software was unable to find optimal solutions, even for a 10 period model with 8 hour
periods (80 integer variables). In these cases, the GAMS/OSL software ran out of
memory (300 MB available) after over 24 CPU hours. The SPFL heuristic found

solutions in under 1 minute. The difliculty in finding integer programming solutions to the

82

MSS model is likely due to the failure of the LP relaxation to provide tight bounds in the
branch and bound procedure.

One problem with the LP relaxation is the term:
222212464611
i j d 1

in the objective function. This term defines the labor cost as a fixed cost if a workcenter is
operating in a period, no matter how many units are being produced. Since production at

a workcenter is defined as p96,] in the LP relaxation the variable 5,], can take on

I ,
fractional values so that the labor cost for production is not a fixed quantity but

proportional to the quantity produced. When the term 22: 2191110515111 is removed
1 j d r

from the model, the ten day assembly problem can be solved to optimality in minutes,
although larger problems are much harder to solve.

Tables 6.2 and 6.3 Show the results for the exhaust system assembly models.
Table 6.2 shows that for this model (with no setups), better solutions can be obtained with
smaller period lengths for both the SPFL heuristic and integer programming solutions.
This is somewhat surprising for the integer programming solution since cutting the period
length in half doubles the number of integer variables in the model. Apparently the
increase in the ability to fit production to the demand schedule with shorter period lengths
more than offsets the increase in problem size. Smaller periods also improve the lower
bound on the optimal solution of the integer programming solution. For the 50 period
model with 2 hour periods, the best integer solution can be no more than 2.68% better

than the best integer solution found. There is some indication that the bound on the

83

TABLE 6.2 SOLUTIONS FOR EXHAUST SYSTEM ASSEMBLY

 

 

 

 

 

 

IP Solutions
Planning Horizon (days)
Period Length 10 20 30 40 50
8 5,858 15,857 27,649 37,831 47,481
4 5,555 26.598 46,001
2 5,249 25,907 44,472
SPF L Solutions
Flaming Horizon (days)
Period Length 10 20 3O 4O 50
8 5,925 15,609 27,042 36,489 46,541
4 5,587 14,447 26,502 35,853 45,545
2 5,191 14,027 26,287 35,438 44,926
[P Solution % of Lower Bound on Optimal
Plannigg Horizon (days)
Period Length 10 20 30 4O 50
8 11.93 15.83 9.36 10.83 9.36
4 13.14 5.87 6.20
2 7.11 3.13 2.68

TABLE 6.3 COMPARISON OF COSTS FOR EXHAUST SYSTEM ASSEMBLY

COMPARISON OF COSTS - 8 hr. Period

 

 

 

 

 

 

 

 

Planning Horizon (days)
Solution 10 20 3O 40 50
Walker 12,480 23,849 34,585 45,409 57,860
1P 5,858 15,857 27,649 37,831 47,481
SPFL 5,925 15,609 27,042 36,489 46,541
ZSZI Bound 4,880 13,263 23,799 32,088 40,577
% OVER ZSZI BOUND - 8 hr. Period
Planning Horizon (days)
Solution 10 20 30 40 50
Walker 155.7% 79.8% 45.3% 41.5% 42.6%
1P 20.0% ‘ 19.6% 16.2% 17.9% 17.0%
SPFL 21.4% 17.7% 13.6% 13.7% 14.7%
COMPARISON OF COSTS - 4 hr. Period
Planning Horizon (days)
Solution 10 30 50
Walker 12,480 34,585 57,860
[P 5,555 26,598 46,001
SPFL 5,587 26,502 45,545
ZSZI Bound 4,880 23,799 40,577
% OVER ZSZI BOUND - 4 hr. Period
PlanningHorizon (days)
Solution 10 30 50
Walker 155.7% 45.3% 42.6%
IP 13.8% 11.8% 13.4%
SPFL 14.5% 11.4% 12.2%

85

TABLE 6.3 (CONT’D)

COMPARISON OF COSTS - 2 hr. Period
Planning Horizon (days)

 

 

 

 

Solution 10 30 50
Walker 12,480 34,585 57,860
[P 5,249 25,907 44,472
SPFL 5,191 26,287 44,926
ZSZI Bound 4,880 23,799 40,577
% OVER ZSZI BOUND - 2 hr. Period
Planning Horizon (days)
Solution 10 30 50
Walker 155.74% 45.32% 42.59%
IP 7.56% 8.86% 9.60%
SPFL 6.37% 10.45% 10.72%

86

Optimal solution is tighter for models with longer planning horizons, but this result is not
consistent for all period lengths.

In Table 6.3, the integer programming and SPFL solutions are compared to the
Walker Manufacturing schedule and the ZSZI lower bound. In all cases, the integer
programming and SPFL solutions are better than the Walker Manufacturing schedule.
Since there are no setups, the ZSZI lower bound is reasonably tight, and provides a good
way to compare the MSS model solutions to the Walker Manufacturing schedules. The
Walker Manufacturing schedule costs are extremely high compared to the ZSZI bound for
short planning horizons. This is because the initial inventory levels are relatively high and
demand can be met in the early periods by ”consuming” the inventory to satisfy demand.
For planning horizons of 30 days and longer, the Walker Manufacturing schedules have
costs around 42-45% over the ZSZI bound, whereas the MSS solutions are in the range of
8-20% over the ZSZI bound. Thus, the MSS model can provide schedules that reduce
costs by up to 80% of the maximum possible cost reduction.

Interestingly, the SPFL heuristic is superior to the integer programming solutions
for planning horizons of over 10 days when the period length was over two hours.

Figure 6.] presents the cost data graphically for the 50 day, two hour period SPF L
solution. These graphs show that the SPFL heuristic operates at a much lower inventory
level than the Walker Manufacturing schedule, resulting in significantly lower labor costs
early in the planning horizon. Once the initial inventory is “consumed,” the labor costs for
the SPFL solution parallel those of the Walker Manufacturing schedule, until the end of
the horizon, when the SPFL solution allows the ending inventory to go to zero, which

reduces labor costs even further.

87

 

 

Daily Inventory Costs - Exhaust System Assembly

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

$350
$300 »
$250 1' —Walker
5200 ~ —SPFL
5150 ‘ ——zszr
$100 ..
$50 4
$0 -
Cumulative Inventory Costs - Exhaust System Assembly
512.1130
$10,000 4-
58.000 <~ —Walker
$6,000 1» —SPFL
54.000 .. —ZSZI
_,____,—————4-1
52,000 1» fl/‘M—I
$0 4W
mestaaaaasss
Period
Cumulative Labor Costs - Exhaust System Assembly
350.1110
——Walker
$33,000 ..
——SPFL
$20,000 .. / —ZSZ| l
/ ___—____i
$10,000 1. /
so « -—‘ "

 

 

 

 

 

FIGURE 6.1 DAILY COSTS FOR EXHAUST SYSTEM ASSEMBLY

88

The graphs of Figure 6.1 show that comparing the total costs for the entire
planning horizon overestimates the cost reduction from the MSS model schedule. The
MSS model solution requires much less labor since the inventory levels are reduced, yet in
practice both methods require the same amount of labor to produce the same number of
parts. Because there are no setups in this model, the only true cost savings are due to
operating at lower inventory levels. Looking at the daily inventory cost graph in Figure
6.1, it appears that the MSS model could reduce finished goods inventory costs by $100-
$250 per day depending on how much of the finished goods inventory is due to
uncertainty in how well the manufacturing system can meet schedules and how much is

used to buffer demand uncertainty.

6.4 MUFFLER ASSEMBLY COMPARISON

The Muffler assembly line was evaluated using Walker Manufacturing’s exhaust
system assembly schedule to generate muffler demand. This allowed the MSS model
schedules to be compared to Walker Manufacturing’s decisions. Tables 6.4 and 6.5
summarize the results for the muffler assembly line evaluation.

The beginning inventory levels for mufflers was not available, so they were set to
the minimum level possible based on Walker Manufacturing’s production schedule. This
created a problem for the MSS model solutions. Although Walker Manufacturing’s
nominal production rate was 2,000 units per day (2 shifts), on November 16, 1993 (the
second day of the planning horizon) they produced 2,506 model 8286 mufflers. The MSS
model was not able to replicate this feat since it scheduled production based on the
nominal production rate and was not able to find a feasible schedule using the (minimum)
inventory levels that were assumed based on Walker Manufacturing’s production
schedule. For the MSS model to find a feasible schedule, 500 units of muffler #8286 and

3 units of muffler #8329 were added to the initial inventory for the MSS model. The

TABLE 6.4 SOLUTIONS FOR MUFFLER ASSEMBLY

89

 

 

 

 

 

 

IP Solutions'
Planning Horizon (days)
Period Length 10 20 30 40 50
8 16,366 30,416 47,933 61,968 83,175
4 15,138 45,931 83,712
2 14,289 46,734 83,671
SPFL Solutions‘
Planning Horizon (days)
Period Length 10 20 30 40 50
8 16,345 32,327 49,011 64,420 85,938
4 16,712 32,134 49,664 68,182 90,428
2 16,225 33,991 52,740 72,052 95,512
[P Solution % of Lower Bound on Optimal
Planning Horizon (gys)
Period Length 10 20 30 40 50
8 35.55 23.27 24.79 16.93 17.59
4 27.31 19.64 18.19
2 20.22 21.51 17.91

 

' Figures do not include production costs for 500 units of #8286 and 3 units of #8329 required to find a

feasible schedule.

TABLE 6.5 COMPARISON OF COSTS FOR MUFFLER ASSEMBLY

COMPARISON OF COSTS - 8 hr. Pei-i6112
Planning Horizon (days)

 

 

 

 

 

 

 

Solution 10 20 30 4O 50
Walker 17,800 32,884 50,791 69,434 92,599
[P 16,861 30,91 1 48,428 62,463 83,670
SPFL 16,840 32,822 49,506 64,915 86,433
ZSZI Bound 12,234 24,853 38,544 53,061 70,693
% OVER ZSZI BOUND - 8 hr. Period
Planning Horizon (days)
Solution 10 20 30 40 50
Walker 45.5% 32.3% 31.8% 30.9% 31.0%
[P 37.8% 24.4% 25.6% 17.7% 18.4%
SPFL 37.6% 32 .1% 28.4% 22.3% 22.3%
COMPARISON OF COSTS - 4 hr. Period2
Planning Horizon (days)
Solution 10 3O 50
Walker 17,800 50,791 92,599
IP 15,633 46,426 84,207
SPFL 17,207 50,139 90,923
ZSZI Bound 12,234 38,544 70,693
% OVER ZSZI BOUND - 4 hr. Period
Plannipg Horizon (days)
Solution 10 30 50
Walker 45.5% 31.8% 31.0%
IP 27,8% 20.4% 19.1%
SPFL 40.6% 30.1% 28.6%

 

2 Figures include $495 direct cost for 500 units of #8286 and 3 unit of #8329 added to initial inventory for
IP and SPFL models.

91

TABLE 6.5 (CONT’D)

COMPARISON OF COSTS - 2 hr. Period3

 

 

 

 

Planning Horizon (days)
Solution 10 30 50
Walker 17,800 50,791 92,599
IP 14,784 47,229 84,166
SPFL 16,720 53,23 5 96,007
ZSZI Bound 12,234 38,544 70,693
% OVER ZSZI BOUND - 2 hr. Period
Planning Horizon (days)
Solution 10 30 50
Walker 45.5% 31.8% 31.0%
[P 20.8% 22.5% 19.1%
SPFL 36.7% 38.1% 35.8%

 

3 Figures include $495 direct cost for 500 units of #8286 and 3 unit of #8329 added to initial inventory for
IP and SPFL models.

92

direct labor costs for these units is $495, and the results are corrected for this cost where
appropriate.

Table 6.4 shows the results for the integer programming and SPFL heuristic
solutions for the muffler assembly problem. There is no clear pattern to the impact of
period length on the integer programming solutions. For the SPFL heuristic, decreasing
the period length dramatically increases total costs. Table 6.4 shows that the integer
programming solution is superior to the SPFL heuristic in all cases except for a ten day
planning horizon with an 8 hour period length. Both the SPFL and integer programming
solution techniques can find solutions that are superior to the Walker Manufacturing
production schedule, as shown in Table 6.5.

For exhaust system assembly, the GAMS/OSL software ran out of the 300 MB of
memory allocated before an optimal solution was found. For the muffler line assembly
problem, memory was not a problem. Some test problems ran for over 48 hours without
finding an Optimal solution or running out of memory. Since computer resources were not
unlimited, a 24 hour CPU limit was imposed on all muffler assembly line problems. In the
trial problems, little improvement was gained by running the problem longer (less than
0.5% reduction in costs).

The LP relaxation for the muffler assembly problem is less tight than for the
exhaust system assembly problem. This can be seen in Table 6.4, where the best integer
solution found could only be shown to be 17.91% from the lower bound on the optimal
solution. In the muffler assembly problem, the LP relaxation of the variable 51'1"

effectively allows for solutions with no setup costs. Setup costs are fomiidable for this

93

problem, accounting for $7,243 of the $92,599 cost for the Walker Manufacturing
schedule.

The SPF L solution degrades as the period length is decreased because of an
increase in the number of setups. Since the heuristic does not consider grouping
production runs to conserve setups, it tends to switch more frequently between products.
This can be seen by comparing Figures 6.2 and 6.3. Figure 6.2 graphically illustrates the
first 25 days of the production schedule for the integer programming solution with a two
hour period length, while Figure 6.3 illustrates the first 25 days of the production schedule
for the SPFL heuristic solution. These figures show that in the integer programming
solution high volume mufflers are grouped into relatively long production runs compared
to the SPFL heuristic solution. The SPFL heuristic solution for the 50 day planning
horizon with two hour periods requires 165 setups, compared to 67 for the integer
programming solution and 53 for Walker Manufacturing’s schedule. The SPFL heuristic
performs better for longer period lengths because it is forced to schedule longer
production runs.

If there were no capacity constraints, the optimal production schedule likely would
have even longer production runs. The economic order quantities for mufflers (expressed
in terms of the equivalent number of two hour periods) is shown in Table 6.6.

The costs for the different muffler assembly line schedules are compared
graphically in Figure 6.4. Note that the SPFL heuristic solution has the lowest inventory
holding costs because it schedules shorter and more frequent production runs of each

muffler. The integer programming solution has labor costs that are approximately the

94

 

    

I Production of 250 units Production of less than 250 units

FIGURE 6.2 GRAPHICAL DISPLAY OF [P SOLUTION

95

“/30

 

I Production of 250 units Production of less than 250 units

FIGURE 6.3 GRAPHICAL DISPLAY OF SPFL HEURISTIC SOLUTION

96

TABLE 6.6 MUFFLER EOQS

 

EOQ equivalent

Muffler 2 hr. periods

8285 9.6

8286 11.4

8289 5.6
8290/91 8.8

8297 5.5

8298 8.8

8329 2.0

same as those of the Walker manufacturing schedule, except towards the end of the
planning horizon where the integer programming solution allows the inventory levels to

fall to zero.

6.5 PIPE AREA RESULTS

Results for the pipe area are presented in Tables 6.7 and 6.8. In Table 6.7, no
clear pattern emerges for period length, either for the integer programming solutions or
the SPFL heuristic. The bounds on the integer programming solutions are not as tight as
those of the muffler assembly line. The muffler assembly problem and the pipe area
problem have the same number Of binary variables-4800 for the 50 period, two hour
period problem--but the pipe area problem is more complex. While the muffler line has
only one workcenter, the pipe area has four. With the number of workers available in the
pipe area either two or three workcenters can be Operated during any period. Also, two
workcenters in the pipe area can produce the same four parts. Thus, in the pipe area more

complicated production “strategies” can be developed, and the branch and bound

97

procedure does not appear to be able to find as good a solution in this more complicated

environment.

98

 

Daily Inventory Costs - Muffler Assembly

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

$160
$140
5120 Walker
:12:
$60 SPFL 1
$40 zszLj
$20
$0
1471013161922252831343740434649
Cumulative Inventory Gods - Muffler Assembly
$4,500
$4,000 ~»
$3.500 «1 ,
$30“) 4» Walkerl
$2.500 1+ a,,""‘ ——--IP
$2,000 4» ’,/’ SPFL
$1.500 ~» _../ _ / ‘ 2821
$1,” 7” /M
$500 4» //
$0 4
1471013161922252831343740434649
Cumulative Labor Costs - Muffler Assembly
$100,000
$80,000 4» / .2 l’,— 1
"C Walker
$60000 1 //’ ————IP
540.000 , //,/./' SPFL
” 2521
3201130 1» '
so - .
1471013161922252831343740434649

 

FIGURE 6.4

COMPARISON OF MUFFLER ASSEMBLY SCHEDULE COSTS

 

 

 

99

TABLE 6.7 SOLUTIONS FOR PIPE AREA

 

 

 

 

 

 

IP Solutions
Planning Horizon (days)
Period Length 10 20 30 40 50
8 1,226 2,976 4,973 7,269 9,152
4 999 4,636 9,219
2 821 4,671 9,054
SPFL Solutions
Planning Horizon (days)
Period Length 10 20 30 40 50
8 1,225 3,105 4,750 7,337 9,519
4 998 3,049 5,164 7,068 9,888
2 1,022 2,963 5,118 7,420 10,108
[P Solution % of Lower Bound on Optimal
Planning Horizon (days)
Period Length 10 20 30 40 50
8 52.16 44.01 36.61 35.97 23.91
4 62.39 28.52 25.13
2 35.78 29.57 22.95

100

TABLE 6.8 COMPARISON OF COSTS FOR PIPE AREA

COMPARISON OF COSTS - 8 hr. Period
Planning Horizon (days)

 

 

 

 

 

 

 

 

Solution 10 20 30 40 50
Walker 2,207 4,042 5,630 7,762 9,922
[P 1,226 2,976 4,973 7,269 9,152
SPFL 1,225 3,105 4,750 7,337 9,519
ZSZI Bound 604 2,030 3,604 5,311 7,363
% OVER ZSZI BOUND - 8 hr. Period
Planning Horizon (days)
Solution 10 20 30 4O 50
Walker 265.4% 99.1% 56.2% 46.1% 34.8%
IP 103.0% 46.6% 38.0% 36.9% 24.3%
SPFL 102.8% 53.0% 31.8% 38.1% 29.3%
COMPARISON OF COSTS - 4 hr. Period
Planning Horizon (days)
Solution 10 30 50
Walker 2,207 5,630 9,922
IP 999 4,636 9,219
SPFL 998 5,164 9,888
ZSZI Bound 604 3,604 7,363
% OVER ZSZI BOUND - 4 hr. Period
Planning Horizon (days)
Solution 10 30 50
Walker 265.4% 56.2% 34.8%
[P 65.4% 28.6% 25.2%
SPFL 65.2% 43.3% 34.3%

101

TABLE 6.8 (CONT’D)

COMPARISON OF COSTS - 2 hr. Period

 

 

 

 

Planning Horizon (days)
Solution 10 30 50
Walker 2,207 5,630 9,922
IP 821 4,671 9,054
SPFL 1,022 5,118 10,108
ZSZI Bound 604 3,604 7,363
% OVER ZSZI BOUND - 2 hr. Period
Planning Horizon (days)
Solution 10 30 50
Walker 265.4% 56.2% 34.8%
IP 35.9% 29.6% 23.0%
SPFL 69.2% 42.0% 37.3%

102

6.6 PRESS AREA RESULTS

Results for the press area are presented in Tables 6.9 and 6.10. These problems
proved extremely difficult to solve. For all previous problems, the branch and bound
preprocessor was used in finding integer programming solutions (bbpreproc = 1 in
GAMS/OSL). For many of the press area problems, there was not enough memory to
allow for preprocessing, so this solution Option could not be used. Table 6.9 indicates
where preprocessing could not be performed. Even without branch and bound
preprocessing, no integer solution could be found for many problems after 24 CPU hours.
The press area problem is much more complicated than the other problems attempted.
Table 6.11 compares the problem complexity for the muffler assembly and pipe area
problems.

For the 10 day problems, the integer programming solution was superior to the
SPFL heuristic, but the integer programming solutions degraded rapidly as the planning
horizon increased. For problems with eight hour period lengths, the integer programming
solution was worse than the SPFL heuristic solution for all planning horizons greater than
10 days, and the integer programming solution had significantly higher costs than Walker
Manufacturing’s schedule for planning horizons greater than 20 days. In all cases the
SPFL heuristic solutions had lower costs than the Walker Manufacturing schedule.

6.7 ENTIRE MODEL RESULTS
Since the press area is a subset of the entire model, it is not surprising that the total

model was very difficult to solve. The results of the entire model problems are given in

103

TABLE 6.9 SOLUTIONS FOR PRESS AREA

 

 

 

 

IP Solutions
Planning Horizon (days)
Period Length 10 20 30 40 50
8 1,296 5,059 9,342 12,396‘ —‘
4 1,007 6,365‘ -"
2 938* -' -"
SPF L Solutions
Planning Horizon (days)
Period Length 10 20 30 40 50
8 1,297 3,585 6,603 9,367 12,539
4 1,056 3,157 5,796 8,858 12.351
2 1,031 3,117 5,837 8,917 -

IP Solution % of Lower Bound on Optimal
Planning Horizon (days)

 

 

Period Length 10 20 30 40 50
8 55.56 146.59 145.05 112.55 -
4 29.17 65.5 -
2 19.77 - -

 

' Problem had to be solved without branch and bound preprocessing.

104

TABLE 6.10 COMPARISON OF COSTS FOR PRESS AREA

COMPARISON OF COSTS - 8 hr. Period

Planning Horizon (days)

 

 

 

 

 

 

 

 

Solution 10 20 30 40 50
Walker 3,1 15 5,838 8,450 1 1,766 14,402
IP 1,296 5,059 9,342 12,396 -

SPFL 1,297 3,585 6,603 9,367 12,539
ZSZI Bound 517 1,245 3,550 5,757 8,294
% OVER ZSZI BOUND - 8 hr. Period
Planning Horizon (days)
Solution 10 20 30 40 50
Walker 502.5% 368.9% 138.0% 104.4% 73.6%
IP 150.7% 306.3% 163.2% 115.3%
SPFL 150.9% 188.0% 86.0% 62.7% 51.2%
COMPARISON OF COSTS - 4 hr. Period
Planning Horizon (days)
Solution 10 30 50
Walker 3,1 15 8,450 14,402
IP 1,007 6,365 -
SPFL 1,056 5,796 12,351
ZSZI Bound 517 3,550 8,294
% OVER ZSZI BOUND - 4 hr. Period
Planning Horizon (days)
Solution 10 3O 50
Walker 502.5% 138.0% 73.6%
[P 94.8% 79.3% -
SPFL 104.3% 63.3% 48.9%

105

TABLE 6.10 (CONT’D)

COMPARISON OF COSTS - 2 hr. Period

 

 

 

 

Planning Horizon (days)
Solution 10 30 50
Walker 3,1 15 8,450 14,402
[P 938 - -
SPFL 1,031 5,837 -
ZSZI Bound 517 3,550 8,294
% OVER ZSZI BOUND - 2 hr. Period
Planning Horizon (days)
Solution 10 30 50
Walker 502.5% 138.0% 73.6%
IP 81.4% - -
SPFL 99.4% 64.4% -

106

TABLE 6.11 MODEL COMPLEXITY FOR MUFFLER AND PIPE PROBLEMS

 

Muffler Assembly Pipe Area

2 hour period length 8 hour period length

50 periods 50 periods
NPmb‘" 0', 2800 3900
Binary Variables
Total Variables 14,400 23,000
Number of 15,200 22,400
Equations

 

 

Tables 6.12 and 6.13. A number of the problems were too large to find integer
programming solutions for within the 24 hour CPU limit. The SPFL heuristic found
solutions for more of the problems, however, it had difficulty as well, especially when the
period length decreased. Capacity becomes a problem for the SPFL heuristic for Short
period lengths because it schedules too many setup changes, which significantly reduces
capacity. Except for the 10 day, four hour period model, the SPFL heuristic solutions are
better than the integer programming solutions, and they are always significantly lower in

cost than the Walker Manufacturing schedules.

6.8 EFFECT OF CAPACITY UTILIZATION ON SOLUTION PROCEDURES

The methods used to generate the high and low capacity demand schedules was
discussed in Section 5.3. Capacity utilization estimates for the three demand schedules are
presented in Table 6.14. The machine capacity estimates for the muffler, pipe and press
areas were made ignoring setups.

The results of the capacity utilization experiments is Shown in Tables 6.15 and

6.16. The exhaust assembly problems were run for 48 hours or until they ran out of the

107

TABLE 6.12 SOLUTIONS FOR TOTAL SYSTEM

 

 

 

 

IP Solutions
Planning Horizon (days)
Period Length 10 20 30 4O 50
8 14,358 41,626 80,084 - -
4 12,481 -‘ -
2 16,608‘ - -
SPFL Solutions
Planning Horizon (days)
Period Length 10 20 30 40 50
8 13,744 41,388 77,169 106,313 137,699
4 12,811 39,434 - - -
2 15,298 45,509 -

IP Solution % of Lower Bound on Optimal

 

 

Planning Horizon (days)
Period Length 10 20 30 40 50
8 50.65 35.28 31.43 - -
4 33.24 -‘ -
2 40.87"

 

° Problem had to be solved without branch and bound preprocessing.

TABLE 6.13 COMPARISON OF COSTS FOR TOTAL SYSTEM

COMPARISON OF COSTS - 8 hr. Period

 

 

 

 

 

 

 

 

Planning Horizon (days)
Solution 10 20 30 40 50
Walker 35,601 66,612 99,457 134,371 174,783
[P 14,358 41,626 80,084
SPFL 13,744 41,388 77,169 106,313 137,699
ZSZI Bound 9,423 30,909 61,934 86,811 1 12,465
% OVER ZSZI BOUND - 8 hr. Period
Planning Horizon (days)

Solution 10 20 30 40 50
Walker 277.8% 115.5% 60.6% 54.8% 55.4%
[P 52.4% 34.7% 29.3% - -
SPFL 45.9% 33.9% 24.6% 22.5% 22.4%
COMPARISON OF COSTS - 4 hr. Period

Planning Horizon idays)
Solution 10 30 50
Walker 35,601 99,457 174,783
IP 12,481 - -
SPFL 12,811 - -
ZSZI Bound 9,423 61,934 1 12,465
% OVER ZSZI BOUND - 4 hr. Period
Planning Horizon (days)
Solution 10 3O 50
Walker 277.8% 60.6% 55.4%
IP 32.5% - -
SPFL 36.0% - -

 

109

TABLE 6.13 (CONT’D)

COMPARISON OF COSTS - 2 hr. Period

 

 

 

 

Planning Horizon (days)
Solution 10 30 50
Walker 3 5,601 99,457 1 74,7 83
IP 16,608 - -
SPFL 15,298 - -
ZSZI Bound 9,423 61,934 112,465
% OVER ZSZI BOUND - 2 hr. Period
Planning Horizon (days)
Solution 10 3O 50
Walker 277.8% 60.6% 55.4%
[P 76.2% - -
SPFL 62.3% - -

110

TABLE 6.14 MACHINE AND LABOR CAPACITY

 

 

 

Machine Capacity

Production Area Low Capacity Walker Demand High Capacity
Welding 16.7 37.7 41.9
Muffler 22.2 55.9 62.9
Bushing 5.2 20.0 23.0
Press 1.6 9.2 11.0

Labor Capacity

Classification Low Capacity Walker Demand High Capacity
Welders 30.8 69.0 76.6
B Operators 16.8 44.0 49.7
C Operators 3.3 19.6 23.4

 

Note: Capacity figures calculated ignoring setups.

111

TABLE 6.15 CAPACITY EXPERIMENT WITH 30 DAY PLANNING HORIZON

Comparison of Solutions

 

Solution Low Walker High
Model Type Capacity Schedule Capacity

Exhaust Assy [P 12,611 27,845 33,065
SPFL 12,701 27,042 33,373
Mufller Assy 17,280 40,315 50,217
SPFL 17,306 40,652 51,793
Pipe Area 1,131 3,702 4,057
SPF L 1,133 3,378 4,520
Press Area 3,211* 4,453* 6,068*
SPFL 2,833* 4,618* 5,762*

Total System 39,609 80,084 -
SPFL 34,790 7 7 ,169 92,721

*Additional inventory had to be added to the problem to find a feasible solution
using the SPFL heuristic.

IP Solution % of Lower Bound on Optimal

 

Low Walker High
Model CapacthI Schedule CapacitL
Exhaust Assy 11.52 10.21 4.46
Muffler Assy 54.54 22.42 17.52
Pipe Area 44.85 59.46 23.55
Press Area 3642* 71.02 98.51
Total System 61 .48 3 1 .43 -

112

TABLE 6.16 CAPACITY EXPERINIENT WITH 50 DAY PLANNING HORIZON

Comparison of Solutions

 

Solution Low Walker High
Model Type Capacity Schedule Capacity
Exhaust Assy [P 22,313 47,481 54,785
SPFL 22,364 46,541 54,377
Muffler Assy [P 35,131 72,822 85,501
SPFL 31,790 73,826 87,144
Pipe Area IP 2,668 7,282 7,634
SPFL 2,603 6,864 8,27 1
Press Area IP 5,328* - -
SPFL 4,652* 8792* 1 1,067*-
Total System IP - - -
SPFL 62,874 137,699 151,605

*Additional inventory had to be added to the problem to find a feasible solution
using the SPFL heuristic.

1P Solution “/o of Lower Bound on Optimal

 

Low Walker High
Model Capacity Schedule Capacity
Exhaust Assy 9.92 9.39 6.93
Muffler Assy 41.25 20.52 17.64
Pipe Area 60.02 40.55 18.50
Press Area 53.28

Total System

113

300 MB of memory available. For the low capacity models, running out of memory
occurred quickly and the first solutions found for the low capacity exhaust assembly
problems were the best found. For the Walker demand schedule, the solution procedure
also stopped after running out of memory, but for both the 30 and 50 day problems, a
number of better integer solutions were found as the problem ran. The high capacity
models ran until the 48 CPU hour limit. It appears that for the high capacity problems the
enumeration tree was smaller because branches could be “pruned” due to infeasibility.
Integer programming found better solutions for the low capacity problems, but the SPFL
heuristic solutions were better for high capacity problems. The bounds on the integer
programming solutions were tighter for the high capacity problems, but that does not
mean that the solutions found were necessarily closer to the optimal.

For the muffler assembly problems, demand was taken from the integer
programming solutions from the exhaust system assembly problems. The integer
programming solutions were in general better than the SPFL heuristic solutions. In only
one case (low capacity model, 30 day planning horizon) was the SPFL solution was better
than the integer programming solution. Low demand levels should favor shorter
production runs, which would explain why the SPFL heuristic performed well in the low
capacity models. For the muffler assembly problem, the bounds again are tighter when
demand is high.

For the pipe area problem, the integer programming solutions were better for the

high capacity problems but not for the Walker schedule or the low capacity problem. The

114

bounds on the integer programming solutions are in general tighter as demand increases,
but this does not always hold true.

In the press area, demand was generated from the integer programming solutions
for the muffler assembly problem. These demand schedules resulted in infeasible solutions
to the SPFL heuristic, so additional inventory needed to be added to the problems. The
labor cost for this additional inventory was small (less than $20), but this points out a
problem with hierarchical decomposition--it may be possible to find a solution to the entire
problem, but decomposing the problem may result in a set of solutions at one level of the
problem that creates feasibility problems at lower levels.

For the press area, integer programming solutions could not be found for all
problems. The 50 day Walker demand schedule problem was run for 48 hours with no
integer solution found. Where solutions could be found, the SPFL heuristic solutions
were better in all but one case, where it was only 3.7% higher in cost.

Solutions for the total system could be found for the 30 day planning horizon
problems with low capacity and Walker schedules. In both cases, the SPFL heuristic
solution was significantly better than the integer programming solution. These solutions
can also be compared to solving the problem using hierarchical decomposition. Adding
the integer programming solutions for the exhaust system assembly and mufiler assembly
problems to the best solutions for the pipe and press area results in costs of 33,857 and
$77,991 for the low capacity and Walker demand schedules, respectively. Thus,
hierarchical decomposition can result in lower cost solutions, but as mentioned above.

feasibility can be a problem.

7.0 DISCUSSION

7.1 SOLUTION OF THE MODEL

The MSS model provides a framework to convert a master production schedule
into a set of shop floor run schedules. These run schedules consider machine capacity,
labor capacity and setups, not as aggregate quantities but in detail. The advantage of the
MSS model over other scheduling methods is that the shop floor run schedules, if
executed correctly, will meet the master production schedule within given capacity
constraints. With techniques like Kanban and MRP, using the method does not guarantee
that the master production schedule will be met.

In this study, two techniques were evaluated for solving the MSS model: integer
programming via the branch-and-bound method and the SPFL heuristic. Integer
programming did not prove to be a practical technique for most environments. When the
problem was complex (many components, many workcenters or dependent demand) the
solutions were not particularly good.

Further, many firms in repetitive manufacturing environments are of small to
medium size and would not have computer resources similar to those used in this study.
Even if these resources were available, the time required to find a good solution (most
likely 24 hours or more) could result in many difficulties in actual implementation. In
practice, many firms have dynamic environments where fi'equent rescheduling would be
necessary. First tier automotive suppliers are frequently confronted with schedule changes
from the big three automotive manufacturers, and this is often the case when the customer

holds most of the power in the buyer-supplier relationship. Even if the master production

115

116

schedule is frozen for a reasonable planning horizon (as is typically done by Japanese auto
manufacturers), other factors may require frequent replanning, such as employee
absenteeism or machine breakdowns (although the MSS model could lead to reduced
machine breakdowns, which is discussed in Section 7.3.5). Some firms in repetitive
environments operate in an order-promising mode and would need quick solutions of the
model to provide customers with firm delivery dates. Finally, the cost of computer
resources to obtain good solutions via integer programming could very easily exceed the
potential cost savings.

The SPFL heuristic can quickly find solutions to the MSS model. Based solely on
the time to find a solution, it would be ideal for order promising, although it does not
consider how best to schedule setup changes. When setups are non-existent, as in the
exhaust system assembly problem at Walker Manufacturing, the SPFL heuristic works
quite well. When setups are significant, as in the muffler assembly problem, the SPFL
heuristic can produce solutions with significantly more setups than are ideal. In addition
to increasing costs, scheduling too many setups can result in a significant loss of capacity.

Capacity management is a challenge in environments with setups. If setups are
made too frequently, too much productive capacity is lost. As the number of setups is
decreased, inventory levels must be increased as it takes longer to cycle through all of the
components produced at a workcenter. When setups are significant, capacity problems
can arise because setups are changed too frequently or not frequently enough. Modifying
the SPFL heuristic to perform better when setups are significant will greatly increase its

complexity, but a couple of approaches could prove USCfiJl.

117

One simple change to the procedure would be to change the choice of which
components are scheduled first at a workcenter. The SPFL heuristic scheduled
components based on low level code, then in order of highest unit cost. For the mufiler
assembly line, the highest cost components are not the highest volume components.
Scheduling high volume rather than high cost components first may result in a schedule
requiring fewer setups. Another approach would be to schedule larger production runs.
For example, economic order quantities could be calculated from the master production
schedule and converted into the equivalent number of periods of production (period order
quantity, POQ). When production of a component is scheduled, the machine could be
scheduled for a number of consecutive periods equal to its POQ. For high demand
situations, the decision to schedule a group of periods may have to be evaluated in light of
other components that need to be produced. Scheduling longer production runs would
likely be a management decision that could be adapted to individual cases.

In some environments the SPFL heuristic may handle setups better than it did for
the muffler assembly line. Demand for the muffler assembly line was driven by the exhaust
system assembly workcenters. This resulted in a demand pattern with frequent, small
quantities. In many production environments, the primary setup problem occurs in final
assembly. If end-item demand results from relatively large customer orders, the SPFL
heuristic may end up scheduling larger, and perhaps more ideal, production quantities.

Further research is clearly needed for MSS model solution procedures. While
integer programming did work well for the muffler assembly line problem, it failed to do
as well when the environment was more complex and had great difficulty finding solutions

for larger problems. Since the branch-and-bound procedure tries to find integer solutions

118

in the “region” where the LP relaxation is optimal, it may fail to do well with more
complex problems because it does not explore the “search space” well. A genetic search
algorithm applied to the MSS model may find better solutions by evaluating more of the
“search space.” The SPFL heuristic and variations on it might provide good starting

“genetic material” in a genetic search algorithm.

7.2 THE COMPARISON TO WALKER MANUFACTURING

While the quality of solution procedures for the MSS model is important, the true
test of the model is how good it is compared to other scheduling techniques. Comparing
the MSS model to MRP or Kanban would provide the ideal evaluation. Unfortunately, it
is difficult to compare the MSS model to these systems because they require numerous
decisions to be made by schedulers and shop floor personnel, and it would be difficult to
determine how these decisions are made in practice, much less how they should be made.
The approach used in this dissertation was to compare the model to the decisions made by
a firm (Walker Manufacturing) in a repetitive manufacturing environment. While this
allowed for the model to be evaluated on an industrial sized problem, it produced only one
comparison. Further, there is no objective way to evaluate how well Walker
Manufacturing was handling its production scheduling compared to other firms, except to
say that it was in business and profitable for a reasonably long period of time.

The value of the comparison to Walker Manufacturing was strengthened by
assuming ideal labor productivity for the Walker Manufacturing schedule. Even assuming
ideal efficiency, the MSS model provided clearly superior schedules. It is reasonable to
expect that the MSS model, especially with improved solution heuristics, could improve

the scheduling capabilities of many manufacturers in repetitive environments. The MSS

119

model structure can provide other benefits to manufacturing firms beyond good
production schedules. While these benefits are difficult to quantify, they could prove to be

significant. Section 7.3 describes these benefits
7.3 OTHER BENEFITS OF THE MSS MODEL

7.3.1 Simplified shop floor management

A principal benefit of the MSS approach is that the management of labor and
machines is coordinated. The product of the MSS model is a detailed shop floor schedule
that, if executed as planned, will allow orders to be shipped on time. Further, the shop
floor schedules can be executed as planned because they were developed considering all
of the facility’s constraints in detail. In comparison, if MRP is used with capacity
planning, what it produces is shop orders with due dates, and it is up to the shop floor
supervisor to determine which order to process next, which workcenters to operate and
where to assign workers. This is a formidable task which can consume much of the
supervisor’s time. With MSS run schedules, these decisions have been made--the
supervisor has a schedule of what each workcenter will be producing at any given time.
The supervisor must assign workers to each operating workcenter, but this is not a
difficult task since the schedule was developed considering the available labor. With M SS
run schedules, the shop floor supervisor is fiee to manage the production task, not the

scheduling.

7.3.2 Reduced lead times compared to MRP

120

For an MRP system to fiJnction properly, lead times must be set so that a high
percentage of shop orders can be completed on time. Long lead times reduce the
responsiveness of the production system and increase WIP inventory. Many firms in
repetitive environments have developed their own scheduling systems because of long lead
times and other problems related to MRP systems. Frequently, these systems take the
form of an “expert” system, where an individual becomes the scheduling expert and
develops schedules through various means, including intuition. This, in fact, was the way
in which Walker Manufacturing developed schedules. The MSS model converts the
master production schedule into detailed shop floor schedules without using inflated lead

times and, therefore, is a more responsive scheduling technique.

7.3.3 Proactive response to changing demand

Kanban systems have proven effective in Japan, but the disadvantage of a “pull”
system like Kanban is that it cannot anticipate changes in demand patterns. One of the
frequently misunderstood (and perhaps most important) factors in a JIT system is the use
of level production schedules. Kanban systems have worked well for Japanese
manufacturers that are willing to set level master production schedules. Japanese auto
manufacturers typically provide suppliers with a demand schedule that is frozen for a
number of weeks. When applied to an environment where demand patterns shifi
dramatically, Kanban systems suffer. The MSS model can provide a means to proactively
respond to changes in demand pattern. The model can be modified easily to allow for the

scheduling of overtime as well, so that overtime can be a planned response to demand

 

121

changes, rather than a short term reaction to a late order as in MRP or an empty Kanban

in a JIT system.

7.3.4 One shop floor performance measure

With the MSS model, evaluating shop floor performance is simplified because
performance objectives are built into the model. If management is convinced that the
model correctly considers and weighs all relevant factors in determining a production
schedule, all that shop floor personnel need to do is carry out the schedule developed by
the MSS model. One of the most difficult tasks may in fact be convincing management
that it is not likely that schedules developed using the model can be improved upon
through trial and error and that other performance measures should not be analyzed.

In an MRP system where the shop floor supervisor makes numerous scheduling
decisions, a number of performance measures (sometimes contradictory) are used to
evaluate the supervisor. In trying to optimize performance measures, production
schedulers and shop floor supervisors can end up making decisions that boost performance

measures but degrade the performance of the system as a whole.

For example, at Walker Manufacturing an important performance measure was
daily labor efficiency, which was defined as the dollar value of finished goods produced
divided by the dollar value of the labor used that day. Labor efficiency measured in a
more aggregate fashion (e. g. weekly or monthly) is probably a good measure of the
efficiency of a production facility, but on a daily basis this measure is too volatile. An
optimal production schedule could require relatively few finished products to be produced

on a particular day, and while the production facility may be very efficient in producing

122

what it should on that day, the daily labor efficiency measure would indicate poor
performance. A manager who is evaluated by daily labor efficiency will face pressure to
push finished goods out the door each day, with the result that the formal planning and
scheduling system will be replaced with “hot lists” or other manifestations of an informal

system.

Performance measures can also lead to poor decisions when measured too
infrequently. Raw material inventory was used as a performance measure at Walker
Manufacturing, but it was measured only at the end of each month. To achieve a good
score on this performance measure, management of the Walker facility would let raw
steel inventories drop to low levels at the end of the month, only to be replenished quickly
at the beginning of the next month. Not only did this measure provide an inaccurate
picture of raw materials inventory, it had an impact on production decisions. Because of
low steel levels at the end of the month, the supervisor for the pipe and press areas could
not consider grouping production batches to conserve setups because there would not be
sufficient steel for other required components.

The MSS model can be used to avoid performance measure problems because only
one performance measure is important--how well was the schedule met. Since the MSS
model schedules are feasible and optimized (to the extent that the model and the solution
procedures allow), there is no practical way to improve on the solution. To evaluate the
performance of the production facility with an MSS schedule, there is only one
performance measure: how well did the shop floor do in producing to schedule. With the
MSS model managers, shop floor supervisors and shop floor workers would all be clear as

to what is required for good performance. They would not be evaluated by a set of

123

measures that may be in conflict and driven to achieve good performance measures by
making decisions that in the long run are bad for the firm. And with one performance

measure, less effort would be spent measuring and evaluating performance.

7.3.5 Better management of labor and maintenance

Managing a labor force in light of changes in demand is one of the more
challenging tasks of the operations manager. This is particularly true when the labor force
is skilled and layoffs would result in the permanent loss of employees that would be
needed in the near future. It is not uncommon for firms to operate with more labor than
required to keep skilled workers in the company. During low demand periods, workers
tend to work at a slower, more leisurely pace. For example, if a worker can produce 200
units a day but only 100 units are needed, the worker may produce the 100 units by
working more slowly and inserting more coffee breaks and conversations into the
workday. With the MSS model, the worker could be scheduled to produce 100 units
during the first half of the day and the second half of the day could be used for other
purposes such as training, maintenance or repair/rework. While excess labor capacity
could be similarly employed with other scheduling approaches, the MSS model is
particularly adept at allowing idle labor to be applied to other usefiJl functions because it

schedules labor in detail.

By producing detailed run schedules, the MSS model can lead to improved
preventative maintenance scheduling. It is generally accepted that preventative
maintenance can result in better facility performance because unexpected breakdowns are

minimized. The trouble with implementing preventative maintenance programs is that

124

traditional scheduling systems do not have the ability to detemrine when equipment will be
idle for maintenance. The MSS model defines what each machine will be doing in each
production period. Maintenance can then be scheduled during idle periods or, if longer
periods are required, the production schedule can be developed with maintenance periods

blocked out.

7.3.6 Potential for increased discipline

All of the items described above can lead to a more disciplined production facility.
First, the MSS model schedules provide a common “script” for the production facility. All
people involved in production can determine what needs to be done from the run
schedules. When the shop floor is not scheduled in detail, it is not unusual for supervisors
and material managers to develop their own planning systems. These systems are
frequently incompatible with each other even though they may be keeping track of similar
information. With the MSS model, the run schedules provide a single detailed production
plan that provides the information needed by all involved parties.

Successfiil implementation of the MSS model should lead to more stable
production facility performance. With performance to schedule as the only performance
measure, decisions that work at cross purposes to the efficient operation of the facility will
likely be avoided. Managers will not be compelled to press shop floor supervisors to
make bad decisions that make the “numbers” look good. The emphasis will be to meet the
plan, which will make planning that much easier. The MSS model can facilitate
preventative maintenance programs, which will result in more consistent production

because there will be fewer unexpected breakdowns. A comprehensive scheduling system

125

like the MSS model can lead to production facility consistency, which improves the ability

to schedule the production system.

7.4 MODIFICATION OF THE MODEL TO ALLOW SETUP CHANGES AT
THE END OF A PERIOD

Afier completion of the experimental portion of this study, a modification to the
model was suggested by Paul Rubin of the dissertation committee that would allow for
setup changes to be started at the end of a period if idle time was available. To do this,
the MSS model presented in Section 3 .2 is modified by adding the continuous variable S],
which is the idle production time in period t-l that can be used to change the setup for
production of a new component in period t. This variable is defined by adding the

following constraint to the mode:

1
512m +—2(th + Yth + 20'!) 5 Z50:
[”1 i i

This idle production time reduces (and, perhaps, eliminates) the time required to change
the setup in period t. This is done in the model by modifying constraint (7). The new

constraint is then:

Zijt +pjijt _>_ (lg-6,7, -Zvi"j7i'jat“l

I
Allowing setup changes at the beginning and the end of a production period
increases the flexibility of the model. The impact should be most pronounced when the

period length is larger than the economic production quantity.

8.0 CONCLUSIONS

The MSS approach to production scheduling presented in this dissertation
provides a framework that can be used to develop detailed production schedules in a
repetitive manufacturing environment considering the three major production factors:
labor capacity, machine capacity and machine setups. In this dissertation, the model was

evaluated using a real production facility and the schedules produced by the model were

 

I?
compared to actual production decisions. This evaluation produced two significant
results: the model provided schedules that were superior to those used by Walker :'

r.
Manufacturing, and improved solution techniques are needed. The SPFL heuristic {I

provided quick solutions that were good except in the face of significant setups. Integer -F
programming can be used to find solutions to the model, and it proved to work well for

smaller problems, but when the problem got more complicated, the ability to find solutions

degraded significantly and in all cases the cost of obtaining solutions via integer

programming were significant.

Based on the favorable comparison of the model’s schedules with Walker
Manufacturing’s decisions and the numerous advantages described in the previous section,
firrther research on this model is warranted. First, improved solution heuristics need to be
developed. Two areas appear promising. First, the SPFL heuristic can be improved. The
primary area for improvement is in how setups are handled. What might develop from
research in this area is a set of easily solved heuristics producing a number of solutions
from which the best solution can be selected. A second approach that might work well is

a genetic search algorithm.

126

127

With an improved set of solution techniques, the next step in the development of
this approach would be to evaluate its performance further. One method of evaluating the
model would be to construct a detailed simulation to compare the MSS model to MRP
and Kanban systems. The major difficulty with this evaluation is the question of how to
properly model the numerous human judgments used in these systems. The second means
of evaluating the model would be to apply it in an actual production setting. The difficulty
here is that a number of implementations would have to be evaluated to be confident that

in general the model is an effective production scheduling technique.

Production scheduling has been an area of significant research, and much work still
needs to be done. While the MSS model is not yet a fully functional production
scheduling system, it does promise to provide a comprehensive system for scheduling

production in a repetitive manufacturing environment.

LIST OF REFERENCES

LIST OF REFERENCES

Anderson, J.C., R.G. Schroeder, S.E. Tupy and E. M. White, "Material Requirements
Planning: The State of the Art", Production and Inventory Management, 1982,
Vol. 23, No. 4, pp. 51-66.

APICS Repetitive Manufacturing Group, "Repetitive Manufacturing", Production and
Inventory Management, Second Quarter, 1982.

Bahl, Harish C. and Larry P. Ritzman, "An Integrated Model for Master Scheduling, Lot
Sizing and Capacity Requirements Planning", Journal of the Operational Research
Society, Vol. 35, No. 5, 1984.

Bahl, Harish C., Larry P. Ritzman and Jatinder N. D. Gupta, "Determining Lot Sizes and
Resource Requirements: A Review", Operations Research, Vol. 35, No. 3, May-
June 1987.

Baker, K. R., Introduction to Sequencing and Scheduling, Wiley, New York, 1971.

Billington, Peter J ., John O. McClain and L. Joseph Thomas, "Mathematical Programming
Approaches to Capacity-constrained MRP systems: Review, Formulation and
Problem Reduction", Management Science, Vol. 29, No. 10, October 1983.

lBitran, G. R. and A. C. Hax, "On the Design of Hierarchical Production Planning
Systems," Decision Sciences, 8(1), 1977.

Blackburn, Joseph D. and Robert A. Millen, "Improved Heuristics for Multi-Stage
Requirements Planning", Management Science, Vol. 28, No. 1, January 1982.

Blackstone, J .H. Jr., Don T. Phillips and Gary L. Hogg, "A State-of-the-Art Survey of
Dispatching Rules for Manufacturing Job Shop Operations", International Journal
of Production Research, Vol. 20, No. 1, 1982.

Bruvold, Norman T. and James R. Evans, "Flexible Mixed-Integer Programming
Formulations for Production Scheduling Problems", 11E Transactions, Vol. 17,

No. 1, March 1985.

Buffa, ES. and J .G. Miller, Production-Inventory Systems: Planning and Control, Irwin,
Homewood, 111., 1979.

Buffa, ES. and W.H. Taubert, Production-Inventory Systems: Planning and ('Torrtrol,
Irwin, Homewood, 111., 1972.

Conway, R., W. Maxwell and L. Miller, Theory of Scheduling, Addison-Wesley, Reading,
MA, 1967.

128

 

129

Crowston, Wallace B., Michael Wagner and Jack F. Williams, "Economic Lot Size
Determination in Multi-Stage Assembly Systems", Management Science, Vol. 19,
No. 5, January 1973.

Elmaghraby, Salah E., "The Economic Lot Scheduling Problem (ELSP): Review and
Extensions", Management Science, Vol. 24, No. 6, February 1978.

Fredendall, Lawrence Dean, "An Experimental Investigation of Information Use in a Job
Shop Operating Under Dual Resource Constraints: A Simulation Study",
Unpublished Ph.D. Dissertation, Michigan State University, 1991.

Gabbay, Henry, "Multi-Stage Production Planning", Management Science, Vol. 25, No.
11, November 1979.

Johnson, Al and DC. Montgomery, Operations Research in Production Planning,
Scheduling and Inventory Control, Wiley, New York, 1974.

McKay, Kenneth N., Frank R. Safayeni and John A. Buzzacott, "Job-Shop Scheduling
Theory: What is Relevant?", Interfaces, Vol. 18, No. 4, August 1988, pp. 84-90.

Panwalker, SS. and Wafik Iskander, "A Survey of Scheduling Rules", Operations
Research, Vol. 25, No. 1, January-February 1977.

Prabhakar, T., "A Production Scheduling Problem with Sequencing Considerations",
Management Science, Vol. 21, No. 1, September 1974.

Raia, Ernest, "Saturn: Rising Star", Purchasing, Vol. 115, No. 3, September 9, 1993.
Smith-Daniels, Vicki L. and Dwight E. Smith-Daniels, "A Mixed Integer Programming
Model for Lot Sizing and Sequencing Packaging Lines in the Process Industries",

IIE Transactions, September 1986.

Silver, E. A. and Peterson, R., Decision Systems for Inventory Management and
Production Planning, John Wiley & Sons, New York, NY, 1985.

Steinberg, Earle and H. Albert Napier, "Optimal Multi-Level Lot Sizing for Requirements
Planning Systems", Management Science, Vol. 26, No. 12, December 1980.

Sum, Chee-Chuong and Arthur V. Hill, "A New Framework for Manufacturing Planning
and Control Systems", Decision Sciences, Vol. 24, No. 4, July-August 1993.

Von Lanzenauer, Christoph Haehling, "A Production Scheduling Model By Bivalent
Linear Programming", Management Science, Vol. 17, No. 1, September 1970.

130

Vollman, T. E., Berry, W. L. and Whybark, D. C., Manufacturing Planning and Control
Systems, Irwin, Homewood, IL, 1988.

Williams, J. F., "On the Optimality of Integer Lot Size Ratios in 'Economic Lot Size
Determination in Multi-Stage Assembly Systems'", Management Science, Vol. 28, No. 1 1,

November 1982.

APPENDIX

APPENDIX

COMPUTER PROGRAM DEVELOPED FOR THE MSS MODEL

Since a computer program was required to calculate production schedules using
the SPFL heuristic, a program was written to both solve the problem using the SPFL
heuristic and create data files for integer programming codes. The computer program,
MSS Plan, was written in VisualBasicTM Professional version 3.0, an object-oriented
programming language, to demonstrate that the MSS model and SPFL heuristic can be

implemented so that a production planner would find it easy to use.

THE MSS PLAN COMPUTER PROGRAM

Figure A1 shows the main screen for the MSS Plan computer program. The
options grouped under Input Component and Process Data allow the user to input
data that primarily describe the production process. The options grouped under Input
Schedule Data, allow the user to input data related to a particular planning problem.
The options grouped under Solution Options allow the user to solve the model using
the SPFL solution heuristic or create an input data file for either the GAMS/OSLTM or
CPLEXTM integer programming sofiware.

Selecting the Components option under Input Component and Process
Data calls up the component data screen shown in Figure A2. This screen allows the user

to define a component by entering the component name in the first text box. Along with

131

\
i
.
\
i
‘
i
l
.
r
‘
i
>
I
.
t
)
i
t
h
)
i
.
s
C
l
i
P
5
i
.'
K
.
s
)
\
i
i
i
1
h

M33

132

Plan

 

 

Input Component
Data

 

Input Labor

 

 

Input Workcenter:

 

 

Print Hodel Data

 

”Input Component and Process Data —‘

 

”Input Schedule Data

 

Period Title:

 

 

Component
Demand

 

 

Labor
Schedule

 

 

Workcenter
Availability

 

 

 

 

 

 

 

Create File 5;: Create File for Bun SPFL
for CPLEX BAHSIOSI. g2; Heuristic

 

 

FIGURE A1 MSS PLAN MAIN SCREEN

 

133

 

Name Text Box

"Enter Component ID A‘_ ”Constituent Components
Chid Components

324182
H 324202
H 324482
I. 3241 42

 

 

 

 

 

  
   
 

 

 
 
 
   

BOM defined
by child components
and quantities

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Child components
.. are selected by
123““ '""°"'°" l clicking on the
component in the

 

 

 

 

list and clicking ADD

 

 

 

 

 

 

 

 

 

 

 

[ Inventory Carrying z |2{

Inventory carrying charge for all components

 

 

 

 

 

FIGURE A2 COMPONENT DATA INPUT SCREEN

134

the component name, the unit cost and initial inventory are also entered in this screen. On
the right side of this screen, the BOM is entered by defining the child components for the
component highlighted in the left-hand list of components. The inventory holding cost (%
of unit value per year) is also entered in this screen. This figure is used for all
components.

Selecting the Labor Divisions option under Input Process and Component
Data calls up the screen shown in Figure A3. This screen allows the labor divisions to be
defined along with the hourly wage rate.

Selecting Workcenters calls up the screen shown in Figure A4. On this screen,
the facility workcenters are defined by naming the workcenters, defining the components
that are produced at the workcenter and entering production data and labor requirements.
Components that can be produced at a workcenter are defined by highlighting the
workcenter in the list and selecting components from the list of components and clicking
the ADD button. For each component that can be produced at a workcenter, additional
data must be defined. When the active component is selected from the upper list of
components the hourly production rate can be defined along with the nature of the
material transfer delay. If Periods is selected, the entry shows how many periods must
elapse before the components will be available for use at a downstream workcenter (in
Figure A4, one period of delay is indicated, meaning that component M8285 will be
available in the next period after it is produced). If Parts is selected, then the value
represents the maximum number of parts that can be transferred to a downstream

workcenter during the production period. This is the parameterfi, defined in Section 3.

135

      
    
  

.....
--------

...... Labor Divisions

............

Beturn

 

 

' Enter Labor Division

 

 

 

 

 

\‘n‘ ‘y'.'o\‘e'a

u... .

. -.-_ .
. u ,
v ~
.3. .
..a_ . . . .
'.‘. ‘ s
n . a ~ 1

 

 

 

(mumm—

Welder

    

 

 

 

 

Wage Hate [Slhr]

  

 

 

 

 

 

 

 

FIGURE A3 LABOR DIVISION SCREEN

136

 

 

 

The labor required
Data shown in the at the workcenter
rest of the screen Text bOX for for the highlighted
is for the workcenter defining a component is entered
highlighted in this list workcenter here

 

 

 

 

 

 

 

 

 

~~UM~ “~-WMM~.M~WA“A-AA w~w~-~~u~w MA“ ‘A \ VK‘AA-rk ku,‘ ~qu A-AA x.- --.- k-.-.-.-.. . A

m Workcentem
fleturn

 

 

neared-jot on. ’Define cm: and Labor near-i m
i center Name C

onponent _ D —
M 3235 @ Periods
M 8289 1 a»,
14 8290191
14 8297

H 0290 0 Parts
M 8329

Partition Press -=' git

55 2-318 his

55 2-5I8 Prod. per hour It Workers
SS 5 "..‘i e ‘5

er.
Workcenter Setup to
" Setups Produce

O No Setup: ....... [M 8329 ‘l -. ‘
._ .i In Fist Period 8 Operator

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Components that can be Selecting this entry adds
produced at the workcenter constraint (6) to the IP
are added from this list model file

 

 

 

 

 

FIGURE A4 WORKCENTER DEFINITION SCREEN

137

The labor requirements are defined by adding the labor divisions required from the list at
the bottom-right of the screen. Selecting the labor division from the top-right-hand list
allows the user to enter the number of workers in the text box.

When all components that can be produced at a workcenter are defined, the nature
of the setups can be identified. Three options are grouped under Setups at the lower-left
side of the screen. If setups are required, they are defined as sequence-independent or
sequence-dependent. For sequence-independent setups, a single figure is entered which
defines the setup loss in terms of the number of components of production lost while the
workcenter setup is being changed. If the setups are defined as sequence-dependent, then
by selecting Show Losses the screen shown in Figure 6.5 appears and allows the
scheduler to define the sequence-dependent setup losses in terms of the units of
production lost in switching from the component listed in the row to the component listed
in the column. In addition to the nature of the setup losses, the scheduler can define
whether production losses are allowed during idle periods. Selecting YES adds constraint
(6) to the CPLEX and GAMS/OSL model files, but has no impact on the SPFL heuristic
since the heuristic does not schedule setups during idle periods, even if they are allowed.

Completing the Components, Labor Divisions and Workcenters screens
defines the production environment. Schedule data is entered by first selecting Planning
Horizon under the Input Schedule Data group, which calls up the screen in Figure
A6. The user can enter the number of periods in the planning horizon, the length of each
period in hours, the number of periods in each inventory counting cycle (Periods per

Cycle) and the number of inventory cycles per year.

138

 

5 Sequence Dependent Setup Losses
Beturn

 

 

 
 

[Grid Commands

 

 

 

 

 

 

FIGURE A5 SEQUENCE-DEPENDENT SETUP LOSS SCREEN

139

 

 

These 4 entries define
the planning horizon

 

 

 

Batu rn

 

 

r v ‘
Number of Hours per Periods Cycles per a,“ Commands
Year

Periods

as

Period per Cvcle

a3 Sui 2w

 

 

 

 

 

 

This grid allows each period to be given 2 identifiers

 

FIGURE A6 PLANNING HORIZON SCREEN

 

 

140

Figure A6 shows a planning horizon screen for a model of the muffler assembly line using
a 4-hour period length. Since the muffler line runs for two 8-hour shifts each day and
there are four 4-hour periods in each day, Periods per Cycle is set at 4 and inventory
costs are assessed on inventory levels at the end of each second shift. Assuming that there
are 50 work weeks in the year, there would be 250 inventory cycles per year. Given the
4-hour period length and the two shifi work day, the 200 period model covers 50 working
days. Once the planning horizon has been defined, two text entries can be entered in the
grid to uniquely identify each period.

With the planning horizon defined, a demand schedule can be entered by selecting
Demand from the Input Schedule Data group, which calls up the screen in Figure A7.
The user can enter the demand for any component in this screen (both end items and
subcomponents). The convention is that the demand must be met by the end of the period
in which it is entered.

The labor schedule can be entered in a similar manner using the screen shown in
Figure A8. This screen defines the number of workers in each labor division that are
available in each period of the planning horizon.

By choosing Availability from the Input Schedule Data group, the planner
can define which workcenters are to be operated each period using the screen of Figure
A9. This entry is required for those facilities where some workcenters are not operated

every period. For example, at Walker Manufacturing the muffler assembly line worked

141

[lemand‘o‘chedule ’ r l r I I M

 

 

{

 

 

 

 

 

FIGURE A7 DEMAND SCHEDULE SCREEN

142

Labor Schedule

 

 

x;
x“ vs .2“

'kaxw ~
.. “N. ~.~.-.~.-. -.

x -:
(KVK‘IA

gag-gr

\.
-..

:1.
~.

ik' -.
W.)

t‘téoftii.
~. w
v. “x.

 

 

 

 

ammmaamaamasmima
we:

 

 

 

 

FIGURE A8 LABOR SCHEDULE SCREEN

143

 

’ Beturn
Grid Commands

 

 

 

 

 

 

 

 

FIGURE A9 WORKCENTER AVAILABILITY SCREEN

144

two shifts, but most other workcenters did not. By entering an X in the appropriate
periods, the program will not include the variables and constraints associated with the
workcenter for those periods in the integer programming models and will not allow the
SPFL heuristic to schedule production in those periods.

With the component, process and schedule data entered, the program will allow
the user to create integer programming models or run the SPFL heuristic. If the SPFL
heuristic is successful in finding a solution to the problem, a number of output options are
available for the results as shown in the Figure 6.10. The production schedule screen
shows the production schedule data (which can be printed) that can be used to run the
shop floor. The screen displays a run schedule--a schedule that shows how many of each
component should be produced at each workcenter in each period. This schedule is
simple to interpret and use to run a shop floor, yet it was developed considering all of the
constraints in the manufacturing facility: labor, setups, machine capacities, etc.

If the user selects the GAMS option, the file name and directory are defined by the
top screen of Figure 6.11, while the GAMS solution parameters can be defined in the
screen shown at the bottom of Figure 6.11. The program currently does not have the
capability to read the solutions from the GAMS output files to create output screens
similar to those in Figure 6.10, but this capability is easily added.

The MSS Plan program, besides providing the capability to quickly enter data to
build integer programming models and generate SPFL heuristic solutions, demonstrates
that the MSS model is easy to use by a production scheduler in an actual repetitive

manufacturing environment.

145

- Return

 

”SPFL Output

    

Workcenter

Cost Data

 

 

 

 

 

 

SPFL output options

ProdufitronSchedulew

 

 

Labor Cost: $129,528.08 Inventory Cost: 33.17333 Total Cost: 31 31.944

 

 

 

Production schedule screen

FIGURE A10 SPFL HEURISTIC RESULTS SCREENS

146

 

 

 

b1 0p8. gms

bl 0p8.log
b20p8.gms
b30p8.gms
b3p8. gms
b40p8.gms
b50p8.dat
b50p8.gms
_m30p8. log

 

 

 

 

 

 

 

' n‘v .
r .
. p .
s .
‘ . ' _“ , l
. ‘. .'
. . . . . . A
1.”.Ww—IWMW‘MM‘WWWAA I! 1W

 

 

 

 

 

 

 

 

"Computer Resources
Memory: MB

”Log Entries .

. Iteration Freq. Iterations: Lampoon ]

Node Freq. IE: Time: E] [hours]

 

 

 

 

 

 

 

 

i FStopping Criteria

E X of Optimal:

 

 

 

 

 

 

 

Screen to specify GAMS solution parameters

FIGURE A11 GAMS MODEL SCREENS