1

System Approach
to the Design
of Generic Software
for Real-Time
Control of Flexible
Manufacturing

Systems (FMS)

1.1 Preface

1.2 Dedication

1.3 Introduction

1.4 Fundamental Steps of the Modeling Process

1.5 Specification of the Model Static StructureWorkstations • Transport System

1.6 Queuing Network ConfigurationProduction Activity Configuration • Job
Configuration • Server Configuration • Transport System
Configuration • Definition of the Queuing Network

Bruno Maione

Politecnico di Bari

Giacomo Piscitelli

Politecnico di Bari

Biagio Turchiano

Politecnico di Bari
© 2001 by CRC Press LLC

1.1 Preface

The control system is the core of any flexible manufacturing system (FMS) because it confers to the plant
the capability to absorb internal changes and external fluctuations in demand and in production environ-
ment. However, the technical literature has repeatedly documented that poor control software design is
the major source of difficulties in implementing FMSs. Namely, the FMS potentiality is not yet fully utilized,
because typical, contemporary control software packages are still proprietary and do not possess flexibility
and genericity. On the contrary, reducing the programming and reprogramming effort needs a generic
software usable in an arbitrary FMS, producing an arbitrary part mix.
To design a generic software, two main problems must be solved. The former is to define an abstract
formalism representing both hardware/software components of the FMS and the production plans. The latter
consists in identifying a modular architecture of the control software capable of integrating standard modules.
To solve the first problem, we use a system approach leading to a discrete event dynamic system (DEDS)
that constitutes a formal framework providing information on both the current operating conditions of
the shop floor (SF) and the production progress. To face the second problem, we use the object-oriented
approach to design the kernel of the generic control software. The resulting modular architecture is
organized so that modules and interfaces among them can be replaced without altering the overall

problem consists in identifying an appropriate, modular software architecture capable of integrating
standard software modules, e.g., for data base management, for field-events detection, and so on. More-
over, if there is the necessity, the modules of this architecture should be changeable to take into account
specific instances of particular FMSs without changing the software main structure and interfaces among
different parts.
© 2001 by CRC Press LLC

To solve the first problem, we refer to Zeigler’s approach [20], [21], [22] which describes DEDS by using
a set-theoretic formalism based on system theory concepts of Zadeh and Desoer [19], Wymore [18], and
many others. In our approach the DEDS state encompasses information on both the current operating
conditions of the SF and the progress of the programmed production. Moreover it includes a logic com-
ponent collecting the decision rules necessary to resolve conflicts arising in the resource allocation. The
information on the SF operating conditions and on the production progress is described using the
primitive concepts of entities, entity attributes, and relationships between entities themselves, all
organized in a relational structure [2] updated at each event occurrence. The decision rules, appearing as
system state components, can be changed at any instant. Due to the formal structure of these rules, one
can establish the information necessary to support the decision making.
The approach followed to define the DEDS state is transparent and has some advantages. First of all,
it allows a detailed and modular description of the production system. Major details can be given, if
necessary, by enriching the state with further entities, attributes, and relationships. Moreover, the model
allows us to describe a generic FMS, producing an arbitrary part mix, under an arbitrary scheduling
policy. Finally, the mechanism for state updating and the definition of all the exogenous events triggering
such transitions lead to a DEDS model that completely describes the FMS behavior at job release and
flow management levels.
To face the second problem, we consider the operation control of FMS from a model reference point
of view. Our approach consists in driving the SF so that it follows the dynamics of the reference DEDS
model. Indeed, this model establishes how the plant should respond to the command signals and interacts
both with the higher level (production planning) and with the lower one (hardware components). The
resulting control architecture emerges as direct consequence of this idea of utilizing the DEDS formulation
to define the kernel of a generic software driving the dynamics of the actual FMS. Inspired by the works

of sentences as “at instant

t

1

the machine

m

1

starts processing job

j

2

” or “at instant

t

1

machine

m

1


