NBS

PUBLICATIONS

NBS1R 88-3503

A 1 1 1 E b313M4

NATL INST OF STANDARDS & TECH R.I.C. cal Control and Real-Time

n lion in Automated

Manufacturing Systems

All 102631 344

Jackson, Richard Hen/Hlerarchlal control QC100 U56 NO.86-3503 1987 V19 C.1 NBS-P

Richard H. F. Jackson

Center for Applied Mathematics

and

Albert W. T. Jones

Center for Manufacturing Engineering

U.S. DEPARTMENT OF COMMERCE

National Bureau of Standards

National Engineering Laboratory

Gaithersburg, MD 20899

December ^986

issued February 1987

A resort: -QC RTMENT OF COMMERCE

100 jreau of Standards

• U56 Manufacturing Engineering

86-3503 rg, MD 20898

1986

c.2

NBSIR 86-3503

RESEARCH

INFORMATION CENTER M

HIERARCHICAL CONTROL AND REAL-TIME

OPTIMIZATION IN AUTOMATED

MANUFACTURING SYSTEMS h%i

C.lr

Richard H. F. Jackson

Center for Applied Mathematics

and

Albert W. T. Jones

Center for Manufacturing Engineering

U.S. DEPARTMENT OF COMMERCE

National Bureau of Standards

National Engineering Laboratory

Gaithersburg, MD 20899

December 1986

Issued February 1987

A report:

U.S. DEPARTMENT OF COMMERCE

National Bureau of Standards

Center for Manufacturing Engineering

Gaithersburg, MD 20899

U.S. DEPARTMENT OF COMMERCE, Malcolm Baldrige, 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 partitions these problems into levels

consistent with the control architecture and reports on early work undertaken

to solve some of them.

KEYWORDS

:

Automated Manufacturing, Factory Model, Flexible Manufacturing, Hierarchical

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

1. INTRODUCTION

In the past, manufacturing plants typically consisted of combinations of

people and machines, working together to maximize corporate profits from the

goods they produced. Because of poor planning and scheduling strategies,

most of these plants were plagued by large work- in-process inventories, low

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

of which decreased profits. Hopes for alleviating these problems were raised

when automated equipment like industrial robots became commercially available

and the 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.

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 five 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. In section 3, we identify the decision problems that exist in the AMRF, organized along the same lines as the hierarchical breakdown described in section 2. Section 4

includes a brief description of the efforts to date to solve some of these

problems. Conclusions are given and future work is outlined in section 5.

References are provided in section 6.

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.

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-ofthe-art techniques in software engineering and artificial

intelligence

.

As noted above, the AMRF control architecture is based on the classic

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

1) 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 [26] and transmitted to

and from control processes via a communication network that conforms to the

Manufacturing Automation Protocols (MAP) [27]

.

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 1. 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

2
Figure 1. Expanded AMRF Control Hierarchy

3
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.

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 "front-end" systems are closely tied to industrial machinery on

the shop floor. Equipment controllers [2,8] are required for robots, NC

machine tools, coordinate measuring machines, delivery systems, and

storage/retrieval devices. The functions of the equipment controller are to

translate 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 sensors attached to the hardware. These

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

4
extended functionality and compatibility with NBS control concepts, until

higher level front-ends are incorporated by system vendors.

This paper expands the control hierarchy described above into a goal -directed one 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

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

goals, each module decomposes the input commands from its supervisor into

procedures to be executed at that level and subcommands to be issued to one

or more subordinate modules (see Figure 2). 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 provided to supervisors by their subordinates is used to close the

control loop and support adaptive, real-time, decision making at. each level.

3. 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.

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

approaches, both classical and state-of-the-art, we direct the reader to some of the existing literature reviews [11-15], or to a recently published

conference proceedings [16].

3.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.

5
Figure 2: Goal-directed Hierarchy.

6
3.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

(sequencing) problem. In the automated manufacturing arena, the challenge is

to do it in real time, and in such a way that the schedule can be changed

when conditions change, without introducing too much nervousness in the

system. There has been some work on this. See, e.g., [25].

The inspection robots and the cleaning and deburring 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 would be 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 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.

7
3.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, refixturings , chip removal, coolant

spraying, and general houskeeping. 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

.

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.

3.1.3 Automated Storage and Retreival 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.

3.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.

3.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.

8
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.

3.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

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

.

3.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.

3.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 supprot 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 like 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.

9
3 . 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.

3.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

