NBS

PUBLICATIONS

A 11 ID 2 L> 3 1 0

1

NATm I? 81 0F STANDARDS & TECH R.I.C. KIRCip Q“ k H All 102631001 IlD^in O I ^

acf?Jn

; Richard Hen/Hlerarchlal declslo QC100 U56 NO.87-351 1 1987 V19 C.1 NBS-P Hierarchical Decision-Making in the

Factory of the Future

Richard H. F. Jackson, Albert W. T. Jones

U.S. DEPARTMENT OF COMMERCE

National Bureau of Standards

National Engineering Laboratory

Center for Applied Mathematics

Gaithersburg, MD 20899

February 1987

A report for: U.S. DEPARTMENT OF COMMERCE

I — QC eau of Standards

i 200 anufacturing Engineering

i IICC |, MD 20899

• U Db

87-3511

1987

c. 2

NBS

RESEARCH

INFORMATION CENTER NBSIR 87-3511

HIERARCHICAL DECISION-MAKING IN THE

FACTORY OF THE FUTURE

Richard H. F. Jackson, Albert W. T. Jones

U.S. DEPARTMENT OF COMMERCE

National Bureau of Standards

National Engineering Laboratory

Center for Applied Mathematics

Gaithersburg, MD 20899

February 1987

A report for: U.S. DEPARTMENT OF COMMERCE

National Bureau of Standards

Center for Manufacturing Engineering

Gaithersburg, MD 20899

Li'd~

U.S. DEPARTMENT OF COMMERCE, Malcolm Baidrige, Secretary

NATIONAL BUREAU OF STANDARDS, Ernest Ambler. Director

ABSTRACT

A major manufacturing research facility is being established at the

National Bureau of Standards. The Automated Manufacturing Research Facility

will address the standards and measurement needs for the factory of the

future. A five -layer hierachical control architecture is under development

to manage all production and support activities within the facility. The

proper execution of many of these activities requires the solution to one or more optimization problems. This paper describes a hierarchical planning

architecture and the decision-making problems that exist at each level within

that architecture.

KEYWORDS

:

Automated Manufacturing, Factory Model, Flexible Manufacturing,

Hierarchical Control, Real-time, Optimization, Scheduling, Routing.

1. INTRODUCTION

Manufacturing plants typically consist of combinations of people and

machines, working together to maximize corporate profits from the goods they

produce. Because of poor planning and scheduling strategies, most of these

plants are plagued by large work- in-process inventories, low utilization of

equipment, insufficient throughput, and excessive delays, all of which

decrease profits. Hopes for alleviating these problems were raised when

automated equipment such as industrial robots became commercially available

and sophisticated computer technology was developed to support it. Many

companies made large capital investments in these new technologies expecting

that their integration into existing plants would increase their profits and

improve their shares of the world markets.

This has not happened, and the problems have not disappeared. In fact,

their presence in these integrated, automated environments tends to have a greater negative impact. It is not possible to increase profits or achieve

the desired rate of return on capital investments when expensive equipment is

idle because of poor planning and scheduling. In addition, because of the

introduction of new equipment and new technologies in data management and

communications, new problems have been discovered that did not exist before.

Clearly, the need exists to:

o design better techniques for solving the old problems,

o Identify and solve the new problems, and

o develop an integrated framework for solving all of them.

This paper describes the approach under development at the National

Bureau of Standards (NBS) to address these issues within the Automated

Manufacturing Research Facility (AMRF) [1].

The remainder of this paper is composed of eight sections. After this

introductory section, section 2 provides an overview of the AMRF, including

the design philosophy used in building it, its decomposition into basic,

hierachically connected components, and a description of each of these

components. Section 3 describes some of the classical approaches to planning

and scheduling, explains why these can no longer be used in the automated

1
factory, and describes briefly a new approach which capitalizes on this

hierarchical design. In section 4, we identify the decision problems that

exist in the AMRF, organized along the same lines as the hierarchical

breakdown described in section 2. A framework to integrate planning and

control is discussed in section 5. In section 6, the problems of managing

data in real-time to support the new structure are discussed. Conclusions

are given and future work is outlined in section 7. References are provided

in section 8.

2. THE AMRF

2 . 1 Overview

The National Bureau of Standards has a fundamental commitment to promote

the development of standards for automated manufacturing systems and to

transfer technology to American industry. To meet this responsibility, the

Center for Manufacturing Engineering at NBS has established an experimental

test bed, the Automated Manufacturing Research Facility [1,4]. Industry,

academia, and other government agencies have played an active role in this

development effort through direct appropriations, equipment loans, and

cooperative research programs.

Physically, the AMRF contains several robot- tended machining

workstations, a cleaning and deburring station, an inspection station, a material handling system, factory control software, database managememt

systems, and the communications support to tie it all together. Basic

principles from physics, computer science, the behaviorial sciences, control

theory, operations research, and engineering disciplines have been used to

transform these individual components into a fully integrated, flexible,

small batch manufacturing sytem (see Figure 1)

.

2.2 Design Philosophy

The AMRF is intended to exhibit a greater degree of flexibility and

