Hierarchies for ComputerIntegrated Manufacturing:

A Functional Description

Wayne J. Davis

Professor of General Engineering

University of Illinois Urbana, Illinois 61801

Albert T. Jones

U.S. DEPARTMENT OF COMMERCE

National Institute of Standards and Technology

(Formerly National Bureau of Standards)

Center for Manufacturing Engineering

Gaithersburg, MD 20899

March 1 988

Issued February 1989

-QC

100

- U 5 6

#88-3744

1989

c.2
NATIONAL INSTITUTE OF STANDARDS &

TECHNOLOGY

Research Information Center

Gaithersburg, MD 20899
NISTIR 88-3744

Nisrrc

GLUDo

no. n-2i<G4

im

6 -^

Hierarchies for Computerintegrated Manufacturing:

A Functional Description

Wayne J. Davis

Associate Professor of General Engineering

University of Illinois Urbana, Illinois 61801

Albert T. Jones

U.S. DEPARTMENT OF COMMERCE

National Institute of Standards and Technology

(Formerly National Bureau of Standards)

Center for Manufacturing Engineering

Gaithersburg, MD 20899

March 1988

Issued February 1989

National Bureau of Standards became the

National Institute of Standards and Technology on August 23, 1988, when the Omnibus Trade and

Competitiveness Act was signed. NIST retains

all NBS functions. Its new programs will encourage

improved use of technology by U.S. industry.

U.S. DEPARTMENT OF COMMERCE

Robert A. Mosbacher, Secretary

Ernest Ambler, Acting Under Secretary

for Technology

NATIONAL INSTITUTE OF STANDARDS

AND TECHNOLOGY

Raymond G. Kammer, Acting Director

HIERARCHIES FOR COMPUTER- INTEGRATED MANUFACTURING

A FUNCTIONAL DESCRIPTION

by

Wayne J. Davis

Associate Professor of General Engineering

University of Illinois at Urbana- Chanpaign

Urbana, Illinois 61801

Albert T. Jones

Automated Manufacturing Research Facility

National Bureau of Standards

Gaithersburg, Maryland 20899

April 21, 1988

NBSIR- 88-3744 (4/21/88)

ABSTRACT

In the recent past, several hiearchies have been proposed as candidate

models for the integration of decision and control functions within a Compeuter- Integrated-Manufacturing environment. A common theme in the

definition of these models is to construct an analog to managerial hierarchies

that are currently employed in many corporate settings. This paper will adopt

an alternate approach. Rather than defining a hierarchy, this paper will

discuss the manufacturing functions that a CIM hierarchy must address.

Whenever possible, mathematical formulations for the functions will be given

with consideration for the stochastic environment in which they will function.

The conclusion outlines several concerns arising in the definition of a generic

CIM hierarchy and associated research topics that must be addressed.

NBSIR- 88 - 3744 (4/21/88) 1

1.0 INTRODUCTION

Throughout history, the organization has played a vital role in the

success of large manufacturing companies by providing a means for addressing

the strategic goals of the company. Designing an organization to address those

goals involves [GAL77]: 1) defining the tasks to be performed; 2) dividing

those tasks into layers of subtasks for assignment to individuals; 3)

developing a managerial structure to coordinate those subtasks; and 4)

determining methods for processing the information to make the decisions

associated with 1, 2 and 3.

Task decomposition allows individuals to become highly skilled at a small

number of tasks. While this improves both the quality and quantity of their

work and leads to greater output from the same number of people, it also

increases the interdependence among workers and the need to coordinate their

output. Traditionally, hierarchical managerial structures (Figure 1) have been

used to ensure such coordination. Each position within that hierarchy is

obliged to follow the commands of a single superior. In addition, each

position is expected to issue commands to its subordinates. In this way, no position is left uncoordinated.

Within a given hierarchy, the number of layers and the responsibilities of

the managers at each layer depend on the size and complexity of the company.

In some cases, all decisions are made at the top, and managers simply implement

them at their own level. In other cases, each manager is expected to make

certain decisions, based on input from his superior, and exert the control

necessary to have subordinates execute his decisions. Each strategy has

implications on the amount and type of information processing required to make

and carry out decisions. Both can be successful [GAL77] in meeting a company's

needs

Recent attempts to design and build Computer Integrated Manufacturing

(CIM) systems have been based on similar concepts of organization. That is,

tasks are decomposed, "logically" grouped, and then assigned to one or more

computers and/or pieces of automated equipment. Several decision-making and

control hierarchies have been proposed [JON85] to manage and coordinate the

activities within these CIM systems, and in nearly every instance, a functional

decomposition has been used to define the levels within a given hierarchy.

That is, the basis for choosing a specific hierarchical design and task
.

‘
FIGURE 1 - MANAGERIAL ORGANIZATION FOR CIM ENVIRONMENT
.
NBSIR- 88-3744 (4/21/88) 2

decomposition for a new CIM system is usually the existing organizational

structure within the same company.

Two questions arise. First, is it necessary, or even desirable, to

implement a design for CIM that is based on existing, people-based

organizational structures? Second, is it possible to develop quantitative

measures which can be used to compare different management structures for CIM?

To date, answers to these questions have not been found. While we do not

answer these questions directly, we do attack a more fundamental issue:

defining the "overall manufacturing problem." Once this problem has been

formulated, meaningful attempts to answer these questions can be made.

It is impossible to develop an exact, detailed problem definition which is

applicable to all manufacturing firms, because goals, strategies, and

activities can vary tremendously from one firm to another. Therefore, we have

chosen to present general mathematical models for several decision and control

functions which impact the design and implementation of every CIM system (See

Figure 2). The list of functions is not complete, since we have excluded those

problems related to data management and communications. However, this paper

represents, to our knowledge, the first attempt to define this "overall

problem.

The organization of the remainder of the paper is as follows. In section

2, we describe models for a single process while section 3 presents models to

