Division of Research
Graduate School of Business Administration
September 1983
USING PETRI NETS TO REPRESENT PRODUCTION PROCESSES
Working Paper No. 339
Didier Dubois
D.E.R.A./C.E.R.T.
Toulouse
Kathryn E. Stecke
The University of Michigan
Proceedings of the 22nd IEEE Conference on Decision and'Control, San Antonio, TX
December 14-16, 1983

USING PETRI NETS TO REPRESENT PRODUCTION PROCESSES
DIDIER DUBOIS
Department d'Etudes et de Recherches en Automatique
Centre d'Etudes et de Recherches de Toulouse
31055 Toulouse, Cedex FRANCE
ABSTRACT
A preliminary investigation, and extension of the
power, of timed Petri nets to describe, model, and analyze production processes is reported. In particular,
insights into real-time control aspects as well as the
performance of flexible manufacturing systems are
sought. Comparisons with previous investigative models
are made. New and general modeling conventions are
provided, which extend the realm of Petri net modeling
capabilities. Various realistic aspects of manufacturing processes are modeled. Efficient algebraic tools
to analyze a certain class of Petri nets are described
[1]. We show that, under some structural assumptions,
timed Petri net models of manufacturing processes
translate into linear equations in a (max,+)- based
algebra. Efficient algorithms can solve these equations for the purposes of both performance evaluation
and real-time control.
INTRODUCTION
Petri nets are useful to model systems whose behavior can be described as interferences between
asynchronous and concurrent processes. To date, Petri
nets have mainly been used to describe computer operating system behavior. Particular applications include
the descriptions of computer hardware and software
[9], communication protocols [3], and queueing networks [4], [6]. In addition, production systems,
such as job shops and flexible manufacturing systems,
exhibit such interference during the manufacture of
part types with different processing sequences. However, to our knowledge, Petri nets have not been used
to analyze control problems of production systems.
Perhaps the main reason for this is that there is very
little literature available on timed Petri nets.
The bulk of the literature focuses on the analysis
of qualitative properties of complex, concurrent computer systems, such as the non-existence or detection
of deadlocks, the safeness, boundedness, conservation,
liveness, and, in particular, reachability of the
states of a Petri net. These properties are described
in ~1.
Ramchandani [8] first introduced timed Petri nets
and provided methods to calculate throughput for certain classes of Petri nets. Ramamoorthy and Ho [7]
specify an enumeration procedure to find the maximum
system performance. Sifakis [10] generalizes the
results of [8].
Our motivation to investigate the usefulness of
timed Petri nets is the study of planning and control
problems of flexible manufacturing systems (FMSs). The
main models used to date to analyze performance have
been queueing networks [11], [13], perturbation analysis [5], and simulation [12]. Queueing networks provide information about the average system behavior
observed over a long time period (steady state). They
are useful for qualitative answers to design and planning problems of FMSs [13], but not very useful to
KATHRYN E. STECKE
Graduate School of Business Administration
The University of Michigan
Ann Arbor, Michigan USA
study control issues. Perturbation analysis "views a
queueing network as a stochastic dynamical system
evolving in time and observes the sample realization of
its trajectory,"[5] similar to simulation. However, by
perturbing one event, and following through an analysis, many useful questions can be answered without
repeating a simulation run. Perturbation analysis has
been used to answer questions that product form queueing networks can't address. Most often, real-time
issues are analyzed using simulation, which is flexible, but t.imeconsuming and expensive.
Our aim is to demonstrate the usefulness of Petri
net models to efficiently analyze problems of real-time
control as well as the performance evaluation of production systems. Our main motivation is to use such
analyses to gain insight into the real-time behavior
of deterministic processes, FMSs in particular. For
example, given a finite number of various resources
(machines, pallets, fixtures, carts, tools,...), after
an initial transient period, we conjecture that a
deterministic production system will eventually reach a
periodical steady state. Petri net representation can
help to capture such behavior, under certain modeling
conditions which are provided subsequently. We have
found new tools that are available to efficiently
analyze a special class of timed Petri nets. These are
shown to be equivalent to certain linear, dynamical,
discrete-event systems.
In ~1, the notation and definitions that are required to represent manufacturing processes by Petri
nets are reviewed. New modeling conventions are suggested in ~2, which extend the realm of Petri net
modeling capabilities. ~3 contains examples of Petri
nets that model various realistic aspects and components of production processes, such as flowshops,
blocked machines, assembly processes, and the FIFO
control rule. We model finite buffer situations as
well as carts, pallets, and different fixture types.
Processing, transportation, set-up, and waiting times
can be included. Cur examples demonstrate the new
modeling capabilities. The algebraic tools that are
available to analyze certain types of Petri nets are
described in ~4. The advantages and limitations of
Petri net representations are outlined in ~5. A summary of existing results and future research is provided in ~6.
1. NOTATION AND DEFINITIONS
A Petri net structure is a four-tuple, CG(P,T,I,O),
where P-{Pl,P2, *,Pn} is a finite set of places and
T{tl...,tm} is a finite set of transitions. PIT=0.
I:T+22 is the input function, which defines for any
transition, its set of input places. A Petri net graph
is a representation of a Petri net structure as a bipartite directed multigraph. In the graph, a circle
represents a place and a bar represents a transition.
A marking u of a Petri net is a function from P
to the nonnegative integers N; j:P+N. u(pi)=vi= number
of tokens in place Pi. Tokens reside in the places and
- 1 -