modularity than any currently available "flexible manufacturing system". To

achieve these goals, the AMRF has adopted the following design philosophies

concerning its control architecture. It is:

o partitioned into a functional hierarchy in which the control

processes are completely data driven and communicate via NBSdeveloped hardware and software interfaces which are uniform

throughout the AMRF,

o designed to respond in real-time to performance data obtained from

machines equipped with sensors,

o implemented in a distributed computer environment using state-of-the-art

techniques in software engineering and artificial intelligence.

2
AUTOMATED MANUFACTURING RESEARCH FACILITY

Figure 1. The Automated Manufacturing Research Facility.
As noted above, the AMRF control architecture is based on the classic

hierarchical, or tree-shaped, command/feedback control structure (see Figure

2) typical of many complex organizations [2-5]. This approach ensures that

the size, functionality, and complexity of individual control modules is

limited. Although the flow of control in this hierarchy is strictly vertical

and between adjacent neighbors only, it is necessary and even desirable to

share certain classes of data across one or more levels. In addition, each

control level is completely data-driven. That is, the data required to

perform its functions is separated from the actual control code. All data is

managed by a distributed data administration system [11] and transmitted to

and from control processes via a communication network that was designed to

be compatible with the Manufacturing Automation Protocols (MAP) [12], but has

not been fully implemented at this writing.

2.3 Functional Decomposition

An analysis [1,4] of traditional small batch manufacturing systems

provided the foundation for the decomposition of the control functions into

five levels: facility, shop, cell, workstation, and equipment. Activity at

each of these levels is data-driven, and each can be expanded to yield a more traditional, tree- like hierarchy as depicted in Figure 2. This structure

provides a convenient mechanism for describing the functions of the automated

facility and the databases needed to meet manufacturing requirements. This

discussion is given next.

2.3.1 Facility Level

At this highest level are implemented the "front office" functions that

are typically found in small batch manufacturing facilities. Activities at

this level are grouped into subsystems that fall into three major functional

areas: manufacturing engineering, information management, and production

management

.

Manufacturing engineering functions are typically carried out with human

involvement via user-data interfaces. This includes computer-aided design

(CAD), Group Technology Classification, and process planning. The

information management activities provide user- data interfaces to support

necessary administrative or business management functions. Production

management tracks major projects, generates long-range schedules, identifies

production resource requirements, determines the need for additional capital

investments to meet production goals, determines excess production capacity,

and summarizes quality performance data [2,8].

2.3.2 Shop Level

This level is responsible for coordinating the production and support

jobs on the shop floor [2,8]. It is also responsible for the allocation of

resources to those jobs. Two major component modules have been identified

within shop control: a task manager and a resource manager.

4
AMRF HIERARCHY

Figure 2. Expanded AMRF Control Hierarchy.

5
The task manager of the shop level system is responsible for capacity

planning, grouping orders into batches, assigning and releasing batch jobs to

cells, and tracking individual orders to completion. The resource manager is

responsible for allocating the production resources to individual cells,

managing the repair of existing resources, and ordering new resources.

2.3.3 Cell Level

At this level, batch jobs of similar parts are sequenced through

workstations and supervision is provided for various other support services,

such as material handling and calibration. The cell [7] brings some of the

efficiency of a flow shop to small batch production by using a set of machine

tools and shared job setups to produce a family of similar parts. The AMRF

cells are dynamic production control structures which permit the time sharing

of workstation level processing systems. This software structure was named

the "virtual" cell to distinguish it from previous "real" manufacturing cells

which are defined by fixed groupings of equipment or machinery on the shop

floor. A detailed discussion of the virtual cell concept is found in [6].

2.3.4 Workstation Level

The activities of small integrated physical groupings of shop floor

equipment are directed and coordinated at the workstation level [2,8]. A

typical AMRF workstation consists of a robot, a machine tool, a material

storage buffer and a control computer. Machining workstations process trays

of parts that are delivered by the material handling system. The controller

sequences equipment level subsystems through job setup, part fixturing,

cutting processes, chip removal, in-process inspection, job takedown, and

cleanup operations.

2.3.5 Equipment Level

These are "front-end" systems that are closely tied to commercial

equipment or industrial machinery on the shop floor. Equipment controllers

[2,8] are required for robots, computer numerical control (CNC) machine

tools, coordinate measuring machines, delivery systems, and storage/retrieval

devices. The functions of the equipment controller are to translate the

commands from the workstation controller into a sequence of simple tasks that can be understood by the vendor- supplied controller and to monitor the

execution of these tasks via the sensors attached to the hardware. These

controllers will be required for "off-the-shelf" equipment to provide

extended functionality and compatibility with NBS control concepts, until

higher level front-ends are incorporated by system vendors.

6
3. APPROACHES TO PLANNING AND SCHEDULING PROBLEMS.

In the preceding sections, the intent was to convey an appreciation of

the benefits of hierarchical decomposition of the control problems within

automated manufacturing facilities. The question addressed in the remainder

of this paper is: Is it possible to mimic this hierarchical approach to