capture the interactions among individual processes. Section 4 contains models

of production planning decisions. We also include a summary section and an extensive bibliography.

2.0 MODELING INDIVIDUAL PROCESSES

We assume that the manufacturing shop floor contains N processes Pn (n-l,...,N) as depicted in Figure 3. These processes can be machining centers,

inspections centers, material handling devices, etc. We also assume that these

processes are used in the fabrication of M distinct products pm(m=l M) . Modeling these processes is based on the concept of state transition functions.

2.1 State Transition Functions

The behavior of process Pn while producing product p m can be modeled by

the state transition function gnm[ xnm(t) .u^Ct) , t] where x^Ct) is the state of

the process Pn and u^Ct) is the controlling input into the process Pn

at time

t. Using a sequence of discrete sampling times { tQ , t]_ , t 2 ,. . . ) where
.

.

.

.

.
AGGREGATE f MARKETING

PRODUCTION 1 AND

PLANNING o i SALES : CO

i cc

III i

MANUFACTURING

DATA

PREPARATION

I

PRODUCTION

QUOTAS

DETAILED

PRODUCTION

PLANNING

ORDER TRACKING

ISSUED JOBS WITH ASSOCIATED DUE DATES

PRODUCTION

SCHEDULING

PROCESS

LINEUP

co

| PROCESS

| SUPERVISION !

PROCESS

SPECIFICATIONS

| PROCESS

1 REGULATION |

PROCESSING STATISTICS CONTROL

INPUTS

FUNCTIONS ADRESSING

QUALITY ASSURANCE

PROCESS

n

FIGURE 2- MANUFACTURING FUNCTIONS COMPRISING CIM ENVIRONMENT

INPUT MATERIALS

FINISHED PRODUCTS

FIGURE 3 -THE CONFIGURATION OF THE DCFH WITH

THE MANUFACTURING PROCESSES

NBSIR- 88 - 3744 (4/21/88) 3

* to + k At for k - 0,1,2, ... (1)

we can define the evolution of x^Ct^) via the recursive relation

xnm( tk+l) =

§nmt xnm^ t-k) * unm^ tk^ * tk^

There are several properties of gnm [ • ] that ultimately govern the

complexity associated with determining the controls unm (tk) and predicting the

states xnm (t^) . The first is the functional dependence on time, which implies

that the functional form of gnm

[ • ] can vary over time. The second is the fact

that this variability is often stochastic in nature. In metal removal

processes, the amount of input energy needed to maintain a constant cutting

force can change drastically as the tool becomes worn. Another familiar

example is the rolling of hot steel slabs, where the rolling process produces

permanent plastic deformation upon the rollers. In both of these examples, it

is impossible to predict g^M or the behavior of Pn with certainty.

Consequently this means that the best that one can hope to do is to specify the

prob {

g

nm [ •

] e G^} where is a known subset of potential functions for

SnnJ *

]

• Another important limitation in modeling manufacturing processes today is

the fact that xnm (t^.) is seldom observed directly. Despite the abundant

research in this area, on-line process monitoring and control techniques are still not available for many processes. Until this happens, we will continue

to measure the output of the process rather than the process itself. This

output, ynm (tk ) , can be defined by

ynm( t-k) ^nm

[

xnm ( tk^ > unm( *-k) » ck^

Since the calibration of a measuring device may change randomly over time, the same potential problems arise in estimating hnm [»] as in the estimation of

gnm [*] in (1) . Furthermore, although h^f*] is expressed as a function of

time, it is rarely possible to measure all the processing outputs in real-time.

As an example, consider a turning operation. In this case, measurements such

as turning speed and the location of the tool holder can be made in real-time.

However, as the tool wears the depth of the cut changes. Therefore,

measurements such as the precise depth of the cut or the resulting surface

roughness can not be made in real-time, and must await for the completion or

the interruption of the process for a precise measurement. Let Tnm and tQ

denote the anticipated duration and initiation time for the processing task;

tnm

= t 0 + ^nm be t^ie anticipated completion time; and ynm (tnm ) the final
NBS IR- 88 - 3744 (4/21/88) 4

measured output. Then the modeler may only have a rough estimate of the

following

ynm^nm) = ^nm f §nm

xnm^ ) ,unm(^ ) * *-

] (4)

where t* is the last sampling time prior to tnm . Letting Ynm represent a set

of acceptable outputs - -usually a set of predefined tolerances -- the best

information the modeler can hope to supplyJ is the Drob (v Ct ) p Y I J nm v nm y nm i xnm( t*) and %!«(<:*))•

It seems clear that using these functional relationships to monitor and

control manufacturing processes will not be possible in the near future. The

task of estimating prob(gnm [.] € G^}, problh^J.] e Hnm ) , and prob (ynm (t nm) e ^nm I xna^ ) and unm^ will also be difficult. In most cases, these

estimates must be based on the experiences gained from past implementations of

each particular product. This, of course, leads to significant problems in

estimating gnm [«] and h^f*] for new products.

2.2 Process Control

To account for uncertainties in the evolution ot a process, a sex L 1 lg, controller can be used [ AST77 , AST84 ] . As depicted in Figure 4, a self-tuning

controller has two basic elements: a system identifier and a controller. The

system identifier uses the current values of and ynm [»], to develop

approximations for the g^M and hnm [«], denoted §nm M and h^m

[«]

respectively. These approximations are then used by the controller to

generate the next control input. Specifically, the controller computes the

difference between the actual output y^Ct^) and the desired output y^m (tk).

This error is used in conjunction with the optimal control law U [ yrim

(

c k) » tfc]

imposed by the Process Coordinator (PC) (see below) , to determine the next

control input for the process. Thus, the process controller continuously

attempts to minimize deviations from the desired output trajectory specified by

the PC. To be effective in this role, the controller's response time must be on the order of At.