control the firing of transitions. A transition may
fire when it is enabled. A transition is enabled when
there is at least one token in each of its input
places. A transition fires by removing one token from
each of its input places and distributing these tokens
among its output places. If XI(tj) and XO(tj) are
characteristic functions of sets I(tj) and O(tj), respectively, then the firing of tj changes the marking V
into p' such that
u'(Pi) =1 (Pi) - XI(tj)(Pi) + XO(t)(Pi), V i. (1)
The state of a Petri net is defined by its marking.
The next state function 6 of a Petri net with marking
j, denoted (C,), is defined for any enabled transition
tj, by 6(O,tj)=p', where p' satisfies (1). 6(u,tj)
is not defined if t- is not enabled. ' is said to be
immediately reachable from p. The execution of a Petri
net results in a sequence of markings (pI,...* n,...) and a sequence of transitions (totJ11,..., tin...) such that V k > 0, 6(pktjk)k+1t
The following properties are those that are addressed in the Petri net literature. A marking p' is
reachable from p if there are sequences of markings
(u..,pin) and transitions (tj;,...,tj) such that
p =0 0, u'uun, and 1i+l is immediately reachable from
pi, i=O,...,n-l. The reachability set of a Petri net
(C,p) is the set of all reachable markings from p and
denoted R(C,u). It includes z itself.
every place is in a circuit containing
exactly one token;
4. A marking P' is reachable from a live marking
u if and only if the number of tokens in each
circuit is the same for V and i'.
A place pi
V'(pi)Cl, i.e.,
Petri net (C,u)
safe. When the
which can be in
not necessarily
A bounded Petri
places.
is said to be safe if V~ 'eR(C,u),
pi contains at most one token. A
is safe when all of its places are
upper bound on the number of tokens
a place simultaneously exists (but is
one), the place is said to be bounded.
net (C, l) contains only bounded
A Petri net (C,v) is strictly conservative if
and only if V ueR(C,n),
E '(Pi) X u (Pi), (2)
PieP PisP
i.e., the number of tokens in the Petri net remains a
constant. As a consequence, for any transition, the
number of input places equals the number of output
places. A transition tj in a Petri net (C,p) is
potentially firable if there exists a u'eR(C,p) such
that ti is enabled in p'. tj is live if it is potentially firable for any P'cR(C,U). A Petri net having
only live transitions is live. Petri nets which are
not live have deadlocks.
A decision-free Petri net structure is characterized by the existence of a single input arc and a
single output arc for each place, i.e.,
Vpi, 3!(tj,tk) 9 pieO(tj)nI(tk). (3)
A directed circuit in a Petri net is a sequence of
transitions and places: tjlPil,..., Pinl,tCjn such
that t1 = tin and Vkl,...,n-l, Pi eO(tjk)n I(tj+)+l
A Petri net s strongly connected A every pair or
places is contained in a directed circuit.
For the subclass of strongly connected, decisionfree Petri nets, the following results are known [6]:
1. The number of tokens on a circuit does not change
after a transition fires;
2. Liveness is equivalent to the existence of at
least one token on each circuit;
3. Safeness is equivalent to the situation where
A timed Petri net is a Petri net C with an associated mapping t:T + [0,-oo). Each transition tj has a
firing time Tj-T(tj). Tokens are moved from the input
to the output places of tj only after time T1 has
elapsed since firing began. In a timed Petri net, each
firing sequence (tjl,.,tjn) has a minimal duration,
which is X Tjk. Also, availability times may be
associated with tokens, as part of the initial
conditions.
2. VARIOUS MODELING PRINCIPLES
New and more general uses of Petri nets to describe production processes are now provided in ~2.1.
Following these is a comparison with previous modeling
conventions in ~2.2. The advantages of our suggestions and some limitations of the conventional methods
are shown through examples. The power of these modeling conventions will be further displayed in ~3.
2.1 Suggested Modeling Principles
The following modeling conventions are suggested
to allow both more general applications of Petri nets
as well as efficient algorithms to analyze their performance for certain classes of Petri nets.
i) The set of activities (tasks, operations) to be
performed in the production system is represented by the set of transitions. Each transition is assigned the corresponding activity
duration.
ii) An activity is defined by the simultaneous use
of one or more resources. In particular,
the number of input places of a particular
transition indicate the number of resources
which the activity simultaneously requires.
Output places specify the activities that are
required next and the release of certain resources.
iii) Tokens of various types represent available
resources which flow through activities
according the system control rule.
2.2 Comparison with Conventional Mbdeling
Differences, advantages, and limitations of the
previous modeling conventions and those suggested in
~2.1 are now demonstrated through examples of PERT/CPM
charts and queueing networks.
PERT/CPM Charts. In conventionally modeling a
PERT chart with a Petri net, an activity is represented by a place, precedence constraints are represented
by transitions, and time is not considered [6]. In our
Petri net model, both activities and precedence are
represented by transitions. Places are reserved to
model multiple resources of limited amounts. In addition, our timed Petri nets are more powerful models
than PERT/CPM charts since:
i) Circuits of activities are allowed. This generalizes PERT modeling by enabling the activities to be performed repeatedly, if necessary.
ii) Required resources for activities appear explicitly, as tokens, in the representation.
iii) Nondeterministic aspects can be dealt with. For
example, the order in which a particular resource performs some tasks may not be totally
specified. In this sense, Petri net models
- 2 -