sets. The cardinality and the members of such sets are permanent elements of the model structure
even if some resource is unavailable occasionally.
2. The processing activity entity sets contain the basic elements of the manufacturing activity. Sets
belonging to this category consist of orders, job types, active processing procedures, and allowable
alternative sequences of operation steps in a given working procedure. The above entities change
during the manufacturing process and hence are transitionary.
3. The job entity set contains the basic temporary entities of the model, i.e., jobs (pieces) in the
system at a given time. Both cardinality and elements of such a set change with time.
The second step of the procedure deals with establishing associations between entity sets and with
defining entity attributes. Associations take the form of mathematical relations among entities and are
expressed as functions mapping from an entity set into another one or appear in the form of specified
relationship sets. Functions mapping from an entity set (or a relationship set) into different value sets
(such as the set of reals, non-negative integers, {0, 1}, {

Up

,

Down

}, etc.) define the entity (relationship)
attributes. Typical attributes encountered in the proposed framework are the number of final products,
the buffer capacity, the server status, the current position of an Automated Guided Vehicle (AGV), etc.
Attributes either characterize each of the entities in the system or keep track of their current status.
An entity may also be indirectly related to another one. Hence the need arises of an overall perspective
in which all the entities, together with their attributes and relationships, contribute to represent the FMS
as a whole. This leads to the concept of configuration. A configuration collects all the relationships and
the attributes defined on entity sets (or subsets) belonging to the same category. For instance, the job
entity set (or a subset of it) is the domain of attributes and relationships pertaining to the job configuration
(

p

, C

j

, C

s

, C

h

), named
queuing network configuration, embodies all the entities with their attributes and relations integrating
all the elements in a whole.
The third step provides the formal representation of the set of decision rules governing the flow of
the transitional entities. Rules concern job loading, routing, and priority setting. In the proposed frame-
work, the focus is on the formal representation of rules rather than on the rules themselves. Namely, the
sole information about a rule is how it utilizes the queuing network configuration knowledge to make
proper decisions.
© 2001 by CRC Press LLC