For deterministic systems in which gnm [ #

] is known with certainty, the

system identification element is not needed. For processes where no formulation of the state transition function exists, the controller block would

not exist. In this case, the system identification element would attempt to

evaluate available system characteristics and would, in turn, subsequently

define the initial process settings or control parameters. After initiation,
TO PROCESS COORDINATOR n

FIGURE 4 - SELF-TUNING CONTROLLER FOR PROCESS Pn
'

'
NBSIR- 88 - 3744 (4/21/88) 5

the process would evolve in open loop fashion. As an example, consider the

Basic Oxygen Furnace process in steel-making. Here the charge of molten iron,

scrap steel, and alloy additives are introduced into the process. After

approximately thirty minutes the finished steel is produced with little or no control intervention during the processing duration. * As a consequence, there

is only a 70% probability that the correct steel chemistry will be achieved.

Although limitations on process modeling exist, the self- tuning controller

is being adopted in industrial environments. Astrom e_t al. [AST84] provide an

excellent overview of the topic as well as several examples. Watanabe [WAT86]

recently reported the development of a similar controller for a milling

process. Papapanagiotou et al. [PAP84] has performed work demonstrating the

applicability of self-tuning controllers to controlling the rollers in a hot

strip mill for steel making. Blattner e_t al. [BLA86] have developed a formulation for controlling the blast furnace in steel-making. Their

formulation includes not only parameter estimation within the system

identification element, but also a simulation to predict the system response

under various control strategies.

2.3 Process Coordination

Process Coordination (PC) determines the desired output trajectory y^m^)

for a given process and the optimal control law U [y^C t-^) » t\r_] to be used in

achieving that trajectory. Although this law is written as a function of time,

it is typically set at the beginning of the processing and remains constant

until some major problem arises. The PC detects potential problems by

monitoring feedback from the process and its controller. Whenever the PC

determines that a new control law and/or output trajectory is needed during the

implementation of a processing task, it must also estimate the resulting

probability that the process will be able to implement that law correctly, and

thus, sucessfuly complete the processing task.

To understand the relationship between the PC and the process controller,

consider the tool wear example from Section 2.1. First, the PC specifies an initial optimal control law, U [y(t^),tQ], which identifies the exact tool,

speed, feed, cutter paths, and cutting time to be used in the process. This

data is then used in negotiation with the production scheduler (PS) to

determine start and finish times. But, as the process evolves in time,

unanticiapated changes in the feed, speed, or cutting time may be required to
NBSIR- 88 - 3744 (4/21/88) 6

account for tool wear or other changes in the processing environment. These

changes, which are a function of the integrated measurements of ynm (t^.) and

xnm( t k^» are dictated by the process controller's success in implementing the

desired trajectory y^Ct) . These changes are typically minor with respect to

their consequences upon processing durations. If the tool breaks, major

modifications could follow. First, the PC must determine if the job can be

salvaged. If yes, then the PC must specify a new optimal control law with the

associated probabilities for successfully implementing the task. These

decisions would be based on the last measured value of ynmCtk)’ the desired

output y^Ct), and the current production schedule which also must be updated.

It can be concluded that the focus of the PC is the total implementation of the

processing whereas the process controller is focusing the immediate restoration

of the desired output trajectory. We will now give two potential formulations

for the determination of the optimal control law.

2.3.1 Off-line Determination of the Control Law . Process planning must

determine the constraints upon the admissible set of functions for the optimal

control law that will be used in completing JOBj . These specifications

prescribe the exact processes, precedence constraints, tools, and materials as well as limits upon operating speeds, feeds, and proposed durations. These

specifications typically generate three types of constraints. The first set of

constraints is the feasible (or admissable) set of control laws which is

limited by the available materials and processing technologies. Second, there

are capacity constraints on processes and tool life. Third, there may be a constraint on the minimum acceptable probability that the employed processing

will produce a product that satisfies all the design specifications. Decision

objectives could include minimizing processing cost, minimizing total

processing time, and in some cases, maximizing the probability of successfully

implementing the processing task.

Most process planning literature has focused upon this off-line,

deterministic determination of the optimal control law. This is an acceptable

approach provided the derived control laws are conservative in nature. For

example, the cutting speeds must be selected without knowing the condition of

the tool to be used. Furthermore, off-line process planning does not take into

consideration the consequences of its decision on the production flow. This

means that there is little interaction between off-line process planning and

production scheduling. As an alternative, we advocate the consideration of the
NBSIR- 88-3744 (4/21/88) 7 following on-line determination.

2.3.2 On-line Determination of the Control Law . As the process evolves in

time, it may be necessary or beneficial to change the predetermined optimal

control law generated by process planning. This problem is fundamentally

different from the one described above for two reasons. First, current

processing history does exist and estimates for g^f*] and h^f*] can be made.

Consequently, an updated control law should incorporate this known information.

Let T{ g^f •

] .h^f •

] } represent the admissible class of functions for the

’A’ optimal control law U [ynm^k) * t^] . This set would be determined in the offline analysis while the real-time analysis would be constrained to select

u*[ynm^ ck)

G T{gnm[ * ]

.

hnmt #

) ) • Secondly, a scheduled finished time, Lj n , has been established by the PS who can predict the consequences in the overall

production flow if changes in Lj n must be made. To that end, we shall presume

that the PS has a collection of objective functions f^(Lj n ) for i=l,...,L with

an overall utility function W[f^(Lj n) , . .

. , f^(Lj n) ] expressing the tradeoffs

among the objectives.^ To permit the PC to coordinate its decision with that

of the PS, we will assume that there are L' compatible objectives for the PC,

^jn^nm^k^ > unm^ tk^ for ^=1 L '

. and a utility function,

wjn^jn[ *]»•••» ^jfnt *] ) t0 quantify the tradeoffs among those objectives. A

formal statement of the real-time optimal control problem can now be given.

