NISTIR 88-3891

Artificial Intelligence

Techniques in Real-Time

Production Scheduling

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

November 1988

Issued February 1989
NATIONAI

Research Information Center

Gaithersburg, MD 20899
NISTIR 88-3891 MM

Artificial Intelligence

Techniques in Real-Time

Production Scheduling

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

November 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. It's 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

ARTIFICIAL INTELLIGENCE TECHNIQUES

IN REAL-TIME PRODUCTION SCHEDULING

Wayne J. Davis

Professor of General Engineering

University of Illinois

Urbana, IL 61801

Albert Jones

Deputy Project Manager, AMRF

National Institute of Standards and Technology

Gaithersburg, MD 20899

ABSTRACT

This paper addresses the real-time production scheduling

problem as a special case of a much larger class of real-time

decision-making/control problems. The paper first reviews the

definition of the scheduling problem, and then reviews a earlier

algorithm proposed by the authors to address this problem. It

then concentrates on the possible application of various AI

techniques to many of the functions that make up that algorithm.

Keywords: artificial intelligence, automation, expert systems,

information models, production scheduling, real-time

decision-making, simulation

1

1 . 0 INTRODUCTION

Solution methodologies to classic decision-making and control

problems in dynamic systems are undergoing a major metamorphosis.

The significant thrust has been to computerize, automate, and

integrate these methodologies, effectively removing the human

being from the loop. Certainly one of the most publicized areas in

which this is happening is discrete parts manufacturing. A

particular problem that has received considerable research

attention within the manufacturing arena is the production

scheduling problem. This problem possesses several properties

which allow it to serve as a representative example for the larger

class of real-time decision-making/control problems.

First, the decision constraints and performance objectives

must be modified frequently to reflect unexpected events in

system's evolution. When these events occur, the problem must be

reformulated and resolved as quickly as possible. Second, those

events take place in a unpredictable, and usually stochastic

manner. This implies that the robustness of any decision must be

demonstrated against these uncertainties. Third, inputs and

outputs for this problem must be coordinated with the inputs and

outputs for other problems. For example the output from process

planning is used by production scheduling. Fourth, the problem

focuses upon a time interval which demands quick determination and

implementation of a solution. Finally, the introduction of

computers and advanced sensors furnish a great deal of feedback

data on a real-time basis. That forces a control mechanism to be

in place which can use that data in resolving deviations between

planned and actual system response.

Davis and Jones [ DAV88 ] have proposed an algorithm which has

general applicability to such real-time decision-making problems.

Their first application was to production scheduling within a

hierarchical control framework. After defining the Production

Scheduling problem, we will present an overview of that algorithm.

We pay specific attention to the role that AI can play in carrying

out the functions contained in the algorithm and managing their

input/output data. We plan to use expert systems in a supporting

role in generating real-time production schedules. In addition,

we expect some of the information modeling methodologies used in

AI to speed up many of the data handling and analysis functions in

the algorithm.

2.0 THE PRODUCTION SCHEDULING PROBLEM (PSP)

We now give a formal statement of the production scheduling

problem (PSP). We assume that JOBj (j=l,...,J) has associated due

date Dj and requires the production of a specific product o 1

(m=l,...,M). We further assume that processes Pn (n=l,...,N) ‘are

available, and that TASKji n (i=l,...,I) represent the individual

processing tasks to be performed on JOBj by Pn

. If we define
2

E ijn as t^ie earliest start time for TASK^j n

Lijn as tlie latest finish time for TASK^j n

the PSP is to optimize the utility function

W[f1 (Em / ,LuN )/...,fL

( )]

where the f^ ( ) are the criteria to be considered in the

optimization. These criteria could include the minimization of

tardiness with respect to assigned due dates, the maximization of

production throughput or the maximization of process utilization.

The optimization is carried out with several technological

constraints. They include due dates, material handling,

precedence relationships among the processes, precedence

relationships among the tasks, and alternative routings.

An exact mathematical representation of the objectives and

constraints for a given the production scheduling problem is quite

complex. For a generic representation of this problem, and a

detailed formulation, the reader should consult [MCP86 , ROD86 ]

. For a survey of mathematical programming approaches to solving the

production scheduling problem, the reader should consult [RAM85

,

GRA82 ] . For a summary of some of the recent work in this area the

reader is referred to [JAC86].

Davis and Jones [ DAV88 ] proposed a decomposition of the