control and decompose the planning process along the same lines described

above for the facility as a whole? Before answering this question, we present a brief review of some other approaches.

3.1 Classical Approaches

Traditionally, planning and scheduling problems have been analyzed

without decomposing them into subproblems [13-15]. The literature abounds

with mathematical programming, simulation, heuristic, and other techniques

for solving these problems under special conditions. Because of their

computational requirements and restrictive assumptions, these approaches tend

to have limited applicability in a real manufacturing environment. They are typically unable to provide useful solutions in a timely manner. It is hoped

that the hierarchical approach described here will provide the mechanism for

solving these problems in the timely and efficient manner required.

Since this is not a survey paper, no attempt is made here to provide a full review of the literature in these areas. For more information on the

state-of-the-art in these traditional approaches, we direct the reader to some of the already existing, and well-done, literature reviews [24-27], or

to the conference proceedings that are also available [34].

3.2 Recent Advances

In practice, planners and decision makers always decompose their

difficult problems into subproblems. Typically, these subproblems are then

given to experts to solve, and the decision maker must combine these

individual solutions to obtain the solution to the original problem.

Researchers [28-33] have recently begun to use concepts from Artificial

Intelligence (AI) to attack these planning and scheduling problems in

precisely this manner, with little success to date. Other researchers [16-

23] have combined AI techniques with the principles of hierarchical control

to address some of these problems, but results have been limited to two

levels of hierarchy. No one to our knowledge has attempted to develop an integrated framework which addresses all of the planning and scheduling

problems in an automated manufacturing system.

3.3 A New Approach

This paper expands the control hierarchy described above into a goal - directed hierarchy in which both planning and control functions are carried out at every level. The amount of computation that can be performed

in real-time at each level is limited by the planning horizon: the period of

time over which the module is responsible for planning and updating local

goals. These goals must be consistent with those set by the module's

supervisor and they must commit the entire subordinate structure to a unified

and coordinated course of action. This course of action, if successfully

7
completed, should result in all goals being achieved. In pursuit of these

goals, each module decomposes the input commands (see section 5.2.2) from its

supervisor into procedures to be executed at that level and subcommands to be

issued to one or more subordinate modules (see Figure 3) . This decomposition

process is repeated until, at the lowest level, a sequence of coordinated

primitive actions is generated which actuates shop floor equipment [10], The

status feedback (see section 5.2.2) that is provided to supervisors by their

subordinates, is used to close the control loop and support adaptive,

real-time, decision making at each level.

4. REAL-TIME DECISION PROBLEMS

In this section, we identify the real-time decision problems that exist

in the AMRF, which we believe are representative of those to be found in any

automated manufacturing facility. The discussion is organized according to

the five -level hierarchy of manufacturing system functions described above.

What follows is, in a sense, a laundry list of problems, some classical and

well-recognized, others new, arising from the introduction of new technologies into manufacturing systems. Indeed, some of the problems may seem insignificant now, but as automated systems become more sophisticated,

the marginal gain from having optimal solutions to these problems could

become extremely significant.

4.1 Equipment Level

The first level to be discussed is the equipment level, the lowest level

in the hierarchy. The general rule for this level is that once a piece of

equipment is instructed to do something, it must determine how best to

perform it. The equipment on the shop floor is basically of two types:

robots and machine tools served by the robots. In addition, we have

separated the automated storage and retrieval system into a third category

because of its special activities. All three catagories are discussed below.

4.1.1 Robots

The mathematical decision problems to be addressed at the equipment

level include path generation, optimal routing for traversing parts for

inspection, sequencing of tasks or activities with priorities, and loading,

unloading, and layout of parts and tool trays.

Sequencing prioritized activities is an area where much is already

known. The literature is extensive on the single machine scheduling, or sequencing, problem. In the automated manufacturing arena, the challenge is

to solve these problems in real time, and in such a way that the schedule can

be changed as often as desired when conditions change. There has been some work on this. See, e.g., [25].

8
CONTROL FLOW

Figure 3. Control System Hierarchy.
The inspection robots and the cleaning and debarring robots both require

paths to be generated for the movement of their arms and hands. These, of

course, should be optimal paths; e.g., shortest, longest, fastest, or cheapest depending on the situation. In fact, in some cases optimality may

not be appropriate and should be replaced with a sub-optimal, yet feasible

and easily generated path. Obstacle avoidance techniques must be included in

this effort also.

Another area where optimization methods can be brought to bear is in the

loading, unloading and layout of trays of parts and tools. Portions of this are facility layout problems, thus some of the ideas from the facility layout

and design literature could be useful. The problems can be complicated by

the possibility that multiple geometries may exist in the same tray.

There is an interesting optimization problem concerned with finding

optimal routes for traversing parts for inspection, cleaning, and deburring.

The objective is to perform these activities in a way that is optimal with

respect to some measure, perhaps time, number of two-handed moves, or number

of reconfigurations such as end-effector (e.g., gripper, assembly tool,

cleaning and deburring tool) changes or part repositionings.

Another problem area is in the precise positioning of robot arms at the