1 L' minimize u>. [ 9 . [•],... , 9 . [•]} jn jn L J jn

subject to for t^»=t^, . . . , t^ + T^

x (t. f1 )=g [x (t. ,),u (t.,),t. ,] nm k'+l 6nm L nm k' nm k' k' J

nm K

h [x (t. , ) ,u ( t. , ) , t. , ] nm 1 nm k' nm k' k' J Unm

(t

k' ) " U

nnJ ynn/

t

k' ^ ,t:k' ^ e T( Snmt •

1 . hnmt ' 1 1 prob {y-/ (t. , ) € Y } > pr

nm k' nm r mm

nm

^

+ ^nm — ^jn

(5)

( 6 )

(7)

( 8 )

(9)

( 10 ) (ID

^ The. PS's objective functions f^

(

• ) for i=l,...,L are actually functions

of several variables beyond the singular variable L^ n

. However, during the

real-time determination of the optimal control law, Lj n

is the only variable

upon which the PC has explicit control.
NBSIR- 88-3744 (4/21/88) 8

2.3.3 Deterministic vs. Stochastic . The preceding formulation assumes that the

gnm [«] and the hnm [»] are known with certainty. Since this is not generally

true, the derived solution will only approximate the true optimum. To overcome

these inadequacies, equations (5) through (11) must be replaced by a collection

of simulations. If the estimated values g^im [ #

] and h^J*] are given, then the

conditional probabilities prob { g^J •

] | g^t •

] } and prohibit •

] Ih^f •] } must be

specified. Using Monte Carlo simulation, we can then generate the optimal

solution to equations (5) through (11) for each sampled g^t*] and h^f*]. For

each simulated trial, the optimal UnnJynm^k' ) * t-k' J wou^ d thus be sampled.

Through repeated simulated trials, an empirical probability density for the

optimal Unm [ynm^ t k' ^

>

tk' ^ would emerge. Subsequent analysis would extract the

actual Unm [ynm^ t k' ^

>

t k' ^ which appears to be the most robust optimal control

law.

3.0 MODELING INTER-PROCESS INTERACTIONS

3.1 Combining Process Models

Thus far, the discussion has focused upon a single process. The state of

the entire shop floor system at tp. is represented by the composite state vector

(Xi mi

( t k ) X .

are governed by gnm [*] if process P n

is manufacturing product p m

. Similarly,

the output from this collection of processes is given by the composite output

vector (y lm ^(tk ) X ... X y^Ct*)).

We note that as soon as process P n completes one product and begins

another, these representations are no longer valid. For each process we define

a universal set of transition functions

Sn -(Gnl [-] G^M,*) • (12)

where is the idle state and Gjj [ •

] is the collection of potential transition

functions from which g^j [ •

] is chosen. If Ej n and Lj n represent the

anticipated start and finish times for process P n

to work on JOBj , then they

also indicate the times where the transition function for the manufacturing

system will change. These times are specified by production scheduling.

“n

(tp.)} where each individual process' state transitions
NBSIR- 88 - 3744 (4/21/88) 9

3.2 Production Scheduling

The primary problem related to inter-process coordination is production

scheduling (PS). A formal statement of the (PS) problem is as follows: Assume

that JOBj ( j =*1 ,• • - , 'J ) have been issued to the PS with associated due dates Dj

(j«l,...,J) and that JOBj requires the production of a specific product pm

(m=l , . .

. ,M)

Further assume that the processes Pn

(n=l, . .

. ,N) are available,

and that TASKkj n (k=l,...,K) are the tasks of JOBj to be performed on Pn

. Then, if we define

Ekj n (k-l,...K; j=l , . . .

, Jn»l N)

as the earliest start time for Pn upon TASKj kn from JOBj and

Lkjn (k-l,...,K; j=l,...,J; n=l,...,N)

as the latest finish time for Pn upon TASKkj n from JOBj , the production

scheduling problem is to optimize the utility function

W [ f

1

C E m Ekjn ‘, 1^111 »lkjn ) »

• • • ] (subject to due date, material handling, resource availability, precedence

constraints, and alternate routings) where f^(«) for 1,...,L are the criteria

to be considered in the optimization. These criteria typically include

minimizing tardiness, maximizing production throughput, and maximizing process

utilization

The PS is incapable of addressing the complete production scheduling

problem by himself. That is, in considering the actual duration of the process

Pn upon the JOBj , the PS typically does not have complete knowledge about the

current state transition function for each process. Hence, the exact

production scheduling problem can not be completely specified. Instead, the PS

must make its decisions based on an estimate for the duration dj n(=Lj n-Ej n ).

Then, as discussed in 2.3, through negotiation the PC will subsequently develop

the optimal control law which permits the process Pn

to complete JOBj by the

mutually determined completion time Lj n

. The basis of this negotiation between

the PS and the subordinate PC's represents an elaborate decompositon of the

production scheduling problem whose iterative solution mechanism represents a research topic beyond the scope of this paper. When the schedule is

implemented, deviations from that plan may require changes to Lj n , or complete

rescheduling. This represnts a control function for the PS that is similar to

that of the process controller in implementing a desired processing trajectory.
NBSIR- 88 - 3744 (4/21/88) 10

The integration of this control function with the solution of the production

scheduling problem again will not be addressed in this paper. For an excellent

survey on the topic of mathematical representation of the objectives and

constraints for the production scheduling problem, the reader should consult

[RAM85 , GRA82 ]

3.3 Production Flow

For each product p m there exists a set of precedence relationships stating

the order in which processes will be applied in the fabrication of the product

which are typically defined by process planning. Consequently, there exists a process transfer function which determines the successor process to process Pn for product p m

. This function is given by

n' = Tm

(n) (13)

and can be used to describe the overall production flow for the manufacturing

system. Based upon the relations of predecessor to successor processes

emerging from equation (12) several production flow configurations can be

defined.

3.3.1 Job Shop . A job shop configuration is characterized by the fact that

there appears to be no preferred path among the processes. In the most general

case, the range of successors for process P nis again the universal set

N - (*,1 N) (14)

where here <f> is the null process representing the completion of process for the

product. Thus, for the general job shop configuration, we can state that

{T]_ (n) u T 2 (n) u ••• U TM(n) } - N (15)