production scheduling problem into two levels (see Figure 1) . The

top level, the supremal, determines the start and finish times of

each JOB

j

at each process Pn , Ej n and Lj n respectively. The

bottom level, the infimal, uses “these bounds to determine the

start and finish times for the TASK-Lj n. The authors made two

important and realistic assumptions in developing this

decomposition. First, decision makers at each level will behave

in a cooperative fashion in solving their own problems. Second,

the decision maker at the Process Coordinator level possess more

detailed information about the variables and constraints

associated with his decisions than the supremal. These

assumptions result in a downward flow of authority and an upward

flow of aggregated information about the state of the process and

duration of activities.

3.0 A DECOMPOSITION ALGORITHM

We now review the approach proposed in [DAV88] in more

detail. The schematic is given in Figure 2. The discussion is

divided into two parts: planning and control.

3.1 PLANNING

The planning elements include the selection of evaluation

criteria and scheduling rules, simulations, statistical analysis,

and compromise analysis. Their combined responsibility is to

find, in real-time, the best compromise scheduling rule given the
FIGURE 1 - THE DECOMPOSITION STRATEGY FOR THE PRODUCTION

SCHEDULING PROBLEM
PRODUCTION

SCHEDULER

FIGURE 2-

MODULAR

SCHEMATIC

FOR

THE

PRODUCTION

SCHEDULER
3

current state of the system.

3.1.1 Evaluation Criteria. The evaluation criteria can be a

combination of goals related to the performance of the entire

manufacturing system, some or all of the processes, and some or

all of the jobs. These criteria are often fixed, and set by

management. However, they can also be a function of the current

state of the system and changed each time a new schedule is

required. Currently, acceptable methods are not available for

choosing the appropriate criteria.

3.1.2 Scheduling Rules. The current research in production

scheduling appears to be focusing upon three methodologies

[RAM85 , GRA82 , JAC86 ] . The first, and perhaps classic, methodology

employs mixed integer programming, including branch-and-bound and

combinatorial techniques. In this approach, the production

scheduling problem is typically posed with a single objective

function to be optimized over a set of mathematical constraints

expressed as linear equalities and inequalities. Recent work with

multi-criteria integer programs has developed methodologies to

generate the nondominated vertices. An alternate approach toward

the consideration of multiple objectives would define the Nadir

solutions which optimize each singular objective. From the

nondominated solutions, a class of candidate schedules would

emerge [DES86]

.

Heuristic/artificial intelligence approaches attempt to

define a set of scheduling rules which can be a combination of

preselected job release strategies, queuing strategies, material

handling strategies, and any number of well-known dispatching

rules. As with the evaluation criteria, these rules can be fixed

or vary with the state of all or part of the system. These rules

can be selected using an algorithm [OGR85], or an expert system

[ WYS86 , PAR86, FOX84 , LAW86] . These approaches use a combination of

production rules and constraint-directed reasoning to generate

feasible schedules. We note two things. First, those approaches

which use only an expert system to define the rules and generate

the schedules have severe computational problems. Second, these

approaches make no claim of optimality or provide no measure of

how close they are to optimality.

Closely related to the heuristic approaches is the recent

trend to employ simulation, or a model-based approach, to generate

a production schedule [MIL86 , NOR86] . The simulation approach

begins by first constructing an accurate representation of the

shop floor as a discrete event system. Next rules are specified

which govern the behavior of the major components of that system

including routing rules, queuing rules and dispatching rules.

Given the list of the current jobs to be scheduled, a single-pass

simulation is then executed. Critical events are recorded from

which the production schedule is specified. For both the

heuristic and simulation approach, the schedule is highly

dependent on the rules. That is, using an alternative sets of

rules will generate different schedules.
4

3.1.3 Simulations. Discrete event simulation is the primary

analysis tool used in the Davis/Jones approach. Concurrent,

independent, real-time simulations are performed for each of the

candidate scheduling rules. These simulations are integrated with

shop floor data collection systems so that each trial can be

initialized to the current "state" of the manufacturing system.

Assuming that K simulation trials are run for each scheduling

rule, an output table of start and finish times can be generated.

Table 1 shows a sample output for the supremal. Here E^n

is the

kth simulated response for the start time of JOBj on process Pn

and L^nis the k

tJl simulated response for the finish time of JOBj

on process Pn .

k Simulation Results

• 1 E^*11 L

ii E^IN

L

1

^lN * * E

i