[21]. In addition, new methods are needed to aid in the (GT) 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.

4. CURRENT WORK

In this section, we discuss some of the solution techinques under

development at the AMRF.

4.1 Job Scheduling

The first project to be described is part of an ongoing cooperative

research effort among staff of the Center for Applied Mathematics and the

Center for Manufacturing Engineering of the NBS , along with researchers from

various universities. The purpose of this long-term research effort is to

identify and solve the real-time optimization problems found in the current

and future configurations of the AMRF. The first part of this plan consists

of a series of research efforts whose goal is to provide solutions to the

multi -machine , multi-task scheduling problems at the cell level. The work

described in [23] is part of the early phase of this research effort whose

purpose was to ensure a basic scheduling/routing capability for the AMRF that was flexible and modular enough to allow incorporation of further results

from other research and testing efforts being performed parri passu.

The report [23] documents the scheduler subsystem used in the June 1985

realization of the AMRF. This subsystem is responsible for managing the

queues at each workstation and monitoring the completion of the tasks

assigned there. The scheduling subsystem relies on data structures that use linked lists to track data so that a schedule can be created, modified,

updated, and entirely deleted for each workstation. This subsystem also

provides for the real-time switching of scheduling algorithms so that jobs

can be expedited by the operator.

As mentioned above, the work reported in [23] provided a short-term

10
solution to the scheduling problems in the AMRF and a foundation on which to

build the longer-term solution. At the same time work was underway to

develop these longer-term solutions.

A literature review [11] helped in determining the state-of-the-art in

this area, and set the stage for the new results described in [25]. This

paper investigates the dynamic scheduling of the Automatic Turning Station

(now called the Turning Workstation.) The dynamic scheduling problem is

treated as a series of static problems which are solved on a rolling-horizon

basis. Characteristics of the optimal solutions to the static mean flow time

and mean tardiness problems are developed and an implicit enumeration

approach to the mean tardiness problem was also developed. These results are extended to drive dispatching procedures for the dynamic case. A simulation model [24] was developed and used to evaluate the

performance of these procedures relative to four other dispatching rules

which are modifications of heuristic methods found to be effective for

conventional single -machine problems. The modifications are necessitated by

the need to incorporate job batching and changeover time. The results

indicate that two new rules developed, the Modified Myopic rule and the

Revised Necessary Condition-Based rule (based on the necessary conditions for

local optimality of the static problem) , work well under a broad range of

experimental conditions. These rules are computationally efficient enough to

operate on a microcomputer within the real-time constraints of an automated

manufacturing facility.

4.2 Cart Scheduling

Materials are transferred between workstations within the AMRF on two

Automatic Guided Vehicles (AGVs) . Each AGV has two roller beds which means

that it can transport two trays of materials simultaneously to any of the

workstations. This transfer takes place over a wire which is taped to the

floor. The actual path is shown in figure 3. The fact that it is not a loop

simplifies the routing problems but enhances the possibility of collisions

and deadlocks. This also complicates the scheduling problems.

A three-phase approach is under development at the AMRF to resolve these

problems [17]

.

The first phase uses a simulation of the current state of the

shop floor conditions to generate feasible schedules, using a predetermined

set of strategies, for all proposed material transfers. The second uses a realization of the Petri net representation, shown in Figure 4, to eliminate

those schedules resulting in collisions or deadlocks. The third phase will

generate performance characteristics for each of the remaining feasible

scehdules and select the "best" one.

4.3 Robot Path Planning

As noted above, obstacle avoidance and path planning are two of the most

important optimization problems to be resolved in the control of robots. A

path planning algorithm, which is guaranteed to be collision- free, has been

developed at NBS [19]. Currrently, this algorithm assumes that the robot is

the only moving object within the work volume and that this work space is

modeled using an "oct-tree" representation [18]. The output from this

algorithm is a piece-wise linear, collision- free , 3-D path from the initial

to the goal state.

11
There are three major search techniques used to find this path. A hill

climbing technique, with the Euclidean distance as its objective function, is

used to reach a local minimum. The A* best- first search technique [22]

,

with

h heuristic equal to the Euclidean distance from the current point to the

goal, is used to move away from this local minimun. These two techniques are combined, possibly many times, until the goal is reached. The resultant path

is then checked, using a multi- resolution search, for collisions. This

process is repeated until a satisfactory path has been found. This path is

then passed to a trajectory planner where the velocity, acceleration, etc.

required to move the robot are calculated.