3.3.2 Flow Shop . At the other extreme, the pure flow shop, which is most

closely realized in assembly operations, has a only single production path

through the processes. This property allows the processes to be numbered in a manner such that for any m - 1, . .

. ,M

Tm(n) - n+1 and Tm

(N) - <t> (16)

Typically, for the same number of processes, the material handling problem (and

consequently the production scheduling problem) is much more complex for the

pure job shop than for the pure flow shop.

3.3.3 Hybrid . The pure flow shop and job shop are configurations that are seldom actually realized in real manufacturing environments. Typically, a
NBSIR- 88 - 3744 (4/21/88) 11

hybrid configuration emerges. One common hybrid is the multiple path flow

shop. Here the processes can again be numbered such that

Tm

(n) = {n' U <j> } for any m = 1 M (17)

where n'> n. In this configuration, if a process is required, it must always

be used after a fixed subset of preceding processes. However, not all

processes need to be employed in the manufacture of a given product p m

. 3.3.4 Flexible Manufacturing Systems . Flexible manufacturing systems are striving toward another hybrid configuration which could be termed a "preferred

path job shop". A group technology (HAM85) approach is used to configure work

cells. This significantly reduces the set of potential successors to a given

process Pn

. In fact, the goal is to partition the entire set of processes into

disjoint subsets with little or no interaction. This, in turn, impacts the

material handling constraints, which simplifies the production scheduling

problem. To date, however, these goals have not been achieved.

4. MODELS FOR PRODUCTION PLANNING

A manufacturing system is always driven by two stochastic inputs:

materials from vendors and demands from customers. However, the impact that

these inputs have may differ from one system to another. For example, the

classic job shop rarely stocks large quantities of finished goods. It usually

responds to the customer order as it is placed. Assembly line systems, on the

other hand, may produce a given product at a specified mean production rate to

meet past and future demands. This implies the possibility of a large

inventory holding. The manufacuturing system responds to the inputs by

generating a stochastic output, namely finished goods. One major objective of

the manufacturing system then is to minimize the difference between the input

demand and the output of finished products. Another common objective is to

maximize the present value of the derived profit stream over a given planning

horizon

In the preceding sections, we have proposed models which can be used to

estimate the contribution of processing decisions to these objectives. We now

present some production planning models which address the optimization of these

obj ectives
NBSIR- 88 - 3744 (4/21/88) 12

4.1 Production Planning Strategies

Today, two complementary production planning strategies are often

discussed: push and pull.

4.1.1 Push . The first type of production planning strategy is the Material

Requirement Planning (MRP) [BUZ68 ,ORL75 ,HAL83] . MRP attempts to "push" each

order through the system just before its due date occurs. The resulting

schedule begins with this due date and works backward to determine the times by

which each required process must begin and end. This technique also considers

the capacity and availability constraints of each process in the manufacturing

system as well as the material handling requirements. Subsequent to the

determination of the initiation times for each process, orders for input

materials must be issued to ensure their availability when the processes are initiated. In short, MRP seeks to minimize all input, output, and work- inprocess buffers simultaneously. Push strategies could also be defined by

considering other objective functions.

4.1.2 Pull . The second type of production strategy, which has found more

application in the flow shop environment, is the pull for which the Kanban or

the Just-in-Time (JIT) approach is one potential implementation [ SUG77 , FIN86 ]

This approach begins by defining an ideal state for the manufacturing processes

and then releases orders to them so that the ideal state is maintained. For

example, one Kanban approach would be to limit the number of orders that have

been processed by a given process, but have not yet completed processing at the

successor process. In the flow shop environment, this Kanban implementation is

particularly useful since it allows a given process to function at maximum

capacity whenever bottlenecks do not exist at subsequent processes, but

inhibits production when excessive orders are building up in the system.

Consequently, an inherent benefit of the Kanban approach is to stabilize the

response characteristics of the overall system.

4.1.3 Remarks . The designation of push versus pull strategy is unfortunate as

it appears to imply that one or the other can be applied. The fact is that

both strategies can be implemented simultaneously. As noted above the MRP is

but one optimizing approach that attempts to minimize the inventories present

in the system. This optimization can be performed subject to the constraints

of a pull approach which simply limits the states that processes can assume

with the hope that the response of the overall manufacturing system will be
NBSIR- 88 - 3744 (4/21/88) 13

stabilized.

4.2 The Aggregate Production Planner

Aggregate Production Planning (APP) attempts to generate production quotas

for individual products (or groups of products) to be manufactured over an extended planning horizon. In addition, the APP must specify target inventory

levels for all buffers. These decisions are made subject to capacity

constraints and both the real and forecasted demand for finished goods.

4.2.1 Problem Formulation . As discussed, above the APP ' s decision can be

based upon individual products or an aggregate product grouping. However, to

minimize the introduction of additional notation, the formulation for that

APP's decision will be given in terms of the basic products pm

(m=l,...,M).

Assuming that T planning periods will be considered, the primary decision input

into the APP are the actual and forecasted demands for each basic product type

in each planning period r, denoted by d^r) for m=l M and r-t+1 , . . . , t+T.

Let a/r)^ represent the production capacity for process Pn consumed in the

production of one unit of product p min period r while c n

(r) will represent the

availability of process Pnin period r (r=t+l , . . ., t+T) . Finally, letting pm

(r)

represent the planned production of product p m

in period r, the basic

production capacity constraint is given as

N

Z a (r) p (r) < c (r) for n=l,...,N and r=t+l , . .