• ‘‘jiLJ1 E

1

• • • ^JN ljn

© • • • • • • • •

• • • • • • « • •

• • • • • • • • • K e

k

b ll L

K

11 e

k

• • • fc 1N lk

lN •* e

k

• *\jlLK

J1 e

k

• • • tJN lk

jn

Table 1 —Simulation Results for each Scheduling Rule

From this table we can evaluate each of the L objectives

f* = f

1 (E^

1

, . . .

,

LjN

) for k=l , . . .K and 1=1, . . .L. (2)

As an example, the tardiness of a given JOBj could be computed as

k k

T. = max{0, max[L. ]-D.} for j=l, . . . , J and k=l,...K. (3)

J n

J J 3.1.4 Statistical Analysis. A statistical analysis is performed

on the resulting function data. Specifically, for each objective

f

1

( ) and for each scheduling rule r an empirical probability

density function is developed giving

Pr[f*( ) < z] = F*(z) (4)

The following statistics can then be computed

fj. = Mean or Ex [f^] (5)

(s£.) 2 = Sample Variance or Ex [f^ - f^] 2 (6)

m£ = Minimum or m^n [f£|r] (7)

M^ = Maximum or max [f^|r] (8)

Developing confidence interval intervals using these statistical

samples is complicated by the fact that each simulated trial will

be initiated from a different initial condition or state. This is

a topic of active research.
5

3.1.5 Compromise Analysis. The next step is to determine the best

compromise scheduling rule. First we determine the nondominated

set of scheduling rules, denoted by R*. The set R* is defined

such that r € R* if for every r' € R there exists an 1 £ {1,...,L>

such that

f£ > f£. (9)

Given the nondominated rule set R*, the next step is to determine

the minimum and maximum for each objective function over R* as

n = mm

rcR1

M' = max

r*R’

(m^)

(M*)

( 10 )

( 11 )

In

R* is

this manner, the range of compromise

defined as the interval [n^,M^].

for each objective f^ over

Using the statistics for

the associated range of

strategy r* € R* is then chosen.

Methods for making this choice in a stochastic, multi-criteria,

decision-making framework are being developed.

the nondominated strategies R and

compromise, the "best” compromise

3 . 2 Control

Implementing the best compromise scheduling rule r* is the

primary function of the control elements: list generation,

coordination, and conflict resolution.

3.2.1 List Generation. The first major control function generates

an event list which the supremal will attempt to implement. Using

the current state of the processes P^ (n=l,...,N) with the

selected best compromise rule r*, an additional single pass of the

simulation is made to generate the following event list

£ - t E n Lii/*«*/ ejn ljn3 (12)

from which we easily obtain the anticipated duration of process Pn

on JOBj , called dj n = Lj n - Ej n

. The event list E is then sorted

into three sublists: 1)

J chronologically into a master schedule T,

2) by JOBj (j=l,...,J) into a scheduling list J, and 3) by process

into a process control list C. The job scheduling list J provides

the information necessary to track each JOBj at any given time.

The process scheduling control list C will permit the prediction

of the status of a given process Pn at any given time.

3.2.2 Coordination. The event lists T, J and C provide the data

needed by the supremal to 1) coordinate the activities of the

subordinate PCn (n=l,...,N) and 2) provide feedback status on job

completion. The coordination comes from all required precedence
6

completion. The coordination comes from all required precedence

relationships and the material handling considerations which are

monitored continuously to ensure feasibility. Under the

assumption of a cooperative hierarchy, we assume that each PCn

will actively attempt to fit the actual process duration, tj n , within the time interval [Ej^,Lj^]. If changes are to be made J to

the list T, then the feasibility of the entire list must be

restored.

3.2.3 Conflict Resolution. The feedback information from the PCn , (Ej n

, Lj n ) gives Ej n as the actual initiation time and Lj n as the

expected completion time for JOBj . This implies that tne actual

processing time is given by

tjn = Ljn ” E jn ( 13 ) Whenever tj n does not equal dj n , the event list T is no longer

valid since JOBj will not be completed at the scheduled time. This

can happen for two reasons. First, the process coordinator selects

the initial tj n based on the status of the process. Second, as

the process evolves in time, the process coordinator may change

the original tj n

. In either case, the actual duration, tj n , can

differ from the supremal 's estimated duration, dj n

. When this

happens, the Cost Analysis module is invoked to negotiate the

determination of an acceptable process duration. This usually