end of a path. This is an important problem and could be viewed as a solution to a nonlinear optimization problem in which the objective is to

minimize the error in the actual position.

Pattern matching for robot vision systems is another area where

significant optimization problems appear. These range from simple nonlinear

least squares problems that arise from attempting to match patterns , to

nonlinear least squares problems that arise in combining small windows of bit

patterns to form larger windows for faster scanning.

The robot carts that serve the workstations must address some of the same problems as the fixed-position robots; they may, however, take on a slightly different look. For example, path calculations for the robots

become routing problems for the carts. The issue here is deciding which path

to take to deliver or pick up trays from the workstations. If the cart can travel forward and backward, the problem becomes more complicated. The

situation is further complicated by having multiple carts, although the

coordination activity for this is performed at the next higher level. The

layout of the wire-guided path is also a task that lends itself to

mathematical analysis and could be studied to determine the best paths to

lay down.

4.1.2 Machine Tools

The decision problems that exist for machine tools are similar to those

described above for robots. Perhaps principal among these is the scheduling

of all activities and sub - activities that occur. Examples of these

schedulable activities are tool changes, ref ixturings , chip removal, coolant

spraying, and general housekeeping. The schedule should be optimal with

respect to some performance measure, such as number of tool changes, number

of refixturings , time in queue, or number of late tasks.

Also associated with the machine tool is the layout problem of

determining the optimal placement of tools in the tool drum. An obvious

application of optimization techniques related to this problem is minimizing

the number of tools required for performing a given sequence of operations.

10
Included here, too, is the problem of deciding which tools on hand should be

kept for later jobs and which should be sent for storage elsewhere.

Just as in the case of the industrial robots above, tool path

calculations are required for these machine tools. Lastly, there is the

problem of developing diagnostics for tool wear and determining how and when

to recover from errors.

4.1.3 Automated Storage and Retrieval System

The automated storage and retrieval sytem has basically two decision

problems that must be addressed. The first is determining optimal buffer

sizes for all buffer storage areas. The second problem is concerned with the

layout of the storage areas. In this latter case, the objective is to store

all the parts and tools required for a given task together in one or more contiguous storage bins. Of course, this is difficult to accomplish since

storage areas are required and released frequently, leaving available

portions spread throughout the storage bin area. This is a problem in

dynamic storage allocation and planning for storage needs. Its solution

would have consequences for the time required to transfer these items to the

workstation for processing.

4.2 Workstation Level

In general, most of the same kinds of problems that appear at the

equipment level appear also at the workstation level, with the additional

problem of coordination of sub-activities at the equipment level.

4.2.1 Material Handling

For the material handling workstation, the first priority task is to

decide the sequence in which to perform the tasks assigned to it. In the case of multiple carts, decisions must be made about which cart to be

assigned to which task. Then, an optimal routing for the cart(s) must be

computed. Lastly, all these activities must be coordinated and monitored for

possible changes and updates.

Also to be coordinated by this workstation is the storage and retrieval

of equipment at the workstation and at the inventory workstation (warehouse)

.

Planning is required here to minimize the number of stores and retrieves

required to perform a task, while restricting the size of local buffers.

Tray layout for mixed and non-mixed geometries must be performed at this

level, also. This problem could be complicated by having multiple batches of

parts on one tray, each of which may have different geometries. A further

complication is that deliveries to more than one workstation may be combined

into one tray. It is not clear whether this latter problem can be resolved

at the workstation level or must be passed up to the cell.

4.2.2 Quality Control Workstations

At these workstations, there is again the problem of sequencing tasks or activities. For the inspection workstation, this consists of determining

which jobs to inspect and when, as well as which inspection activity to

perform at which time. Once these have been determined, the decision about

11
which probes to use to inspect must also be made. Then, after inspection has

been completed, some parts will have to be scrapped and some will be

candidates for rework. There are decision problems here that relate to the

costs and benefits in each case. They must be resolved in light of due

dates, priorities, and other existing jobs. Once these decisions are made,

the rework parts must be put into a tray for further processing. There is a tray layout problem that must be solved. Again, some results from the

facility layout literature may help here. It is also possible that an expert

system may be useful in this process.

For the cleaning and deburring workstation, it is important to note

that, since it consists of two robots, assigning tasks for it may very likely

be non- trivial. It is possible that both robots will be required at the same time to perform one task, which is an additional complication.

As in the case of the other workstations, the quality control

workstations are also responsible for coordinating activities of all

subordinates

.

4.2.3 Machining Workstations

At the machining workstation, the sequence of jobs to be done must be

calculated, along with the coordination of activities of all subordinates.

Conflicts of subordinate activity must be resolved, and if necessary, tasks

reassigned. Assembly of parts may also be required at this level.

4.3 Cell Level

Basically, the cell must decide which workstation to use to perform a given operation. The problems at this level consist of scheduling tasks for

the workstations in the cell, coordinating activities (parts and tool

shipments) in support of that schedule, and coordinating delivery of parts

and tools from one workstation to another. Coordination becomes a more crucial activity when there exist shared resources such as material handling

workstation carts. If there are, there is a serious problem in coordination