.

, t+T . (18)

. nm m n

m=*l

Note this formulation assumes that the production quota p m(t) for the current

period t has already been submitted to the DPP for implementation. Also in the

more general case, we might desire to differentiate between regular and

overtime production capacity.

The next set of constraints will consider the material balance pertaining

to inventory. Let I m

(r) be the level of planned inventory for product pmin

planning period r while Bra (r) represents any backorder for product p m that

results in production planning period r. The resulting inventory constraints

have the form
NBSIR- 88 - 3744 (4/21/88) 14

Pm<0 + V'-D ' V'-D ‘ VO + Bm(0 " 0

for m-1, . .

. ,M and r-t+1, . .

. , t+T (19)

The planner may additionally desire to impose production smoothing limiting the

fluctuations in p m

( r) from period to period as well as inventory smoothing

constraints which limit the fluctuations in inventory. An additional set of

constraints, which must be considered but are difficult to include due to their

product specificity, are the constraints dealing with the availability of input

materials for each product type.

The APP will typically have a collection of objective functions to be

optimized. Let

[ P\ ( t+ l) .

• • • » P M ( t+T ) •Il( t+ l)>-**> t+T) . ( t+1) ,

. . . , Bj^( t+T) ] for i=l,...,L represent a collection of L objectives to be considered in the

planning problem which are to be optimized subject to the above constraints.

To represent the compromise to be considered among the objectives, it will

further be assumed that the utility function (•),... ,$^( •)

has been

defined. The above problem represents a chance - cons trained optimization. That

is, the demands d^r) for m-l,...,M and r-t+1 ,..., t+Tthe productivity

efficiencies a nm (r) for n-l,...,N and m=l M; and the process availabilities

c n

(r) for n=l,...,N and r-t+1 ,..., t+T are never known with certainty.

4.2.2 Potential Problems . The production planning decision must be strategic

in nature, considering all possible contingencies and stochastic aspects of the

problem. Charnes and Cooper [ CHA69 , CHA83 ] have investigated the chanceconstrained optimization problem. Several shortcomings exist in the adoption

of this approach. First, the inclusion of chance - cons trained elements

significantly complicates the structure of the problem. For example, linear

constraints become nonlinear when the probabilistic definition of the

constraint is made. Second, the decision optimizes only the expected values,

foregoing an extensive analysis of contingencies that could arise if the

expected planning scenario did not occur. Finally, the approach currently

considers a single objective only.

Davis and West [DAV87] recently merged the approaches of Monte Carlo

simulation and mathematical programming to develop a method for strategic

project scheduling. They used Monte Carlo simulation to generate and solve one thousand potential linear programs. Subsequently, an empirical probability

density function for the optimal solution was developed which could be employed
NBSIR- 88 - 3744 (4/21/88) 15

to analyze potential contingencies that could arise. Although their approach

was computationally expensive, the comparison of the method to other stochastic

decision-making approaches provided potential avenues for simplifying the

approach. Nevertheless, the need for analyzings potential contingencies was clearly demonstrated. To date, the authors are unaware of any reported

investigations of chance-constrained, multi-criteria optimization approaches.

4.2.3 Feedback and Updates . Although the APP plans for the production periods

t+1 through t+T only the product quotas pm(t+l) for m-1 M are implemented.

During the next planning period, feedback indicating the actual production from

the previous period and a new pm(t+l) will be generated. Thus, the APP must

respond to the deviations between actual and planned production quotas.

Furthermore, the APP must continually update its planning as forecasted demand

becomes realized with actual booked orders. Again, however, the time scale

upon which this updating must proceed is on the order of a week or more. Finally, the APP must continually learn through the acquisition of real

production data that arises from it previous planning.

4.3 The Detailed Production Planner

The detailed production planner (DPP) considers the specified production

quotas over a shorter horizon, and issues a request that specific products be

produced along with their associated due dates for finished production. Before

the request for a given product is issued, the DPP ensures that all essential

inputs for the product will be available when required during production and

that the essential processes to manufacture the product will be available. The

DPP also executes all the inventory policies established by achieving the

preplanned target inventory levels. Bitran et al . [BIT81 , BIT82 , BIT84] have

provided an aggregation/disaggregation formulation for the interaction between

the APP and the DPP. Their formulation provides for a static decision-making

framework with no uncertainty. Axsater and Jonsson [AXS79 , AXS81 , AXS83 ] have

adopted a similar approach. Graves [GRA82B] has treated the problem as a twopoint boundary value problem and have presented a dynamic formulation of the

problem. The two-point formulation represents a special case of the optimal

tracking problem, and their formulation again lacks the consideration of the

uncertainties that exist. Recently, Gershwin [GER87] has defined a hierarchical structure which employs control theory methodology to define

optimal production rates which will implement the selected production goals.
NBSIR- 88 - 3744 (4/21/88) 16

The approach recognizes the stochastic nature of the production system, and

develops its strategies based upon expected system performance.

4.3.1 Determining the Job List . When receiving the product quotas, p m

(t) for

m-l,....M, for a given product (or group of products) in the current planning

period t, the DPP will first review the booked orders to specify which JOBj for

specific products p m should be issued. However, before the actual JOBj is

generated, the DPP first assures that all the essential material inputs are available. As input materials are removed from inventory, the stocks would be

replenished by issuing orders to vendor as prescribed by current inventory

policies. (The reader is referred to Orlicky [ORL75] for a discussion of

several inventory models.) The availability of the required processes is an additional factor. The DPP does not explicitly consider material handling

requirements, but it nevertheless must consider both the anticipated processing

time at the individual process Pn

as well as the travel times between

subsequent processes. The latter consideration explicitly requires the

inclusion of the precedence relationships for the specified product p m and

implicitly contains the consequences of material handling. The above decision

cannot consider the JOBj individually, but must consider the consequences of

production flow and process availability arising from the complete ensemble of