means that T must be updated to resolve this discrepancy. This

requires the supremal to update its solution, in real-time, to

restore feasibility.

First, we determine if the event list T can be updated

without redoing the entire analysis. We are investigating the

Perturbation Analysis technique described in [H083,SUR84] and the

Match-up approaches discussed in [BEA86,SAL88] . If restoration is

possible, then we simply update the estimates for the expected

durations, dj n , and generate new lists T, J, and C. If restoration

is not possible, then a complete regeneration of E is required.

This will happen if 1) the deviations between the planned and

actual durations are large, 2) the compromise rule r* is changed,

and 3) a new Jobj is added to the list for scheduling.

3.2.4 Remarks. Normally we would anticipate that the continuous

rescheduling would introduce nervousness or instability in the

interaction of the supremal with the subordinate PC's. However,

the (Ej n

,Lj n ) pair will be released to the PCn on a need to know

basis only. Once the Jobj has been released to PCn , f the f PS can no

longer enforce (Ej n

,Lj n ), but rather reacts to (Ej n

,Lj n ). The

updating of the schedule is in anticipation of future system

performance. Since the PS can not enforce a modification upon

(Ej n

,Lj n ), the PC's are insulated from this potential problem.

4.0 AI FOR INFORMATION MODELING

We are beginning to implement the various modules described
7

above. We envision using two major AI methodologies: information

modeling and expert systems. Information modeling is necessary to

handle the simulation input/output data and the various control

lists. Although expert systems are not used as the primary

analysis tool, they will be used them to aid in selecting

performance criteria and candidate scheduling rules, and in

analyzing some statistical output from the simulations. We

discuss these issues in more detail in the following sections.

4 . 1 Input Data

The algorithm described in [ DAV88 ] require simulations to be

initialized to the current "state” of the system. At the supremal

level the state contains status information about the processes,

buffers, and jobs currently on the shop floor. In addition, it

includes the current schedule and information about the new jobs

to be added to that schedule.

4.1.1 Processes. We assume that the shop floor contains N

distinct processes denoted by Pn (n=l,...,N). These processes

can be one of three types. First, a process can perform operations

that physically alter the state of a job such as machining or

deburring. Second, a process can perform operations that

ascertain the true attributes of the job such as inspection or

performance testing. Finally, a process can perform operations

that change the physical location of a job such as robots,

conveyors, or automated guided vehicles (AGV)

.

The state of each type 1 and type 2 process Pn contains the

following information for each JOBj at the process: job ID, the

product type m corresponding to JOBj, the batch size #(JOBj), and

E jn' Ejn' Ljn* anc* Ljn* Although there are a variety of type 3

processes, material transportation devices, we limit our

discussion to automatic guided vehicles (AGV) . We note that

expanding the definition to handle other devices is straight

forward. In addition to a BUSY/IDLE indicator, the state of each

AGV contains the following information for each JOB it is

transporting: the JOB ID, destination and path being used, current

location, expected completion time (Ej n for deliveries, Lj^ for

pickups) . The topology of the transportation network has direct

impact on the complexity of both location and path definitions.

In small, simple networks the last node visited may suffice for

location, and a list of nodes for the path. In more complicated

systems, the network can be partitioned into sectors. These

sectors IDs can then be used to define both pieces of data.

4.1.2 Buffers. Buffers are used as temporary storage repositories

for work-in-process or raw material inventory. They can also be

used to store other types of inventory such as tools, fixtures,

and robot end effe*ctors. Buffers typically have several distinct

characteristics which impact the complexity of their state

definition. Some buffers are located near and only store

inventory for a unique process. Others can store inventory for

more than one process regardless of their location. Some buffers
8

have no natural ordering, such as bins. Others can have a two or

three dimensional ordering, such as tables and shelves. Some

buffers can hold one item per storage slot; others can hold

several items per slot.

The state should include some information on the type of

buffer, the ID and location of each item in the buffer, and a

linking mechanism to link items together that are logically

connected.

4.1.3 Current Schedule. The current schedule at the supremal

level contains timing data on all jobs and processes on the shop

floor for some period T into the future. (Typically, T is one day

or one shift.) For each process, that data includes the expected

start and finish time for each JOB to be executed during T. For

each job, that data includes

Ej n

- the planned arrival time for JOBj at process Pn , Lj n

- the planned pickup time for JOBj at process Pn , Ej n - planned time for Pn to begin processing JOBj, and