subsume disjunctive graphs.
Queueing Networks. A manufacturing system can be
modeled as a queueing network, where machines and
transporters are the servers and the parts to be processed are the customers. Suppose that the part route
is known and the ordering of customer service is fixed.
Then previous Petri net representations of queueing networks, both untimed [6] and timed [4], have the
queues as places, servers as transitions, and customers
as tokens. These specifications appear to be arbitrary: alternatively, one may view machines as flowing
through parts. More seriously, limited amounts of
multiple resources cannot be modeled. For example, a
server may require tools to service a customer. Also,
blocking effects due to limited queue capacity cannot
be modeled.
An alternative Petri net model, following the
suggestions provided in ~2.1, would represent the
service activities as transitions of some duration.
Each transition has two input places, for both server
and customer tokens. Note that if additional resources
are required, such as a robot, buffer, transporter,
pallet, fixture, and/or one or more cutting tools,
these are modeled with additional places (or different
token types). In addition, finite buffers, blocked
machines, FIFO queue discipline, and assembly processes
can be modeled. Examples of these are provided in ~3.
3. MODELING SOME COMPONENTS OF MANUFACTURING PROCESSES
In order to assess the descriptive power of Petri
net modeling as applied to production processes, examples of different features are now provided.
3.1 Fixed-Route Flexible Manufacturing System
Consider the FMS of Figure 1, consisting of three
different machine tools that process three different
part types according to a specific part mix and the
specified part routes.
P1
P24< p TJ
p2 ---| Ml -- ^==1 M2 M3 | ^
P3 _
Figure 1. Three-Machine FMS.
Processing times of each operation of each part
type on each of the machine tools are given in the
following matrix:
P1 P2 P3
Ml 1 5
M2 3 2 3
M3 4 3
The characteristics of the system that are modeled
include the following:
1. The sequence of parts on the machine tools is
given in Figure 1;
2. Set-up times on a machine tool for part changeover are negligible (the system is flexible,
having automated tool interchange);
3. Transportation times are neglected;
4. For each part type, there is one pallet and one
fixture;
5. The product mix is balanced, and can be obtained
through a periodic input of parts. Here the
sequence 1-2-3 is used.
The pallets ensure a proper positioning of parts on
machines. When a pallet leaves the last machine on
its processing sequence, it returns to the first
machine to carry a new part. (The use of carts to
transport parts is modeled in ~3.3.)
The Petri net of Figure 2 is obtained. For
Figure 2. Petri Net of a Three-Machine FMS
with Three Part Types.
clarity, the different token types in Figure 2 (machine
tools and pallets) have been alphabetically named.
Sometimes different token types are alternatively represented by colored tokens. However, they are unnecessary in this instance since the different token types
appear in distinct places. Colored Petri nets are
sometimes used to simplify large Petri net representations [3]. The Petri net of Figure 2 is decision-free,
safe, and live for any feasible initial marking, for
example, a marking consisting of three "machine" tokens
and three "pallet" tokens. A similar Petri net can be
constructed for a more general job shop type of FMS.
In addition, adding another pallet for one of the part
types can easily be represented. Two ways are
suggested:
i) Expand the number of transitions;
ii) Add a token to the appropriate processing sequence circuit.
In the first case, the safeness of the Petri net is
preserved, but not in the second case. Both proving
the equivalence of these representations, as well as
determining their pro's and con's, are matters for
further research.
Both set-up and transportation times can easily be
introduced as one-place-in, one-place-out transitions
that separate processing transitions. These are demonstrated in ~3.2. To keep the Petri net of Figure 2
simple, we would value the arcs linking processing
transitions to their output places by the required
set-up or transportation times. An efficient analysis
technique is demonstrated using this example in ~4.
3.2 Blocking Phenomena
In the example of ~3.1, it is assumed that there
is sufficient storage provided between machines so
that no machine is blocked when the downstream machine
is busy. We now model a three machine system similar
to that of Figure 1, but with no buffer storage available. For simplicity of exposition, there are two part
types, each having the same processing sequence: Ml+
M2+M3, but possibly different operation times. There
is one pallet for each part type.
To capture the blocking effect, we distinguish
between two types of transitions: one type represents
the processing of a part on a machine for a fixed duration; the other represents the instantaneous departure
of a part from a machine when the next required machine
is free. Transportation follows the part release. Between processing and transportation, waiting may occur.
A Petri net model of this situation is displayed
- 3 -