that must resolved. Even if there are no shared resources, there is still

the problem of multimachine scheduling that must be confronted. Conflict

resolution is also a responsibility of the cell. When conflicts arise at the

workstation level, the cell must replan, reroute, and reschedule to overcome

them

.

4.4 Shop Level

The shop level has overall responsibility for inventory control, tool

management, scheduling, sequencing, conflict resolution, cell creation, and

preventive maintenance for all equipment in the shop. Also developed at this

level is the master production schedule and the material requirements plans.

The actual responsibilities in these areas will depend on the

configuration of the shop; principally whether it contains any shared

resources, which for the shop means whether there are any virtual cells. In

this case everything below the shop level is a shared resource and the

problems for the shop level controllers are more complicated.

12
4.5 Facility Level

The facility level has responsibility for the business and engineering

functions which support the entire manufacturing plant. The mathematical

techniques used in cost accounting, capital investment strategies, and many

other business functions must be changed to include the impacts of automation

[36]. In addition, new methods are needed to aid in the Group Technology

classification and coding of parts from CAD data, the geometric modeling of

parts, the decomposition of complex geometries into features that can be

machined and inspected, and the design, revision, and verification of process

plans

.

•k -Jc ~k

In the next section, we discuss an implementation strategy under

development at NBS , and the data requirements for it.

5 . AN INTEGRATION FRAMEWORK

Work is underway at NBS to implement a framework in which integration of

planning and control can be successfully carried out. This framework

includes

:

o a generic planning and control module which can be used at every

level of the hierarchy,

o a process planning system to provide the technical data needed to

plan and control activities, and

o a rich command/feedback structure to link one level of the hierarchy to

the next.

These structures have been implemented at the bottom three levels of the AMRF

hierarchy. The following sections provide a brief overview; more details can be found in the references provided.

5.1 The Production Control Module

A Production Control module [10] has been developed to plan and control

activities within the AMRF. It is a generic module that has been implemented

at the Cell, Workstation, and Equipment levels. This module is itself

decomposed into a three level hierarchy: Production Manager (PM) , Queue

Manager (QM) , and Dispatch Manager (DM) . The planning functions are carried

out by the PM and the QM; the control functions are assigned to the DM. The

following sections provide a brief description of these levels.

5.1.1 The Production Manager

The Production Manager (PM) is the highest level within this module. It

receives input from both its supervisor and the Queue Manager. Its

supervisor provides a list of jobs to process and resources to allocate,

while the Queue Manager provides feedback on the current status of all in13
process work. Whenever a change is detected in the status of any job on that

list or a new job is added to the existing list, the PM must retrieve all

relevant data for that job and generate a real-time production plan. This

production plan contains a list of the tasks assigned to each subordinate,

precedence and coordination flags for each task, and a schedule of start and

finish time for each task.

Commands are formulated from this plan using the command structure

formats described below and passed to the appropriate Queue Manager.

Coordination flags are used to change the status on jobs in one queue based

on feedback about jobs in another queue. If everything is on schedule, then

the plan is not altered. But, whenever a problem is encountered, the current

plan must be updated to reflect the expected delays and the appropriate Queue

Managers informed of any changes.

5.1.2 Queue Manager

There is one Queue Manager (QM) for each subordinate controller. It

receives a list of jobs from the Production Manager and feedback from the

Dispatch Manager. The QM will resequence the queue to accomodate any changes

in job status or the addition of new jobs. Whenever the status of any job

changes or a new job is added, the QM. passes the appropriate command

information to the Dispatch Manager (DM) for eventual release to the

subordinate. Whenever the DM sends feedback indicating that a job is

completed the QM removes this entry from the queue and reports this up to the

PM. The QM also updates timing information and reports this to the PM so that

appropriate action can be taken to update the production plan.

5.1.3 Dispatch Manager

There is one Dispatch Manager (DM) for each subordinate controller. The

DM has a library of software routines that support the internal processing

procedures derived from the process plan. The routines at this level define

the way in which the DM, as a supervisor, controls the execution of tasks by

the subordinate. It releases jobs to the Production Manager level of that

subordinate and monitors the execution of those tasks to completion. Any

problems that may result in delays in completion times are reported directly

to the Queue Manager. Although it is theoretically possible to combine the

QM and DM into a single job manager, that aggregation would unnecessarily

increase the complexity of the QM.

5.2 Data Requirements

As was stated earlier, the AMRF hierchical control and planning

structure is data-driven. There are basically two sources of data for the

system: the process plans which describe what must be done, and the

command/feedback process which provides information on what is being done.

These are described next.

5.2.1 Process Plans

As indicated above, one source of input data to these production control

modules is provided by the process planning system. An internal structure

14
for these process plans has been identified and used at the bottom three

levels of the AMRF hierarchy [9]. It specifies all of the technical

information necessary to plan and control activities in an automated

manufacturing environment. This includes not only the machining and robot

handling instructions, but also workstation level operations and cell -level

routing steps. Alternate processing sequences are also specified at each

level. For each step in the plan, a work element description, precedence