Lj n - planned time for Pn to complete processing JOBj

GANNT [BAK74] charts are the conventional method for representing

all this information on one diagram.

4.1.4 Current Jobs. The "state of the system" also contains the

progress of each job on the shop floor. The status of each job

includes job ID, current location (buffer, transporter, or

process) , due date, expected completion time, shop floor release

time, list of process to be used and any alternates, and

expected/actual start and finish time at each process. The list

of processes being used to fabricate a given part can be derived

easily from the GANNT chart.

4.1.5 New Jobs. Several pieces of information must be generated

by the process planning department before a NEW_JOB can be

schedule: a JOB_ID, due date, release time, expected completion

time, and a routing. A routing is either a completely-ordered or

partially ordered listing of the processes needed to produce,

transport, and inspect this NEW_JOB and the expected time spent

at each process. ordered pairs (PROCESS_ID, DURATION) . If we

allow only one, completely-ordered, M step routing then a simple

ordered list processes and durations is sufficient. If we allow

the routing to be a partially-ordered list of M activities, then

we must include the precedence relations among processes. This

can be visualized using the concept of a PERT [BAK74] diagram,

(see Figure 3) . Precedence relationships are enforced using, the

following convention: a given activity cannot begin until all

activities ending at its start node have been completed.

If we allow the scheduler to consider more than one routing

for each NEW_JOB, then the preceding definitions are inadequate.

One possible representation for such a generalized routing uses

an AND/OR graph (see Figure 4) . This is an extension of the PERT
9

graph used above. Each arc represents an activity, each activity

has a start node and an end node, square nodes represent OR

branches and circular nodes represents AND branches. Precedence

relations are handled exactly as they described for the PERT

diagram.

4.2 Output Data

As we saw earlier, the output from each simulation trial at

the supremal level is limited to E^n and L^n. Distinct values

for the start and finish times are derived on each simulation

trial for a given rule. Since each simulation trial requires a

finite time to implement, a generated output will contain both

events for which actual system response will have already been

measured and events for which system response has not yet been

measured. As the simulated output record in Table 1 ages, the

number of events representing predicted system response must

decrease as more events are realized by the actual system. One

immediate consequence is the essential requirement that the

simulated output records must be updated as each newly measured

event is recorded. In addition, all of the performance measures

and their associated statistics must also be updated.

4.3 Control Lists

As noted above, the control lists T,J, and C form the major

outputs from the scheduler. They are, in fact, the master, job,

and process schedules. They also form the principal information

FIGURE 3. SAMPLE PERT CHART

FIGURE 4. SAMPLE AND/OR GRAPH
10

used in the negotiation and conflict resolution that takes place

between the various levels in the control hierarchy.

4.4 Using AI Methodologies

We have described the information needed to define the

’'state'* of the system which is used to initialize the real-time

simulations. We are in the process of examining different

representations, including semantic networks and object-oriented

programming, for storing and updating this information.

Substantial testing is required to estimate the robustness and

efficiency of various structures in both the laboratory and the

real-world. There is an additional problem in a real-world FMS

because the data required to generate those structures will come

from the shop floor sensors and computers, the process planning

data base, and the production scheduling data base. This "raw"

data must be converted to the selected structures before they can

be used to initialize the R concurrent simulations.

We have also described the output and related statistical

calculations generated by those simulations. Here again, we

foresee the need to develop efficient data structures for storing

and updating this information. In addition, computer based

procedures must be designed to filter the statistical results and

bring the salient features of the data to the decision-maker.

The automated procedure must then act to determine the best

compromise rule. In this function, it is essential that the

decision-maker be able to query the algorithm for the basis of

its current selection. Finally, the algorithm must be capable of

recognizing instances which are beyond its logical or programmed

capacity and request human intervention. In these instances, the

algorithm should employ the human's response to improve its

knowledge base, increasing its capacity to handle similar future

instances

.

Finally, we have described the information that is contained

in the control lists. It is extremely important to develop

structures that capture the relationships between the entities in

these lists and which allow one to quickly search through each

list to determine the impact of any delay or other, anticipated

changes

.

5. RULE-BASED METHODOLOGIES

Although we do not plan to use a large expert system to

generate schedules, we do plan to use that paradigm in executing

several functions within our algorithm.

5.1 Planning Functions

We expect to use rule-based systems to aid in determining

both the evaluation criteria and candidate scheduling rules. In

addition, we will develop some rule-based procedures for