TTL/UL+M2. Then cart C1 travels to M3, in time
TTM2+M3, to unload the finished, assembled unit,
transport it to the L/UL station, where it is taken off
and a new case is loaded to begin cart l's cycle again;
C2 begins at machine 1 to unload a case and bring it to
machine 3 in time TTMI+M3. Then C2 travels (empty)
to machine 2 to unload a cover and bring it to machine
3 (TTM3+H2 + TTM2+M3). Finally C2 returns to
the first machine to begin its cycle again.
The Petri net model of this system is provided in
Figure 6. Notice that travel times, processing times,
Petri net is obtained. Any feasible marking of five
tokens guarantees a live and safe Petri net.
Notice that a particular machine set-up can start
when transportation begins for the next part to be processed; both activities begin when a part is released
from the machine in question. Hence, both release
transitions and the corresponding successor processing
transitions can be combined into one transition, as
shown in Figure 4. Firing time for each combined
transition is set equal to the processing time plus
the maximum of the appropriate set-up and transportation times. Such reductions in the number of required
transitions appear to generalize for systems with
limited storage capacity.
Max(Sl13 T23) + t13
Hax(Sli, T31) 11 Hax(S12 T12) + t2
Max 2l1 T31) + t2 Max(S 2 T) +2
Max(S23, T23) + e23
Figure 4. Reduced Petri Net Model of Blocking.
3.3 Assembly Processes
Figure 6. Petri Net of the Four-Machine Flexible
Assembly System.
and even loading and unloading times (set-up times, if
the set-up at a machine tool is not automated) are included. In this model, the tokens are continuously
disappearing (into the assembled unit) and then reappearing (as the raw castings for a case and a cover).
Hence this Petri net is not strictly conservative.
Non-conservative Petri nets seem to be specific to
assembly processes. However, for the obvious distributions of 6 or 7 tokens in the initial marking, the
Petri net is safe and live. We have constructed this
model to be decision-free, also. Finally, notice that
we did not explicitly require places to model the L/UL
station.
Consider the flexible assembly system of Figure
5, consisting of three different machining centers
and a load/unload station (L/UL). There are three
part types being machined. Cases (on machine 1) and
covers (on machine 2) meet and match on a one-to-one
basis at machine 3, for additional operations to be
performed on the assembled unit. There are two cart
types: C1 begins by loading a case at the L/UL station
Ml " c
C_
ci l - c
Figure 5. Four-Machine Flexible Assembly System
with Two Cart Types.
and automatically transporting the palletized case to
Ml in time TTL/UL+Ml. Then it travels back to the
L/UL to pick up a cover and bring it to M2 in time
3.4 FCFS Control Rule
All of the previous Petri nets were decision-free:
all tasks were explicitly ordered a priori. In many
situations, however, the ordering of parts on machines
is specified by means of priority rules. The FCFS
rule is often assumed (for example, in product form
queueing networks having exponential servers).
Consider a service station with a buffer consisting of n-l consecutive places. To model the FCFS queue
discipline requires n transitions, where transition i
means "enter place i in the buffer", for i=l,...,n.
The lastCn-th) transition is the service. Time Tk is
required to reach place i, where i=l,...,n and k=l,...,
number of customers. The Petri net is given in Figure
7. There are n-l tokens required for the buffer
places, one token for the server, and tokens for the
customers. Customers are generated according to some
arrival process. Customer tokens can be input when
-4 -