{ JOB]_ ,. . . , JOBj ) . Since the stochastic elements exist within the manufacturing

environment, a deterministic specification of these consequences is impossible,

and a statistical specification will be required.

4.3.2 Due Dates . The customer's requested delivery date, Rj , for JOBj becomes

one of the important considerations in generating the assigned due date Dj . In

specifying the optimal due dates for the ensemble { D]_ ,

. . . , Dj ) , typically

multiple criteria must again be considered. To optimally track the output of

the manufacturing system against the customer demand, the desired objective in

its simplest form may be to

2 J

I Minimize F (D. , . .

.

,

T ) - £ C7 (D. - R.) (17)

1 J j_i J J J

where

Dj < Rj for j = 1,...,J (18)

and Cj is the per unit time inventory cost. Obviously the due date performance

constraint, equation (18), may not be feasible and the optimal tracking
NBSIR- 88 - 3744 (4/21/88) 17

objective must be enhanced to account for both the costs and losses due to back

ordering. Other objectives might include maximizing process utilization,

maximizing production throughput, and optimizing production smoothing. In

conclusion, a collection of objectives (D]_ ,

. . . , Dj) for 2 = 1,...,L will

exist to be considered. Their existence implies that there must exist an overall utility W[F^ (D]_ ,

. . . , Dj) ,. . . , F^(D]_ ,. . . , Dj) ] to be optimized. After the

"best" compromise due date ensemble (D*,...,Dj) is selected then the

perturbation costs associated with each F^ (D* , . .

.

, Dj) for 2 *= 1,...,L must be

defined to allow the production scheduler (PS) to define both a commensurable

0 set of objective functions, f (E]_i ,

. . . , Ejjj.Ljjj) for 2 = 1,...,L and an utility function u[f^( •),..., f^(» )

]

which has already been addressed above.

Furthermore, the perturbation costs for the DPP must also be commensurate with

similar costs pertaining to perturbation costs associated with the APP's

objective functions, $^(») for i=l,...,L and the utility function

n[*1 (-) *L (-)].

4.3.3 Feedback and Updates . The DPP must correct for deviations between its

9 planned due dates, and the feedback information Dj supplied by the production

scheduler. Futhermore, as the JOBj is completed it must be removed from the

list and new jobs appended. The size of the actual buffer of pending jobs

should be kept small. Specifically, the jobs ideally should be released to the

PS just before it is to be released to the shop floor.

5. SUMMARY AND FUTURE WORK

This paper discusses mathematical models for several decision and control

functions which impact the design and implementation of a CIM system. Because

of the limits of current technology, many of these models cannot be used

directly to solve their corresponding manufacturing problems. They do,

however, provide a baseline to guide future manufacturing-related research and

development in several areas: operations research, artificial intelligence,

on-line process controls, and sensor technology. In addition, these models

form the foundation for serious investigation of the problems involved in

integrating various manufacturing functions into a viable organizational

structure for CIM.

We plan to continue this model development in several other areas: datamanagement and communications, on-line versus off-line process planning, and

design for manufacturability. We hope to use these models to develop metrics
NBSIR- 88 - 3744 (4/21/88)

which can then answer the questions posed at the beginning of the paper.

18

REFERENCES

[ AST77

]

Astrom, K.J., "Theory and Applications of Self-Tuning Regulators,"

Automatica, Vol. 13, 1977, pp. 457-476.

[ AST84

]

Astrom, K.J. and Wittenmark, B., Computer Controlled Systems: Theory

and Design, Prentice -Hall , Englewood Cliffs, New Jersey, 1984.

[ AXS79

]

Axsater, S. "On the Design of the Aggregate Model in a Hierarchical

Production Planning System," Engineering and Process Economics, Vol.

4, 1979, pp. 89-97.

[AXS81] Axsater, S. "Aggregation of Product Data for Hierarchical Production

Planning, Operations Research, Vol. 29, No. 4, 1981, pp . 744-756.

[ AXS83

]

Axsater, S. and Jonsson, H., "Aggregation and Disaggregation in

Hierarhical Production Planning," European Journal of Operations

Research, Vol. 17, No. 3, pp . 338-350.

[BIT81] Bitran, G. R., Haas, E. A. and Hax, A. C., "Hierarchical Production

Planning: A Single Stage System," Operations Research, Vol. 29,

No. 4, 1981, pp. 717-743.

[ BIT82

]

Bitran, G. R. , Haas, E. A., and Hax, A. C. "Hierarchical Production

Planning: A Two Stage System," Operations Research, Vol. 30, No. 2,

1982, pp. 232-251.

[ BIT84

]

Bitran, G. R. and Yanasse, H . H ., "Deterministic Approximations to

Stochastic Production Problems," Operations Research, Vol. 32, No. 5,

pp. 699-1018.

[ BLA86

]

Blattner, J.L., Mika, L.M. , Tanski, J.A. and Schiller, T.L., A Blast

Furnace Dynamic Model- -Reconstruct ion of the PLAIC Blast Furnace

Model (Volumes I ,11 and III), PLAIC Reprot Number 149, Purdue

Laboratory for Applied Industrial Control, Purdue University, W.

Lafayette, Indiana, 1986.

[ BUZ68

]

Buzacott, J.A., 1968, "Prediction of the Efficiency of Production

Systems without Internal Storage," International Journal of

Production Research, Vol. 9, 1968, pp . 173-188.

[CHA69] Charnes, A. and Cooper, W. , "Chance-Constrained Programming,"

Management Science, Vol. 16, No. 1, 1969, pp . 73-79.

[CHA83] Charnes, A. and Cooper, W. W. , "Response to 'Decision Problems Under

Risk and Chance Constrained Programming: Dilemmas in the

Transition'," Management Science, Vol. 29, No, 6, 1983, pp . 750-753.
NBSIR- 88 - 3744 (4/21/88) 19