The fourth step defines the model clock, i.e., the event occurrence times, and measures the elapsed
time from the last event occurrence. We consider two types of events. The internal system dynamics
generates the internal events (operation step and transport operation completion, etc.). The external
events (hardware component failure or repair, order removal, or insertion, etc.) represent disturbances
or manipulated variables. In a time interval in which no event takes place, (


Consider an FMS with

N

M

available workcenters. These constitute the set
Each machine

m

i

is provided with an input/output buffer, or, alternatively, with both an input buffer
and an output one. Sometimes, the FMS has a central buffer where jobs wait for their next destination.
At this point we introduce the set
where

N

B

indicates the number of buffers in the system. The attribute
distinguishes the type of buffer, where TB(

b

␮

)


m

i

is equipped with

S

i

servers. All the servers within the system make up the
Now, to specify how elements from

B

(from

S

) are related to elements of

M

, we introduce the functions
where BEL-

B

(


(

s

ij

)

ϭ
m

i

means that

s

ij

is a
server of

m

i


Within the FMS, there are many possible transport subsystems to transfer pieces from a machine to
another one. Here we consider only AGV systems, while [7] describes a wide variety of transport systems.
So let

N

H

AGV subsystems be available. An AGV subsystem

h

n

(

n

= 1, 2,…,

N

H

) consists of

N

nT

if the subsystem

h

n

can carry a piece from

m

k

to

m

j

, while TT[(

h

n

,

n
, n 1, 2,…, N
H
ϭ{}ϭ
Transport unit entity set: U {u
nr
, n 1, 2, …, N
H
, r 1, 2, …, N
n
}ϭϭ ϭ
BEL-U : UH→
Th
n
, m
k
, m
j
()h
n
Hm
k
, m
j
Mʦʦ{}ϭ
TT : T R
ϩ
→
© 2001 by CRC Press LLC
Production Orders

) ʦ A iff
(if and only if) the parts resulting from the working procedure w
␲␣
are components of items manufactured
according to w
␲␤
. The relationship set A has the attribute weight
where WE(w
␲␣
, w
␲␤
) defines the number of pieces resulting from w
␲␣
which concur in the assembly of
one item to submit to w
␲␤
.
Finally, the subset W
I
collects elements from W representing initial working procedures (to perform
on not assembled jobs just loaded into the system).
Job type entity set: Pp
␲
,
␲
1, 2,…, N
P
ϭ{}ϭ
Order entity set: Oo
␥

␲␤
, W BEL-Ww
␲␣
()ʦ BEL-Ww
␲␤
()ϭ p
␲
}ϭϭ
WE: A I
ϩ
→
© 2001 by CRC Press LLC
Operation Steps
A working procedure is executed by a sequence of operation steps selected in a set of alternative allowable
sequences. Denoting by V
␲␣
the number of operation steps composing w
␲␣
, we introduce the
The relationship
indicates the working procedure which an operation step belongs to and the following function
represents the attribute processing time of the operation steps.
Furthermore, the alternative routing relationship describes all the alternative sequences carrying out
a working procedure
The pair (v
␲␣␤
, v
␲␣␦
) ʦ R iff there exists an allowable sequence in which the operation step v
␲␣␤

␲␣␤
needs machine
m
1
only.
Finally, the attribute type of step
indicates if any operation step is normal (N) or involves assembling of parts (A).
For systems with a central buffer a particular remark is in order. Namely in this case each of sets V and
W must contain a special element (respectively v
0
and w
0
) with BEL-V(v
0
) ϭ w
0
, PT(v
0
) ϭ 0, TS(v
0
) ϭ N,
JHM(v
0
) ϭ m
0
and where COM(v
0
) is equal to the empty set. The operation step v
0
does not stand for a real

,()v
␲␣␤
v
␲␣␦
, V BEL-Vv
␲␣␤
()ʦ BEL-Vv
␲␣␦
()ϭ{}ϭ
M
l
M
l
M
JHM: VM→
COM: V
M
{}→
m
l
, M
l
() M
l
TS: V N, A{}→
C
p
O, P, W, A, V, R, DD, BEL-P, PN, BEL-W, WE, BEL-V, PT, JHM, COM, TS{ }ϭ
© 2001 by CRC Press LLC
Job Configuration

completion, it cannot move to the output buffer, because the hosting server is blocked; Waiting for
destination, if j
k
resides in an output or input/output buffer and is waiting for the selection of its next
destination and of an appropriate transport unit; Waiting for transport, if j
k
is in an output or input/output
buffer and is waiting for a transport unit. In this case, both the next operation step and the transport
unit have been already chosen; and Carried, if j
k
is moving to the next workcenter.
According to the values of J-STATUS(j
k
), we can partition the job entity set into the following six subsets:
J
R
, J
RA
, J
Ru
, J
DW
, J
TW
, and J
C
. Indeed, introducing the above subsets is necessary to define the functions
pertaining to the job configuration. A first group of functions associates jobs with entities belonging to
the processing activity entity sets. Namely, at the instant t each piece within the system requests or receives
service, according to an operation step from V. This relation is indicated by the function reference

k
ʦ J
Ru
, ROS(j
k
) coincides with the operation step in progress;
if j
k
ʦ J
DW
, ROS(j
k
) specifies the operation step just completed.
In a similar way the function last operation step
indicates the operation step executed by a job just before ROS(j
k
). The condition LOS(j
k
) ϭ n.o.s. (no
operation step) means that ROS(j
k
) is the first operation step executed by (or to execute on) j
k
.
A second group of functions maps job entity subsets into the resource entity sets. In particular, the
following functions establish relationships between subsets of J and the buffer entity set and the transport
unit entity set
where HOS(j
k
) indicates the buffer hosting j

ʦ J
TW
and the whole time to perform the next operation
step (i.e., ROS(j
k
)), if j
k
ʦ J
R
ʜ J
RA
; finally ROT(j
k
) ϭ , if j
k
ʦ J
DW
. Note that each residual time is
always evaluated starting from the instant of the last event occurrence.
As mentioned before, blocking conditions may occur during the FMS operation, i.e., when, on a
transport or an operation step completion, the destination buffer is full. In such a case, the job remains
blocked on the transport unit or on the hosting machine server. The blocking attribute function
points out this condition. Namely BA(j
k
) equals 1 (0) if j
k
is blocked (not blocked). There is another
situation similar to blocking, indicating that a job is prevented from changing its status. In this case the
job cannot release the resource it currently holds. This condition can be indicated by the attribute ‘‘State
Change Inhibitor”

ϱ{}ʜ→
ϱ
BA: J
Ru
J
C
ʜ 0, 1{}→
SCI: J 0, 1{}→
BAT: J
R
J
RA
J
DW
J
TW
R
ϩ
→ʜʜʜ
SAT: J R
ϩ
→
© 2001 by CRC Press LLC
Now we are in the position to define the 13-tuple:
C
j
ϭ {J, TJ, J-STATUS, ROS, HOS, BOO, CAR, ROT, LOS, BA, SCI, BAT, SAT} named job configu-
ration. It fully characterizes the jobs within the system and the operations which they are currently
subject to.
Server Configuration

is called the server configuration.
Transport System Configuration
The following function characterizes the status of each truck
U-STATUS : U → {Idle, Carrying, Blocked, Booked, Down}
with an obvious meaning of the four conditions. In particular, U-STATUS(u
nr
) ϭ Booked if u
nr
is moving
to the buffer hosting the piece j
k
to transport next. When U-STATUS(u
nr
) ϭ Idle, we assume that u
nr
is
standing close to a machine. So, denoting by U
Id
the subset of Idle trucks, we establish such a relationship
by the function rest close to the machine
To account for failure conditions of a whole transport subsystem, we introduce the Transport Sub-
system status attribute
In conclusion, the triple
fully describes the transport system configuration.
RES: S
R
J
R
J
RA

1.7 Scheduling Policy
Adding flexibility to the factory floor increases the scheduling alternatives and, hence, the decision
complexity. Moreover, the necessity of quickly reacting to dynamic changes in the system makes the
operation scheduling more difficult. To approach this problem, we consider the currently applied sched-
uling rules as an essential component of the system state. That is, at each instant, the rules are elements
of the knowledge of the current system behavior. Hence, we do not propose any particular scheduling
policy for resource management at the job release and job flow levels; rather we decompose the scheduling
problem into elementary decision makings (micro-decisions) generally concerning the selection of one
entity (job, operation step, server transport unit, etc.) in a proper subset. Then, to formally describe such
micro-decisions, we introduce appropriate functions (decision rules) by indicating their domain and
their range and leaving undetermined their specific decision mechanism. In essence a decision rule
corresponds to a module that, when invoked, receives data from the current queuing network configu-
ration and makes the decisions it is in charge of. Furthermore a scheduling policy is a set of decision
rules, each of which specifies a micro-decision. In consequence of a modification in production goals,
the scheduling policy may vary with time because at any instant the upper decision levels may require
to apply a new rule and to remove another one. To this aim, a set of possible scheduling rules can be
predetermined by the planning staff and stored in a library.
The job loading and job flow management require the choice of the product type to introduce next
into the system and the corresponding loading time, the routing of each job within the systems, if
alternative paths are available, and the resource allocation when concurrence conditions arise.
Job loading decision rules. Decisions concerning the piece type to introduce next into the system and
the corresponding loading time must be taken simultaneously. The sequencing function and timing
function describe the loading decisions
In particular,
␻
ls
(F) specifies the initial working procedure of the next job entering the system. In other
words, the value of
␻
ls

ls
: FW
I
n.c.{}ʜ→
␻
lt
: FR
ϩ
ϱ{}ʜ→
ϱ
␻
ls
F() n.c.
␻
sci
: FJ 0, 1{}→ϫ
© 2001 by CRC Press LLC