token of buffer i-1
<rL} I~ - ~9 7
input of token of ~ -" ---
customers buffer i Service
output
Figure 7. Petri Net of the FCFS Queue
Discipline for n-l Buffers.
ever the first customer place is free. Transition i
(e[2,...,n]) fires only when:
1) a customer is waiting in the (i-l)st buffer
(hence the tokens are in the input places of
transition i); and
2) the i-th buffer is free (hence its token is also
in the input place of transition i).
Again, the Petri net is safe, conservative, live, and
decision-free.
4. ANALYSIS OF PETRI NET MODELS
The fixed-route FMS presented in ~3.1 has been
modeled equivalently by a set of "linear" state equations in the sense of a (max,+) algebra in [1]. The
main appeal of the algebraic representation lies in the
existence of very efficient algorithms to evaluate
system performance. This is a significant advantage
over time-consuming and expensive simulation, which is
usually required to obtain the same information.
Petri nets have been used to plan a well-designed
simulation. The simulation run consists of letting
tokens flow through the Petri net structure and collecting statistics on the results. For example, a simulation of the FMS described in ~3.1 that is starting with
an empty system, produces the Gantt chart of Figure 8.
fact immediately. However, in more realistic and more
complex situations, this will not be the case. The
duration of the transient period that precedes the
periodical behavior depends both on the initial state
and the lengths of the sub-critical circuits of tasks.
It may be very long.
As an alternative to simulation, the algebraic
approach presented in Cohen et al. [1] is independent
of the length of the transient period and, in addition,
directly calculates the periodical steady state minimum
cycle time.
The translation of a particular Petri net model
into algebraic equations is straight-forward when the
Petri net is safe and decision-free. Each transition
is then characterized by the meeting of a specified set
of tokens, one per input place. For example, in the
FMS example of Figure 2, the transition requiring one
time unit occurs when the machine 1 token meets the
pallet 2 token. All other transitions are similarly
enabled.
The description variables of the algebraic representation can be the dates xj when transition tj
fires. Denoting r-(j) as the set of transitions tk
such that there is a place pi which is an output of
tk and an input of tj, we have
xj > max xk + Tk,
ker-(j)
(4)
Ml P2 P3 P2 P3
M2 PI P2 P3 PI P2 P3
M3 PI P2 Pi P2
2 3 4 5 6 7 8 9 10 12 19
Figure 8. Schedule for the Fixed-Route FMS.
Notice that the system has a periodical behavior, with
a period of 19 time units. The same result is obtained
analytically in Cohen et al. [I]. A set of critical
tasks and resources is also provided as determined by
the critical circuit. The results indicate that:
1) The critical resources are the second machine
and pallet type 2;
2) The bottleneck machine is M2 and is underutilized;
3) The utilization of the bottleneck machine can
be improved only by adding a pallet of type 2;
4) The period (minimum cycle time) is 9.5, which
provides the maximum production rate as the
reciprocal.
In addition, all machine utilizations are provided.
As demonstrated by the simple example in Figure 8,
the simulation gave the periodicity result rapidly, in
where T\ is the duration of transition tk. The variable xj can also be conditioned by the availability
date of one of its input.tokens, as prescribed by the
initial marking. Equations similar to (4) can be
specified for all transitions. These can then be
analyzed via efficient algebraic techniques [1]. If
the Petri net is strongly connected, we can specify a
linear, (max,+), recurrence equation, Y(n)=Y(n-l)A.
The dimension of matrix A is the number of tokens and
Yr(n) is the date when token r reaches a prescribed
place in its circuit for the nth time. The real complexity of a safe, decision-free, strongly connected,
Petri net is the number of its tokens (which remains
constant throughout —see ~1).
Further research is required to investigate performance evaluation algorithms for other classes of
Petri nets, such as the non-conservative ones that
describe assembly processes. In addition, the safeness
property is not guaranteed for a strongly connected,
decision-free Petri net. For such decision-free Petri
nets, Ramamoorthy and Ho [7] suggest a rudimentory
procedure that finds the minimum cycle time by totally
enumerating all circuits. However, no additional
useful information is provided, such as the order of
periodicty or the determination of critical resources
(see [1]).
Another analysis technique for timed Petri nets is
that suggested by Sifakis [10], which captures the evolution of successive markings. In addition to depending on the structure of the Petri net and its firing
rules, it appears that the times when firing occur must
be known. This assumption is not made with the (max,+)
algebraic technique: the firing times are found. The
framework of [10] is more similar to that of vector
addition systems [4].
5. POTENTIALS AND LIMITATIONS OF PETRI NET MODELS TO
ANALYZE CONTROL PROBLEMS OF PRODUCTION SYSTEMS
There appears to be not much of a limit to the
modeling capabilities of Petri nets. However, at present, the decision-free requirement appears to be un
- 5 -