[DAV87] Davis, W.J. and West, S.M., "an Integrated Approach to Stochastic

Decision-Making: A Project Scheduling Example," IEEE Trans, on

Systems, Man, and Cybernetics," Vol. SMC-17, No. 2, 1987, pp. 199-

209.

[FIN86] Finch, B.J. and Cox, J.F., "An Examination of Just-In-Time Management

for the Small Manufacturer: with an Illustration," International

Journal of Production Research, Vol. 24, 1986, pp. 329-342.

[GAL77] Galbraith, J.K., Organizational Design, Addison-Wesley , Menlo Park,

California, 1977.

[GE070] Geoffrion, A.M. , "Elements of Large-Scale Mathematical Programming,

Parts I and II," Management Science, Vol. 16, No. 11, 1970, pp. 652-

691.

[GER87

]

Gerswhin, S.B., A Hierarchical Framework for Discrete Event

Scheduling in Manufacturing Systems, Technical Paper LIDS-P-1682,

Laboratory for Infomration and Decision Systems, Massachusetts

Institute of Technology, Cambridge, Massachusetts, 1987.

[GRA82] Graves, S, C., "A Review of Production Scheduling," Operations

Research, Vol. 29, 1982, pp . 646-675.

[GRA82B] Graves, S. C., "Using Lagrangian Techniques to Solve Hierarchical

Production Planning Problems," Management Science, Vol. 28, No. 3,

1982, pp. 260-275.

[HAL83] Hall, R.W.

,

Zero Inventories, Dow Jones-Irwin Co., Homewood,

Illinois, 1983.

[HAM85

]

Ham, I., Hitami, K. and Yoshida, T., Group Technology Applications in

Production Management, Kluwen Publishing Company, Boston, 1985.

[ JON85

]

Jones, A.T. and Whitt, N. , ed. , Proceedings on Factory Standa~

Model Conferenc, National Bureau of Standards, Gaithersburg

Maryland, November 20-21, 1985.

[LAS 70] Lasdon, L.S., Optimization Theory for Large Systems, Macmillan, New

York, 1970.

[ORL75

]

Orlicky, J., Materials Requirement Planning, Mc-Graw Hill, New York,

1975.

[ PAP84] Papapanagiotou, I., Maliotis, G. and Koivo, A.J., A Self-Tuning

Controller for Rolling Mill Processes, Report No. 141, Purdue

Laboratory for Applied Industrial Control, Purdue University, W.

Lafayette, Indiana, 1984.

[RAM85

]

Raman N. , A Survey of the Literature on Production Scheduling as it

Perteins to Flexible Manufacturing Systems, National Bureau of

Standards Report NBS -GCR- 85 -499 , U.S. Department of Commerce,

National Bureau of Standards, Githersburg, Maryland, 1985.
NBSIR-88-3744 (4/21/88) 20

[ SUG77

]

[WATS 3]

Sugimori, Y. , Kusunoki , K. , Cho , F. and Uchikawa, S., "Toyota

Production System and Kanban System: Materialization of Just-in-Time

and Respect- for-Human System, International Journal of Production

Research, Vol. 15, pp . 553-564.

Watanabe , T., "A Model-Based Approach to Adaptive Control

Optimization in Milling," Trans, of ASME: Journal of Dynamic

Systems, Measurement and Control," Vol. 108, No. 1, 1986, pp . 56-64.
H BS-114A (REV. 2-80

U.S. DEPT. OF COMM.

BIBLIOGRAPHIC DATA

SHEET fSee instructions)

1. PUBLICATION OR

REPORT NO.

NISTIR 88-3744

2. Performing Organ. Report No. 3. Publ ication Date FEBRUARY 1989

4. TITLE AND SUBTITLE

Hierarchies For Computer-Integrated Manufacturing: A Functional Description

5. AUTHOR(S)

Wayne J. Davis, Albert T. Jones

6. PERFORMING ORGANIZATION (If joint or other than MBS. see instructions)

NATIONAL BUREAU OF STANDARDS

U.S. DEPARTMENT OF COMMERCE

GAITHERSBURG, MD 20899

7. Contract/Grant No.

I. Type of Report & Period Covered

9. SPONSORING ORGANIZATION NAME AND COMPLETE ADDRESS (Street. City. State, ZIP)

National Bureau of Standards

Factory Automation Systems Division

Building 220 Room A-127

Gaithersburg, MD 20899

10. SUPPLEMENTARY NOTES

H Document describes a computer program; SF-185, FIPS Software Summary, is attached.

11. ABSTRACT (A 200-word or less factual summary of most si gnificant information. If document includes a significant

bi bliography or literature survey, mention it here)

In the recent past, several hiearchies have been proposed as candidate models

for the integration of decision and control functions within a Computer-Integrated

Manufacturing environment. A common theme in the definition of these models is

to construct an analog to managerial hierarchies that are currently employed in

many corporate settings. This paper will adopt an alternate approach. Rather

than defining a hierarchy, this paper will discuss the manufacturing functions

that a CIM hierarchy must address. Whenever possible, mathematical formulations

for the functions will be given with consideration for the stochastic environment

in which they will function. The conclusion outlines several concerns arising

in the definition of a generic CIM hierarchy and associated research topics that

must be addressed.

12. KEY WORDS (Six to twelve entries; alphabetical order; capitalize only proper names; and separate key words by semicolon s) automated manufacturing, functional decomposition, hierarchical control,

integration, mathematical models, organizational structures

13. AVAILABILITY

1'X) Unl imited

1 1 For Official Distribution. Do Not Release to NTIS

| | Order From Superintendent of Documents, U.S. Government Printing Office, Washington, D.C.

20402.

LX: Order From National Technical Information Service (NTIS), Springfield, VA. 22161

14. NO. OF

PRINTED PAGES

29

15. Price

$12.95

USCOMM-DC 6043-P80