constraints, and estimated durations have been identified. These plans also

provide an extended bill of materials that lists required tooling, fixtures,

materials, processing systems, data, programs and/or plans that are required

to complete the job. Finally, this information is provided in a uniform,

consistent, error- free format which is compatible with the input requirements

of the production control module.

5.2.2 Command/Feedback Interface

In addition to the interface with the Process Planning system, each

control module must interface with one supervisor and one or more subordinates. The mechanism for this is the command and feedback structures

described below [7,10].

As noted earlier, the architecture under development provides for the

planning and control of parallel activities. The command structure to

support this capability is shown in Figure 4.

| ACTION_VERB | J0BS_P0INTER | RESOURCE_POINTER |

Figure 4. Command Interface Structure.

Each module will have a valid set of ACTION_VERBs which initiate

STARTUP, SHUTDOWN, EXECUTION, MAINTENANCE, and WAIT sequences. The

J0BS_P0INTER parameter is a pointer to a list of jobs in the database. Each

entry in this list contains a job type flag (NEW or OLD), a job ID, a j ob

action to be taken (PLAN, EXECUTE, CANCEL), priority, and timing information

for scheduling purposes. The last field in this command structure is the

RESOURCE_POINTER which is a reference to another table in the database. Each

entry in this list refers to a specific resource request from a subordinate.

It also contains the supervisor's response value (ACKNOWLEDGED, ALLOCATED,

UNAVAILABLE, COMPLETED, etc.), and the expected time of availability.

The feedback structure to support these parallel activities mirrors the

command structure and is shown in Figure 5.

15
| OPERATIONAL | JOBS_STATUS | RES OURCE_REQUES T |

Figure 5. Feedback Interface Structure.

OPERATIONAL indicates the current operational status of the control

module. JOBS_STATUS tracks the evolution of all jobs assigned to the module.

RESOURCE_REQUEST reports ordinary or emergency run-time resource requests to

the supervisor. Each of these three fields will be further divided into two

subfields: CONDITION, and POINTER. The former consists of a simple set of

ASCII responses and the latter is a pointer to a more detailed list in the

database. This structure reduces the complexity involved in implementation

by fixing the number of input parameters and by limiting the number of values

that each of those parameters can take on. In the next section, we discuss briefly some of the problems in managing

this data in the real-time environment of the AMRF.

6. REAL-TIME DATA MANAGEMENT

The data management function is concerned with providing data to the

manufacturing processes in a timely, accurate, and consistent manner. A new

set of planning and scheduling problems is associated with the real-time

management of data within these automated manufacturing facilities. These

problems can be divided into two major categories: Data Administration and

Data Communication.

6.1 Data Administration

A recent report [11] suggests that centralized data collection and

administration will not be sufficient to satisfy the data demands in the

factory of the future. As an alternative to the centralized data

administration approach, NBS researchers have been developing a distributed

data administration system called IMDAS [11]. Although it is logically

centralized, IMDAS provides for the distributed administration of physically

distributed data.

The desire to distribute data physically across the facility is prompted

by the time-criticality factor involved in certain data requests,

particularly at the equipment level of the planning and control hierarchy.

Several questions must be addressed concerning the optimal selection of local

data storage devices and their database management capabilities, the actual

allocation of the master copy of each data item to a particular device, and

the number and location of the copies of that data item.

The physical distribution of data also has a significant impact on the

administration of that data. Typical administrative functions include

satisfying all data requests, maintaining all data dictionaries, ensuring

that the data is accurate, and supervising all concurrency and consistency

checks. A three-level, tree-like architecture has been defined to carry out

these functions. Each level will have a queue of jobs to perform. Each job

16
will consist of some tasks to be carried out at that level and, possibly,

some tasks to be executed by one or more modules at the next lower or next

higher level. This leads to some scheduling and sequencing problems at each

level which are different from those described in the planning and control

hierarchy (see section 4) . They are complicated by the difficulty involved

in a) determining the time required to complete a task, b) obtaining a "due

date" for a given task, and, c) coordinating the parallel activities at all

three levels which may be involved in the completion of a single complex data

request

.

Little is known about approaches to solving these problems.

6.2 Data Communication

The transfer of information between computer processes in an automated

manufacturing environment will be managed by a Data Communication System

(DCS). This implies that processes do not communicate directly with one another; rather, they simply make information available. It is the DOS's

repsonsibility to deliver that information to those processes that require

it, at the time they require it. The protocols for accomplishing this data

transfer are being specified in the Manufacturing Automation Protocol (MAP)

standards [ 12 ]

.

It is likely that many of the techniques used to design and manage

computer networks [35] will be applicable here. However, the introduction of

the "virtual cell" notion (see section 2.3.3) will have a significant impact

on the both the design and real-time administration of the DCS. The

difficulties result from the need to "disconnect and connect" processes, and

therefore origin-destination pairs and paths, from one another in real-time.

To date, these issues have not been addressed.

7. CONCLUSIONS AND FUTURE WORK

Two major areas related to real-time production planning for automated

manufacturing systems have been addressed in this paper. First, these