avoidable to use analytical techniques to analyze the
performance of Petri nets. In theory, all sequencing
on machines must be known. In addition, the problems
of optimizing control rules remains unsolved. On the
other hand, it is now possible to efficiently check the
performance of a particular control strategy.
Petri nets appear to be a very general modeling
tool that is useful for representing discrete-event
systems by means of several primitive symbols (places,
transitions, and tokens), which are simply interpreted.
Systematic system investigation is allowed by varying
parameters. Petri nets model a set of events and the
conditions which cause the occurrence of events. This
provides at least a useful design tool to ensure a
well-defined simulation.
Because of the simplicity of the primitives, one
might conjecture the existence of efficient means to
analyze discrete event systems. This expectation is
founded as reported in ~4 for the subclass of safe,
decision-free Petri nets.
Petri net modeling and analysis can provide insight into the real-time behavior of FMSs. Some issues
that can be addressed include the determination of:
i)
ii)
iii)
iv)
v)
vi)
vii)
viii)
optimal buffer size via the knowledge of the
maximum buffer occupation;
optimum pallet distribution;
appropriate priority rules;
material handling system capacity and performance;
critical tasks and resources;
machine utilizations (dynamical, not just the
steady-state mean values);
appropriate input sequence of parts;
operation sequence at each machine tool.
computer control system for FMSs. The same model can
represent both the physical and control systems.
REF ERENC ES
1. Cohen, G., Dubois, Didier, Quadrat, J. P. and
Viot, M., "A Linear-System-Theoretic View of
Discrete-Event Systems", Proceedings of the
22nd IEEE Conference on Decision and Control,
San Antonio TX (December 14-16, 1983).
2. Cuninghame-Green, Raymond, Minimax Algebra,
Springer-Verlag, Berlin (1979).
3. Diaz, Michel, "Modeling and Analysis of Communication and Cooperation Protocols Using Petri
Net Based Models", Computer Networks, Vol. 6,
No. 6, pp. 419-441 (December 1982).
4. Gelenbe, Erol, "Stationary Properties of Timed
Vector Addition Systems", in Deterministic and
Stochastic Scheduling, Dempster et al., editors,
D. Reidel Publishing Company, Dordrecht, Holland,
pp. 223-232 (1982).
5. Ho, Yu Chi and Cao, Xiren, "Peturbation Analysis
and Optimization of Queueing Networks", Journal
of Optimization Theory and Applications (1983).
6. Peterson, James L., Petri Net Theory and the
Modeling of Systems, Prentice-Hall, Inc.,
Englewood Cliffs NJ.
7. Ramamoorthy, C. V. and to, Gary S., "Performance
Evaluation of Asynchronous Concurrent Systems
Using Petri Nets", IEEE Transactions on Software Engineering, Vol. 6, No. 5, pp. 440-449
(September 1980).
8. Ramchandani, Chander, "Analysis of Asynchronous
Concurrent Systems by Timed Petri Nets", Ph.D.
dissertation, Department of Electrical Engineering, MIT, Cambridge MA (1974).
9. Shapiro, R. M. and Saint, H., "A New Approach to
Optimization of Sequencing Decisions", Annual
Review of Automatic Programming, Vol. 6, No. 5,
pp. 257-288 (1970).
10. Sifakis, J., "Use of Petri Nets for Performance
Evaluation", Acta Cybernetica, Vol. 4, No. 2,
pp. 185-202 (1979).
11. Solberg, James J., "Analytical Performance Evaluation of Flexible Manufacturing Systems", Proceedings of the 18th IEEE Conference on Decision
and Control, San Diego CA, pp. 640-644
(December 1979).
12. Stecke, Kathryn E. and Solberg, James J., "Loading
and Control Policies for a Flexible Manufacturing System", International Journal of Production
Research, Vol. 19, No. 5, pp. 481-490 (September-October, 1981).
13. Stecke, Kathryn E. and Solberg, James J., "The
Optimality of Unbalancing Both Workloads and
Machine Group Sizes in Closed Queueing Networks
of Multi-Server Queues", Working Paper No. 322,
Division of Research, Graduate School of Business Administration, The University of Michigan,
Ann Arbor MI (November 1982).
In contrast with the type of information obtained
by queueing networks, Petri nets provide dynamical information, over a finite time horizon, concerning the
evolution of the states of a system.
6. SUMMARY AND FUTURE RESEARCH
A new model has been proposed that can be much
more efficient than simulation, to help the investigation of dynamical, real-time control problems of FMSs.
The state-of-the-art in Petri net modeling capabilities
has been extended. Because of the new application of
Petri nets, new modeling conventions needed to be
developed. In addition, with the equivalence of a
subclass of Petri nets to a linear (max,+) algebraic
representation, the existence of efficient analysis
techniques was noted.
Future research includes further extending the
modeling capabilities, for example, to efficiently
model groups of pooled machines [13], or queue disciplines in addition to FCFS. Other plans include the
determination of systematic rules for translating
Petri nets into the (max,+) equations. Larger classes
of Petri nets that can be expressed in the algebraic
setting should be investigated. Perhaps non-safe, conservative, decision-free Petri nets can be so represented. Other techniques to analyze Petri nets will be
investigated. The complementary nature of Petri nets
and queueing networks shall be explored. Procedures
that derive appropriate (perhaps "optimal") periodic
sequences of parts on machine tools, given FMS priority
rules, will be investigated. The corresponding Petri
net model would be equivalent to a multiclass, deterministic, closed queueing network with finite buffers.
The real-time planning and control issues that were
summarized in ~5.2 will be investigated. Finally,
Petri nets will be used to model the hierarchical
- 6 -