analyzing the statistical data generated from the simulations.
11

This analysis will help the decision maker understand the complex

relationships and correlations that may exist among the various

performance measures. It will also provide a means to filter

that data and aid in the selection of the best compromise rule.

Finally, it will provide the opportunity to learn from past

decisions, thereby increasing the effectiveness of the scheduler.

5.2 Control Functions

As described above, the scheduler at the supremal level will

attempt to implement the selected compromise scheduling rule r*.

The event list generator will first generate a tentative list of

future events given the current system status while using

preselected processing durations, dj n

. The process coordinator

will then determine his "best'1 schedule based on his own

determination of the actual process duration, tj n

. The cost

analysis function is invoked whenever there is a difference

between the estimated and actual process durations. We expect to

use some type of rule-based system to carry out this negotiation.

We note that early all the current research in real-time

production scheduling has ignored this issue by assuming that

processing durations are fixed. We believe that if time-varying

processes are to be considered and hierarchical approaches used

for production scheduling, that this issue cannot be ignored.

We also plan to use some type of rule-based system to determine the appropriate course of action to take each time a

conflict occurs. That means that a decision must be made about

the current schedule. Today's ad hoc approaches are simply

inadequate. We need a fast method to determine the impact of any

problem on the current schedule, determine if a quick fix is

possible and the impact of that "fix", or determine that a

completely new schedule must be generated.

5.0 CONCLUSIONS

This paper has focused on the potential for applying AI

techniques to the functions described in [ DAV88 ] algorithm for

doing real-time production scheduling. Due to the embryonic

nature of the algorithm itself, specific AI algorithms can not

yet be prescribed. Nevertheless, the nature of the problem which

is being addressed provides attributes which point to the

appropriateness of considering AI methodologies.

Before concluding this paper, it should be noted that the

problems cited herein are not limited to real-time production

scheduling. Several other problem domains could have been used.

We can expect a more generalized algorithm for real-time

decision-making to emerge and that additional problem areas will

be defined for which AI will provide a beneficial solution

methodology.
12

[BAK74]

[ BEA86

]

[DAV88]

[ DES86

]