planning problems have been identified and partitioned into five layers to

match the AMRF control hierarchy under development at NBS . Second, a framework has been proposed which provides a means for integrating planning

and control into a single hierarchy. That framework consists of a generic

production control module which can be used at every level in the hierarchy,

a process planning system and command/feedback structures to provide data to

those modules, and a data management system to store, update, and transfer

that data in a timely and accurate manner. Future research will focus on the development of solution techniques for

the decision problems described in the preceding sections. This research

will be conducted in three concurrent phases. First, we must determine the

information, both qualitative and quantitative, required to solve each

problem. Next, we must find efficient structures for representing that

information. Finally, we will attempt to marry techniques from Operations

Research and Artificial Intelligence to solve each problem.

17
We believe that this work fills an important gap in the literature,

provides a fundamental contribution to the field, and will provide the

groundwork for more fruitful research 8. in this area.

REFERENCES

1. Simpson, J., Hocken, R. , and Albus , J., "The Automated Manufacturing

Research Facility of the National Bureau of Standards", Journal of

Manufacturing Systems, Vol. 1, 1982, pp . 17-31.

2. McLean, C., Mitchell, M. , Barkmeyer, E. , "A Computing Architecture for

Small Batch Manufacturing, "IEEE Spectrum, May, 1983.

3. Albus, J., Barbera, A., and Nagel, N., "Theory and Practice of

Hierarchical Control", Proceedings of 23rd IEEE Computer Society

International Conference, September, 1981.

4. Albus, J., et al . , "A Control System for an Automated Manufacturing

Research Facility", Robots 8 Conference and Exposition, Detroit, MI,

June 4, 1984.

5. Barbera, A., Fitzgerald, M. and Albus, J., "Concepts for a Real-Time

Sensory-Interactive Control System Architecture", Proceedings of the

14th Southeastern Symposium on System Theory, April, 1982.

6. McLean, C,, Bloom, H., Hopp , T. "The Virtual Manufacturing Cell",

Proceedings of Fourth IFAC/IFIP Conference on Information Control

Problems in Manufacturing Technology, NBS , October, 1982.

7. Jones, A. and McLean, C., "A Cell Control System for the AMRF" , Proceedings of the 1984 ASME International Computers in Engineering

Conference, Las Vegas, Nevada, 12-15 August, 1984.

8. Jones, A., and McLean, C.," A Proposed Hierarchical Control Model for

Automated Manufacturing Systems", Journal of Manufacturing Systems,

Volume 5, No. 1, 15-25, 1986.

9. Mclean, C., "Process Planning for Distributed Manufacturing Control",

Working Paper, National Bureau of Standards, Gaithersburg, MD , 20899.

10. Jones, A., and Mclean, C., "A Production Control Module for the AMRF",

Proceedings of the ASME International Conference on Computers in

Mechanical Engineering, August, 1985.

11. Barkmeyer, E., et al . , "Distributed Data Management Architecture for

Computer Integrated Manufacturing", Technical Report NBSIR 86-3312,

National Bureau of Standards, Gaithersburg, MD , January 1986.

12. Data Processing - Open Systems Interconnection - Basic Reference Model,

North Holland Publishing Company, 1981, pp . 81-118.

18
13. Baker, K. R. , Introduction to Sequencing and Scheduling, John Wiley, New

York, 1974.

14. Conway, R. W. , Maxwell, E. A., Miller, K. W. , Theory of Scheduling,

Addison-Wesley , Reading, Massachusetts, 1967.

15. Elmaghraby, S. E., (ed.), Symposium on the Theory of Scheduling,

Springer-Verlag , Berlin, 1973.

16. Gershwin, S., "An Approach to Hierarchical Production Planning and

Scheduling", Proceedings of the Symposium on Real-time Optimization in

Automated Manufacturing Facilities, National Bureau of Standards,

Gaithersburg, MD , January 21-22, 1986.

17. O'Grady, P. and Menon, U. , "A Hierarchy of Intelligent Scheduling and

Control for Automated Manufacturing Systems", Proceedings of the

Symposium on Real-time Optimization in Automated Manufacturing

Facilities, National Bureau of Standards, Gaithersburg, MD , January 21-

22, 1986.

18. Akella, R. , Choomg, Y. , Gershwing, S., "Performance of Hierarchical

Scheduling Policy", IEEE Transactions on Components, Hybrid and

Manufacturing Technology, CHMT-7, pp . 225-240, 1984.

19. Bitran, G. R. , Hax, A. C., "On the Design of Hierarchical Production

Planning Systems", Decision Sciences, 8, pp . 28-54, 1977.

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

Planning: A Single Stage System", Operations Research, 29, pp . 717-743,

1981.

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

Planning: A Two Stage System", Operations Research, 29, pp . 232-251,

1982.

22. Davis, W. J., "Decision Making and Control Hierarchies for Produciton

Systems", Technical Report No. 145, PLAIC, Purdue University, West

Lafayette, IN, 1984.

23. Shaw, M. , "A Two Level Planning and Scheduling Approach for Computer

Integrated Manufacturing", Proceedings of the Symposium on Real-time