5. 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 control hierarchy under development for the Automated

Manufacturing Research Facility at NBS . Second, a review of the recent

efforts to solve some of these problems has been included.

Future research will focus on two major areas. First, work will

continue on the integrated planning and control architecture proposed in

[20]

.

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. Second, we 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.

12
E>€^

AMRF

SHOPFLOOR

(not to scale)

Legend

# Workstation

1 Vertical Milling

2 Horizontal Milling

3 Turning

4 Debarring

Figure 3. Wire-Guided Cart Path.

13
Ltgend — One token (path ownership) — Two tokens (cart transfer)

Figure 4. Petri Net Representation of Cart Path.

14
6.

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., and 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. Brown, P. and Mclean, C., "Interactive Process Planning for the AMRF,"

Proceedings of the Symposium on Knowledge Based Expert Systems for

Manufacturing, ASME Winter Anual Meeting, Anaheim, CA. , Dec. 7-12, 1986.

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. Raman, N. , "A Survey of the Literature on Production Scheduling as it

Pertains to Flexible Manufacturing Systems," Technical Report NBSGCR

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

12. 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.

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

646-675, 1981.

15
14. Graham, R. L. , et al . . "Optimization adn Approximation in Deterministic

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

pp. 288-326, 1979.

15. Lawrence, 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.

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

Bureau of Standards Special Publication, Gaithersburg, MD, to appear.

17. Davis, W. and Jones, A., "An integrated Approach to Real-time Production

Planning," Working Paper, National Bureau of Standards, Gaithersburg,

MD, June, 1986.

18. Jackins, C., and Tanimoto, S., "Oct-Trees and Their Use in Representing

Three-Dimensional Objects," Computer Graphics and Image Processing, 14,

pp. 249-270, 1980.

19. Herman, H. , "Fast, Three-Dimensional, Collision-Free Motion Planning,"

Proceedings of the IEEE International Conference on Robots and

Automation, San Frans isco, CA, April 7-10, 1986.

20. Jackson, R.H.F.

,

and Jones, A.W.T.

,

"Hierarchical Decision-Making in the

Factory of the Future," National Bureau of Standards Technical Report,

to appear.

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

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

22. Nilsson, N.J., Problem Solving Methods in Artificial Intelligence,

McGraw-Hill, New York, 1971.

23. Jackson, R.H.F.

,

and Knapp-Cordes , J., "Guide to the June 1985 AMRF

Scheduling Routines," National Bureau of Standards Technical Report

NBSIR 86-3338, Gaithersburg, MD, April, 1986.

24. Raman, N. , Talbot, F.B., and Rachamadugu, R.V.

,

"A Simulation Model for

the Automatic Turning Station at the Automated Manufacturing Research

Facility," National Bureau of Standards Technical Report NBSGCR 86-513,

Gaithersburg, MD, March, 1986.

25. Raman, N. , Talbot, F.B., and Rachamadugu, R.V.

,

"Due-Date Based

Scheduling in a Flexibel Manufacturing System (the ATS)," National

Bureau of Standards Technical Report NBSGCR 86-514, Gaithersburg, MD,

March, 1986.

26. 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.

16
27. Data Processing - Open Systems Interconnection - Basic Reference Model,

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

* x x

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.

17
U.S. DEPT. OF COK4M. BIBLIOGRAPHIC DATA

1. PUBLICATION OR

REPORT NO.

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

SHEET (See instructions) NBSIR-86/3503 __J_ FEBRUARY 1987

4. TITLE AND SUBTITLE

Hierarchical Control and Real-Time Optimization in Automated Manufacturing Systems

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/Granc No.

I. Type of Report & Period Covered

9.

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

10.

SUPPLEMENTARY NOTES

I | Document describes a computer procram; 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

bibliography 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 partitions these problems into levels consistent with the control

12. architecture and reports on early work undertaken to solve some of them.

KEY WORDS (Six to twelve entries; alphabetical order; capitalize only proper names; and separate key words by semicolons)

Automated Manufacturing, Factory Model, Flexible Manufacturing, Hierarchical

Control, Real-time, Optimization, Scheduling, Routing

13. AVAILABILITY

Unlimited

| 1 For Official Distribution. Do Not Release to NTIS

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

20402.

fy] Order From National Technical Information Service ( NTIS), Springfield. VA. 22161

14. NO. OF

PRINTED PAGES

21

15. Price

$9.95

USCOMM*OC 6043-P 80