[ FOX84

[GRA82

[HO 83]

[ JAC86

[ LAW82

[LAW86]

REFERENCES

Baker, K. R. , Introduction to Sequencing and

Scheduling, John Wiley & Sons, New York, 1974.

Bean, J. and Birge, J., "Match-up Scheduling",

Proceedings of the Symposium on Real-Time Optimization

in Automated Manufacturing Facilities, National Bureau

of Standards, Gaithersburg, Maryland, January 21-22,

1986, pp. 197-212.

Davis, W.J. and Jones, A.T., "A Real-Time Production

Scheduler for a Stochastic Manufacturing Environment,"

International Journal of Computer-IntegratedManufacturing, Vol. 1, No. 2, 101-112, 1988.

Dessouky, M. I., Ghiassi, M. and Davis, W. J.

"Estimates of the Minimum Nondominated Criterion Values

in Multiple-Criteria Decision-making," Engineering

Costs and Production Economics, Vol. 10, 1986, pp. 95-

104.

Fox, M. S. and Smith, S. F. , "ISIS — A Knowledge-Based

System for Factory Scheduling," Expert Systems, Vol. 1,

No. 1, 1984, pp. 25-49.

Graves, S, C. , "A Review of Production Scheduling,"

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

Ho, Y. C. , SPEEDS: A New Technique for the Analysis

and Optimization of Queuing Networks, Technical Report

No. 675, Division of Applied Sciences, Harvard

University, Cambridge, Massachusetts, 1983.

Jackson, R. H. and Jones, A. T. , (eds.), Proceedings of

the Symposium on Real-time Optimization in Automated

Manufacturing Facilities, National Bureau of Standards

Special Publication 724, Gaithersburg, Maryland, 1986.

Law, A. M. and Kelton, W. D. , Simulation, Modeling and

Analysis, McGraw-Hill, New York, 1982.

Lawrence, S. R. and Morton, T. E. , "PATRIARCH: Hierarchical Production Scheduling", Proceedings of the Symposium on Real-time Optimization in Automated Manufacturing Facilities, National Bureau of Standards Special

Publication 724, Gaithersburg, Maryland, 87-98, 19*16.

McPherson, R. F. and White, K. P. , "A Management

Control Approach to the Manufacturing Planning and

Scheduling Problem", Proceedings of the Symposium on

Real-time Optimization in Automated Manufacturing

Facilities, National Bureau of Standards Special

[MCP86

]
[MIL86

]

[NOR86

]

[OGR85

]

[ PAR86

[RAM85

]

[R0D86

[ SAL88

]

[ SUR84

]

13

Publication 724, Gaithersburg, Maryland, 145-166,

1986.

Miles, T., Erickson, C. and Batra, A., "Scheduling a

Manufacturing Cell with Simulation," Proc. of 1986

Winter Simulation Conference, Washington, D.C., pp.

668-676.

Norman, T. A. and Norman, V. B. , "Interactive Factory

Scheduling Using Discrete Event Simulation, Proc. of

1986 Winter Simulation Conference, Washington, D.C.,

pp. 665-667.

O'Grady, P. and Harrison, C. , "A General Search

Sequencing Rule for Job-shop Sequencing," International

Journal of Production Research, Vol. 23, No. 5, 1985.

Parrello, B. D. and Rabat, W. C. , "Job-Shop Scheduling

Using Automated Reasoning: A Case Study of the CarSequencing Problem," Journal of Automated Reasoning,

Vol. 2, 1986, pp. 1-42.

Raman, N. , A Survey of the Literature on Production

Scheduling as it Pertains to Flexible Manufacturing

Systems, National Bureau of Standards Report NBS-GCR85-499, U.S. Department of Commerce, National Bureau of

Standards, Gaithersburg, Maryland, 1985.

Rodammer, F. A. and White, K. P. , "Design Requirements

.for a Real-time Production Scheduling Decision Aid",

Proceedings of the Symposium on Real-time Optimization

in Automated Manufacturing Facilities, National Bureau

of Standards Special Publication 724, Gaithersburg,

Maryland, 401-422, 1986.

Saleh, A., "Real-time Control of a Flexible

Manufacturing Cell", unpublished Ph.D dissertation,

Lehigh University, 1988.

Suri, R. and Dille, J. W. , "On-Line Optimization of the

FMS Using Perturbation Analysis," Proc. of Flexible

Manufacturing Systems Conference, First ORSA/TIMS

Special Interest Conference, Ann Arbor, Michigan, Aug.

1984.

Wysk, R. , Wu, S. and Yang, N. , "A Multi-pass Expert

System (MPECS) for Job-shop Scheduling", Proceedings of

the Symposium on Real-Time Optimization in Automated

Manufacturing Facilities, National Bureau of Standards,

Gaithersburg, Maryland, January 21-22, 1986, pp. 251-

278.

[WYS86

]
NBS-1 14A REV. 2-3C' J.S. DEPT. OF COMM. 1. PUBLICATION OR 2. Performing Organ. Report No. 1. Puolication Date

REPORT NO. 1 BIBLIOGRAPHIC DATA j SHEET ('See instructions) NISTIR 88-3891

, FEBRUARY 1989

4. TITLE AND SU BTITLE

Artificial Intelligence Techniques in Real-Time Production Scheduling

5. AUTHOR(S)

Wayne Davis, Albert Jones

5. PERFORMING ORGANIZATION (If joint or other than NBS, see in struction s)

NATIONAL BUREAU OF STANDARDS

7. Contract/Grant No.

U.S. DEPARTMENT OF COMMERCE

GAITHERSBURG, MD 20899

8. Type of Report & Period Covered

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

National Institute of Standards & Technology

Bldg. 220 Room A-127

Gaithersburg, MD 20899

10. SUPPLEMENTARY NOTES

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

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

bi bl iography or literature survey, mention it here)

This paper addresses the real-time production scheduling problem as a special

case of a much larger class of real-time decision-making/control problems. The

paper first reviews the definition of the scheduling problem, and then reviews a

earlier algorithm proposed by the authors to address this problem. It then

concentrates on the possible application of various AI techniques to many of the

functions that make up that algorithm.

12. KEY WORDS (Six to twelve entries; alphabetical order; capitalize only proper names; and separate key words by semicolon s) artificial intelligence, automation, expert systems, information models,

production scheduling, real-time decision-making, simulation

13. AVAILABILITY

r~x] Unl imited

| { For Official Distribution. Do Not Release to NTIS

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

20402.

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

14. NO. OF

PRINTED PAGES

19

15. Price

$$9.95

U SCOMM-DC 6043-P80

»«-38S> I

Jun 1

3

,

2.0 1

<3