Optimization in Automated Manufacturing Facilities, National Bureau of

Standards, Gaithersburg, MD , January 21-22, 1986.

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

Pertains to Flexible Manufacturing Systems", Technical Report NBS-GCR

85-499, National Bureau of Standards, Gaithersburg, MD , 1986.

25. Sen, T., and Gupta, S. K. , "A State-of - the-Art Survey of Static

Scheduling Research Involving Due Dates", Omega, 12, No. 1, pp . 63-76,

1984.

19
26 . Graves S., "A Review of Production Scheduling", Operations Research, 29,

646-675 , 1981.

27. Graham, R. L. , et al . , "Optimization and Approximation in Deterministic

Sequencing and Scheduling: A Survey", Annals of Discrete Mathematics, 5,

pp. 288-326, 1979.

28. Lawerance, S. R. , and Morton, T. R. , PATRIACH: Hierarchical Production

Scheduling", Proceedings of the Symposium on Real-time Optimization in

Automated Manufacturing Facilities, National Bureau of Standards,

Gaithersburg, MD, January 21-22, 1986.

29. Fox, M. Constraint-Directed Search: a case study in job shop scheduling,

Doctoral Dissertation, Carnegie-Mellon Universtiy, 1983.

30. Steffen, M. S., and Greene, T. J., "Hierarchies of Sub-Periods in

Constraint Directed Scheduling", Proceedings of the Symposium on Realtime Optimization in Automated Manufacturing Facilities, National Bureau

of Standards, Gaithersburg, MD , January 21-22, 1986.

31. Wysk, R. , Wu, S., Yang, N. , "A Multi-Pass Expert Control System for

Flexible Manufacturing Systems", Proceedings of the Symposium on Realtime Optimization in Automated Manufacturing Facilities, National Bureau

of Standards, Gaithersburg, MD , January 21-22, 1986.

32. Chiodini, V. , "A Knowledge Based System for Dynamic Manufacturing

Replanning", Proceedings of the Symposium on Real-time Optimization in

Automated Manufacturing Facilities, National Bureau of Standards,

Gaithersburg, MD, January 21-22, 1986.

33. Maley, J., Ruiz-Mier, S., and Solberg, J., "Dynamic Optimization in

Automated Manufacturing - A Knowledge Integrated Approach" , Proceedings

of the Symposium on Real-time Optimization in Automated Manufacturing

Facilities, National Bureau of Standards, Gaithersburg, MD , January 21-

22, 1986.

34. Jackson, R., and Jones, A., (eds,), Proceedings of the Symposium on Real-time Optimization in Automated Manufacturing Facilities, National

Bureau of Standards, Gaithersburg, MD , January 21-22, 1986.

35. Kleinrock, L. , Queueing Systems Volume II: Computer Applications, John

Wiley, New York, 1976.

36. Eiler, R. , "Cost Accounting Faces Automation", Managing Automation, Vol.

1, No . 1 , pp. 25-29, 1986.

20
The NBS Automated Manufacturing Research Facility is partially supported

by the Navy Manufacturing Technology Program.

This is to certify that the article written above was prepared by United

States Government employees as part of their official duties and is therefore

a work of the U.S. Government and not subject to copyright.

21
NB$°1 14A (rev. 2 »ec) U.So DEPT. OF COMM.

BIBLIOGRAPHIC DATA

SHEET (See instructions)

1. PUBLICATION OR

REPORT NO.

NBS-IR 87-3511

2. Performing Organ. Report No, 3. Publication Date

FEBRUARY 1987

4. TITLE AND SUBTITLE

Hierarchical Decision-Making in the Factory of the Future

5. AUTHOR(S)

Richard H. F. Jackson, Albert W. T. Jones

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

national bureau of standards

DEPARTMENT OF COMMERCE

WASHINGTON, D.C. 20234

7. Contract/Grant No.

8. Type of Report & Period Covered

9.

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

10.

SUPPLEMENTARY NOTES

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

11.

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

bi bl iography or literature survey, mention it here)

A major manufacturing research facility is being established at the National

Bureau of Standards. The Automated Manufacturing Research Facility will address

the standards and measurement needs for the factory of the future. A five-layer

hierarchical control architecture is under development to manage all production

and support activities within the facility. The proper execution of many of

these activities requires the solution to one or more optimization problems. This

paper describes a hierarchical planning architecture and the decision-making

problems that exist at each level within that architecture.

12.

KEY WORDS (Six to twelve entries; alphabetical order; capitalize only proper names; and separate key words by semicolon s) Automated Manufacturing; Factory Model; flexible manufacturingl Hierarchical

control; real-time; optimization, scheduling; routing

13. AVAILABILITY 14. NO. OF

PRINTED PAGES

[~yl Unlimited

[_ I For Official Distribution. Do Not Release to NTIS 24

~j Order From Superintendent of Documents, U.S. Government Printing Office. Washington, D.C. 20402. 15. Price

QX) Order From National Technical Information Service (NTIS), Springfield, VA. 22161 $9.95

USCOMM-DC 6043*P 80