APPROXIMATION METHODS FOR

STOCHASTIC PETRI NETS

by

Hauke J6rg Jungnitz

Rensselaer Polytechnic Institute

Electrical, Computer, and Systems Engineering Department

Troy, New York 12180-3590

May 1992

CIRSSE REPORT #119
(_)Copyright 1992

by

Hauke JSrg Jungnitz

All Rights Reserved

ii
CONTENTS

i.

ACKNOWLEDGEMENT ............................. vii

ABSTRACT .................................... viii

1. Introduction ................................... 1

1.1 Motivation ................................. 1

1.2 Goal of this Research ........................... 5

2. Literature Review ................................ 8

2.1 Introduction ................................ 8

2.2 Jackson Queuing Networks ........................ 8

2.3 Aggregation in Queueing Networks ................... 10

2.3.1 Near Decomposability ...................... 11

2.3.2 Flow Equivalent Aggregation (FEA) .............. 11

2.3.3 Marie's Method .......................... 13

2.3.4 Response Time Preservation ................... 15

2.4 Approaches to Contain the Problem of State Explosion in Generalized

Stochastic Petri Nets ........................... 17

2.4.1 Bounds on the Throughput Vector ............... 17

2.4.2 Efficient Construction of the Tangible State Space ....... 17

2.4.3 Iterative Method for the Solution of Genera/ized Stochastic

Petri Nets ............................. 18

2.5 Approximate Aggregation in GeneraUzed Stochastic Petri Nets .... 19

2.6 Summary ................................. 20

Terminology and Basic Properties for Petri Nets ............... 21

3.1 Introduction ................................ 21

3.2 Terminology ............................... 21

3.3 Subnets .................................. 27

3.4 Petri Net Subclasses and Their Properties ............... 28

3.4.1 State Machines .......................... 29

3.4.2 Marked Graphs .......................... 29

.

iii
3.4.3 Free Choice nets ......................... 32

3.5 Stochastic Petri Nets ........................... 33

3.6 Conclusions ................................ 39

4. Structural Decomposition and Response Time Approximation for Marked

Graphs ...................................... 40

4.1 Introduction ................................ 40

4.2 Single Cut, Aggregated nets, Basic Skeleton and Response Time

Approximation .............................. 41

4.3 Single Input/Single Output (SISO) Cut ................ 43

4.3.1 SISO and Canonical SISO cuts ................. 44

4.3.2 Qualitative Aspects ........................ 45

4.3.3 Quantitative Aspects ....................... 48

4.4 Single Input/Multiple Output (SIMO) Cut ............... 52

4.4.1 Alternative Interpretation of the SIMO cut ........... 59

4.5 Multiple Input/Multiple Output (MIMO) Cut ............. 60

4.6 Multiple Cuts and Response Time Approximation: Hierarchical Decomposition ................................ 65

4.7 Conclusions ................................ 70

5.' Alternative Approximation Methods for Marked Graphs .......... 72

5.1 Introduction ................................ 72

5.2 Flow Equivalent Aggregation. ...................... 72

5.2.1 Qualitative Aspects ........................ 73

5.2.2 Quantitative Aspects ....................... 73

5.2.3 Flow Equivalent Aggregation vs. Response Time Preservation 74

5.3 Marie's Method .............................. 78

5.4 Delay Equivalence by Y. Li and M. Woodside ............. 80

5.4.1 State Dependent Firing Rates .................. 81

5.4.2 State Independent Service Rate ................. 83

5.4.3 Comparison of Response Time Approximation and Delay

Equivalence ............................ 84

5.5 Conclusions ................................ 85

iv
6. Examples for Marked Graph Systems ..................... 86

6.1 Introduction ................................ 86

6.2 Fork/Join Queueing Network ...................... 86

6.2.1 Single SISO Cut A ........................ 86

6.2.2 SIMO/MISO Cut B ........................ 88

6.2.3 Hierarchical Decomposition using RTA ............. 91

6.2.4 Comparison ............................ 92

6.3 Four Task PipeLine ............................ 93

6.3.1 Single SISO Cut B ........................ 93

6.3.2 SISO Cut B, Response Time Approximation .......... 93

6.3.3 SISO Cut B, Flow Equivalent Aggregation ........... 94

6.3.4 SISO Cut B, Marie's Method .................. 95

6.3.5 SISO Cut B, Delay Equivalence ................. 96

6.3.6 Hierarchical Decomposition ................... 97

6.3.7 Comparison ............................ 99

6.4 Kanban System .............. . ............... 99

6.4.1 Response Time Approximation ................. 101

6.4.2 Flow Equivalent Aggregation ......... ......... 101

6.4.3 Marie's Method .......................... 102

6.4.4 Delay Equivalence ........................ 102

6.4.5 Hierarchical Decomposition using RTA ............. 104

6.4.6 Comparison ............................ 104

6.5 Conclusions ................................ 105

7. Macroplace/Macrotransition Nets ....................... 107

7.1 Introduction ................................ 107

7.2 MPMT-nets: Motivation and Definition ................. 107

7.3 Basic qualitative properties of MPMT-nets ............... I14

7.4 Well-formed SISO cuts .......................... 116

7.5 Summary ................................. 117

8. Examples for SISO Cuts in MPMT-nets ................... I18

8.1 Introduction ................................ I18
8.2 Modeling of Transfer Lines with Petri Nets ............... 119

8.2.1 Choong and Gershwin Approximation in Flow Lines ...... 121

8.2.2 Experimental Results: Three Machine Transfer Line ...... 123

8.2.3 Experimental Results: Long Transfer Lines ........... 129

8.3 Uninterpreted Dataflow Graph ...................... 131

8.4 Summary ................................. 137

9. Flow Equivalent Aggregation for SIMO-cuts in MPMT-nets ......... 139

9.1 Introduction ................................ 139

9.2 Well-Formed $IMO MPMT Cut ..................... 139

9.3 Quantitative Aspects ........................... 143

9.4 Example for SIMO-MPMT Cut ..................... 145

9.5 Summary ................................. 148

10. Case Study of a Dual Arm Robotics System for Assembly ......... 149

10.1 Introduction ................................ 149

10.2 Hardware and Software Configuration .................. 150

10.3 Case Study ................................ 151

10.4 Summary .......... , ...................... 154

11. Conclusions ................................... 158

11.1 Discussion ................................. 158

11.2 Outlook .................................. 160

LITERATURE CITED .............................. 162

vi
ACKNOWLEDGMENT

I am thankful to my advisor, Alan Desrochers, for his guidance and help. During

my years at RPI, I had the chance to develop and work on my own ideas. I would

also like to thank my committee members for their suggestions and help during the

preparation of the thesis.

Of the many people at RP! who contributed directly or indirectly, I can only

mention a few: Alessandro Giua patiently read through the entire thesis, pointed

out many inconsistencies and helped with many discussions, Don Lefebvre was of

great help with measurements of the case study. I also want to mention my o_ce

mates who were great companions along the way.

I am deeply indebted to Manuel Silva, who invited me to the University of

Zaragoza, Spain. Every discussion wi_h him produced new ideas and encouragement. Without my stay in Spain, this thesis would not exist in its present form. In

Za.ragoza, I would also like to thank Jos6 Manuel Colom for our many discussion

and Beatriz S_achez for our joint work.

I am thankful to the Center for Intelligent Robotics System for Space Exploration (CIRSSE), who offered me a graduate assistantship under NASA Grant #

NAGW-1333 and IBM who also provided financial support. I would also Like to

acknowledge the Siemens International Scholarship, which helped to finance some

of my travel.

I am thankful to Kishor Trivedi's for providing the SPNP program and G.

Chiola's for providing the GreatSPN software package.

Finally, I would like to thank my parents for the support received throughout.

vii
ABSTRACT

Stochastic Marked Graphs are a concurrent decision free formalism provided with a

powerful synchronization mechanism generalizing conventional Fork Join Queueing

Networks. In some particular cases the analysis of the throughput can be done analytically. Otherwise the analysis suffers from the classical state explosion problem.

Embedded in the divide and conquer paradigm, this thesis introduces approximation techniques for the analysis of stochastic marked graphs and Macroplace/-

Macrotransition-nets (MPMT-nets), a new subclass which is introduced in this thesis. MPMT-nets are a subclass of Petri nets that allow limited choice, concurrency

and sharing of resources. The modeling power of MPMT is much larger than that of

marked graphs, e.g., MPMT-nets can model manufacturing flow lines with unreliable

machines and dataflow graphs where choice and synchronization occur.

The basic idea leads to the notion of a cut to split the original net system into

two subnets. The cuts lead to two aggregated net systems where one of the subnets

is reduced to a single transition. A further reduction leads to a basic skeleton. The

generalization of the idea leads to multiple cuts, where single cuts can be applied

recursively leading to a hierarchical decomposition.

Based on the decomposition, a response time approximation technique for the

performance analysis is introduced. Also, delay equivalence, which has previously

been introduced in the context of marked graphs by Woodside et al., Marie's method

and flow equivalent aggregation are applied to the aggregated net systems.

The experimental results show that response time approximation converges

quickly and shows reasonable accuracy in most cases. The convergence of Marie's

is slower, but the accuracy is generally better. Delay equivalence often fails to

converge, while flow equivalent aggregation can lead to potentially bad results if a

strong dependence of the mean completion time on the interarrival process exists.

viii
CHAPTER 1

Introduction

1.1 Motivation

Manufacturing systems, computer systems and robotics systems cannot be described by differential or difference equations. System changes happen in random

intervals of time, and are therefore stochastic in their nature. These systems are

commonly referred to as discrete event dynamic systems (DEDS). Modeling, control

and the analysis of DEDS represents a big challenge. Robotics systems composed

of multiple arms, a vision system, force/torque sensor and control computer for

example, are discrete event in their operation and have a rather large number of

interacting components. It is the interaction of the subsystems coupled with the

discrete nature of their dynamics which makes the modeling and performance analysis challenging [AJD90a].

In the modeling and analysis of DEDS there is a trade-off between the ability of

how realistically our model is able to represent the actual system (modeling power),

the cost and effort involved in the modeling process (economical considerations) and

the analytical tractability, i.e., the ease of analysis of our model. Ideally we would

like to have a single model, which cart express the following characteristics in one

representation.

• Logical properties

1. Asynchronous operations. The model should be concerned with the independent "internal clocks".

2. Concurrency and parallelism. Several activities can take place at the

same time.
2

°.

3. Conflict. This may occur when two or more processes require the same

resource or a part can take several paths through the system.

4. Synchronic distance. How often can transition A fire before transition B

has to fire.

5. Deadlock. A state can be reached where none of the processes can continue. For example this can happen with the sharing of a resource between two processes, e.g., two robots want to acquire a vision system

simultaneously.

6. Event driven. Since operations can occur concurrently, the order of events

is not necessarily unique.

• Temporal properties such as the duration of activities and timeout.

• Operational properties such as real time scheduling using mathematical or

heuristic models a_ad high level decision making.

Figure 1.1 shows the hierarchy of the modeling process. As we move to the top

of the pyramid, we can increasingly model the desired characteristics of the system.

At the bottom of the modeling hierarchy are product form queuing networks

(PFQNs) which are computationally very easy to solve, but this computational saving has a drawback: classical PFQNs (Jackson QNs, BCMP QNs) cannot model

blocking, finite buffer size, synchronization and control over the dispatching of customers. Therefore, their modeling power is low. Because of their computational

ease, PFQNs are most useful for the initial rough design and analysis of a system.

Petri nets (PNs) allow the modeling of the logical properties of the system.

Depending on the net subclass, polynomial time algorithms e.,dst for the analysis of

liveness, boundedness and deadlock. The incorporation of time leads to generalized

stochastic Petri nets (GSPNs) where transitions can fire in zero time (immediate

transitions) or after an exponentially distributed amount of time (timed transitions).
ease of .,,_ . ___._ cost

analysis f / rro_o_ype_.simulation "_ powermodeling

,t ..... Stochastic Petri Nets

f Product Form Queuing Networks

Figure 1.i: Hierarchical Representation of the Modeling Process

The underlying assumption is that the system is memoryless (Markovian), i.e., the

next state depends only on the current state and not on the history of the previous

states which were visited, or how long the system has been in the current state. The

only continuous probability distribution which satisfies the Markovian property is

the exponential distribution.

:: GSPNs can be interpreted as a generalization of traditional queuing networks (QNs) allowing synchronization, fork, split, choice and timeout constructs

(see [VZL87] for a comparison of the modeling power between QNs and GSPNs).

In order to determine the performance measures, the underlying continuous time

Markov chain (CTMC) is constructed from the teachability graph and the corresponding system of linear equations is solved.

GSPNs can model a system with considerable level of detail. The major drawback for the use of GSPNs for the performance analysis is the problem of state

space ezplosion. Even a moderately sized system can have thousands of states, and

the solution of the CTMC becomes increasingly space and time consuming. Using

more powerful computers or more efficient algorithms would help, but state space

explosion is ezponential, while faster algorithms [JGDgl] or increased memory are

a polynomial improvement at best. Ultimately, it is the problem of state explosion which renders the analysis of complex systems using GSPNs difficult. GSPNs

C'Y PO_;R QDAt.ITY
4

have been used for the analysis of computer systems [Mo182, Beo85], flexible manufacturing systems [AJ88, KDD88, BCFR87, Ccsg0] and manufacturing message

specifications [WJG91]. GSPNs are most useful in the intermediate design state

where various options are being explored, e.g., different buffer sizes, machining or

processor speeds can easily be explored. Once a PN model has been found, it can

also be used as the underlying structure for the simulation model [HS89, BCg0].

Further up in the hierarchy is simulation, one of the most widely used techniques in operations research. Simulation allows an "as good as possible" approach

to the modeling of systems, i.e., almost every imaginable detail of the system in the

model can be captured in the simulation, e.g., the probability distributions for the

processes can be arbitrary. Models of large scale systems tend to be very complex,

so the coding and validation of the model can be very arduous.

The drawback for the high modeling power is the lack of any kind of methodological analysis. Furthermore, in order to obtain small confidence intervals,the

simulation runs tend to be very long and expensive. The resultsof a simulation

run have to be analyzed with caution, because we do not get exact performance

measures, but only a (hopefully)closeestimate.Simulation enjoys a high credibility

and ismost usefulfor the finalstage of the system design for the finetuning of the

system and the evaluation of differentscheduling policies,etc.

Often we are interestedin findingthe optimal allocationof resources. This

involves analyzing the sensitivityof the system with respect to the change of the

parameters we are interestedin. In order to find the gradient at an operating point

we usually use a finitedifferenceapproximation. Therefore, we require two runs:

one with the nominal set of parameters, and a second one where the parameter of

interestis slightlyperturbed. On one hand we want to make the perturbation as

small as possiblein order to get the true gradient. But thisinvolves long run times

in order to get the small confidence intervalswhich are necessary. On the other
5

hand, we want a large increment in the parameter in order to have short run times,

but in general this will not give us the true gradient.

The efficiency of simulation can be increased by perturbation analysis where it

is possible to find the gradient with respect to the change of parameters based on

one long simulation run [HC79, HC83, Sur89]. The parameters can be continuous

(e.g., processor speed) or discrete (e.g., buffer size).

At the top of the hierarchy is building a prototype of the system which is the

most "reliable" way of analyzing the performance of a system, but also the most

expensive. Prototyping is done once the system has been designed and no further

changes are expected.

1.2 Goal of this Research

The major problem for the use of GSPNs is the problem of state space explosion. The goal of this research is to move GSPNs up in the modeling hierarchy

shown in Figure 1.1, so we can use Petri nets for models which previously could only

be analyzed by simulation or heuristics due to the large state space.

In the study of QNs, efficient algorithms have been developed for the approzimate analysis of QNs whose topology (or service rules) locally violates the product

form assumption [LZGS84, Mar79, ABS84]. These QNs are called "almost" PFQNs.

The approximate analysis is done in two steps:

I. In the structural decomposition, the QN is partitioned in such a way that the

topology and routing probabifities can be interpreted as being from a PFQN.

. During the approximate analysis, the system is analyzed either iteratively

(Marie's method, [Mar79], response time preservation [ABS84]),or ina single

step (flow equivalent aggregation [LZGS84]).

In this work, we study the problem of reducing the underlying state space of
the CTMC in order to allow the analysis of large systems.

The basic approach is to partitionthe GSPN by a single cut and substitute

the subnets by simpler constructsresultingin aggregated net systems, thus reducing

the state space. At the same time, the logicalproperties of the unaggregated parts

of the net system are preserved.

We combine features from queueing theory and the results from the structural analysisof Petri nets. We startout from marked graphs (MGs), a concurrent

decision free formalism provided with a powerful synchronization mechanism generalizing conventional QNs. For the structural decomposition of MGs, we make

extensive use of the structuraltheory of MGs. In QNs, the characterizationof the

workload of PFQNs (or "almost" PFQNs) isusually not a problem, while in MGs

this step is not obvious. Here we definethe workload of a server as the maximum

number of customers in itsinput queue. In Petrinets,places represent queues while

timed transitionsrepresent servers. Furthermore, in the decomposition phase, we

-want to preserve some marking propertiesof the aggregated systems.

Once the MG ispartitioned,any of the availableapproximate techniques for

QNs (Marie's method, FEA) or delay equivalence [LW91, WL91] can be used. The

latter is an iterative technique and was first introduced in the context of MGs. In

addition, a new iterative technique, r_sponse time approzimation (RTA), specifically

designed for the case of a single cut is introduced, which shows good convergence

properties. The four methods are discussed and the computational effort and accuracy discussed.

MGs are then generalized to macroplace//macrotransition nets (MPMT-nets),

a new subclass of Petri nets based on the combination of the basic structures of

state machines (SMs) and MGs. The practical modeling with this new subclass of

net systems has some advantages in the field of manufacturing with respect to the

use of the well known subclass of live and bounded free choice net systems, allowing
timeout and the limited sharingof resources.

The modeling power of MPMT nets is much higher than that of state machines

(SMs) or MGs alone. RTA can therefore be seen as a more general approximation

technique.

The work is organized as follows: In Chapter 2 we briefly review some of

the pertinent literature of GSPNs and qNs. In Chapter 3 we establish the Petri

net notation and review some of the important properties of PNs. In Chapter 4

we present the structural decomposition of MGs and a new iterative approximation

technique (RTA) as a hier=rchical decomposition approach Petri nets based on RTA.

In Chapter/5 we present other approximation technique for qNs in the context of

Petri nets and a recently introduced approximation technique for MGs. In Chapter

6, we present numerical results for MGs. In Chapter 7, a new subclass (MPMT-nets)

of Petri nets is introduced, and several numerical examples are given in Chapter 8.

Chapter 9 introduces SIMO cuts for MPMT-nets. In Chapter 10, a dual arm robotics

testbed is examined. Conclusions are given in Chapter 11.
CHAPTER 2

Literature Review

2.1 Introduction

This chapter discusses the pertinent literature of QNs and GSPNs. First in

Section 2.2 we give a brief review about Jackson and Gordon-Newell QNs. In Section

2.3 four general approximation techniques for QNs are briefly reviewed.

We then concentrate on efforts to contain the problem of state explosion in

GSPNs. A very efficient computational approach, where bounds of the throughput can be found in polynomial time based on the net description, is presented in

Section 2.4.1. In Section 2.4.2 the efficient construction of the underlying CTMC

is examined. In Section 2.4.3 an iterative solution method for weakly interacting

subnets is discussed. Finally in Section 2.5 results of an approximation method

based on the combination of QNs and GSPNs is reviewed. The iterative method

for the approximate solution of stochastic marked graphs introduced by Woodside

[LWgl, WLgl] et al. as well as Marie's method will be discussed in detail later in

this work once the structural properties of the decomposition have been defined.

2.2 Jackson Queuing Networks

Jackson [Jac57, Jac63] considered an arbitrary network of queues with N

nodes, each consisting of mi exponential servers with rate _i. The state of the

system is denoted by the vector _ = (kl, k2... kjv), where ki is the number of customers in the i-th service center i and K --- _i=1N ki is the total number of customers

in the system. The outside arrival of customers to the system is modeled by a Poisson process. An example of an open Jackson queueing network is shown in Figure

2.1.
Let _ be the outside arrival rate of customers to the QN. The routing of

customers through the QN is modeledasa randomwalk through the servicecenters.

The customersleavethe QN with probability one after a finite time. The routing is

described by the matrix R = r(i,j),i = 0... N, j = 1 ...N + 1.

r(0, j) is the probability that center j will be first on a routing,

r(i, N + 1) is the probability that if center i is l th on a routing then it is the

last one,

r(i,j) is the probability that if center i is Ith on a routing, then there is an

(l + 1) th element and it is center j.

The matrix R defines the random walk of the customer through the system.

For the sake of simplicity, let mi = 1, i = 1... N. The traffic flow equations (flow

into a service center = flow out of a service center) are given by:

N

T, = Ar(0, 1)+ __r(j,l)T_ (2.1)

j=l

where T_ is the total throughput of costumers at service center I. Jackson proved

that the steady state solution p(k) is given by:

p(k,, ks,.., k,v)= p,v(k,v) (2.2)

where pi(ki) is the solution to the classical M/M/m queueing system, i.e., the probability of finding ki costumers in the queue at service station i is.

p,(ki) = Cip_' (2.3)

Ci is a normalizing constant chosen such that _=oPi(a) = 1, pi = Ti/_ti. If r(i, N+

1) = 0 and _ = 0 no outside arrivals are permitted and the number of customers

in the system is constant. Such a queuing network is -known as a Gordon-Newell

queuing network [GN67]. The structural equivalent of Gordon-NewelI QNs in Petri
10

departure _ node j /

/ _u'rival

Figure 2.1: Example of Jackson Queuing Network

• A  ̧

nets are state machines. The class of PFQNs was extended by the work of Baskett,

Chandy, Muntz and Palacios [BCMP75]. The BCMP QN allows several classes

of customers in the QN and different scheduling disciplines. The BCMP model

has been expanded to include batch arrival and batch service in some special cases

[HPTD90, HTg0].

' " As soon as synchronization, limited buffer size, Or the sharing of resources is

present, a product form no longer exists. If only a "few" service centers violate the

product form assumption, we loosely say the QN has "almost" product form.

2.3 Aggregation in Queueing Networks

All of the methods presented in the following are concerned with finding the

equivalent service rate of the subnetworks to be aggregated. The service rate can

be state dependent (i.e., dependent on the number of customers in the subnetwork)

or state independent. See Table 2.1 for a comparison.

The basic approach is to set the conditional throughput (obtained under

controlled environment) to the service rate of the subnetwork, which in turn is

substituted back in the original system.
11

[.Method 11A rrival Process Service Rate Solution Method

Flow Equivalent short circuit, fixed state

Aggre.gation number of customers dependent single step

Response Time state independent state

Preservation Poisson process independent iterative

Marie's Method state dependent state

dependent iterative

Table 2.1: Comparison of Approximate Methods for "Almost" PFQNs

2.3.1 Near Decomposability

If the order of the transition probabilities _0p01 and/_1p10 between Ro and R1

in Figure 2.2.a is much greater than the order of magnitude between the transitions

of R2, then the QN formed by R0 and RI will obtain local equilibrium before any

interaction with R2 can occur [Cou75]. A system with this property is known as

nearly decomposable. The network can (approximately) be analyzed the following

way: Ro and RI are analyzed separately. We are interested in the flow _/,12(n_) of

customers out of the subsystem, where nl is the number of customers in Ro and

t/1. An aggregate model can be constructed which is shown in Figure 2.2.b. This

approach was applied to GSPNs in the work of [BT86].

2.3.2 Flow Equivalent Aggregation (FEA)

The basic approach is to replace a general server or subnetwork of queues by a

flow equivalent service center (FESC) [Bra85, LZGS84]. An arriving customer sees

the FESC as a black box whose behavior is completely characterized by a listing

of the residence time (the inverse of the throughput) as a function of the possible

customer population. In order to determine the state dependent service rates, the

subsystem is studied offline, i.e., without any interaction with the environment. In

general, a FESC can only match the first moment of the probability distribution,
12

,,0, , ,J

I °' f

(a) System (b) Aggregated System

Figure 2.2: Nearly Decomposable System

as the higher moments are toe cumbersome to obtain. Three steps for constructing

an FESC can be determined [CS78]:

: 1. Determine a subsystem which can be analyzed by FESCs.

2. Analyze the subsystem by maintaining the number of customers constant.

This is done by shorting out (Norton's theorem) all other parts of the network

and varying the number of customers up to the maximum allowed in the

subsystem.

, The aggegated network ANis constructed as a server with a queue-dependent

service rate. Let Xsw(k) be the conditional throughput of the subnetwork

(SW) when k customers are present, and _Alv(k) the (state dependent) service

rate of AN. The approximation is done through the following equality, under

the assumption of exponential service time:

Xsw(k) : _,A,v(k) (2.4)

Figure 2.3 illustrates the concept from an example of computer systems [LZGS84].

Here the set of queues surrounded by the dashed box would be analyzed in isolation
13

--_-...t..r_ I _ i

!

Figure 2.3: Concept of Flow Equivalent Server

and substituted by a single queue with a state dependent service time.

In FEA we assume that the behavior of the subnet is independent of the

arrival process and depends only on the number of customers in the system, i.e., the

behavior is completely independent of the environment. This condition is violated

in several cases (e.g., if internal loops are present). Thus in general, the mean

completion time (MCT) depends on the interarrival time of customers. FEA does

not always lead to an approximate solution, as the following property shows.

'" Property 2.3.1 (Flow Equivalent Aggregation IV'an78]) For the particular

......... " case of product form QNs, flow equivalent aggregation leads to exact results.

This approach does not involve any iterative process and is computationally

efficient. As we do not iterate there exists no convergence problem. Courtois [Cou77]

showed that the approximation is good when the number of state changes within the

subsystem between interactions with the environment is reasonably large. Chandy

et al. [CS78] observed that if the actual coefficient of variation of the service time is

much larger than the coefficient of variation of the exponential distribution, significant error can be introduced. FEA techniques have been introduced in the context

of SPNs [JD91a, JD91b] and are presented in Section 5.2.

2.3.3 Marie's Method

Marie's method provides an alternative way to derive the state dependent

service rate of subsystems [Mar79] in an iterative fashion. While in FEA the number
14

of customers in the system is held constant, and in RTP the arrival rate is held

constant, in Marie's method the arrival and service rate is assumed to be state

dependent and must be found in an iterative manner. While the network may

possess general service times, blocking and fork/join operations, the QN must be

decomposable in the sense that the partitioned subnetworks can be interpreted as

servers in a PFQN (i.e., the QN is in "almost" product form). To this end, the QN

is partitioned into M subsystems according to the following definition:

Definition 2.3.1 (Product Form Decomposition) [BD90]

form QN is said to be decomposable into product form if:

A non product

1. The transitions between subsystems are single transitions, e.g., bulk service or

arrival between subnetworks is not allowed.

2. The behavior of the subnetwork depends only on its internal state, e.g., the

service rate cannot depend on the queue length of another" subnetwork.

8. The input/output behavior o/a customer is independent of routing decisions

taken during its stay in the subsystem, i.e., the visit ratio is unique.

4. All fork/join operations happen within the subsystem.

After the partitioning, each subsystem is iteratively analyzed in isolation under

a state dependent Poisson arrival process. As with many iterative methods, the

uniqueness of the solution can not be proven although numerical experience has

shown that a unique fixed point does indeed exist, although convergence sometimes

presents a problem [BD90].

In [BDg0], an introduction and comparison between Marie's method and FEA

is given. The authors conclude that the results obtained using Marie's method are

usually closer to the actual solution than those obtained with FEA, especially when

large coefficients of variation are encountered. In terms of computational effort,
15

k

Marie's method seems to be more efficient for large values of N, while FEA is more

efficient for small values of N.

A detailed discussion of the numerical aspects of Marie's method and its application to GSPNs is presented in Section 5.3.

2.3.4 Response Time Preservation

In response time preservation (RTP) [ABS84], the QN is first decomposed

according to the rules in definition 2.3.1. In the stochastic phase, we replicate the

response time of a general server G with first come, first served (FCFS) discipline

by an exponential server as shown in Figure 2.4. Here the assumption for the

analysis phase is that the complement of the general server (shown in the dashed

box in Figure 2.4.a) generates a Poisson arrival rate p of customers. The isolated

subsystem shown at the bottom of Figure 2.4.a is the classical M/G/1 network of

two queues: a single exponential server of rate p and a complex server with general

service time G. Let s be the service time, CV be the coefficient of variation and X be

the throughput of the general server (which could also be formed by a subnetwork).

By the PoUazcek-Khinchin formula [Kle75], the response time for an open M/G/1

queue is given by:

(1 + CV2)s . U

RTa = s + 2(i - U) (2.5)

where U = X's is the server utilization. During the aggregation phase RTa is

replicated by the response time RT' of the isolated exponential server as shown in

Figure 2.4.b.

RTa(l_) = RT'(p) (2.6)

RT' for an open M/M/1 with service time s' is given by:

8 t

RT' = 1 - Xs' (2.7)
16

(a) OriginalModel (b) Transformed Model

,_comp|emenf, Of _ .]comp|ement Of [._

| '-_._1 ! "_'°"°°'_"]

FCFS FCFS

_t R' = Ro ¢r

===o.

M/G/I M/_cf/1

(c) isolated subsystem (d) isolated equivalent server

Figure 2.4: RTP for FCFS Server with General Service Time

Solving equation (2.5) and (2.7) for the unknown service time 8' yields

s' = RTa

+ XRTc (2.s)

In the last step the exponential server is substituted back into the original system to

yield the transformed model which is now in product form. Ideally we select/_ such

that the M(i_)/G/1 queue has the same response time as the system in Figure 2.4.d.

As we do not know the throughput a pr/om', we also cannot find the correct Poisson

arrival at the beginning. An iterative process is therefore concerned with finding/_.

Note that in RTP, the coefficient of variation of the service time is required. RTP

yields good results for moderate coefficients of variations (CV < 5) of the customer

interarrival time [ABS84].

Iterative methods are especially suitable when the interaction of the subnet

with the environment is strong. The drawback is that convergence might eventually

present a problem.
17

2.4 Approaches to Contain the Problem of State Explosion in Generalized Stochastic Petri Nets

2.4.1 Bounds on the Throughput Vector

Whenever possible it is desirable to base the analysis of a PN on algorithms

which are of polynomial complexity on the net structure rather than on the reachability graph (whose construction is of exponential complexity). J. Campos et al. use

a linear program based on the incidence matrix to find upper and lower bounds for

the throughput of MGs [CCCS92]. These bounds are tight, i.e., there exist probability distributions which will reach the bounds. The results have been generalized

to Petri nets with a unique repetitive firing count vector [CCS91a] and free choice

nets [CCS91b, Cam91]. Some of the results are presented in Section 3.4.2.

2.4.2 Efficient Construction of the Tangible State Space

• Tangible markings correspond to states where the system spends some amount

of time, while vanishing states often correspond to logical states and represent some

intermediate decision process. Typically during the construction of the reachability

graph, quite a few number of vanishing markings are encountered [BCR87]. In the

solution of GSPNs we are more constrained by memory than time (at least when

using the software package SPNP [DBCT85]), so much could be gained by using a

technique which avoids the construction of the entire state space, and would reduce

the number of vanishing states which have to be considered when reducing the

CTMC to the set of tangible markings.

In [BCFR87] G. Balbo et al. examine the problem of the efficient construction

of the tangible reachability graph. The reduction is done at a structural level,

partitioning the GSPN into confusion free subnets. The reachability graph of each

subnet is generated and the set of tangible states can be found.
18

2.4.3 Iterative Method for the Solution of Generalized Stochastic Petri

Nets

In [CTglb, CTgla] Gianfranco Ciardo et al., propose an iterative (approximate) method for the solution of GSPN models. They identify several Petrl net

constructs which interact weakly. The solution of the GSPN is obtained by iteratively solving the subnets. In addition to tight synchronization (parbegin-parend),

the following constructs were identified:

• Processor-Sharing: In this construct, two disconnected subnets share an

implicit resource, i.e., a resource which is not explicitly represented by a place.

Now the firing rates of two subnets are mutually dependent on each other

depending on the amount of resources the other subnet has already used.

• One-way condition testing: Figure 2.5 shows a GSPN with the one way

condition testing. Transition tt is enabled only if place px is marked, but

its firing does not remove a token from pt. As Subnet SN2 can be solved in

isolation, and the results are going to be exact. In order to solve for the subnet

SN2, two methods have been proposed:

1. Rarefaction: The argument here is that the absence of the marking of Pz

can only slow down transition tz. The equivalent firing rate for tx can

then be computed as:

A,_,w tl = A_dp{pl is marked}

2. Compression: Here the idea is to compress the behavior of subnet SN1

into a small subnet SNa. Now SN_ and SNa can be combined for the

analysis of SN2. The analysis is going to be exact if the time in which

Px is m_rked is exponentially distributed.
19

Figure 2.5:

\ /

\ / sly,

,

/ \

One Way Condition Testing in a Petri net

[-

!

E

r- -1

)

Figure 2.6: Producer and Consumer

* Producer and Consumer

The construct is shown in Figure 2.6. This construct represents a synchronization between the two processes of net SNI and SN2.

2.5 Approximate Aggregation in Generalized Stochastic Petri Nets

G. Balbo et al. combined QNs with GSPNs for the computationally efficient

analysis of complex systems [BBG86, BBG88]. They combine features from QNs

and GSPNs for an efficient analysis. In [BBG86] they start from a GSPN model.

They then identify subnets which allow for a product form solution, and find flow

equivalents for these subnets. These subnets are then substituted into a high level

GSPN. This allows for a reduction of the state space.

The authors use a hybrid modeling approach. Parts of the system are modeled

by QNs (either directly in QN notation or simply by state machines), while other

parts are modeled by GSPNs. If the QN has a product form, then the flow equivalent

server can be found analytically, by solving the PFQN. If the QN does not have a
2O

product form, then the QN has to be solved (for example by means of a GSPN),

and a flow equivalent server constructed. In this case the flow equivalent server has

the form of a timed transition with a marking dependent firing rate.

In both papers, Balbo et al. use QNs as the underlying model, and only use

GSPNs whenever necessary, to represent parts which cannot be represented by QNs.

In the proposed work, we want to use GSPNs as the underlying model and only use

the techniques adapted from QNs for the analysis, rather than QNs themselves.

2.6 Summary

In this chapter we have briefly reviewed some of the relevant literature for

QNs. Of special interest are FEA, RTP and Marie's method as they are well known

methods for the approximate analysis of QNs. Later in this work, we will use these

techniques to devise efficient approximation techniques for MGs.

An approximation method for MGs by Li et al. will be reviewed once the

structural decomposition of MGs has been defined.
CHAPTER 3

Terminology and Basic Properties for Petri Nets

3.1 Introduction

In thissectionthe basic definitionsfor Petrinets are introduced. Itisassumed

that the reader isfamiliarwith the basic concepts of Petri nets. See [Pet81, Mur89,

Si185] for an introduction.

3.2 Terminology

Definition 3.2.1 (Petri net) A Petri net structure is a bipartite directed graph

represented by a quadruple A/" = (P, T, Pre, Post) where,

P=

T = {tl,...,t,_}

Pre : P x T _-* 1N

Post : T x P _ 2V

isafiniteseto/places,n = IPI

is a finite set of transitionsm = ITI

is an input f'anction that defines the set of directed

arcs from P to T

is an output function that defines the set of directed

arcs from T to P

;_V is the set of nonnegative integers. P [q T = 0, P tO T _ O.

Here, Pre and Post are linear incidence functions representing the input and

output arcs respectively.

Alternatively, a graph-based perspective of the net structure is given by jV" =

(P, T, F, W) where F is a flow relation, f C (P x T)U(T x P), and W is a weighting

function on F. If the net is ordinary (all weights are 1), W can be removed (i.e., an

ordinary net A/" can be defined as A/" = (P, T, F)). Here we consider only ordinary

nets.

21
22

Definition 3.2.2 (Incidence Matrix) The incidence matrix of the net structure

A/" is the n x m matrix C, where C = Post - Pre. Post, Pre and C represent

matrices, while Post(ti), Pre(ti) and C(ti) represent the respective column vectors

corresponding to transition ti, while l(pi) represents the row vector of pi in C.

Definition 3.2.3 (Marking) A marked Petri net (Af, Mo), is a net provided with

an initial marking Mo. M(p) refers to the number of tokens residing in p.

In this thesis net refers to the structure, while net system refers to the structure

plus some initial marking.

Definition 3.2.4 (Firing of Transitions) Transition t is firable (enabled} at

marking M, if M > Pre(t). If the firing oft leads to M' (i.e., M[t)M'} then

M'= M + Post(t)- Pre(t) = M + C(t) (3.1)

Equation (3.I} is referred to as the linear state equation. Assuming a" =

tixti2...ti, is a sequence of transitions firable from 114o (i.e., Mo[_r)M}, then M =

Mo + C. _, where _ is the m x 1 firing count vector (i.e., the firing order is lost).

If _ is a vector, then _(j) is the scalar representing the number of firings oft i in or.

The pre-set and post-set of a transition and place are defined as follows:

Definition 3.2.5 (pre-set, post-set)

"t = {plPre(p, t) > 1} = pre-set of t, i.e., the set of input places of t

t" = {plPost(t,p) > 1} = post-set oft, i.e., the set of output places oft

"p = {tlPre(p, t) > 1} = pre-set of p, i.e., the set of input transitions of p

p" = {tlPost(t,p) > 1} = post-set of p, i.e., the set of output transitions of p

Definition 3.2.6 (reachability set) M,, is said to be reachable from the initial

marking iff there ezists a firing sequence a that transforms Mo into M,,. The reachability set R( N, Mo) is the set of markings which are reachable from the initial marking Mo. A marking M is potentially reachable iff 3._ > 0 9 M = Mo + C . ._ > 0
23

Definition 3.2.7 (home state [Camg0]) A state M is a home state iff VM' E

R(N, Mo), M E R(N, M'). Home states form a closed (i.e., mutually reachable)

set.

Later we will see, that the presence of home states leads to ergodic systems.

Definition 3.2.8 (Marking Bound) Let (.AI",Mo) be a net system

1. The bound of a place p E P is

B(p)--max{M'(p)lM'_ R(X, Mo)} (3.2)

where M'(p) refers to the number of tokens in place p.

_. The structural bound of a given place p of A[ is given by the following linear

program:

def

, SB(p) = mize M(p)

" subject to M = Mo + C. _ > 0

_>0

(LPP1)

A net A/" is structurally bounded iffVMo the net is bounded.

i.e., all net systems constructed from A[ are bounded.

Definition 3.2.9 (persistent place) A place is persistent iff IP'] = 1

Once a persistent place is marked, the routing of the token out of the place is

deterministic.

Definition 3.2.10 (Liveness) A transition t E T in <N, Mo) is live if

VM E R(N, Mo) : 3M' E R(N,M) 9 M' >_ Pre(t)

(N, Mo) is live iff all transitions are live.
24

ii.

F

X_xE

F

Is

L.__

(a) Petri net system (b) Reachability graph

(Marked places are

indlv.ated by letters)

Figure 3.1: Ordinary Petri Net System and its Reachability Graph

Definition 3.2.11 (Invarlants [Cam90)) A T-invariant (or consistent component) is an m-vector X : T _--_SV such that C.X = 0 and X _ O. A P-invariant (or

conservative component) is a n-vector Y : P _ _V such that yT. C = 0 and Y _ O.

The support of a T-invariant (P-invariant) denoted by [[X[[ (][y[[), is the set of

tra_Uio._ (place#suchthat IlXll= {t _ TIX(t) > O}O[YII= {P_ PIY_) > 0}).

A (t> or T) invariant I is:

1. Minimal iff there ezists no other invariant I' such that III'll c IlIll.

,_. Canonical iff the greatest common divisor is I.

3. Elementary iff it is minimal and canonical.

The nonzero solution to C. X = 0 (yT. C = 0) is also called the T-semifiow

(P-semiflow).

A firing count vector which leads back to the original marking is a T-invar]ant

(but not necessarily vice versa). A net is consistent iff all transitions are covered

by T-invariants, i.e., 3 a T-invariant X 3 X _> 11 (11 is a vector of appropriate size

whose entries are all one). In the support of a P-invariant, the weighted sum of

tokens over a set of places is constant for any marking.
25

Figure 3.1 shows an example of a simple Petri net. For the given initial marking, there are five possible states (all states are home states). The incidence matrix

is given by:

C .._

1

-1

t2 t3 t4 ts

-1 0 0 1

1 0 --1 0

0 1 -1 0 1

0 -I 1 --1 --I

0 0 0 1 --1

A

B

D

E

F

Solving for the invariants yields two minimal P-invariants:

(3.3)

Y1T=[1 1 0 0 1], Y2T=[0 0 1 1 1]

Two minimaI T-invariants exist:

x_=[1 1 1 o 07, x[=[o 1 2 1 1]_"

Consistency and boundedness do not guarantee other "nice" properties such as

the existence of home states or even liveness. Figure 3.2 shows the example of

a structurally live and structurally bounded Petri net system without home states

and its reachability graph. Depending on whether tl or t2 are fired first, the resulting

states are disjoint and form dosed sets. The net has 3 minimal T-invariants:

xf=[z1111111111_, xf =[2o112o2o22] _', xf = [oollo._o2o:]_"

For the given initial marking, only X1r leads to a feasible firing sequence, i.e., 3cr 3

= X_. In general, the existence of home states depends on the initial marking!

Figure 3.3 shows a consistent, structurally live and bounded Petri net, which

has an interesting property: By increasing the initial marking (e.g., mo(ps) = 1),

the net system can deadlock.
26

1

(

O 5--

9

A

2

"--8

(a) Live and Bounded Petri Net System

10 9 9

Figure 3.2:

(b) and its Reachability Graph

Live and Structurally Bounded Petri Net System Without Home States
Figure 3.3:

3.3 Subnets

Pl

Structurally Live, Consistent and Bounded Petri Net System

27

Definition 3.3.1 (Single Cut) A single cut _ traced through a set of interface

places Q splits a net jV" = (P, T, F) into two subnets SN, = (Pi, T_, F_) i = 1, 2,

where

• T uT2=T, TlnT =O

• 1:'1 U P_ = 1:', 1:'1fl P2 = Q { the interface}

• Fi=Fn((PixTi)t.j(TixPi))

• Q = {TI" u° T1} (1 {T2" u° T2} defining the interface between SN1 and SN2.

In other words, the subnet SNi is characterized by T/ because Pi =°T/U T/'. The

complement of SN1 is SN2 and vice versa. Figure 3.4 shows a single cut through a

MG system and the corresponding subnets. The interface places are given by places

A and M.

Definition 3.3.2 (Projection) Let H be a Petri net and SNi be a subnet of X.

Let _ be a marking vector of H.. bIio is the projection oft on SNi such that:

vp e,, M (p) = (3.4)
28

c.,t

I

',4

1 6

B I

$ I0

!

(a) Sample Petri Net N

A A

S E [0

(b) Subnet SN1 (c) Subnet SN_

Figure 3.4: Example for Single Cut Generating two Subnets

3.4 Petri Net Subclasses and Their Properties

In this section we introduce three well known subclasses of Petri nets (state

machines, marked graphs and free choice nets).

Let us first introduce a well known property from graph theory.

Definition 3.4.1 (strongly connected [Mar71]) A directed graph is said to be

strongly connected iff a directed path exists between every pair of vertices.

Therefore, a Petri net is strongly connected iff a directed path exists between any

pair of places and transitions.
29

3.4.1 State Machines

Definition 3.4.2 (State Machine) A state machine (SM) is a Petri net such that

Vte T l°tl= x and It°I= I (3.5)

The following properties for state machines hold [SV90]:

Theorem 3.4.1 (State Machine)

i) SMs are structurally bounded and Y = 11.

ii) A SM is live iff J_f is strongly connected and _=i _[o(i) > I.

From a structural point of view, closed monoclass PFQNs (Gordon-NeweLl QNs)

can be represented by strongly connected SMs. SMs allow choices but cannot model

synchronization.

3.4.2 Marked Graphs

Definition 3.4.3 (Marked Graphs) A marked graph (MG} is an ordinary net

such that any place has one input and one output transition.

vp e P I'pl= l=d Ip'l= 1 (3.6)

MGs allow the modeling of concurrency and synchronization but not of decisions.

From the perspective of Petri nets, the structure of monoclass Fork/Join Queueing Networks (QNs) with Buffers (FJQN/B) [DLT90] is represented by strongly

connected MGs [DLT90].

For MGs, the properties stated in the following theorems can be established

using polynomial time algorithms:

Theorem 3.4.2 [Mur89] Let N', be a MG:

i) (jV', Mo) is live iff all circuits (P-in_'ariants) are marked.
30

ii} .IV"is structurally bounded (i.e., bounded for any Mo) iff it is strongly connected.

Corollary 3.4.1 MGs are structurally live

Corollary 3.4.2 [Cam90] The liveness of a MG can be checked by the absence of

unmarked P-invariants.

_Y _ 0 9 yT . C = O, yr. Mo = O, (3.r)

where Y _ means Y > 0 and Y # O.

Theorem 3.4.3 [Mur77] Let (Af, Mo) be a live MG system. The three following

statements are equivalent:

i} M is reachable from Mo (i.e., 3a such that M0[a)M).

iO M is an integer solution of M = Mo + C . _ > O, _ > O.

ii O M is an integer solution of yr. M = yr. 3Io for any P-invariant Y (i.e.,

3Y >_O,yr . c = o).

In MGs, all states (in particular Mo) are home states.

Corollary 3.4.3 Let (.N',Mo) be a live MG system, then Vp E P: SB(p) = B(p).

i.e., the structural and marking bound are the same.

Corollary 3.4.4 In MGs, the marking bound is given by the minimum number of

tokens in a directed circuit containing p.

Stating from a place p, a directed circuit in a Petri net is obtained by traversing

along the arcs and eventually returning to p. In MGs, the places in a directed circuit

are P-invariants.

Stochastic MGs are obtained by associating time to transitions, i.e., a transition fires after it has been enabled for some time. Tight insensitive (i.e., for any

probability distribution) cycle time lower bounds are known for stochastic MGs

[cccs89].

OF rv_,.,_r_'uQOALD_
31

Theorem 3.4.4 [CCCS92] The minimum mean interfiring time 6.e., cycle time)

for a live and strongly connected stochastic MG system can be obtained by solving

the following linear programming problem:

F '_i" = mazimize yr. Pre. _ w.r.t. Y

subject to yT.C=O

(LPP2)

yT.Mo = 1

Y>_O

where i is the vector of the mean service times of the transitions. Moreover, there

ezist probability density functions for which the bound can be reached (tightness). In

the particular case of deterministic, timing the bound is reached.

According to the previous result, a lower bound for the mean interfiring time of

a live and bounded MG system can be computed in polynomial time solving the linear

programming problem (LPP2). From the theory of LPP [NRKT89], it is well known,

that optimal solutions appear at the eztremalfeasible solutions. In (LPP2), feasible

solutions are P-invariants (i.e., Y > O, yT. C = 0), and the extremal solutions

are the minimal P-invariaats. Moreover, minimal P-invariants define elementary

directed circuits of the net (Theorem 3.4.3), while the constraint yT. M0 = 1 is

just a normalization. Therefore, in order to deal with the interpretation of the

computation in (LPP2) it is enough to observe that yr. Pre. flY T. Mo is nothing

more but the sum of service times associated with the transitions belonging to the

elementary circuit defined by the minimal P-invariant Y, divided by the number of

tokens in that circuit. This value is just the mean interfiring time of any transition

of the circuit if it is assumed to work in isolation. Therefore, (LPP2) computes

the mean interfiring time of the slowest circuit considered in isolation. In other

words, (LPP2) only gives a lower bound, because it disregards the interaction with

other circuits (i.e., it disregards the waiting times due to the synchronization among
32

circuits). Later in this work wewill usethe theory of bounds to find suitable initial

conditions for ResponseTime Approximation (RTA).

As a final remark, F'_i'_ (in LPP2) is finite iff there exist no unmarked Psemiflows (i.e., directed circuits). If F _i'` is unbounded, then a deadlock (thus

non liveness) is detected. Because the bound given by (LPP2) is tight, liveness,

deadlock-freeness and the absence of unmarked circuits for bounded MG systems

are equivalent conditions.

Theorem 3.4.2 states that liveness and boundedness can be established on the

net structure and initial marking. Theorem 3.4.3 states that every integer solution

(e.g., obtained by solving a linear system of equations) is indeed a reachable state,

while LPP1 (Definition 3.2.8) allows the computation of the marking bound in

polynomial time [Kar84].

State Machines and Marked Graphs are duaI net subclasses (i.e., by exchanging

places with transitions, the structure of MGs is obtained from the structure of SMs

and vice versa). The reverse of a net is obtained by reversing the flow relation (i.e.,

the arcs). The reverse of a MG (SM) is a MG (SM), in other words, MGs and SMs

are serf-reverse net subclasses. Therefore the reverse-dual of a MG (SM) is a SM

(MG).

3.4.3 Free Choice nets

Free choice nets (FC-nets) are a well known subclass of Petri nets which can

model sequence, choice and concurrency. In FC-nets, choices and synchronization

do not directly interfere with each other, i.e., they cannot coincide on the same

transition. More formally, a FC-net is an ordinary net such that if two transitions

have a common input place, this is the only input place of both transitions.
33

Definition 3.4.4 (free choice nets [Hac72]) Free choice nets are ordinary Petri

nets such that

vp e P: Ip°l> i {p}

The following theorem can be used to determine whether a given structurally

bounded FC-aet is structurally llve.

Theorem 3.4.5 [CCS91b] Let C be the incidence matriz of the strongly connected

structurally bounded FC-net Af. Then the net A f is structurally live iff rank(C) =

rn - 1 - (a - n), where m -- ITI, n -- IPI and a is the total number of input arcs to

the transitions.

Theorem 3.4.6 [ES90b] Let {A/',M0) be a live and bounded FC net, then

Vp E P : B(p) = SB(p)

Similarly to MGs, we can find sufficient conditions for the liveness and botmdedness

of FC nets based on the net structure with polynomial time algorithms.

3.5 Stochastic Petri Nets

In order to use Petri nets for the performance analysis of systems, the notion

of time has to be introduced. There are potentially two ways to incorporate time

into a Petri net:

i) By associating time to places, i.e., places have to be marked for some time

before the tokens can be removed [Ram74, WDF85],

ii) or by associating time to transitions. In the literature, two different firing

rules have been defined:

(a) In two stage firing, the transition absorbs the tokens and releases them

after some time [Zub85],
34

(b) In the one stage firing rule, transitions fire after being enabled for some

time, i.e., the firing is atomic and identical to the usual firing rule [Mo182,

RP84].

By associating time to transitions, Petri net models directly represent synchronized

QNs [Cam90], where places represent queues and transitions represent service stations or fork/join operations.

In any of the two models, the conflict resolution has to be addressed. In the two

stage firing of transitions, the resolution of conflict is predetermined either deterministically or stochastically by associating a routing probability to the transitions in

conflict. In the atomic firing, conflict is usually resolved by race policy, i.e., the transition which samples the minimum service time fires first. If other conflict resolutions

are used (e.g., age memory) the models become increasingly complex [AMBC+89].

Stochastic Petri nets (SPNs) with atomic firing can model pre-emption, while this

is not possible for SPNs with the two stage firing rule. Due to their larger modeling

power, in the present work we adopt SPNs with time associated to transitions and

atomic firing rule.

We assume that the delay associated with transition ti is a nonnegative continuous random variable Xi with the exponential distribution function.

fx,(z) = Pr[Z, < z] = 1- exp(-A, z) (3.8)

i.e., the probability density function (pdf) is fx, = Ai exp(-Aiz).

The average delay is given by:

s_ = /5[1 - Fx,(z)]dz - /5exp(-1_z)dz - _ (3.9)

_i is called the firing rate of ti.

The exponential distribution is the only continuous time probability distribution which has the memoryless (Markovian) property,

P{X > • +_lX > a} = p{x > z} (3.10)
35

It is possible to show [Mo182], that the reachability graph of a bounded SPN

with exponential firing distribution is isomorphic to a CTMC.

Activities which do not require any amount of time are often modeled by logical

states in the sequence of events and can be modeled by using immediate transitions.

In the graphical representation, immediate transitions are drawn as thin black bars,

while timed transitions are drawn as thick white bars. The probability that the

immediate transition tk from the enabled choice set S(M) fires is:

P{tk} = rk (3.11)

Z]i:t,_S(M)ri

where ri E _V+ is the probability rate of ti. Subsequently we have two types of

markings:

A Vanishing marking is a marking where an immediate transition is enabled.

The GSPN leaves that state immediately. If there are no trapping loops consisting only of vanishing markings, the probability of finding the GSPN in that

marking is zero. Vanishing markings occur frequently in the execution of the

GSPN, and are often associated with logical states [BCR87]. For example,

after a task is completed, a vision system will not remain idle if another task

is waiting (it will leave the idle state immediately and become busy). In the

construction of the CTMC the vanishing markings have to be eliminated.

o A Tangible marking is a marking where only timed transitions are enabled.

The GSPN has a nonzero probability of being in that state. These states are

associated with states where some sort of non-zero length activity takes place.

A typical example would be the downloading of an image into the memory of

the computer.

An important performance measure is the visit ratio of transitions. It can be

defined as the normalized (with respect to a transition) throughput.
36

Definition 3.5.1 (visit ratio) Let ,_' be the vector of throughputs in steady state

and Xj its j-th entry (i.e., the throughput of tj) of the net system (A/', Mo) • The

vector of visit ratios v"t_) (normalized for tj} is given by

¢"= !_ (3.12)

x,

If the conflicts in FC nets are modeled by immediate transitions, the visit ratios can

be computed based on the net structure [Cam90]. It is obvious that _J) must be a

T-invariant, i.e.,

di) C'V =0 (3.13)

Let til, ti2 be two transitions in structural conflict (i.e., with the same pre-set)

with probability rates ril and ri2 respectively and Xi the flow into °til. Then the

throughput of til and ti2 is given by:

Xil = r--------k_lXi (3.14)

rl + r2

x_ = r2 _ (3.15)

rl + r2

Dividing eq. (3.14) by eq. (3.15) and rearranging terms yields

r-(_= il Ui2 _,=_[/_ (3.16)

By considering all conflicts in the net, eq. (3.16) can be combined together with eq.

(3.13) and can be rewritten in matrix form as

U)

vj = 1 (3.171

Eq. (3.17) has a unique solution iff the number of the independent rows of the matrix

is m - 1 with m = ITI. J. Campos [Cam90] showed that the number of independent

rows in the matrix in eq. (3.17) for subclasses of Petri nets which include FC nets,

is indeed m - 1.
37

===_

Figure 3.5: Modeling of Timed Structural Conflict with Immediate Transitions

(Firing and Probability Rates are in Parentheses)

Consider the structural conflict modeled with timed transitions in Figure 3.5.a.

Since the minimum of two ex'ponential distributed variables X1 and X2 with rate _1

and )_2, rain(X1, X2) is again an exponential distributed random variable with rate

A_an(x_,x_) = ,_l + _2, the sojourn time of a token in pi is a random variable with

negative exponential pdf with mean

1

si = 2-,i_'=1Aij . (3.18)

i.e., the rate out of pl is _=t AiJ [MarS9].

minimum time (i.e., that it will fire) is

The probability that tik samples the

_ik

Pr(tik) = (3.19)

_=1 _ij

Based on the previous discussion we can transform Figure 3.5.a into an equivalent

conflict with immediate transitions as shown in Figure 3.5.b. The steady state

probability of place p_'_" being marked is zero, while the immediate transitions ti_

model the conflict.

Theorem 3.5.1 Let jV" be a stochastic FC net and pi be the input place of a structural conflict modeled with ezponentially timed transitions. The transformation presented in Figure 3.5 preserves the underlying CTMC.

Proof: It is a direct consequence of the construction rules for the underlying CTMC

from the reachability set that includes vanishing markings. O
38

In our model wedo not allowpriorities to be associated with immediate transitions or inhibitor arcs. An alternate definition of the generalized stochastic Petri

net (GSPN) defined in [Mar89] is therefore given by:

Definition 3.5.2 (GSPN) The GSPN is a siz-tuple

GN = (P, T, Pre, Post, Mo, R) (3.20)

(P, T, Pre, Post, Mo) is the underlying Petri net system.

R = (rl,r2 ...rm) is the array where ri

- is the parameter of the ezponential probability density function of the

firing delay if t_ is a timed transition,

- is a weight used for the computation of firing probabilities of immediate

transitions if ti is an immediate transition.

From a performance analysis point of view, we want to estimate the average

behavior of the system in the long rum The usual assumption is that the system is

ergodic [Ros83], i.e., in the long run the average of the observed values tend (almost

surely) to the theoretically expected ones. In finite ergodic systems, if starting in

state i, the expected time to return to state i is finite.

Definition 3.5.3 [Camg0] A stochastic process Z_ (r > 0 representing the time),

is said to be ergodic iff the following condition holds:

1

lim f Z_du tim E[Z,] < cc (3.21)

Not all live and bounded stochastic Petri nets are ergodic. Consider the net in

Figure 3.2, here two closed subsets of states exist. The steady state marking wiU

depend on the initial resolution of the conflict between tl and t2. We can circumvent

this difficulty with the following important results:

OF POOR QU_XL!'P/
39

Theorem 3.5.2 [Cam90] If a Markovian bounded marked net has a home state,

then its marking process is e_odic.

Starting from the reachability graph and its stochastic interpretation, we can find

the underlying homogeneous irreducible CTMC.

3.6 Conclusions

The practical modeling power of Petri nets is constrained by subclasses, but

they allow more powerful analysis techniques using fast (e.g., polynomial time)

algorithms that avoid the state explosion problem. These algorithms are based on

establishing a relationship between the behavior of the net system and its structure,

and are parameterized by the initial marking, which plays an auxiliary role.

In the present work we limit ourselves to the analysis of subclasses of net

systems whose marking process is ergodic (Definition 3.5.3) and where all states

are home states. Thus, we only deal with systems whose underlying CTMC is

irreducible (Theorem 3.5.2). Furthermore, we restrict our attention to subclasses

of net systems where we can determine ergodicity of the marking process based

on the net structure .V" and an initial marking Mo, considering only net subclasses

where the teachability of a marking can be determined based on the state equation

(Theorem 3.4.3) and thus all states are home states. From the above discussion, we

now limit our attention to two net subclasses: SMs and MGs. Strongly connected

SMs can trivially be solved because they have the structure of monoclass GordonNewell QNs and well known product form solutions can be applied. For MGs, no

product form solution is known, therefore in the following chapter we concentrate

our efforts on this particular net subclass. In Chapter 7, we consider MPMT-nets

where we show that the above properties also hold.
CHAPTER 4

Structural Decomposition and Response Time Approximation for

Marked Graphs

4.1 Introduction

The basic approach in the presented approximation methods is to divide and

conquer. We can identify two phases in the process: a structural decomposition

phase (divide) and a stochastic aggregation phase (conquer). The structural decomposition phase consists of two steps:

1. Structural: the system is partitioned into subsystems yielding the aggregated

nets AN'.

2. Marking: the marking of the aggregated nets is computed such that a notion

of environment is kept (yielding the aggregated net systems .AS).

Based on the results of the decomposition phase, in the second phase the

aggregated net systems subsystems are analyzed some assumptions which depend

on the method we are using (e.g., arrival process, number of customers).

In the following we are concerned with finding suitable assumptions (arrival

process) for the analysis phase, while at the same time preserving some information

about the environment of the subsystem. For MGs with deterministic timing or

Jackson QNs, the aggregation preserves the performance measures, but in general

the representation of the environment presents a dilemma. If we represent the complement of the subsystem better, the state space of the underlying CT.'_[C is going to

be larger. In the proposed approach, we try to preserve the response time (RT) of

the subsystems exactly. As we will see, this is only possible for certain special cases,

4O
41

while in generalwe only approzimate the RT. Therefore, the proposed method can

be seen as an RT approximation (RTA) [JSS92b].

In this chapter, we present mostly the theoretical aspects of the decomposition. Several examples are introduced arid analyzed in Chapter 6, after all of the

aggregation techniques have been presented (Chapter 6).

4.2 Single Cut, Aggregated nets, Basic Skeleton and Response Time

Approximation

The basic idea is illustrated in Figure 4.1.a: the net is split into two subnets

by a single cut _ defined through some places called interface places (A and M in

Figure 4.1.a) [JSS92b, JSS92a]. From the cut we define three nets: two aggregated

nets #UV" (one per subnet, Figures 4.1.b, .AUV'I, and 4.1.c, ./UV'2), and the basic

skeleton (Figure 4.1.d). AA/'i is obtained by preserving subnet SNi and connecting

the interface places through a transition rj representing the reduction of the other

subnet SNj,j # i. Transitions rl (Figure 4.1.c) and r2 (Figure 4.1.b) represent the

aggregation of subnets SN1 and SN2, respectively. The basic skeleton (i.e., the fully

aggregated net, Figure 4.1.d) is obtained by maintaining the interface places, while

reducing each subnet to a single transition. For a single cut, the basic skeleton alwavs

has the same structure, i.e., it is independent of the topology of the stochastic MG

under analysis. The markings of .AUV'I,.AuV'2 (leading to the aggregated net system

.,4Si = (.ZbV'i, M_)) and the basic skeleton are computed based on the initial marking

of the original net.

Assuming single server semantics for the aggregated transitions r representing

the subnets, the basic skeleton will be interpreted as a classical M/M/I/K queue,

where K represents the number of customers in the system (and therefore also the

maximum queue size). Therefore, the throughput 2' of the basic skeleton can be
42

1

B(

sC

D

4

s_v, C4t

!

'A

S/V2

6

t£' I

;o

!

Ca)(H,Mo>

I

_M .= q2! M = q21 j

A -- q12

rl _r2

M = q21

(d) Basic Skeleton System

Figure 4.1: Aggregated Nets (b+c) and Basic Skeleton (d) Systems Obtained from

the Indicated Single Cut to the Marked Graph (a)
43

written as [GH85]:

_ pK+_

X=U( I _+_) (4.1)

where p = A/# isthe ratiobetween the rates A and/_ of the aggregated transitions.

With the above presentation we devise a divideand conquer approach to compute an

approximation of the throughput: itshould be obtained through an iterativescheme

using both aggregated net systems and the basic skeleton system. Assuming an initial

guess for one of the aggregated services (e.g., transition r_), the throughput of .AS1

(Figure 4.1.b) is computed (solving the underlying CTMC) and a value for the

service rl is determined such that the basic skeleton has the same throughput (using

equation (4.1)). In this way we approzimate the RT of SN1. The value of the service

time of vl, is then substituted into the other aggregated net system (Figure 4.1.c)

and the throughput is computed (solving the underlying CTMC). A new value for

the servicetime of r2 isdetermined such that the throughput of the basic skeleton

and MS: are equal. The schema isiterateduntil a reasonable convergence of the

throughputs isobtained.

The goal of the above presentation is just to convey the basic idea. The

next sections formalize the technical aspects of single cuts. First in Section 4.3

the fundamental singleinput/singleoutput (SISO) cut ischaracterized. The other

possible singlecuts are representedin Section4.4 (SIMO/MISO cut) and Section 4.5

(MIMO cut).

4.3 Single Input/Single Output (SISO) Cut

This section is devoted to the characterization and analysis of the case where

a net is split into two subaets in such a way that the interface is defined by a subset

of input or output places of a unique transition and by a subset of input or output

places of another (eventually the same) transition.
44

Case 1 qu

w_---_2.: .

t i

: t i .,_b

! iJ

|

Case 2 !

b Jp ')J

_ tl.y t s

Figure 4.2: Canonical Transformations Presented on the Interface Iij (from SNi to

SNj: tij is an Immediate Transition)

4.3.1 SISO and Canonical SISO cuts

The idea of the single cut was formalized in Definition 3.3.1. As all places in

MGs are persistent, it is possible to further characterize the interface:

Definition 4.3.1 (Interface) Let _ be a single cut traced through a set of interface

places Q (Definition 3.3.i). Q = Qx2uQ2x where Qii is the subset of places defining

the interface from SNi to SNj, i.e., "Qij c Ti and Q_j c_ Tj. t is a source (sink)

transition of SN, iff t E Ti and t E "Qij (t E Q_,).

Eventually source and sink transitions will be the same.

Definition 4,3.2 Let _ be a single cut producing subnets SN1 and SN2, connected

through the subset of interface places Q12, Q21 c_ P. Furthermore, let Ii/ be the

condition that the interface from SNi to S,.Vj has to satisfy. _ is SISO if:

I

I12 : 3t12 E TI: Ql2 C_t_2 or 3t't2 E T2:Q12 c_ *t12

t
45

Both subconditions in I/j are illustrated in Figure 4.2. Moreover Figure 4.2

illustrates a canonical transformation to deal with the case where we have multiple

places interfacing to the same pre-set (post-set) of a transition (i.e., when I Q12 l> 1

or I Q21 I> 1). in the transformed net each interface has only a single place. We

introduce an immediate transition tij and replace the interface Qij by a single place

qii"

The canonical transformation preserves the underlying CTMC (only vanishing

markings are introduced). Conceptually we could transform any SISO cut into a

canonical SISO cut (i.e., through two different interface places, q12 and q21 which

connect SIV I to SN2 and vice versa), but the canonical transformation increases the

vanishing state space. Therefore, we would not introduce the immediate transition

tii in Figure 4.2 for the generation of the CTMC. In order to simplify notation and

statements, in the rest of this section we assume without loss of generality, that

the cut is canonical (i.e., done through a single input place and a single output

place) or that the canonical transformation is done whenever necessary (even if only

conceptually, because of the increased vanishing state space). Therefore, in the rest

of this section [Q_2 I=[ Q2_ [= 1, Q,2 = {q,2} and Q_ = {q_x}.

Property 4.3.1 (SISO cut)

i) It is possible to check whether a cut is SISO is in linear time.

ii} The canonical transformation preserves the CTMC associated to the original

system.

4.3.2 Qualitative Aspects

The process of obtaining aggregated net systems .AS (Figure 4.1), can be

viewed as a reduction of the net system [Ber85, Si185]. Ideally speaking, we look for

a reduction rule preserving the performance indices, in particular the throughput.
46

Rules preservingthe throughput will bevery limited. If the throughput cannot be

preserved,what property should be reasonableto preserve in such a way that our

iterative scheme yields a "good" approximation for the throughput? We decide to

preserve the mazimum number of tokens in the non-aggregated places (i.e., its marking bound). This corresponds to the idea of preserving the number of customers of

the original system to its abstract views: the aggregated nets and the basic skeleton

system. The preservation of the number of customers will imply the preservation of

liveness for MG systems (remember that non-liveness is equal to null throughput!).

The work will proceed in two steps: First the qualitative aspects will be stated

in this section using known facts from the structural theory of MG systems, and

later the quantitative aspects will be addressed (Section 4.3.3).

Once a SISO cut has been decided on by the analyst, the transformation of

the original net system into an aggregated net system can be viewed as a reduction

process in which one subnet subsystem is aggregated into a single transition pre-

• serving the interface places and the other subnet subsystem. The marking of the

remaining places has to be computed.

Let N" = (P, T, F) be an MG and _ a canonical SISO cut through places ql2

and q:x defining two subnets SNi = (P_, T_, F_) with i = 1,2, where Q = {q12, q21}.

The original net system (:V',M0) leads to two ag_egated net systems,

-ASI = (.#bY'i, Mg) i = 1, 2, and the basic skeleton system. Structurally speaking from .IV', SNj is reduced to rj in A.V'i ( here ._bV" refers to the structure, while

.AS refers to .AW" plus some initial marking). The decomposition process is formalized by the following rule.

Rule 1: SISO Decomposition Rule

1. Structure: A._'i = (Pi, T/, Fi), i = I, 2 is an aggregated net, where:

oP,=P,
47

• _,= _u{n}

• P_=F,u(q_ x _,)u(_ × qj,); (_q,j= *n,qj,=_-;)

The basic skeleton is just the cycle {qn -"+ r2 ---* q2t _ rl _ q12}

2. Marking:

Let _ be an optimal solution to the following linear programming problem:

maximize "M (q21)

subjectto _7= Mo+C._> 0

__>0, M>0

(LPP3)

where C is the incidence matrix of the canonical MG obtained from the original

net and cut. The initial markings for the two aggregated nets and basic

skeleton are the projection of _7:

• for .AJV'i : M_(p) = _/'(p), Vp 6/5i

• for the basic skeleton: M_(ql2) = 0 and K = -]kI_(q21) = _'_(q21)

Property 4.3.2 (SISO Reduction Rule) Let (;V', Ado) be a live MG.

1. For any reduction (from the original net system to an aggregated net system

or to the basic skeleton system) the bounds of the places are preserved: B(p) =

_(p), vp _ e_

12. Liveness in both aggregated net systems and the basic skeleton system is preserved.

Proof.' It is a direct consequence of the teachability and liveness theorems for

strongly connected MGs (see Section 3.4.2). The transformation of the marking

empties the least-loaded path in the subnet which is being reduced, therefore we
48

qji

(a) .4s

Figure 4.3:

(b)Abstraction to M/G/1/K

M(r_) K customers

M(G)

(c) Reduction to M/M(G)/1/Ix"

Abstraction of .AS and Throughput Preserving Reduction

maintain the marking bound of places. Thus, the liveness of the system is preserved. •

Moreover, it is not difficult to realize that for any optimal solution of (LPP3)

M'(q12) = 0. This is true because q12 and q21 belong to the same set of cycles (Psemiflows). Thus, the maximization of _7"(pii) implies the minimization of l-'_(pi; ).

Because LPPs are of polynomial time complexity, polynomial time algorithms

lead to the aggregated net systems and to the basic skeleton systems.

4.3.3 Quantitative Aspects

During the RTA aggregation, we replace a subnet SNi by an equivalent station

(transition ri) with single server semantics. The response time of ri in isolation

under an assumed arrival process approximates the response time of the replaced

subsystem (i.e., subnet plus marking). In the aggregated net system AS./, the

aggregation of subnet SN_ (represented by r_) is the generator of the arrival of

tokens to the subnet SNj, i _ j. The service time associated with the transitions

ri, s(r,) = 1//.t_, i = 1,2 represents an approximation of the mean completion time

(MCT) of SNi in the original MG system.

An interpretation of the system ASj (Figure 4.3.a) is the classical M/G/1/K

queue, shown in Figure 4.3.b. Here we know the mean service time of the exponential

server (transition r_), the number of customers in the system K = M(q12)+M(q_.l) =
49

M(q21), and the throughput X of the system. Then our goal is to find an equivalent server for G (where G is a general distribution function which summarizes the

behaviorof the subsystem(S_;, M_)).

One possible solution is to approximate M/G/1/K by an M/M(G)/1/K queue

(Figure 4.3.c), preserving the throughput of the original system (here M(G) expresses

the fact, that the general server G is approximated by the exponential server M(G)).

Then the problem at hand is the following: with the information from the analysis

of the t_I/G/1/K queue (population K, interarrival rate A and throughput ,-Y), we

have to find the service rate/_ of M(G) such that the throughput of M/G/1/K and

M/M(G)/1/K is the same. Equation (4.1) can be rewritten as:

1

X- A(1 - E/___.op_, ) (4.2)

It is easy to see that X < A, because the throughput cannot be higher than

the fastest firing rate of a transition. Rewriting equation (4.2) as polynomial and

defining B = X/,_, /_ < 1, we have to find the positive solution of the following

polynomial:

/

(_) =_p__" 1 1-Z_ = 0

i=1

The polynomial f(-_) has a unique positive real solution because:

(4.3)

i.e., the function is strictly increasing in 1/p. The unknown firing rate is obtained

by setting _ = ,_/p.

With this mapping of a M/G/1/K to a M/M(G)/1/K. queue, we maintain the

response time of the system when K = 1 because the steady-state probabilities of an

ll/£/G/c/c and an M/M/c/c queue are the same [GH85]. Therefore, the throughput

and the response time of both queues are the same if K = 1. When K > 1, we only

f(0) = <0 (4.4)

1-_

df(_) K 1_ v!

d(_) = ,=,i(p)'-_ _ > 0, p > 0 (4.3)
5O

approximate the RT. Note that in the original work of RTP, the isolated subsystem

was analyzed under an open arrival process, while here we analyze the subsystem

as a closed system.

_Ve can define the following functions:

function solve_basic_skeleton(A, A')

{Solves basic skeleton with unknown rate #}

input: A: known arrival rate

X: throughput

returns: p

function solve_aggregatedsystem(#, k)

{Solves the underlying CTMC of ASh}

input: k: indicates system to be solved

/_: firing rate of aggregated transition 7"

returns: Xk

function test_convergence(X.._,, Xotd)

{checks whether a convergence criterion has been achieved}

input: X,_.,.: most recently computed throughput

Xoid: previously computed throughput

returns: TRUE if convergence has been achieved

FALSE otherwise

Algorithm 1: Quantitative analysis of SISO cuts

1) Select a cut

2) Generate the aggregated net systems AS1 and .ASs and the basic skeleton

system using the Decomposition Rule.
51

3) Initial Value computation: Determine an initial value of the firing rate of rl,

po (belonging to JLS"2). A reasonable initial value can be obtained as follows:

Let r2 be an immediate transition (i.e., Sz2 = o¢) in M.,5'1.

:= 1/rl;

where F1 is given by (LPP2) (Theorem 3.4.4).

X ° := solve_aggregated_system[lz °, 2);

4) r := O; {iteration steps}

5) repeat

r:=r+l;

p_-z := solve_basic_skeleton(_t_-l,,.y_-l);

X[ := solve_aggregated.svstem&_ -1, 1);

convergence := test_convergence(X[, X_-z );

. if convergence = FALSE then

/a_ := solve_basic..akeleton(/a_ -_, R'[ ) ;

X_ := solve_aggregated_system(l_ , 2);

convergence := test_convergence(,.t'_, 2([);

end if

until convergence = TRUE

Algorithm 1 implements an iterative method. Thus, the ezistence and uniqueness of the solution, and the convergence of the method should be addressed. Extensive tests have shown that for all cases considered, there exists one and only one

solution, which is typically computed between 2 and 6 steps, until the difference between the two last estimations of the throughput is less than 0.1% (the convergence

criterion is computed in the function test_convergence).

Although experimental convergence does not seem to depend on the initial
52

values for the iteration, _goodinitial values" can reduce the number of iterations,

thus the practical complexity. The throughput of deterministic timings is frequently

relatively close to the case of exponential timings, and its computation is polynomial

(using Theorem 3.4.4). Therefore, the choice of the initial value of rl is justified.

Because of shorting out and the assumption of deterministic time, the initial value

is an optimistic initial value. From our experience, the cycle time of the subnet in

short circuit is in many practical cases within 20% of the actual value.

4.4 Single Input/Multiple Output (SIMO) Cut

This section considers a class of cuts (disjoint with respect to the SISO class)

where the places of one and only one of the two interfaces does not belong both to

the pre-set or the post-set of a single transition.

The output interface of SN2 in Figure 4.4.a, {ps,pr}, is a multiple interface.

More precisely stated, the pre- and the post-conditions of the interface Q21 have two

transitions: {t3, t4} and {ts, t6}, respectively. The input interface leading to SN2 is

defined through a single place/_. Thus, the cut is SIMO with respect to SN2. On

the other hand, if SN1 is taken as the reference subnet, the same cut is Multiple

Input/Single Output (MISO, the symmetrical case). Therefore, in the rest of this

work we refer to these types of cuts as SIMO cuts.

Definition 4.4.1 Let_ be a single cut'producing subnets SNI, and SN_, _ is SIMO

with respect to SN2 (MISO with respect to SN1) if:

.._ t t

[21

{single interface}

: 2t2t e T2:Q2t C_ t_t and 2t'_t E Tt:Q2, C_'t'2_ {multiple interface}

Comparing Definition 4.3.2 and 4.4.1, it is clear that a SIMO cut simply

negates the second condition of the SISO cut. Thus, SISO and SIMO are disjoint

classes of cuts.
53

Ld-J :

t7

(a) Original net system and cut

Pl P2 t3 P4 P9

"O

$?

t2

PS

t?

(b) Introducing the shadow transition t, associated to the cut

Pl P3

t2

PS

(c) The two aggregated net system <.AJ_fi, ll/Iio>.

Places rk or sk represent pk of the original net

P3 t3 P4 1o9

r$

t7

Figure 4.4: SIMO Cut and Aggregated Net Systems

We already know how to deal with the SISO case. Thus, an idea is to transform

the underlying net structure in such a way that the resulting subnets have SISO

characteristics. The necessary transformation on the net structure leads to the

introduction of a single immediate shadow transition ts.

Definition 4.4.2 (shadow transition) Let Qij be the set of multiple interface

places generated by a cut _. The duplicate interface places Rij, Sij and the shadow

transition t, are generated as follows:

I @¢ @l

VqijEQij, ri.i - qij

le Io

Sij -" qij
54

Io O I

rij = Sij = t, (4.6)

Figure 4.4.b shows the introduction of a shadow transition ts leads to the

duplication of the interface {ps,pz} creating the places {rs, rz} and {ss, st}. Then

we have:

•ts= {re, t; = {se,

The cuts defined now through qz2 = {p3} and Q21 --" {re, rT} or Q2z -- {se, sT}

are SISO. From a structural point of view, the introduction of a shadow transition

means the introduction of a new synchronization constraint. In general, the presence

of the shadow transition creates new elementary cycles. In our case:

(_) P3 "4 t3 "+ rz "-> ts _ s5 _ te _ P6 _ t6 -'+ Ps -+ t2 "+ P3

are new cycles. They lead to the following P-invariants:

(a) M(p3) + M(rz) + M(sh) + M(p6) + M(ps) + M(p3) = K_(Mo)

(8) M(_) + M(p4) + M(rs) + M(sz) + M(ps) + M(ps) = Ko(Mo)

where K=(Mo) and A_(M0) is the number of tokens in the newly created Pinvariants.

Using the standard reduction approach on the SISO cut in Fig 4.4.b, the

aggregated nets in Fig. 4.4.c are obtained. Observe that both can easily be derived

from the original net. In our presentation we introduce the transformed net with

the shadow transition to highlight the presence of the additional synchronization

constraint.

Now we have to choose appropriate initial markings for the aggregated nets

(Fig. 4.4.c). To better understand the problems, let us go back to the original net

system, and the transformed net with the shadow transition. One solution could be
55

derived by maximizing the numberof tokens in the places of the multiple interface

of the original net system (i.e., {ps,pr}). Such a solution is, for example: M T =

(1,0,0,0,2,0,1,0,2,0). Observe that M(ps) - B(ps) -- 2, M(pr) = B(pT) = 1 and

M(pa) = O.

The following property formalizes the previous discussions:

Property 4.4.1 Let (H,.AAo) be a live MG system, _ a 5111/I0 cut with the single

interface ql: and the multiple interface Q21. Any solution of the marking of the

multiple interface places:

maz EpeQ21 M(p)

subject to M = Mo + C " _ > O

_>_0, M__O

is s ch that Vpe Q I, then M(p) = B(V) and M(ql ) = O.

(LPP4)

With a solution of LPP4, the number of tokens in the places belonging to the multiple interface is their marking bound.

Proof." It is easy to see that any elementary circuit through q12 should go through

one and only one place of the interface Q21. Thus, reasoning on the P-invariants generated by these circuits and considering the teachability theorem (Theorem 3.4.3),

it can be concluded that maximizing the marking on Q21 leads to M(q12) = O.

On the other hand it can be proved that there exists no elementary circuit

containing two (or more) places of Q21: from p E Qzi we should reach q12 before

returning to any place of Q21. Thus, a circuit through two places of Q21 should go

twice through ql: and the circuit is not elementary.

The elementary P-invariants generated by the circuits containing places of Q:I

have one and only one place of Q21 (i.e., they do not interfere). Thus, maximizing

the sum of tokens is equivalent to maximizing the number of tokens in each place
56

of Q2x- The result follows because of the teachability theorem (Theorem 3.4.3). •

Once a solution of (LPP4) has been computed, the problem of where the tokens

should belong to once the structure of the net is transformed arises:

• Case a: tokens into "ts, i.e., into the pre-set of the shadow transition,

M0(rs)= 2, M0(rT)= 1,M0(ss)= M0(_7)= 0.

• Case b: tokens into t_, i.e., into the post-set of the shadow transition,

Mo(,-_)= Mo(,-7) = o,Mo(_)= 2,Mo(sT)= _.

In the original net system we have the following marking bounds:

B(p4) -B(ps)= 2; B(p3)-- B(pr) -- B(ps) -- i.

After the computation of the new markings we have the following changes in the

marking bounds:

Case(a), tokens in pre-set of ts: B(._5)=l , Ss E SN1

Case(b), tokens in post-set of ts: B(p4)=I, P4 E SN2.

Because of the shadow transition, in both cases the behavior of the resulting net

system is different from the original. A closer examination shows that computing

the marking according to (a), we only preserve the marking bound of the places

in SN2. On the other hand if we compute the marking according to (b) only the

marking bounds of the places in SN1 are preserved.

In case (a) ((b) respectively) the initial marking for the transformed net with

the shadow transition preserves the bounds of the places belonging to SN2 (SNI) if

tokens corresponding to the original interface places Q21 are deposited in the pre-set

(post-set) of the shadow transition, "/, = {r} (t: = {s}).

For the computation of the two aggregated net systems and the basic skeleton

system we do not need to introduce the shadow transition e.xplicitly (after all it leads

to an increase of the vanishing state space). Theprocess leading to the ag_egated
57

net systems and basic skeleton system can be expressed directly by means of the

following decomposition rule. In this way, all the marking bounds are preserved.

The effect of its application is shown in Fig. 4.4.c.

Rule 2: Multiple Interface Decomposition Rule

I. Structure:

(a) .#bV', = (/3, 7_,, _) i= 1,2 is an aggregated net, where:

.P_=P,

• f_,=T,u{_-j)

• P_= F_u (Q,_× _j)u (_j × Qj_), (_ "_j= Qq, ,-j"= Q_,)

(b) The basic skeleton is just the cycle {q12 _ r2 ---* q:l "_ r_ ---, q_2}, where

qlj now represents the subset of places Qii2. Marking:

Let _ be a solution of the following linear programming problem on the

original net system (a generalization of (LPP3)):

1-_= maximize E21-

subject to _'/= Mo + C. _ > 0 (LPP5)

__>0

where E21 is the characteristic vector of the multiple interface, Q_I, i.e.:

=/ 1 ifpeQ21 E21(p)

( 0 otherwise

The initial marking of .4N'i, i = 1,2, is l_g, the projection of_'_ on .AN'i, i.e.,

21,l_(p) = "ff[(p) Vp E Pi, considering that places rk and sk represent p_ of the

original net. The initial marking for the basic skeleton is:

Mo(q_:) = 0 and Mo(qn) = min {_-_/(p)} = B(q2_)

pEQ2z
58

The multiple interface reduction rule is a generalization of the SISO rule (Rule

2). For SISO interfaces both rules lead to the same transformation. We can identify

the projection of the marking vector on .AH1 as case (a) (tokens in "ts), while the

projection on .AN'I corresponds to case (b) (tokens in t_).

Property 4.4.2 Let (N',._o) be a live MG system, _ a SIMO cut on N', and

- i

.Ado) ' i = 1, 2, the partially aggre#ated net systems obtained by apphjin9 the

Multiple Interface Decomposition Rule, then:

1. S(p)= vp

e. (.4Hi, .A4o), - i = 1, 2 is live.

Proof.-

1. Any circuit of.AN'i is the projection of a circuit of the original net (observe that

all the new circuits introduced by the shadow transitions disappear with the

subsequent reduction processes). The result follows because of the reachability

theorem and the P-invariants induced by the circuits.

2. The bounds being preserved, all the circuits of the aggregated nets should be

marked. Therefore, the ag_egated net systems are five. •

In order to approximate the throughput, the initial value computation and

iterative schema of the SISO case (see Algorithm 1, steps 3 and 4) can now be

used with the two aggregated net systems and the basic skeleton system. Now the

number of customers K = B(qn), i.e., K is given by the marking bound of the

single interface place, qn.

It can easily be verified that the two aggregated net systems obtained with the

Multiple Interface Decomposition Rule can be derived from the same transformed

net (with the shadow transition, Figure 4.4.b) but for two different initial markings

(i.e., two different net systems).
59

4.4.1 Alternative Interpretation of the SIMO cut

Another way of interpreting the SIMO decomposition is as follows: Is it possible to reconstruct the original net system from the two aggregated net systems .AS1

and AS2 obtained with the Multiple Interface Decomposition Rule? As we will we

see not, because we have made a structural change by introducing the shadow transition. It is possible to construct a net system where a S/SO cut leads to the same

aggregated net systems as with the SIMO cut. Let the initial marking of the net

shown in Figure 4.4.5 be M(sr) = M(rs) = M(pI) = 1 and M(ss) = M(po) = 2.

The SISO cut through the places Sz, Ss and P3 together with the canonical transformation also leads to to the aggregated net systems shown in Figure 4.4.c but its

behavior is completely different from that in Figure 4.4.a. Here we have introduced

the shadow transition and added tokens until the marking bound of all places is the

same as in the corresponding places of Figure 4.4.a.

Theorem 4.4.1 Let (,IV', Mo) be a MG system with the SIMO cut _ defined through

the single interface qq and the multiple interface Qji and A/"_ the net structure after

introducing the shadow transition. The SISO cut _' through (jV",M_) with the

interface places Rji or Sji produces the same aggregated net systems as the cut

in (H, Mo) • Mf is given as follows: Let Tf'[(p) be a solution of LPP5. M_ is the

projection of _'[(p) on P' considering that Rji now represents Q#i. Furthermore, let

k be the minimum number of tokens in the interface Rji, i.e.,

The marking of S)i is given by

k = rain M(p) (4.7)

pER j,

I

e sj,, = M(r;,) - k (4.S)

Proof: We have to show that the marking bound of the places in (H', M_) is the

same as in (H, M'0) •
6O

1. The bound of placesin SNj cannot have decreased because we have at least

maintained the number of tokens in each directed circuit by using the projection of the marking vector of LPP5 (Rji is now part of SNj).

2. The maximum number of tokens in a directed circuit in SNi is the same

because there exists at least one path in SNi (between qi.i and Sji) which is

empty. By using corollary 3.4.4 we have not increased the marking bound of

the places in SNj.

The same reasoning holds for SNi, because by firing t, the situation of SNj and

SNi is now symmetrical and the same argument holds. •

The above reasoning is conceptual, because the aggregated net systems can

be obtained directly from the original net system by elementary net reduction rules,

specifically the macrotransition reduction rule (the reverse-dual of the macroplace

reduction rule presented in [Si185]). Nevertheless, when interpreting the results generated by a SIMO cut, it is important to remember that a structural transformation

has taken place.

Because of the shadow synchronization constraint (a pessimistic transformation) and the change in marking by Theorem 4.4.1 (an optimistic transformation),

the global estimated performance may be pessimistic or optimistic.

4.5 Multiple Input/Multiple Output (MIMO) Cut

The third (and last) class of single cuts is obtained when the places of the

input and the output interface do not belong to the pre-set or the post-set of a single

transition. In other words, several (multiple) transitions define both interfaces.

Definition 4.5.1 Let _ be a single cut producing subnets SN1 and S,.V:, connected

through the subsets of interface places Ql2, Q21 c_ P. _ is MIMO if:

: 2t, . T,: c_th and Q,: c_.t',:
61

I

q4_q$ i 7

(a) (b)

tf. .........

Pa

(c)

Figure 4.5: A Bad MIMO Cut and Two Possible Interpretations of the Net System

Transformation

721 : _/_t21 e T2:Q21 _-_ t_l and 2tr21 E Tl:Q21 __'t'21

Comparing Definitions 4.3.2 and 4.5.1, it is clear that a MIMO cut negates

both conditions of a SISO cut. SISO, SIMO and MIMO form a complete set of the

disjoint classes of single cuts.

MIMO cuts can be much more problematic from a performance analysis point

of view. In general, if we apply the technique presented previously, we do not

maintain the meaning of the original net system. We wiII iIIustrate the previous

statement with two examples.

The net system shown in Figure 4.5.a (without place _') is a monomarked

(i.e., marked with a single token) elementary circuit. The MIMO cut presented

is bad from any point of view: by making a structural transformation analogous

to that introduced in Section 4.4 (i.e., introducing two shadow transitions, one per
62

i;

interface), the net in Figure 4.5.b is obtained. New circuits have been introduced into

the net system, which is now obviously dead. Adding a token to p3, the net system

becomes effectively live, but the behavior of the transformed system has nothing

to do with that of the original system (e.g., compare the possible firing sequences).

Another interpretation for the reduction process is illustrated in Figure 4.5.c where

the behavior (taken as the firing sequence) is preserved, the only difference being

that instead of firing a or d, an aggregated transition ad is fired. There are two

problems associated with the second interpretation of the aggregation process:

(1) The aggregated net depends on the behavior of the original system and

(2) The aggregated net is not an MG.

What is the problem with the MIMO cut in Figure 4.5.a? The answer is quite

simple: an elementary circuit has been cut in more than two places (four to be more

precise, because the number of cuts on a circuit to split a net into two parts must be

even). Doing that, two subcircuits of the same circuit axe forced to be aggregated,

something that is functionally meaningless.

In another way the MIMO cut of Figure 4.5.a is also problematic: we are "aggregating" two disconnected subnets Pl, t_, P4 and P2, Q, Ps and from a performance

point of view this may be dubious. Nevertheless, we can add an implicit place _" to

the original net ( "rr = t_ and r" = t_). Because r is implicit [CS90], this new place

does not change the behavior of the original system, and the subnet to be aggregated

is now connected. But if we reduce the subnet we will change the parallel behavior

( t= II ta) in Figure 4.5.b to a sequential behavior ( t= o Q). Therefore, two net

systems (with and without the implicit place rr) have identical behaviors, but lead

to two transformed net systems with quite different behaviors! We can alleviate the

problem by introducing the notion of well formed cuts.

Definition 4.5.2 (Well Formed Cut) A MIMO cut _ is said to be Well Formed

if no elementary circuit is cut more than twice.
63

Given a cut on an MG, it can be easily characterized as being well (or ill)

formed. Let G_ be the arc weighted graph obtained from the MG considering the

transitions as nodes and the places as arcs. Arcs are labeled with weight 1 if the

corresponding place belongs to the interfaces defined by the cut, and 0 otherwise.

Thus, the following can be concluded:

Property 4.5.1 The MIMO cut _ is well formed iff the mazimum weighted circuit

of G_ has weight two (i.e.,no circuit is cut more than twice}.

The problem of computing a maximum weighted circuit [Deo74] has polynomial time complexity, therefore, well formed cuts are characterized in polynomial

time.

The transformation of the MIMO cut into a SISO cut leads to the introduction of two shadow synchronizations: one for the input and another for the output

interface. Figure 4.5.b shows the structural transformation. Of course the shadow

transitions can introduce many new circuits.

The process leading to two aggregated net systems and the basic skeleton

system can be directly expressed by Rule 2, Multiple Interface Decomposition Rule.

The two aggregated net systems produced by _¢in Figure 4.6.a are represented in

Figure 4.6.c. The following are two interesting observations on our example. In the

transformed net with the shadow transitions:

• Places P4 and rl (representing Pl) in AS1 are now 1-bounded, while they were

2-bounded on the original net system, i.e., now the "number of customers" is

not preserved.

• Place s3 is implicit [CS90] and the behavior is not changed if we delete it.

The definition of the multiple interface decomposition rule emphasizes maximizing the number of tokens in the multiple interface. As the cut is now MIMO,
64

SN_ _. SN2

Ps pr

r2 tJ12 $2 P$

Ps Pr

p

)r6

_.t,38

r"

r"

(a) Original net system (b) Transformed net structure

with shadow transitions

a2 Ps

j1"1

Ps P?

(b)

Figure 4.6: Example for MIaMO Cut: Marking Bound Changes

both interfaces are multiple and a solution for _7 can be obtained by maximizing

the number of tokens in Q21 or in Q12-

The situation is now somewhat more symmetrical, what happens if we maximize the marking of the other multiple interface, i.e., E12- M = _pcQ,2 M(p)?.

The solution for _ is now _7 = M0, thus:

• M(r,) = 2, M(r2) = 1, M(sa) = M(ss) = M(p4)= M(pr)= M(ps) =

M(pg) = O.

• M(s:) = 2 M(s2) = l, M(ra) = M(r6) = M(ps) = O.

The new initial marking for ./LV'2 is reachable in AS2, therefore, basically

the situation for AS2 has not changed. Nevertheless, AS1 has an initial marking
65

such that the bound of all places except ss is preserved! Moreover, even if B(sa) is

different from B(p3) it is easy to see that sa is implicit [CS90] and can be removed

without affecting the behavior! In other words, optimizing the marking on Q12 or

on Q2t has different effects on the behavior of the aggregated net systems!

Property 4.5.2 Let (A/',,44o) be a live MG system, _ a well formed MIMO cut on

Af, and (j-_, _o) the net system obtained applying the multiple interface decomposition rule. Then (27, _o) is live, but in general the bounds of places are not

preserved.

Proof." By maximizing the number of tokens in the output interface, we guarantee

that each circuit is marked (the new circuits as well as the old ones, because each

new elementary circuit has to include one input and one output interface place),

therefore, the transformed net system is live. •

: Anyhow, approximate quantitative results are obtained by applying the ini-

_ia/ value computation and iteration schema of Algorithm 1 to the aggregated net

systems and the basic skeleton system obtained with the multiple interface decomposition rule and maximizing the marking on Q21 or on Q12. K is now the minimum

number of tokens in the circuits which have been cut.

From the above discussion the following property follows:

Property 4.5.3 The marking bound of ASi, i = 1,2 is preserved, if the number of

tokens in each cut cycle is the same.

4.6 Multiple Cuts and Response Time Approximation: Hierarchical Decomposition

In Section 4.2 the fundamental ideas for an approximation technique based

on single cuts have been introduced. Sometimes, the decomposition of the system
66

by a singlecut into two subsystems is not sufficient, because we cannot solve the

underlying CTMC's of the aggregated subsystems in a reasonable amount of time.

Once again we have to look for other approaches to cope with the problem of state

space explosion.

The basic idea is to consider not only a single cut, but to introduce several

cuts. We consider that multiple cuts can be implemented in a recursive manner,

leading to a hierarchy of subsystems which are structured in several levels.

In this approach we assume that the MG is decomposable into subnets by

more than one single cut. In general, this assumption is not true, when we consider

only a very restricted class of cuts like the SISO cut in this work. However, when we

consider all possible kinds of single cuts (SISO, SIMO or MIMO) this decomposition

is always possible.

Figure 4.7 illustrates the idea of the hierarchical decomposition. At each level

the nets are recursively partitioned into two subnets by a single cut until the size of

the state space of the resulting aggregated net systems is sufficiently small. Dashed

transitions represent the aggregation upon which the service times are iterated at

the current level. The approximate value of the throughput is computed in a hierarchical manner. The CTMCs associated with the aggregated net systems are

computed at the lower level of the decomposition when they are small enough (systerns AS_x,AS_2, AS_, and AS_2 in Figure 4.7).
67

t I t3 t t _ _ tg .lo c12

P2 t2 P3 Pt Ps ¢5 P6 PT p8 ¢8 P9 PIO Pll tl 1 P12

tl 1"2 _JL _] _ m.._ _ .12

P2 e2 P3 Pt PS t5 P6 .or P7 _ t8 P9 PIO Pll tl I P12

P2 t2 P3 P4 P4 P5 |S J_

PI5 PI4 t13 -m.3

P7 P8 ¢8 P9 P10 PlO Pll tl I P_2

As =

Figure 4.7: Hierarchical Decomposition into Various Levels
68

At each step of the recursivedecomposition, the analyst must define a cut

for each subnet, and evaluate the new set of ag_egated subsystemswhether it is

possible to solve the associatedCTMCs in a reasonableamount of time. Since

an accurate estimation of the size of a CTMC is difficult (although a promising

approach is outlined in [WD92a, WD92b]), the analyst should define when the

CTMC is "small enough" to be solved analytically. Moreover, if an additional

decomposition is needed,the analyst shoulddefine the new cut. Note that in this

decomposition method the number of subsystemswhoseassociatedCTMC has to

be solved is doubled with eachdecomposition.

_vVeare now going to describe,in an intuitive way,the hierarchical decomposition method with the examplepresentedin Figure 4.7. Becauseof the difficulties

associatedwith MIMO cuts, in thefollowing weonly considerSISO and SIMO cuts.

Consider the original system denoted by A/" at the top of Figure 4.7. Then

we choose a cut B through the places Pr and/hr. This cut satisfies the SISO cut

conditions. After the first cut is defined, we apply the decomposition process for a

single cut presented in Section 4.3.2, and obtain the aggregated systems .ASI and

,4sl.

Now we have to determine if the sizes of the state space of the aggregated

systems .AS_ and AS_ are small enough. If the answer is affirmative, we can compute the throughput of the original system with the iterative process presented in

Section 4.3.3. Note that if this condition holds at the first hierarchical level, we are

applying the single cut method.

All systems that are not sufficiently "small" must be further decomposed. This

means that for those systems we have to choose either a SISO or SIMO cut and apply

the appropriate decomposition rule.

In the general case, the number of systems can be large and distributed in

several levels. The number of systems and the number of levels are related. If we
69

have I systems, at most l- 1 levels are implicated in the process. An abstract sketch

of the recursive-interactive function for the quantitative analysis of the general case

is presented below. All functions have been previously defined in Section 4.3.3.

Alsorithm2 : Recursive- Interactive Analysis with SISO cuts

•procedure solvesystem (net system, level)

inquire ifthe net system is "small enough";

ifsmall enough then solve the underlying CTMC;

else if the net system has not been solved before

then

request a new SISO cut;

use the decomposition rule to generate the left and right

aggregated net systems, and the basic skeleton system;

endif

repeat

solvesystem (le ftsystem, level+I);

solve_basic_skeleton;

solvesystem (rightsystem, level-l-i);

until e= < e(level)

end if

An important observation on the sketched algorithm is that the requirements of accuracy on the different levels of the recursion can be different. In the

test_convergence function, we can use a convergence criterion dependent on the hierarchical level, i.e., _(level). This is interesting in practice because lower levels

are computed more frequently (they partially determine the time complexity) and

the impact of less accurate results at lower levels is partially canceled at the upper
7O

levels. The initial v_lue problem for intermediate and lower levels is not detailed

but the practice is to recover the last estimation at the corresponding level.

Property 4.6.1 (Multiple SISO Cuts) Let (H, Mo) be a live MG system.

1. For every aggregated net system and for the basic skeleton system, the bounds

of the places are preserved: S(p) = B(p), Vp 6 Pi.

_. tiveness in all aggregated net systems and the basic skeleton system is preserved.

Proof: Since the SISO decomposition rule is applied at each step of the hierarchical

decomposition, Property 4.6.1 follows from Property 4.3.2. ,,

In the hierarchical decomposition, the full environment is recursively defined

using the notion presented for the single cut. At each level, the environment of a

subnet contains all information of the environment of previous levels in its branch.

In other words, the error in the representation of the environment is bigger at

deeper levels of the hierarchy. So we can say that the accuracy of the hierarchical

method will be an inverse function of the number of levels in the hierarchical tree

of decomposed systems.

Finally, recall that in the hierarchical decomposition, the approximated value

of the throughput is computed by a recursive procedure. In order to solve each node

of the decomposition tree, the children of the node must be solved. This means,

that each iteration at level k implies a new computation of the throughput of all

children at level k. So the analyst must evaluate the convenience of carrying out a

new decomposition taking not only the size of the associated CTMC, but also the

number of times the lower levels are evaluated into account.

4.7 Conclusions

In this chapter we have introduced the structural decomposition of MGs. It is

based on a single cut through a single or multiple interface. We have seen that the
71

SIMO and MIMO cuts correspond to a structuraland marking transformation. Furthermore, in the MIMO cut the n_rldng bound of places isin general not preserved.

This justifiesthat in the following we concentrate on SISO and to some extent on

SIMO cuts. It isimportant to note that the basic skeleton is in product form, i.e.,

we have decomposed the MG system according to Definition 2.3.1 (product form

decomposition). Based on the aggregated net systems and the basic skeleton,we

can use both RTA, and any of the other techniques developed for "almost" PFQNs.

From the stochasticperspectivewe have introduced RTA, a new approximation

technique for the case ofsinglecuts. We have simplifiedRTP, so that in the proposed

method the computation of the coei_cient of wriation is not required. RTA can

be performed on a single levelor can be used in conjunction with a hierarchical

decomposition.
CHAPTER 5

Alternative Approximation Methods for Marked Graphs

5.1 Introduction

In the previous chapter we have explored the structural decomposition of MGs

to derive the aggregated net systems. Based on the structural decomposition, we

now present alternatives to RTA. In Chapter 4, we have presented Response Time

Approximation (RTA), which is specifically designed for the single cut. In the

following, we present Flow Equivalent Aggregation (FEA) and Marie's method.

Both are well known approximation methods for QNs, which are here applied in the

context of MG systems. They derive from the fact that by decomposing the MG

system by a single cut, the basic skeleton is in product form.

Delay equivalence (DE) [LW91, WL91] is another approach for the iterative

solution of MGs. Contrary to the previous approaches, it does not make use of the

basic skeleton.

In this chapter, we present the approximation methods. In Chapter 6, all of

the presented methods are compared with several examples.

5.2 Fl0w Equivalent Aggregation

In MGs, the basic approach is to substitute subnet SNi by a flow equivalent transition (FET) ri, whose (state dependent) firing rate is characterized by the

number of tokens in its input place qji (i.e., the queue length of the flow equivalent server). After the aggregation phase, both subnets are substituted by their

respective FETs (rl and r2). From a structural point of view, this leads to the

basic skeleton. The overall performance analysis is done by solving the underlying

CTMC.

72
73

5.2.1 Qualitative Aspects

The qualitative aspects of the decomposition have already been addressed in

Rule 1: SISO Decomposition Rule (section 4.3.2) and Rule _2: Multiple Interface Decomposition Rule (section 4.4). Based on a single cut, we generate both aggregated

nets..AS_ (.AS2) will be used to analyze SN_ (SN_) under a varying load which

allows us to formulate the flow equivalent transition rx (r2).

5.2.2 Quantitative Aspects

In FEA, the subnets are analyzed in short circuit. This corresponds to setting

"rl in .AS2 (r2 in AS1) to an immediate transition. Alternatively we can merge the

interface places and delete ri (this is preferred, because it reduces the number of

vanishing markings). For the quantitative analysis, the number of tokens k in the

interface place q21 has to be varied up to the maximum allowed, i.e., k = 1... K,

where K is the initial marking of q21 and computed by solving LPP3.

Algorithm 2: Flow equivalent analysis of single cuts

Select a SISO cut

Generate the aggregated net systems .A$I and .AS2 in short circuit by mer_ng

the interface places as well as the basic skeleton system using the Decomposition Rule (SISO or Multiple Interface).

3) Analyze AS_, i = 1,2 with too(q21) = I, l = 1 ... K by solving the underlying

CTMC and obtain the conditional throughputs XI and X2.

4) Set the service rates of the aggregated transitions to the conditional throughput, i.e.,

U,(1)=X,(l) i=I,2; 1--I...K (5.1)
74

5) Analyze the basic skeleton with the transitionrates obtained from step 4.

The above algorithm yields the mazimum reduction of the state space (higher

than in RTA), but as we will see the accuracy can suffer. Alternatively, we can

aggregate only one of the subnets (e.g., SN1) and substitute the state dependent

rate of/_1 into AS2. The state space will be higher, but in general the quality of

the approximation will be better.

5.2.3 Flow Equivalent Aggregation vs. Response Time Preservation

In FEA the assumption is that the service time depends only on the number of

customers which are currently present in the subsystem. In FEA the behavior of the

subsystem is assumed to be independent of the arrival process and depends only on

the number of customers in the systen_ i.e., the behavior is completely independent

of the environment. This assumption is violated in several cases.

Let us illustrate the fact that even in very special cases the mean completion

(or traversing) time (MCT) may depend on the interarrival process of the token.

Informally, the MCT is the average time spent by a token traversing the subnet.

Figures 5.1(b) and 5.1(c) show two 1-bounded MG systems. In the first (second)

we assume r2 (rl) to have different rates. Figure 5.1(b) essentially represents, the

circuit (Pl - t_ - p_ - tc - P3 - r2) in which "the server" at to has a setup time

modeled by tb. Figure 5.1(c) is essentially a cyclic fork-join system.

The system in Figure 5.1(b) can be interpreted as a _I/G/1/1 queue where

_'2 represents the exponential server, while SN1, represents the general server. Note

that the service time of G is just the MCT of SN1 (a similar argument holds for the

system in Figure 5.1(c)). The cycle time in an M/GIll1 queue is simply the sum

of the service times of M and G (insensitivity) [GH85].

therefore given by:

rs, = r - 0

The MCT of SN, rs,v, is

(5.2)
75

_.q._ .... ""_V'XY;"P_Lr-_ _ Cq.L_.._._.SN,

(a) < H, Mo >

tb

..........

Ii

(b)_s, = <.,_/',,_o')

q12

_ll

-_ ......_,v-=-,_:--p¥ ....'=e....._-

(c) AS2 = (.A.M2, Mo2)

q21

(d) Basic Skeleton

Figure 5.1: Aggregated Net and Basic Skeleton Systems Obtained from the Cut

(Service Times: s, = 0.33, sb -" 1.0, sc = 0.25, sd -- 0.20, s, - 0.33, sg -- 0.5)

where r is the mean interfiring (cycle) time with respect to any transition, and 0

denotes the firing (service) time of any transition _', 0 = sn = s_.

Table 5.1 presents the numerical data of the analysis of the systems in Figures

5.1(b) and 5.1(c). Both systems are 1-bounded, thus the variation in FsN, (from

1.383 to 0.583) can be explained only due to the dependency between the general

(time dependent, in particular) and the exponential server. If 0 is very large (0 >>

10), tb will almost surely fire before the firing of r2 ends. Thus, F = s_ + s, + 0

and Fs2v_ = s, + so. If 0 is zero (i.e., r2 is immediate), then Fs,v_ will be much

higher because now it depends on, sb, the firing time of tb, plus so. On the other
76

0

0.1

1.0

2.0

10.0

>> I0

System in Fig. 5.1(b)

r b

1.383

1.411

1.983

2.850

10.656

9 + 0.583

FSN1

1.383

1.311

0.983

0.850

0.656

s_ + s¢ -- 0.583

System in Fig. 5.11(c)

F" rSN2

1.783

1.883

2.783

3.783

11.783

8 + 1.783

1.783

1.783

1.783

1.783

1.783

1.783

Table 5.1: Dependence and Independence of the Mean Completion Time on the

Interarrival Time

hand, the value of FsN2 (Table 5.1) is constant, i.e., for the given initial marking

there exists a perfect decoupling (independence) between the general (in this case

time independent) and the exponential queues. This is easy to explain because the

1-bounded system is insensitive to the pdf of the server: both servers act as delay

rlodes.

The case of Figure 5.1(b) is just an illustration of the fact that the ezistence of

internal loops in a subnet may violate the independence condition. Another situation

where the independence condition can be violated is when trapped tokens exist in a

fork- join. To illustrate this case, assume a token is added to P4 in Figure 5.1(c).

Even if p4 and Ps are now 2-bounded, q12 is 1-bounded and the general server '%vorks"

as with a single customer. Therefore, insensitivity ira the M/G/1/I queue remains

and Eq(5.2) is valid. Nevertheless, with the modified marking the MCT of SN_ is

no longer independent of 0 (see Table 5.2).

For the particular case of the examples (1-bounded exponentially timed MG

systems), it is easy to observe a monotonicity property: increasing the service time

0 (representing a complementary subsystem) never leads to a bigger 3[CT for the

subsystem under consideration (see Tables 5.1 and 5.2 for Fs,vl and Fs,v2, respectively). This is easy to understand: the strong dependency between the general

and the exponential servers is due to the fact that the general server (i.e., the one
77

0 = s_ = 1/#1

0.25

0.5

1.0

2.0

4.0

F c FsI%

1.556 1.306

1.757 1.257

2.198 1.198

3.141 1.141

5.097 1.097

Table 5.2:Fslv2 Depends on 8 for the System in Figure 5.1(c) if a Token is Added

to P4

summarizing SA/'I) is time-dependent. But as 1rIGs are conflict-free, the increase of

the interarrival time of tokens eventually allows the tokens in the subnet to progess

towards the output places (i.e., q12 for SN1 and q21 for $1V2), resulting in a smaller

or equal (but never larger!) MCT.

Because of the insensitivity of M/G/1/1 queues, the estimated values of the

cycle time F in FEA, (FF_A) are as follows:

(a) Figure5.1(5): r_-sA= e + 1.383 (# r _,Tables 5.1)

(b) Figure 5.1(c): F._EA = 8 ÷ 1.783 (= F _, Table 5.1, because of the independence)

If the FEA is performed on SN1 for the marking in Figure 5.1(b), for 0 = 2,

an error of 18.7% in the computation of the throughput is obtained.

In response time preservatio_t (B.TP) [ABS84] the response time of the subsystem is replicated. Here the assumption for the analysis phase is a Poisson arrival # of

customers representing the environment of the subsystem. During the aggregation

phase the RT is replicated by an exponential server, i.e.,

Rrsw(_) = RTA,v(_) (_.3)

The advantage of iterative methods lies in the fact that it can model the interaction of subsystems. The drawback is that convergence might eventually present a

problem.
78

1 l

Figure 5.2: Open Subnetwork R_

5.3 Marie's Method

The first step in Marie's method is the Product Form Decomposition of the

Petri net according to Definition 2.3.1. For a SISO cut in a MG system, these

conditions are obviously satisfied.

Let R t be the l-th subsystem with n t customers present, Al(n t) the state dependent arrival rate and K the total number of customers. The open system in

isolation is denoted by R_9 as shown in figure 5.2 and is analyzed in isolation under

a state dependent Poisson arrival process.

Suppose that Al(n t) is known, then R_ can be analyzed. Note that although

the system is nominally open, the arrival rate to the system is zero, once K customers

are in the system. For the case of a single cut in MGs, the closed system has the

structure of an aggregated net system. Now the transition rj (with firing rate _t(nt))

is the generator of the arrival of customers to SNi, i # j.

Particularly, we are interested in the steady state probability Pr(n I) of ha_'ing

n t customers in the open subnetwork. Then the conditional throughput vto(n _) can

be.obtained as [5[ar79].

Pr(n I 1) l 1

vM( ) = 1) er(n ) nt = 1,...,K

As in FEA, the service rates #t(nt) are set to the conditional throughput.

The problem is now reduced to finding the state dependent arrival rates At(n t)

for the open subnetwork R_. To this end, the partitioned system (now in product
79

Figure 5.3: Birth-Death Process

form) is analyzed with the rates obtained from equation (5.5) (either by using mean

value analysis [RLS0] or simply the analysi_ of the CTMC).

2(- t) = u%' + 1)P(_ + 1) ,_, (5.6) p(nt ) = 0,..., K - 1

Having computed the state dependent arrival rates the iteration can be repeated.

An alternative interpretation of Marie's method for single cuts in MGs is the

following: We analyze ASi with a state dependent arrival rate )_(n), n - 1 ... K

and obtain the conditional probabilities of having n customers in the subsystem.

We then interpret ASi as a general Markovian birth-death process as illustrated in

Figure 5.3.

Here, the states represent the number of customers in SNi. In Figure 5.3 the

state dependent arrival rates _(n) (birth rates) are known, while we are interested in

computing the state dependent service rates #(n) (death rates). From the underlying

CTMC of ASi, we can compute the conditional probabilities of having n customers

in SN_.

By formulating the local balance equations on the CTMC of the birth-death

process in Figure 5.3 at w-th station (flow in = flow out):

_(w- 1)Pr(w- 1)= u(w)Pr(_), w= 1...K

From eq. (5.7) immediately follows

P_(_- 1)

tt(w)= Pr(w)

(5.7)

_(_- 1), w = 1...K (5.s)
8O

which is just eq. (5.4) in slightly different notation. _(w) is going to be the generator

for the arrivals of ASj, i.e., it denotes the conditional throughput of SN_.

As with many iterative methods, the uniqueness of the solution cannot be

proven although numerical experience has shown that a unique fixed point does

indeed exist, although convergence sometimes presents a problem [BD90].

For the case of K = 1 (independence of M/G/l/1 queue), equation (S.4) and

(5.6) are equivalent to equation 4.3 for RTA, i.e., for K = 1 both methods are

equivalent.

5.4 Delay Equivalence by Y. Li and M. _Voodside

The work of Li and Woodside [LW91], presents an alternative approach to

compute the approximate throughput for stochastic MGs. In their work, the original system is also split into subsystems and a delay equivalence (DE) criterion

is used for throughput approximation. Their service rates for aggregated subsystems are marking dependent. In a very recent work [W'L91], the authors present

an application, while the computed service rates are made constant in order to get

acceptable robustness.

Consider the two aggregated net systems in Figure 5.4 (called auxiliary systems

in Woodside's paper). In AS1, a customer suffers two delays as he cycles through

the system: a delay in SN1 itself (D1), and a delay through the aggregation of SN:

(d2 represented by q12 and r2 with firing rate #2)- Similarly dl and D= represent the

delays in ASs (note that d represents the delay in the aggregate transitions r, while

D represents the delay in the unaggegated subsystems, i.e., SN).

Let K be the customer population (i.e., the number of tokens in the basic

skeleton), E[qii] the expected number of tokens in place q_.j, ,_'i the throughput of

•ASi and #_(1) the state dependent firing rate of ri when l customers are present in

its input place qji. The delays can obtained by Little's law:
81

q12

, , "0. SN2i

,ti SN_ [,_ i r2 q21 [

,.,.__----.g

Figure 5.4: Aggregated (Auxiliary) Net Systems

Dz = K-E[ql:] (5.9)

xl

= E[q,2] (5.10)

zl

92 = g-E[q2_] (5.11)

Z2

dz = E[qu,] (5.12)

Z2

The key to Woodside's method is, that in steady state the delay a token suffers

in the subnet is the same as in the aggregate. For example, the delay of a customer

in SNx of ASz should be the same as in q2z and rl in AS2. Therefore

D1 = d_ (5.13)

D_ = d2 (5.I4)

5.4.1 State Dependent Firing Rates

Let us first consider the case when the ag_egated transition has a state dependent firing rate [LW91]. The basic approach is to first compute the equivalent

delay for l = 1 (1//_(1)) where l is the customer load. This information is used to

compute 1/#(2) and successively up to 1/p(K).

(A) Case: K = I

Here,

= = Z (5.15)

X, _2
82

(from Little's law, ,_l = #2 E[q12]). Now with d2 = D2 and writing the equation in

iterative form,

similarly for #_'+*)

/ (,+1) _(") 1

2 = 1- E[qn](") = DS,V, ¢'' (5.16)

h(_+,)= Jc'l(_) 1

* 1 - E[ql=](') = Df N,`'' (5.17)

Property 5.4.1 For the particular case of a single customer, delay equivalence and

response time approzimation are equivalent.

Proof." Let us consider AS2 at a given iteration: We know X2 and Pl and we have

to determine #2. We can either solve equation (4.3) or simply write:

1 1 1

-- = --+ -- (5.18)

X2 #1 #2

rearranging terms yields

X2#t

us = (5.19)

#1 - ,t"2

We have to show that equation (5.16) and (5.19) are the same, i.e.,

X2u X=

= (5.20) u,-x2 1-E[q=1]

From [GH85], we know that the steady state probability of an M/G/c/c and

an M/f_f/c/c queue are the same if the means of the servers are the same. Therefore,

we can write E[q1._] and ,I"2 as if they were obtained by solving an iSf/:_f/I/l queue.

E[ql=] = #2 and X2 = #=Ux (5.21)

_, +/_= Pl + #=

By substituting eq. (5.21) into (5.20), the equality follows. •

Based on the previous results, the following property holds:

Property 5.4.2 Because o/the independence o/the M/1/G/1/1 queue, for the case

of a single customer (K = 1), RTA, Marie's method and delay equivalence yield the

same results.
83

(B) Case: K > I

In the previous steps, the firingratesof r for n = 1 ...L - 1 customers have

been determined. The present step isconcerned with finding/.t(L).

Substituting X1 = E.=I L _2(_).Pr[m(q12)=_] _toequation(5.10)

E[q121 (5.22)

d2 = g2(L) " Pr[rn(qn)=Ll + _,_ g2(rt) . Pr[rn(q,2)=n]

As before, set d2 = D2 and by using eq. (5.11) the iterative equation foUows:

_2(r+*)(L)= pr_r,[m(q1_)=L] 1 (

Similarly, ,_+I)(L)is _venby;

L ECr_[qn] - E'"[q21]- ,_=r.-1 _1/_2(n)" Pr (_)[rn(q12)=n])

//, (L) = pr(_,[m(_21)=L] L--_n] - .=1 _//1(n)- Pr(')[m(q21)=n]

(5.23)

(5.24)

The iteration has to be performed for L = 1 ... K.

Note that for the computation of g(2"+')(N) the quantities Pr[rn(qn)=n], n=

1... K and E[q12] are computed with AS_ while E[q2_] is computed with AS2 (similarly for/,t[_+_)(N)). At the current iteration, quantities from the analysis of both

subnets are used.

5.4.2 State Independent Service Rate

We now examine DE for the case of state independent firing rates for the

ag_egated transitions [W'Lgl].

Substituting X_ = #5" (1 - Pr[m(q12) = 0]), into equation (5.10)

d2 = E[ql,.] (5.25)

_t2-(1 - Pr[rn(q_2) = 01)

As before, set d,. = D2 and by using eq. (5.11)

K - E[q2_] E[qn]

= (5.26)

X2 #2" (1 - Pr[rn(q_) = 01)
84

Rewriting eq. (5.26) in iterative form yields

Similarly

E'[q,_] X; (5.2T) /_+1= K- E'[q2x] (1 - PF[m(q12)= 0])

/_[+1= K- E'[qn] (1 - Pr'[rn(q21)= 0]) (5.25)

As for the case of state dependent firing rates, quantities from the analysis of

both subnets are used.

The iterative process is now straightforward. The structural decomposition is

the same in all methods, only the computation of the new firing rate changes (step

5 in Algorithm 1: Quantitative Analysis of SISO cuts).

5.4.3 Comparison of Response Time Approximation and Delay Equivalence

In order to compare the two methods, it is useful to examine the solutions

when the iteration has reached steady state, i.e., X', = X2. From (5.10) and (5.11),

we have

E[qn] = If - E[q2,] (5.29)

and the first term of eq. (5.27) disappears. In order to interpret the results, we will

indicate with superscripts how the quantities are computed, e.g., X# 51 indicates

that ,'Y1 is computed by" solving the underlying CTMC of AS1. Using equation

(5.29), (5.27) simplifies to:

x_ s=

/_2 = (1 - Pr[m(q,=) = O]"_s,) (5.30)

In steady state, the above formula also holds for RTA, ezcept that Pr[m(q12) =

0] is computed based on the basic skeleton, while DE uses Pr[rn(q_=) = 0] as computed with AS1. This derives from the fact that in RTA we reduce the subnets to

the basic skeleton.
85

RTA

Marie

Delay

Equiv

FEA

use of 68

X

X

use of ASt.2

X

X

X

s

Iterative

X

X

X

Information used

Throughput

Marking probabilities

Throughput and

Marking probabilities

" Throughput as a function

of number of customers

Table 5.3: Comparison of the Stochastic Approximation Methods

5.5 Conclusions

FEA is computationally efficient, although its accuracy may be low due to the

previously outlined problems. Its accuracy can be improved by aggregating only

one subnet to a flow equivalent transition.

It has been shown that Marie's method can be used in the context of decomposition of MGs by a single cut because the basic skeleton is in product form.

DE works directly with the delay in the paths and does not reduce or make the

abstraction to a basic skeleton. In this thesis we use a response time approximation

based on the throughput of the aggregated net systems, i.e., we reduce our system

to the basic skeleton (an M/M/1/K queue). In steady state, the results using both

methods are different.

For the case of a single customer, RTA, Woodside's method and Marie's

method yield the same result due to the independence of the M/G/1/K queue.

Table 5.3 summarizes the characteristics of the four presented methods.
CHAPTER 6

Examples for Marked Graph Systems

6.1 Introduction

In this chapter we give several numerical examples for the SISO and SIMO

cuts introduced in the previous section. We compare the results obtained with

single level and hierarchical Response Time Approximation (RTA), Flow Equivalent

Aggregation (FEA), Marie's method and delay equivalence.

6.2 Fork/Join Queueing Network

The net system on top of the hierarchy in Figure 6.1 shows a Fork/Join QN

with blocking. The exact value of its throughput is 0.22866, computed with the

underlying CTMC which has 33480 states using the tool SPNP [DBCT85].

{}.2.1 Single SISO Cut A

We define the SISO cut A through P4 and ps (not shown in Figure6.1). We

now follow the steps for the analysis outlined in Algorithm 1.

(1.a) The net is partitioned (Fig 6.1) by means of the canonical SISO cut (A through

P4 and Ps. AS1 is defined by the transitions left of the cut, while .AS2 is defined

to the right of (A-

(1.b) A solution for LPP3 (Section 4.3.2) is:

M(p_) = 2, M(p4) = 3, M(ps) = 3, M(/_) = 2, M (Ps) = 3, M(p_2)= 3, M(p_a) = 2.

i.e., the customer load at cut A is K=M(q:I =p4)=3.

(1.c) In order to show the rapid convergence of RTA (Section 4.3.3), we arbitrarily

select the service rate of r2 as #0 _ 20.0.

86
87

Figure 6.1: Fork/Join Queueing Network with Aggregated Net Systems Obtained

from the Hierarchical Decomposition at Cut _s and _c (Service Times: sl = 0.33,

a2=2, s3=l, 84=4, s5=2, s6=0.5, sT=l, 8s=l, 89=i, 810=1 ,sn=l)

(2) The results of the iterations axe shown in Table 6.1:

6.2.1.1 Response Time Approximation

In order to show the rapid convergence of the method, the iterative results

are shown in Table 6.1. The initial value of/z ° - 20.0 is far off the final value of

0.59674.

The error of the throughput introduced by the aggregation is -0.14%, while

.A,St has only 372 states and .A5'2 has 360 states. By finding proper initial values

for the iteration (Algorithm 1, Step 3) the ma.'dmum cycle time in SN1 is 1.278,

therefore/z ° = 0.7826. This way, we reduce the number of CTMCs which have to be

solved for the same precision by one.
88

l

2

3

_! = 20.0; Xcxac t = 0.22866

0.23281 0.23281 0.22444 0.60422

0.22852 0.23749 0.22824 0.59674

0.22833 0.23759 stop

Table 6.1: Results Using RTA for SISO Cut A at Fork/Join QN

6.2.1.2 Flow Equivalent Aggregation

In this example the firing rate of AtSz is the same for all possible customer

populations. Here, the merged interface places form a selfloop with r2, i.e., all

tokens are trapped. Table 6.2 shows the conditional throughputs as a function of

the number of tokens.

conditional throughput 0.3430406 0.232809

tangible state space 93 90

Table 6.2: Results Using FEA for SISO Cut A Fork/Join QN

By substituting the values in Table 6.2 into the basic skeleton, the throughput

is computed to be equal to 0.20313, i.e., the error introduced by the FEA is -11.2%.

6.2.1.3 Delay Equivalence

Table 6.3 shows the results using state independent delay equivalence ag_egation (Section 5.3. The number of iterations required to reach convergence is higher

than in RTA, while the accuracy is comparable (the introduced error is 0.I8%).

6.2.2 SIMO/MISO Cut B

The resulting net systems are shown in Level 1 of the hierarchical decomposition presented in Figure 6.1 (AS] and A$_). A solution for LPP5 (Rule 2 in Section
89

r

1

2

3

4

5

6

7

8

/_ = 1.0; /J_ = 1.0; Xe_ac t = 0.22866

0.342741 0.167135 0.146091 0.189616

0.186681 1.310073 0.232623 0.226793

0.219454 0.561616 0.227288 0.247681

0.236306 0.624189 0.228989

0.227493 0.638?46 0.229293

0.236558

0.238451

0.229019 0.627703 0.229065 0.238784

0.22928T 0.630124 0.229117 0.238509

0.229066 0.630256 stop

Table 6.3: Results Using Delay Equivalence for SISO Cut A at Fork/Join QN

4.4) is:

M(pl) = 2, M(ps) = 3, M(pv) = 2, M(p6) = 3, M(p_2) = 3, M(plj) = 2.

i.e., the customer load at the cut is: K = 2.

6.2.2.1 Response Time Approximation

For this cut, the error introduced in the throughput is 0.18%..AS_ has only 48

states, while .AS_ has 3240 states. The large difference in the size of the respective

state space is due to the fact that the cut is not balanced in the sense that it

does not produce aggregated net systems with roughly the same state space (which

is obviously bad from a computational point of view). Nevertheless, it has been

considered for illustrative purposes. Table 6.4 shows the iteration results.

r

1

2

3

4

0.23125

0.25172 0.22851

0.25248 0.22906

0.25251

p_ = 20.0

0.23122 0.68693

0.22919 0.67390

0.22909 0.67343

0.22908 stop

0.21317

Table 6.4: Results Using RTA for SIMO Cut B for Fork/Join QN
90

6.2.2.2 Flow Equivalent Aggregation

Similar to the previous example, the conditional throughput of AS_ and .A,5"_

(i.e.,the firingrate for rl and r_) isthe same for allpossible customer populations

as shown inTable 6.5. The throughput obtained using FEA isequal to 0.19712, i.e.,

the error introduced by the aggregation is-13.79%.

ASI AS2

conditional throughput (n - I) 0.43619 0.22941

tangible state space (n = i) 15 1080

conditional throughput (n = 2) 0.46801 0.23123

tangible state space (n = 2) 27 1440

Table 6.5: Results Using FEA for SISO Cut B in Fork/Join QN

6.2.2.3 Delay Equivalence

Table 6.6 shows the results using state independent delay equivalence aggregation (Section 5.4) at cut B. The error introduced by the aggregation is 0.05%.

r

1

2

3

4

5

6

.ui(1)-" 1.0 1.0

X;

0.431732

0.230400

0.221138

0.347934

0.740182

0.632954

0.215488

0.229558

0.254321

0.228680

0.230585 0.639804 0.228756 0.251808

0.22.8572 0.641122 0.228770 0.252058

0.228755 0.640600 0.228765 0.252084

0.241750

0.254576

Table 6.6: Results Using Delay Equivalence for SISO Cut B at Fork/Join QN
91

6.2.2.4 Marie's Method

Table 6.7 shows the results obtained using Marie's method for both cuts. The

error introduced by the aggregation is -0.09% for cut A and 0.23% for cut B.

7"

1

2

4

5

6

All initial values 1.0

X(cut A) X(cut B)

0.193942 0.201954

0.236053 0.245348

0.227551 0.227600

0.228805 0.229971

01228446 0.229053

0.229177

Table 6.7: Results Using Marie's Me_hod for SISO Cut B at Fork/Join QN (throughput shown for the basic skeleton system)

6.2.3 Hierarchical Decomposition using RTA

........ Figure 6.1 also shows the hierarchicaldecomposition. The marking of the

aggregated nets are obtained from Algorithm 2 (Section 4.6). Cut B partitionsthe

original net system into the ag_egated net systems ASI and .AS 1 at Level I. On

the next level,only AS_ ispartitionedby C to form AS_I and .AS_2. X2 iscomputed

at Level 2 using .AS_t and AS_2. The initialrate for/_o was chosen as 20.0. The

iteration resultsare shown in Table 6.8.

r

1

2

3

4

= 200

0.46760 0.22376

0.66209 0.23042

0.67181 0.23058

0.67199 stop

0.46735 0.27148

0.24255 0.25512

0.23097 0.25459

0.23059

Table 6.8: Results Using Hierarchical Decomposition at Fork/Join QN
92

The original net system has 33480 states, while .ASI has 48 states, AS221 has

144 states, and .AS222 has 90 states. The error introduced during the aggregation

is 0.84%. During the iterative process, .AS_ was analyzed a total of 4 times while

.AS21 and AS_2 were analyzed 7 times.

6.2.4 Comparison

Table 6.9 shows a summary of all results for the throughput of the Fork/Join

QN, as well as the largest state space of an aggregated subnet encountered during

the appro.,dmation.

original net: X - 0.22866, State Space - 33480

Cut A

Method Throughput Error State Space Iterations

RTA 0.22833 -0.14% 372 3

FEA 0.20313 -11.16% 93

Marie's Method 0.22845 -0.09% 372 5

Delay Equivalence 0.22907 o.18% 372 8

RTA

FEA

Marie's Method

Delay Equivalence

,,

Hierarchical RTA

Cut B

0.22908

0.20313

0.22918

0.22907

0.23059

o.18%

-13.79%

-0.23%

0.05%

0.84%

3240 4

1440

3240 6

3240 6

144

Table 6.9: Comparison of the Approximation Results for Fork/Join QN

With the exception of FEA, all methods show very good accuracy at a significant computational saving. RTA shows the fastest convergence.
93

6.3 Four Task Pipeline

We now analyze the MG in Figure 4.7 whose structure (but not the marking)

represents a four task pipeline found in concurrent software environments. The

example is inspired by the example in Y. Li's paper [LW91]. It is analyzed with two

different initial markings:

Mo(1) : This is the marking shown in Figure 4.7. The exact value of the throughput

for M O) is equal to 0.513195, computed with the underlying CTMC which has

4500 states (using the tool SPNP [DBCT85]). Note that/_0, p21 and p2= are

implicit places for the initial marking shown.

Mo(2) : Now M(p21)= 1, M(p4)= 1 and M(p19) =2, while all other markings remain

the same. None of the places in the net is now implicit. The exact throughput

of this MG system is 0.490362, while the underlying CTMC has 2916 states.

The service times are as follows:

. " • sl -" 0.20, s2 = 0.20, s3 = 0.10, s4 = 0.10, Ss = 1.00, ss -- 0.10, s7 ----0.20, Ss = 1.20,

Sg=0.10, s10=0.09, s11=0.90, s12"-0.08, s13=0.07, s14---0.15, 81S=0.10, 31S-- 1.00.

6.3.1 Single SISO Cut B

We define the SISO cut B through pT and PiT as shown on top of the hierarchy

in Figure 4.7. The aggregated net systems are shown in the first level of the decomposition (AS_ and A,S_). The net in Figure 4.7 is already shown with a solution

for LPP3, i.e., the number of tokens in q21 (q21 = plz, Figure 4.7) has already been

maximized. The customer load at cut B is two.

6.3.2 SISO Cut B, Response Time Approximation

In order to examine the speed of convergence of RTA as a function of the

initial values of the iteration, we study the system for different values/_o of r2 in

0;; PO(9[t _ ..... ,,.
94

r

1

2

3

4

1

2

3

4

_l r-l

.098578

.481131

Initial Marking Mo(1)

IterationResults

.784181

.615319

Initial Marking M0 (2)

for _=0.i

.557147

.503148

0.89741

1.03136

.098764

.471021

.845246

.705199

.512319

.485372

.707871

.753004

.498699 .607624 .499849 1.03956 .482587 .697578 .483479 .755988

.499609 .607214 stop .483300 .697094 .483357 .756180

IterationResultsfor _=1.0

.495060 .609250 .500553 1.03780 .525254 .664642 .474687 .769652

.499416 .607301 .499708 1.03990 .486492 .694906 .482804 .757049

.499647 .607197 stop .483553 .696922 .483314 .756248

.483362 .697052 stop

1 .570988

2 .503844

3 .499886

4 .499673

Iteration Results for/z°= I0.0

.572760

.605292

.607089

.607186

.483818

.498832

.499616

stop

1.07983

1.04209

1.04013

.577380

.495621

.484168

.483402

.579211

.688439

.696502

.697025

.446575

.481142

.483208

.483340

.811949

.759651

.756414

.756207

Table 6.10: Results Using RTA for SISO cut B with Different Initial Values of r2

at Pipeline System

,4,5'_.Table 6.10 shows the iterativeresultsfor the two initialmarkings. The error

of the throughput introduced by the aggregation for Mo (z)is-2.71%, while AS_ has

75 states and A_'_ has 180 states.For Mo(2)the error of the throughput introduced

by the aggregation is-1.45%, while AS_ has 81 states and .AS_ has 108 states.

From the resultsof the differentinitialvalues in Table 6.10 we see that initial

values "close" to the finalones can reduce the number of iterationsby one.

6.3.3 SISO Cut B, Flow Equivalent Aggregation

Table 6.11 shows the conditional throughputs obtained with all possible customer populations.For M0{1), the throughput obtained using FEA is equal to 0.38897,

therefore the error introduced by the aggregation is -24.2%. For MoTM, the approximated throughput is 0.37797 with an error of -22.91%.
95

Initial Marking/l/Io (IJ

conditional throughput (n = 1)

m

tangible state space (n = 1)

ASl

0.50267

AS

0.62190

20 60

conditional throughput (n = 2) 0.57433 0.62190

tangible state space (n = 2) 50 60

Initial Marking MoTM .,4Si

0.57742

36

0.57742

36

conditional throughput. (n = 1)

=.

tangible state space (n = 1)

conditional throughput (n = 2)

tangible state space (n = 2)

"AS2

0.55699

36

0.55699

36

Table 6.11: Results Using Flow Equivalent Aggregation for SISO Cut B at Pipeline

System

6.3.4 SISO Cut B, Marie's Method

Table 6.12 shows the resultsobtained by using Marie's method forboth initial

markings. All initiM values were taken to be one.

AU initial values 1.0

r A'(M_ 1)) X(M_ 2))

1 0.455636 0.428801

2 0.5197860.508209

3 0.499322 0.479429

4 0.505794 0.490432

5 0.503682 0.486397

6 0.504346 0.487948

7 0.504129 0.487379

Table 6.12: Results Using Marie's Method for SISO Cut B at Pipeline System

(Throughputs shown for the Basic Skeleton System)

The error introduced by the aggregation is -1.77% for AIo_1) and -0.61% for

/1/Io(2} . Convergence did not present a problem.
96

6.3.5 SISO Cut B, Delay Equivalence

In Table 6.13 the iteration Results Using state dependent delay equivalence

with the initial marking M0(1) are presented. The values of/_i are now a function

of the number of customers n in its input place. In a previous step, the firing rates

with a costumer load equal to one were determined to be: /11(1 ) = 1.00010 and

/_2(1) =0.60499. These values were also used as the initial values for/_°(2) and g°(2)

respectively. The second (fourth) column shows the throughput obtained with AS1

(.AS2) at the current iteration. In the third (fifth) is the new firing rate of #2(2)

(/.t1(2)) which is going to be used in the next iteration in ASx (AS2).

p1(1) = 1.00010 p2(1) = 0.60499

x( x;

1 0.495072 1.214634 0.498700 0.623275

2 0.506690 1.122975 0.505133 0.617402

3 0.502279 1.100289 0.503109 0.611861

4 0.501071 1.129935 0.501163 0.616615

5 0.502640 1.135421 0.502834 0.615856

6 0.502921 1.116811 0.502569 0.615088

7 0.501956 1.127689 0.502300 0.615153

8 0.502524 1.125427 0.502323 0.615761

9 0.502407 1.126214 0.502536 0.615194

Table 6.13: Results Using State Dependent Delay Equivalence for SISO Cut B and

Mo(1) at Pipeline System

The error introduced by the approximation is -2.1%. Note that the initial

values of/_(2) and/_2(2) are already very close to their final values, still it takes 9

steps to achieve convergence. If initial values for p°(2) = #°(2) = 1.0 are used, the

method takes 29 steps to converge. For the same net structure, but for different

initial marldn_, we were not able to find initial values for which state dependent

delay equivalence converges. This method is not robust, i.e., convergence is depends

very much on the initial marking and is often difficult to achieve.
97

Table 6.14 shows the results for state independent delay equivalence. For Mo(1)

the introduced error is -2.44% (-2.49% for Mo(2)).

F 1.o = 1.0

Initial Marking Mo (I)

7"

1

2

3

4

5

6

r

1

2

3

4

5

6

0.530136 0.461693 1.243986

0.517779 0.609419 0.500626 1.016688

0.497029 0.613985 0.502582 1.048344

0.500566 0.608701 0.500315

0.500950 0.609637 0.500720

0.500684 0.609703 stop

InitialMarkingM_ 2)

1.051924

1.049439

X[ g_(2) X_ /_(2)

0.525254 0.543843 0.432350 0.801388

0.493443 0.699546 0.483973 0.705709

0.470429 0.680914 0.479159 0.740314

0.479483 0.675243 0.477630 0.736225

0.478459 0.678178 0.478425 0.735028

0.478157 0.677693 0.478294 0.735662

Table 6.14: Results Using State Independent Delay Equivalence for SISO Cut B

and M (1) at Pipeline System

6.3.6 Hierarchical Decomposition

Figure 4.7 shows a hierarchical decomposition by the cuts A, B and C. The

marking of the aggregated nets are obtained from the procedure outlined in Algorithm 2 in Section 4.6 (with the shown marking, the number of tokens in all interface

places is already maximized). Cut B partitions the original net system into the aggregated net systems AS_ and AS_ at Level 1. On the next level, .AS} is partitioned

by A to form AS_I and AS_2, while AS_ is partitioned by C to form AS_I and

AS]2. X_ (9='2) is computed at Level 2 using AS_I and AS_2 (AS_I and AS_2 ). The

iteration results are shown in Table 6.15, while a comparison of the state space and
98

the number of iterations is shown in Table 6.16. All initial rates were chosen to be

10.0.

rl

1

2

3

1

2

3

4

Initial Marking MoI1)

_lr--1 /z_ -1

0.548352 0.5499239 0.466712 1.056116

0.477591 0.5672174 0.474982 1.034340

0.475409 0.5679352 0.475307 1.033512

_1 r-J.

Initial Marking M0(2)

0.568095 0.5698403 0.441979 0.8121824

0.486450 0.666298 0.473333 0.7622874

0.476178 0.6735495 0.475281 0.7590964

0.475474 0.6740473 0.475411 0.7588733

Table 6.15: Results Using Hierarchical Decomposition for Pipeline System

Tangible State Space

marking ash .4sh As , tsh

MoTM 5 30 45 12

Mo(2) 9 27 27 12

Number of Evaluations

marking A,.¢_ AS_ AS_, .,48_2

31(o_) 6 4 7 4

MoTM 10 10 10 7

Table 6.16: Tangible State Space for Hierarchical Decomposition and Number of

Evaluations

From Table 6.16 we see that the state space is reduced by more than two orders

of magnitude: For the original marking, the error introduced during the aggregation

is -7.3% (-3.13% for the modified initial marking).
99

6.3.7 Comparison

Table 6.17 shows a summary of the results. The iterative aggregation methods

introduce a very small error into the final result, and at very reasonable computational efforts. The only method that poses major convergence problems is state

dependent delay equivalence, which often fails to converge. RTA converges particularly fast, even when using "bad" initial values for the iteration. FEA introduces an

unacceptably large error in the aggregation. This is due to the strong dependence

of the mean completion time on the interarrival process.

Initial Marking M0_1_

Method Throughput Error State Space

orioHnal net 0.51319 m 4500

RTA 0.49967 -2.71% 180 3

FEA

Marie's Method

Delay Equivalence

(state dependent)

Delay Equivalence

(state independent)

0.38897

0.50413

0.50253

0.50068

-22.91%

-1.77%

--2.1%

-2.44%

6O

Iterations

180 7

180 9

180 6

Initial Marking Mot2)

original net 0.49036 w 2916

RTA 0.48334 -1.45% 108 4

FEA 0.37797 -24.20% 36

Marie's Method 0.48738 -0.61% 108 7

Delay Equivalence 0.478294 -2.49% 108 6

(state independent)

Table 6.17: Comparison of the Approximation Results for Pipeline System

6.4 Kanban System

The following is an application taken from the field of manufacturing systems.

Figure 6.2 shows a 6 stage Kanban system.
i00

.°

, \ /\ .

cl c2 c3 c4 c$ c8

Figure 6.2: Six Stage Kanban System

The just-in-time philosophy for the control of manufacturing systems consists

of producing just the needed parts at each production stage in just the right time.

Kanban control is a way to implement a just-in-time manufacturing system. A

Kanban is a ticket that accompanies a part through several stages of the production

system. When a part of a given stage is consumed by the succeeding stage, the ticket

is sent back to trigger the production of a new part. Petri nets have been shown

to be well adapted to provide a unified modeling of decision-free Kanban systems

[M'FDD89] and most models can easily be represented by MGs.

In the MG system of Figure 6.2, places fi (i = 1... 6) represent the available

space in the work area (number of Kanban tickets), p/ the parts awaiting service,

wi the parts which have finished processing at transitions tpi and ci the available

number of machines at each stage. In this MG system, we assume that a transition

enabled K times in a marking M (i.e., g = max{k I M > k Pre[t]}) works

at conditional speed K times it would work in the case it was enabled only once

(infinite server" semantics) [RP84, Zub85, HV85].

Here c_ limits the enabling degree of twl, i.e., twi is enabled min{M(pi), M(c_)}

times. For the sake of simplicity we assume that all machines have exponentially

distributed processing times with unity mean. The exact throughput is 1.496715,

computed with the underlying CTMC which has a total of 93843 states (18040

vanishing and 75803 tangible markings using the tool GreatSPN [Chi85]).
i01

For single level decomposition, the net is split into two subnets by a single SISO

cut (a defined through the interface places P4 and f4. As before, ,4S1 is defined to

the left of the cut while AS2 is defined to the right of _a. By solving LPP3 (Section

4.3.2, we find that a possible solution for the marking of the interface places is:

M(f4) = 4; M(p,) = 0, i.e., the customer population is It'= M(q21 = f4)= 4.

6.4.1 Response Time Approximation

Table 6.18 shows the results using RTA..AS1 has a total of 1285 states (380

vanishing and 905 tangible markings) while .AS2 has a total of 335 states (210

vanishing and 125 tangible markings). The introduced error is -1.47%.

The reduction is by a factor of 73 (=93843/1285) when the total state space

is considered and by a factor of 47 (=18040/380) if only the tangible state space is

considered.

r 2'_-'

1 1.573246

2

3 1.474889

= 10.0

1.574060 1.308050 1.706777

1.480033 2.058081 1.471149 1.690805

2.072899 1.474685 1.690446

Table 6.18: Results Using RTA. for Single Cut at Kanban System

t}.4.2 Flow Equivalent Aggregation

Similar to the previous example, the throughput of .AS1 is the same for all

possible customer populations. Here, the merged interface places form a selfloop

with r2, i.e., all tokens are trapped. Table 6.19 shows the conditional throughputs

as a function of the number of tokens.

The throughput obtained using FEA is equal to 1.26180, i.e., the error introduced by the aggregation is -15.70%.
102

Conditional throughput A3"l = 1.573250

Number of tangible States = 50, n= I,2,3,4

n conditional throughput AS2 State Space AS2

i 0.956173 34

2 1.587574 42

3 1.652232 50

4 1.697872 58

Table 6.19: Results Using Flow Equivalent Aggregation at Kanban System

6.4.3 Marie's Method

Table 6.20 shows the resultsobtained by using Marie's method (Section 5.3).

All initialvalues were taken to be one.

All initial values l.0

r X

1 1.839026

2 1.408609

3 1.523192

4 1.484177

5 1.495074

6 1.491380

7 1.492412

8 1.492063

Table 6.20: Results Using Marie's Method at Kanban System (Throughput Shown

for the Basic Skeleton System)

The error introduced by the aggregation is -0.31%. Convergence did not

present a problem.

6.4.4 Delay Equivalence

Table 6.21 show the results using state independent delay equivalence aggregation (Section 5.4). For this example, convergence depends on the initial values of
103

the iteration, e.g., using/_o =/_o = 1.0 delay equivalence does not converge. The

number of iterations required is significantly higher than in RTA, while the accuracy

is comparable (the introduced error is -0.34%).

In RTA and delay equivalence, the structure and marking of the aggregated net

systems are the same, therefore the state space is also identical. Delay equivalence

uses the conditional probabilities of customers in both aggregated net systems at the

current iteration. We believe that this makes delay equivalence less robust, as an

unfortunate combination of initial values can cause unstable oscillations.

/_o = 1.0 /t o = 4.0

0.995363 28.328484 1.694930 1.685173

1.473015 1.223924 1.113728

r

1

2

3

4

5

6

7

8

9

I0

11

12

13

14

15

16

17

18

19

20

21

22

2.283125

1.560674 1.776035 1.388686 1.461586

1.370634 4.147622 1.650823 1.673865

1.469159 1.718533 1.367792 1.979070

1.537082 1.854180 1.414690 1.646106

1.459144 2.740666 1.579719 1.689514

1.474462 2.038670 1.466410 1.830199

1.512249 1.973474 1.449564 1.727731

1.486418

1.482097

1.498054

1.492434

1.487435

1.492805

1.492700

1.490069

1.491431

1.492092

1.491079

1.491248

2.313612

2.157780

2.067290

2.183312

2.171140

2.118218

2.149813

2.160998

2.139305

2.144376

2.152818

2.146035

2.145147

1.523348

1.493647

1.473355

1.498943

1.496441

1.485076

1.491957

1.494324

1.489700

1.490793

1.492596

1.491149

1.491677 stop

1.713405

1.769801

1.748789

1.731198

1.750136

1.749755

1.740347

1.745181

1.747555

1.743924

1.744530

1.746062

Table 6.21: Results Using Delay Equivalence at Kanban System
104

6.4.5 Hierarchical Decomposition using RTA

Figure 6.2 also shows the cuts leading to a hierarchical decomposition. The

markings of the aggregated nets are obtained from Algorithm 2 (Section 4.6). Cut B

partitions the original net system into the aggregated net systems ASI and AS_ at

Level 1. On the ne,'ct level, only .A,SI is partitioned by C to form AS_x and AS_:.

X, is computed at Level 2 using AS_x and .AS_. The initial rate for/_o was chosen

as 20.0. The iteration results are shown in Table 6.22.

r

1

2

3

t ° = 20.0

t,i xf

1.49467 1.42838

1.52824 1.45317

1.52968 1.45422

1.49408 2.69747

1.45576 2.66603

1.45433 2.66471

Table 6.22: Results Using Hierarchical Decomposition at Kanban System

Here, the state space is reduced by more than two orders of magnitude: AS11

has a 22 states, ASx2 has 230 states while JtS2 has 58 tangible states. The error

introduced during the aggregation is -2.84%. The aggregated net systems have to

be analyzed repetitively, e.g., during the iterative process, AS_ was analyzed a total

of 3 times while AS_I and AS_ were analyzed 6 times.

6.4.6 Comparison

Table 6.23 shows a summary of the results.

With the exception of FEA, all methods show good accuracy. RTA provides

a significant computational saving by showing the fastest convergence. In this example, the initial values for delay equivalence have to be chosen carefully in order

to achieve convergence. The number of required iterations for this method is high

when compared to RTA.
105

original net: 9:' = 1.496715, Tang. State

Method Throughput Error

B.TA 1.47469 -1.47%

FEA 1.26180 -15.70%

Space = 75803

State Space Iterations

380 3

58 m

Marie's Method 1.49206 -0.31% 380 7

1.491677 -0.34% 380 22

230

Delay Equivalence

Hierarchical R.TA 1.45422 -2.84% 3

Table 6.23: Comparison of the Approximation Results for Kanban System

6.5 Conclusions

In this chapter we have presented numerical results for the approximation

methods which were introduced in the previous chapter. For the particular examples,

we can draw the following conclusions:

• FEA has the lowest state space of the CTMC and is therefore computationally

very efficient. The drawback is obvious: in the examples, there exists a strong

dependence of the service time on the arrival process, therefore as outlined in

Section 5.4.3. the accuracy can suffer.

• Delay equivalence shows good accuracy, provided it converges. The choice of

proper initial values is critical for convergence. This is particularly true for

state dependent delay equivalence, which failed to converge in almost all cases.

This method uses the token distribution of both aggregated net systems at the

current iteration. In the initial step, these distributions have to be determined

with the initial values of the iteration. A poor choice will lead to instabilities

(and eventually non-convergence) in the iteration.

• RTA shows similar accuracy as delay equivalence, but at a greatly reduced

computational cost. RTA is insensitive with respect to the initial values and is

the one which requires the least amount of iterations. R.TA does not make use
106

of the token distribution in the subnets, and only uses the throughput. We

believe, that this accounts for the good robustness of the method. Hierarchical

decomposition can possibly lead to a larger error.

• Marie's method shows the best accuracy for all SISO cuts, with a reasonable

computational cost (about twice as many iterations as RTA). Note that Marie's

method uses all information about the token distribution in the aggregated

net systems, i.e., it uses more information than RTA. On the other hand,

convergence is slower.

The savings in the state space immediately leads to a great saving in the time

required to obtain the solution. For the Kanban example, the time needed on a SUN

4/330 SPARC with 16 Mb RAM to compute the exact solution of the original system

was around 2 h. 30 m while the approximate solution computed with 3 iterations

was obtained in less than 1 minute using SPNP [DBCT85].

At this point it is important to state that a Kanban system with 8 stages

generates such a large state space that the computation of the exact throughput is

impossible because of the lack of memory. Its decomposition into two agooTegated

nets of 4 stages plus the environment transitions (rl and r2) leads to a computation

in less than two minutes!
CHAPTER 7

Macroplace/Macrotransition Nets

7.1 Introduction

In the previous chapters we have introduced approximation methods for

stochastic MGs. The modeling power of this net subclass is restricted, because

decisions are forbidden. In this chapter, we introduce a new class of Petri nets,

Macroplace-Macrotransition-nets (MPMT-nets), a subclass which allows limited

choice, concurrency and sharing of resources [DJS92]. MPMT-nets have a greatly

increased modeling power over SMs and MGs by iteratively combining Macrotransitions (where a single transition has been expanded to a MG) and Macroplaces

(where a place has been refined to a SMs). By exploring the qualitative properties of

MPMT-nets, we show that the previously introduced approximation technique for

SISO cuts are applicable to this subclass of PNs.

7.2 MPMT-nets: Motivation and Definition

Even if some practical systems can be modeled by Fork/Join queueing networks with blocking or closed queueing networks (thus essentially strongly connected marked graphs state machines, respectively), the interleaving of choices and

synchronization is fundamental in many cases. For example, the structure of flow

line models with unreliable machines are neither MGs, nor SMs (e.g., see Figure

8.2).

A traditional way of interleaving choices and synchronization in a controlled

way is given by Free Choice nets. The behavioral and structural analysis of FC nets

is particularly elegant and well understood (see [ES90a] for a survey). Nevertheless,

classical schemes in manufacturing in which two or more processes share a common

k

107
I08

resource (e.g., a robot) cannot be modeled with FC net systems.

Here we introduce a different combination of the basic structures of SMs and

MGs. The practical modeling with this new subclass of net systems has some

advantages in the field of manufacturing with respect to the use of the well known

subclass of live and bounded free choice net systems allowing e.g., the limited sharing

of resources and some synchronization at choice places.

The new net subclass is called MPMT-nets, because they can be obtained by

using the macroplace (MP) and macrotransition (MT) reduction/refinement rules.

The MP-rule is strongly related to the concept of SMs [Sil81], while the MT-rule is

its reverse-dual and therefore, strongly related to MGs (see [ESg0a] for an integn:ated

consideration of both rules).

The MP (hiT) rule consists of the substitution of a given SM (MG) subnet

by a single place (transition). Only a particular case of MP (MT) reduction rule

is considered here: a unique way-in place (transition) and a unique way-out place

(transition) e.xists.

Way-in places are those that can be used to "enter" into the subnet, and

way-out places are those through which we can _leave" it. More formally:

Let .h/' = (P', T', F') be a subnet of N" = (P, T, F)

[i.e., F' = F N ((P' x T') U (T' x P'))]:

(a) p' 6 P' is a way-in place of H' iff "p' _ (T \ T') # 0

(b) p' 6 P' is a way-out place of N" iff p'" _ (T \ T') # _}

where (T \ T') means the set T minus the set T'.

"Way-in and way-out transitions are defined analogously.

Definition 7.2.1 Let N" be a subnet of N'. H'= (P', T', F') is reducible to a place

if..
109

(

3

d b

Figure 7.1: Macroplace Reduction Rule

2

Figure 7.2: Macrotransition Reduction Rule: Disregarding the Marking, the Subnet

is the Reverse-dual of that in Figure 7.1

(a) AI" is a state machine containing one way-in place, p_, and one way-out place,

p'o (p_= p'__ possible).

(b) For every tt E P', there ezists at least an F-path from:

(b.I) the way-inplace p_to 11.

(b.#) 11 to the way-out place, 11o.

The next definition expresses the standard notion of substitution of a net by

a place, a'. See Figure 7.1 for an example.
ii0

Definition 7.2.2 Let (H, Mo) be a system and .b rt = (P', T', F,) a subnet of.A[ =

(P, T; F) reducible to a place. The net A/', = (P,, T,; F,), with:

• P. = (P \ P') u (,_}

• T,=(T\T')

• F. = (F n ((P. × T.) u (T. × P.))) UF., where:

- (t,=)_f. iff (t,p_)_F

-(_,t)_F. iff (_,t)_F

is a macroplace reduction of A/', and m is the macroplace that replaces A "_.

system (A/'., Mr> where Af. is the reduction of N and lkI. is given by:

The

• M.(p) = Mo(p) lip # ,_

• M.(_) = Z._P, Mo(p)

is called a macroplace reduction of (K, Mo>•

The value of the macroplace concept lies in the following result [SilS1]: The

reduction of a macroplace preserves liveness and the bound of the places of the system.

Moreover, in our particular case (single way-ha/single way-out place), reversibility is also preserved. Therefore:

Property 7.2.1 The reduction of a macroplace preserves liveness, the bound of

places (thus boundedness} and reversibility.

At the structural level, the reverse-dual (i.e., reversing the arcs, chan_ng

places to transitions and vice versa) of the MP-rule is the MT-rule.

Definition 7.2.3 Let Af' be a subnet of H. A/" = (P', T'; F') is reducible to a

transition if:
iii

(a) A/"_ is a marked graph containing one way-in transition, t_ and one way-out

transition, to (t_ = to is possible).

(b) For every t _ E T' there ezists at least an F_-path from:

(b.1) the way-in transition, _, to t'.

(b.#} t' to the way-out transition, t o.

Definition 7.2.4 Let (N, Mo} be a system and A/" = (P',T';F') a subset of A/" =

(P, T; F) reducible to a transition. The net :V', = (P,, Tr; iF,) with:

• Pr = (P\P')

• Tr = (T \ T') tJ {O}

• F,=(fn((P, ×T,)tJ(T, xP,)))tJFo, where:

- (p,O) E Fo iff(p,_) e F

- (O,p) E Fo iff(to, p) E F

is a macrotransition reduction of.A" and 0 is the macrotransition that replaces Hr.

The system (iV'r, Mr} is called a macrotransition reduction of (:V', Mo) where:

Mr = Mo IP \ P' + g. Post(t;)

and K is the minimum number of tokens found in the different paths from t_ to to.

In other words, Mr is the restriction of Mo to the remaining places plus K tokens

per output place of to.

Figure 7.2 shows a macrotransition reduction. There exists one token in place

e, thus the unique path from transition 3 to transition 1 has one token and I( = 1.

The value of the macrotransition concept lies in the following result that basicaUy derives from MG systems theory:
112

(

ts E

(

t4

_6

\

,)

I]

(

/

tlO

(a) A shared resource is used by two different processes (one with internal

concurrency)

t14 _ ]_69

(b) MT-reduction of the net system in (a)

7_ _ re9

(c) An MP-reduction of the System in (b)

Figure 7.3: The Original Net isnot Free-Choice, but MPMT (and simple)

Property 7.2.2 fn the absence of an unmarked circuit (or p-semiflow) in .A/", the

reduction of a macrotransition preserves liveness, boundedness (but not the bound

of the system} and reversibility.

Now the MPMT-nets can be recursivelydefined as follows:

Definition 7.2.1 A macroplace/macrotransition (MPMT} net is an ordina_ net

such that, disregarding the conditions on the markin# in the MP- and MT-rules, it

can be reduced to a simple self-loop of one place and one transition by recursively

applz/in# the MP and MT r_duction rule (Definition 7._.J and 7.2._}.
Token inlti_Uze Get PLtt Descriptioa Get ID Un|osd Psrt

NC Dowllo6d . Progrsm Imtl_Use

J / 1IC

(a) Petri net representation of a controller [AJD90b]

(b) MP-reduction of the net system in (a)

(c) MT-reduction of the net system in (b)

Figure 7.4: An MPMT and FC net system

113

Figures 7.3 and 7.4 show the reduction (and refinement) processes leading

to two different MPMT-nets. The reduction (refinement) also verifies the marking

conditions on the MP- and MT-rules, therefore, both net systems are bounded, live

and reversible.

Property 7.2.3 The r, verse and the dual (thus the reverse-dual also) of an MPMTnet is also an MPMT-net.

Figure 7.5:

()

A Reversible Non-live MPMT-system
114

The net in Figure 7.3 is MPMT but not FC. The net in Figure 7.4 is both

MPMT and FC.

How do we recognize if a given net is an MPMT-net? We need to find the

subnets of a net which can then be reduced to a place or to a transition. For the

reduction to a place, in [Sil81] an efficient (polynomial) algorithm for this purpose

is given. It consists of first removing all transitions with more than one input or

one output arc, which splits the net into one or more SMs. Then simple recursive

procedures can be applied to each connected subnet to check conditions (b.1) and

(b.2) from Definition 7.2.1. Now, for the reduction to a transition the same procedure

is applied, but now first all places with more than one input or one output arc are

removed. This splits the net into one or more MGs. Conditions (b.1) and (b.2)

of Definition 7.2.3 can be checked by using simple procedures on each connected

subnet. The entire process can be done in polynomial time.

The net in Figure 7.1 (Figure 7.2) is analyzed by applying first the reduction

of subnets to a transition (place).

7.3 Basic qualitative properties of MPMT-nets

From the definitions it is not difficult to observe that MPMT-nets are strongly

connected. For SMs, strong connectedness guarantees the e.,dstence of live markings

(i.e., structural liveness) and for MGs the boundedness for any initial marking (i.e.,

structural boundedness). On the other side, SMs are conservative nets (i.e., 3Y > 0

s.t. yr. C = O, thus, structurally bounded), while MGs are structurally live nets.

Combining these facts, the following important structural properties hold.

Property 7.3.1 MPMT-nets are:

1. Ordinary and strongly connected.

_. Conservative (thus, structurally bounded).
115

3. Structurally live (then also consistent, i.e., 3 > 0 s.t. C. X = O, because

they are also conservative}.

The basic structural properties of MPMT-nets have already been presented.

Behavioral properties can be studied in a straightforward way.

Property 7.3.2 Let AI" be an MPMT-net. (N, Mo) is a live net system iff all psemiflows are marked:

W>>_O s.t. yT.c=0 , YT-Mo>0

Corollary 7.3.1 Liveness of MPMT net systems can be characterized in polynomial

time: (A/',Mo) is live iff there ezists no unmarked P-semiflow. Analytically, (H, Mo)

is live iff there ezists no solution for the following linear system:

yT.c=o

Y _>0 (7.1)

yT.Mo =0

Corollary 7.3.2 Let .g" be an lkIPMT-net and .hf_ its reverse. (A/', Mo) is live iff

(.A/',., Mo) is live.

Property 7.3.3 Let (Af, Mo) be a live MPMT-system. The three following statemerits are equivalent:

i) M E R(A[', Mo), i.e., M is reachable from Mo.

ii) M = Mo + C . 6, with M E zW", _ E z_V".

iii) B T. M = B T. 3"Io, with B a basis of left annullers of the incidence matrix

(i.e., B r . C = O) and M E SV _

According to the above property, M E R(N', Mo) iff Mo E R(jV', M). In other

words:
116

Corollary 7'.3.3 Live MPMT-systems are reversible, but the converse is not true.

(see Figure 7.5).

The bounds of places can be computed in polynomial time using Linear Programming Techniques [MJ88]:

Corollary 7.3.4 Let (./V',M) be a live MPMT-net system. The behavioral and

structural bounds of place p coincide:

B(p) = max{M(p)lM E R(A/', M0)} =

SB(p) = max{M(p)lM = Mo + C. _ >_ 0,_ > 0} (7.2)

Property 7.3.3 relates directly to Theorem 3.4.3, while Corollary 7.3.4 is equivalent

to Corollary 3.4.3 for MGs.

7.4 Well-formed SISO cuts

While in MGs, every SISO cut was a well-formed cut, in MPMT-nets we have

to restrict the types of cuts which we can perform. Specifically we only cut the net

at persistent places, i.e., places where Ip'l = 1, i.e., once a token has entered an

interface place, the routing out of it is deterministic.

Definition 7.4.1 (Well-formed SISO MPMT cut) A cut _ is well-formed if

IqGI= Iq ,l= 1.

With the above properties of structural liveness, reachability and the marking

bound of places, we can apply the results of the previously introduced methods

directly to MPMT-nets. Note that in general the vector of the visiting ratios can

not be computed from the net structure.

As a final comment, we can now give a particular case when to use FEA in

MPMT-nets. From Property 2.3.1, we know that FEA leads to exact aggregation
i17

in PFQNs. Therefore, if we aggregate a macroplace (i.e., a subnetwork which is in

product form) by flow equivalence, we will be able to replicate at least the MCT

of the subnet. Nevertheless as we will see, the change in the coefficient of variation

might still introduce considerable error in the aggregation.

7.5 Summary

In thischapter we have introduced a new subclass of Petri nets with extended

modeling capabilities over SMs and MGs. Having established the structural similarity of MGs and MPMT-nets for the marking bounds and the reachability of

markings, we can use any of the previously discussed approximation methods for

SISO cuts in MPMT-nets without any modification for the iterative part. This will

be demonstrated in the next chapter.
CHAPTER 8

Examples for SISO Cuts in MP_/IT-nets

8.1

nets.

Introduction

In this chapter, we present some numerical examples for SISO-cuts in MPMTThe first example considers the performance analysis of manufacturing transfer

lines (or simply flow lines) which has received considerable attention in the literature

due to their economic importance. In the first survey of this area [Koe59], the earliest

papers date back 40 years, while today a vast amount of literature exists. In the

most recent survey [DG91] 180 papers are cited which are directly related to their

modeling and analysis. In the context of Petri nets, flow lines with reliable machines

(FLR.Ms) can be modeled by marked graphs (MGs), while flow lines with unreliable

machines (FLUMs) involve choice (i.e., the break down of machines) and therefore,

can only be modeled using MPMT-nets.

An analytic solution for the very particular case of a short two machine, one

buffer flow line with exponentially distributed machining, failure and repair time has

been found [GB81]. In [CG87] this analytic solution of a short line has been used to

devise an efficient approximation for longer flow lines whose exact analysis by solving

the underlying CTMC becomes computationaUy intractable due to the problem of

state explosion. Another approximation method is described in [DDL89] which

employs an approximation based on continuous material flow. These approximation

methods are problem specific, i.e., only suitable for the analysis of flow lines. For

this example, we compare Response Time Approximation (lZTA), Flow Equivalent

Aggregation (FEA), Delay Equivalence (DE) and Marie's method.

In the second example, we examine an MPMT-net, whose structure is that

118
119

Figure 8.1: Flow Line with N Machines

of an uninterpreted dataflow graph [KBB87]. Here we use a hybrid approximation

approach. In the first step a nmcroplace is reduced to a single transition by FEA.

In the second step, the reduced net is analyzed by RTA and Marie's method and

the accuracy is compared.

8.2 Modeling of Transfer Lines with Petri Nets

Figure 8.1 shows a flow line with N machines. Parts enter through Mt and

leave through MN. We denote the i-th machine as -_Ii and the buffer which lies in

between M'i and/l/Ii+l as B_. C'i is the capacity of Bi, i.e., the total number of parts

which can be stored in between Mi and Mi+1. The current buffer content is denoted

by c_ while _" denotes the vector of the buffer capacities.

We now give a short review of flow line models and how they can be modeled

using Petri nets. We concentrate on FLUMs with operation dependent failures, i.e.,

failures that can only occur when the machine is working. Time dependent failures,

i.e., failures which do not depend on the machining operation and which can occur

even if the machine is blocked or starved are not considered, but could also be

incorporated into the Petri net model. Figure 8.2 introduces the notation for all of

the transfer line models.

A common assumption of these models is that the first machine is never starved

and the last machine is never blocked. The machining operation of Mi is represented

by transition mi with rate Ai, failure by fi with rate/Ji and the repair by ri with rate

0i. Note that the failure-repair model is a Macroplace. PB_ represents Bi. If PM,

is marked, Mi is currently idle (i.e., starved), whereas _T¢'i is marked if the machine
120

__/3_ "' "__/3__ "' "_/3_ "' "___7

Figure 8.2: Blocking After Service (BAS) Flow Line

Figure 8.3: Blocking Before Service Parts not Occupied (BBS-PNO) Flow Line

is currently processing a piece. P,,_ is marked if the machine is down while bli is

marked for a nonzero period of time if Ms is blocked. Where no confusion arises,

the names of places and transitions are omitted from the Petri net models.

In [DG91], flow line models were divided into the following categories:

• Blocking After Service (BAS)(Figure 8.2):

ifat the instance of completion of a part at Mi the part cannot be put into

the downstream buffer Bi because itis full,the machine ks blocked. _Ii will

become operational only ifa part kstransported from Bi to Mi+I freeingone

buffer space.

• Blocking Before Service,Parts Not Occupied (BBS-PNO) (Figure 8.3):

here the part is not admitted into Mi ifno buffer space is available in Bi.

The BBS-PNO line with buffer capacity _" + 11has the same throughput as

a BAS line with capacity _ (11isa vector of appropriate size whose entries
121

hi1 _ PMz __ PM= PM4_

_ 1Pa. bt2 _m, P., b13 _/_ a Pa= .

Figure 8.4: Blocking Before Service Parts Occupied (BBS-PO) Flow Line

are all one). This result was first established by Perros eL al. [OP86] for the

case of exponential timing, and has also been shown for the case of general

distributions [DLT91]. Note that in BBS-PNO, ifPM, is marked, Mi is starved

of blocked.

• Blocking Before Service, Parts Occupied (BBS-PO) (Figure 8.4):

In this model, the part is admitted into the machine, but operation does not

start until a space in the output buffer is available.

Actually BAS is most likely to be encountered in manufacturing systems [DG91],

e.g., in metal cutting operations there is no reason why a part should not be allowed

into the system even if no output buffer space is immediately available.

Flow lines with reliable machines can be constructed by simply deleting the

failure circuit, i.e, fi, rl and Pt_ from all machines.

8.2.1 Choong and Gershwin Approximation in Flow Lines

The basic idea is to decompose an N machine transfer line into N- 1 modules

[CG87] consisting of the buffer Bj, M_,(j) (the upstream machine) and Ma(j) (the

downstream machine), which can analytically be solved by the method outlined in

[GB81]. In Figure 8.5, the five machine flow line is decomposed into four modules.

Each of the modules is characterized by six parameters, three for each machine: A_,,

p,,, 8_, and A,_,/_a, 8d. The goal of the approximation is to find these 6 parameters

such that the pseudo-machines capture the upstream and downstream behavior of
122

__ Line (1)

Line (2)[_----__

Line (3)

Line (4)

Figure 8.5: Decomposition Method of Choong and Gershwin

the flow line, i.e., the rates with which parts are processed if the line upstream is up

(A{), the rate with which the upstream part of the line goes from the up to down

state (/_{)and vice versa (0_).A similardiscussionholds for A_, _ and 0_.

The stand-alone efficiency of a machine is given by:

(8.1)

P_ = 0i +/zl

In the line, the production rate will, in general, be smaller because there is a nonzero

probability that the machine is blocked or starved (or both). The efficiency E of

the machine in the line is therefore given by

El = Pl prob[c/_l > 0 and (c_ < Ci and M_ not blocked)] (8.2)

The conservation of flow implies that

E1 -- E2 =...EN-1 = EN (8.3)

If the probability of the event _machine blocked and starved at the same time is

small, equation (8.2) can be simplified to

Ei = pi(1- prob[c,_l > 0]- prob[c/< C, and M_ not blocked]) (8.4)
123

The next step is to examine A, _ and g in the modules and how they relate to the

machine parameters. From the examination of the interruption and resumption of

flow at the modules and together with equations (8.3)and (8.4)a set ofsixequations

per module can be derived, which then have to be solved iteratively.The method

breaks down ifthe line isstrongly unbalanced and p; _>_>pj.

8.2.2 Experimental Results: Three Machine Transfer Line

The flow lines which are analyzed in this section were previously described

and analyzed in [CG87]. The linesare of the type BBS-PNO, nevertheless,here the

flow hnes were modeled as BAS with the appropriate change in the buffer size as

outlined in Section 8.2.

As the convergence criterion,we chose that the throughputs obtained during

the iterationdo not change by more than 0.1%.

In order to interpret the results,it is useful to look at the Moment Generating Function of the time z ittakes to move a token from place Wi to bI_. The

moment generating function, T(s) can be derived by using the techniques outlined

in [GDZg0]. First we transform the macroplace into a construct where the conflict

isgiven by immediate transitionsaccording to Theorem 3.5.1 and is presented in

Figure 8.6.

The transformed macroplace forms a loop struc_.urc.I_VI(s) represent the loop,

while W'2(s) represents the _gain" afterthe loop as shown in Figure 8.7. First we

find the stochastic "transfer function" W1(s) of the loop given by {fi,ft,r}, i.e.,

two exponentials in seriestimes the probabilitythat path istaken.

w1(s)=

- + - e)

W2(s) isthe "gain" afterthe loop and issimply an exponential times the probability
124

,-(e)

(,_) A

'n_(+x_;)_' (,_+ _,)

r (0_

ft CA +/J)

Figure 8.6: Transformation of Macroplace in Unreliable Machines (Probabilities and

Rates of Transitions in Parentheses)

wl(s)

w2(s)

Figure 8.7: Loop Structure for Finding Moment Generating Function

the path istaken.

w_(s) =

_-(_+_)

The overall transfer function is given by

w:(8)

T(s) = 1- WI(_)

(8.6)

(8.7)

By substitutingequation (8.5)and (8.6)into (8.7),the moment generating function

isobtained:

_(0-_) (8.s)

T(8) = s2 _ s(A +/_ + O) + Ae

By differentiating the T(a) with respect to s, it is now easy to determine the first

two moments and obtain the mean and variance:

E[z] = 1 01_ E[z 2] = 2 A/_ + (0 + #)2 (8.9)

p = O+----_ e2A2
125

The coefficient of variation (CV) is a measure for the dispersity of the probability

density function (pdf) (for the case of an exponential pdf CV = 1.0). For the model

at hand, the CV is given by:

[ E[ x2] - E[z]2

CV[z]

E[z] 1 + (e2"A+ u)2 (8.10)

Note that with this information it is possible to transform a transfer line with

unreliable machines to a model with reliable machines by substituting the machining

rate in the FLRMs by the pdf obtained from eq. (8.8) [DGgl]. This corresponds to

finding the flow equivalent from MPi to bli. By doing so, we disregard the higher

moments of the pdf, by substituting an exponential where CV = 1.0.

The parameters of the three machine line are shown in Table 8.1. This short

flow line is analytically tractable (the underlying CTMC has 798 tangible states).

Rather than comparing our results to the simulation published in [CG87], we chose

to compare our approximation results for the short line to the exact solution of the

CTMC (which by and large confirms the simulation).

The results of the approximation are shown in Table 8.2. Cut _A traced

through PM, and bli introduces the single level decomposition as shown in Figure 8.8

(here only the cut, but not the aggregated net systems are shown). The first four

columns show the throughput obtained with the exact solution of the underlying

CTMC, together with the mean and coefficient of variation of the effective machining time of machine 2. Columns 5 and 6 show the number of iterations as well as

the error introduced by using RTA (remember that because of Property 5.4.2, all

presented iterative methods yield the same result for K = 1). Columns 8 through

11 show the results using a hierarchical decomposition approach as shown in Figure 8.8. We apply the first cut (_) at buffer 1 which results in AS_, AS_ and 6S _.

At the next level, we apply cut _2 at buffer 2 in ASg (now at level 1) to yield the

aggTegated net systems AS], , AS_, and 6S 2. Figure 8.8b shows the resulting tree

with the basic skeletons.
126

i Machine Parameters

0_ #_ A_ Pl C_

1 0.05 0.03 0.5 0.3125 2.38

2 0.06 0.04 - - -

3 0.05 0.03 0.5 0.3125 2.38

C

8

8

Table 8.1: Parameters for 3 Machine Transfer Line

Column 12 shows the resultsobtained by using FEA at the macroplaces representing the machine failures and repairs. In the three machines, Wt, ml, fi, PI_

and ri are substituted by a single transition with the stand alone machining rate Pl,

which is computed with equation 8.9. Finally, column 13 shows the results obtained

using the decomposition approach by Choong.

For the SISO cut _A, ASt has 59 tangible states (AS2 has 21). In the hierarchical decomposition, A,.9_ and .A,SI2 have 19 while ASIt has 180 tangible states.

8.2.2.1 Interpretation of Results

All approximation methods for the SISO cut at machine 2 yields a bad approximation of the throughput. Three factorscontribute:

1. The number of tokens at that cut islow (K = 1).

2. In [ABS84], Aggrawal et al.observed that response time preservation is an

effectivetechnique for low to moderate coefficientsof variation (CV < 5) and

a large number of customers (K > 5). From Table 8.2 we can see that the

error increasesrapidly as A2 (and thereforeC_) increases.

3. An additionalerror isintroduced by cutting the fastestmachine.

The resultsin Table 8.2 derive from an bIPMT-net. In order to examine

the source of the rather large error, let us now analyze a similar marked graph

system, i.e.,letus analyze a transferlinewithout failures(a marked graph!) whose
127

All Errors in %

Analytical Results SISO cut _A Hierarchical FEA Choong

RTA FEA RTA Marie MP

A2 P2 CV2 X r Err Err r Err r Err Err Err

0.1 0.06 1.3 .0598 2 0.2 -0.1 2 -0.2 4 0.0 0.i 0.1

0.2 0.12 1.6 .1154 3 0.7 0.8 3 -2.5 4 0.0 1.8 -0.2

0.3 0.18 1.8 .1592 3 2.0 3.2 3 -5.7 5 -0.4 7.9 -0.i

0.4 0.24 2.0 .1897 4 3.7 6.0 3 -8.2 7 -0.8 17.0 -0.3

0.5 0.30 2.2 .2093 4 5.9 8.0 3 -9.4 7 -I.i 23.4 -0.i

0.6 0.36 2.4 .2216 5 8.0 9.0 3 -9.7 7 -1.3 25.0 0.5

0.7 0.42 2.6 .2296 5 9.8 9.4 3 -9.7 9 0.8 24.3 0.5

0.8 0.48 2.7 .2350 5 11.4 9.4 3 -9.4 9 0.2 23.1 1.2

0.9 0.54 2.9 .2388 6 12.6 9.3 3 -9.1 9 0.0 22.0 1.6

1.0 0.60 3.0 .2416 6 13.5 9.2 3 -8.7 ii 0.7 21.1 1.7

1.2 0.72 3.3 .2454 7 14.9 8.9 3 -8.0 16 1.1 19.9 2.6

1.5 0.90 3.6 .2489 8 16.1 8.6 3 -7.3 19 0.0 18.6 3.1

1.6 0.96 3.7 .2497 8 16.5 8.5 3 -7.0 - - 18.3 3.2

2.5 1.50 4.6 .2538 I0 17.8 7.9 3 -5.7 - - 16.8 4.0

3.0 1.80 5.0 .2549 11 18.1 7.8 2 -5.4 - - 16.4 4.4

Table 8.2: Results for Three Machine Transfer Line

machining rates are the stand alone machining rates Pl (equation 8.9) of the three

machine, two buffer transfer line. Again, the SISO cut is performed at PM_ and bl_.

Table 8.3 shows the results (p2 is the effective machining rate of machine 2, this is

the value which was used in the marked _aph system).

From these results, we can draw two conclusions:

• The aggregation in the marked graph system leads to a reasonable accuracy,

i.e., the ma.'dmum error is only 5.1_. From a stochastic perspective, the

difference between the system corresponding to Table 8.2 and Table 8.3 is a

change in the coefficient of variation of the machining time. In the MPMT-net

(Table 8.2), the coefficient of variation is larger than one, while in the marked

graph system (Table 8.3), all coefficients of variation are equal to one.
128

Analytical SISO Cut (A

A2 P2 Xexact X_a Err

0.1 0.06 .0600 .0600

0.2 0.12 .1200 .1200

0.3 0.18 .1794 .1794 -

0.4 0.24 .2331 .2327 .1%

0.5 0.30 .2689 .2690 -

0.6 0.36 .2853 .2887 1.2%

0.7 0.42 .2916 .2986 2.4%

0.8 0.48 .2940 .3038 3.3%

0.9 0.54 .2950 .3067 4.0%

1.0 0.60 .2955 .3084 4.4%

1.2 0.72 .2961 .3101 4.7%

1.5 0.90 .2964 .3111 5.0%

1.6 0.96 .2964 .3112 5.0%

2.5 1.50 .2967 .3118 5.1%

3.0 1.80 .2967 .3119 5.1%

Table 8.3: Results for Three Machine Transfer Line Modeled with Reliable Machines

Therefore, we conclude that the poor accuracy of the SISO cut through the

MPMT-net is due to the large coefficients of variation of the equivalent machining times.

• From Table 8.3, it can be seen that as soon as A2 increases beyond 0.52 (where

the flow line is approximately balanced, i.e., Pl - P2 = P3 "- 0.3125) the error

increases rapidly. Therefore, we conclude that a cut at the fastest machine

can lead to a larger error.

The hierarchical decomposition using RTA also yields a substantial error. The

problem with Marie's method however, is that the number of required iterations is

larger than RTA and that it fails to converge for large values of A2 (A2 > 1.6). The

iteration simply cycles and does not converge.

Aggregating the macroplaces yields a poor result (column 12 in Table 8.2).

All we did here was to reduce the coefficient of variation to unity. As we reduced a
129

8 Machine Parameters

i 8i #_ Ai Pl CVi

1 0.3 0.03 1.5 1.3636 1.35

2 0.5 0.05 1.3 1.1818 1.20

3 0.1 0.01 2.0 1.8182 2.08

4 0.4 0.06 1.6 1.3914 1.38

5 0.3 0.04 2.0 1.7648 1.54

6 0.1 0.01 1.7 1.5455 1.95

7 0.3 0.02 1.2 1.1250 1.21

8 0.4 0.05 1.6 1.4222 1.34

Ci 8i

4 0.3

3 0.4

4 0.I

2 0.4

4 0.3

2 0.I

5 0.4

7 Machine Parameters

#i Ai Pl

0.02 0.20 0.1875

0.05 0.23 0.2044

0.01 0.30 0.2727

0.07 0.26 0.2213

0.03 0.21 0.1909

0.03 0.27 0.2077

0.06 0.26 0.2261

CV_ C_

1.04 2

1.06 2

1.22 4

1.08 2

1.06 2

1.40 4

1.07 -

Table 8.4: Parameters for Long Flow Lines

macroplace, the MCT of the subnet is independent of the interarrival process. Here

we see clearly that the dependence of the MCT on the interarrival time is not the

only factor which introduces an error in the ag_egation, but that the coefficient of

variation can have a strong impact on the throughput.

For the SISO cut _A, FEA yields a better approximation than the presented

iterative methods. This is coincidental and due to the interplay of the change of the

coefficient of variation of the interface transition and the dependence of the MCT

on the interarrival time of tokens. This relatively good results is specific to this

example, as we will see in the next section.

8.2.3 Experimental Results: Long Transfer Lines

Table 8.4 shows the machine parameters for the 7 and 8 machine line. Both

lines were analyzed by SISO cuts and hierarchical decomposition. Table 8.5 and 8.6

show the numerical results of the approximation. Finally Table 8.7 shows a comparison of the tangible state space for the SISO cuts.

The hierarchical decomposition of the subnets (Figure 8.9) yields a balanced

binary tree. For the ease of notation, the ag_egated net system containing ,l,Ii is
130

f:'

Table 8.5:

Top Level)

All Errors in %, DE = Delay Equivalence

Throughput using Simulation: X = 0.1333

Choong SISO M4 SISO B3, K = 4

RTA FEA

Err r Err Err

-2.2 4 2.9 -44.6

RTA Marie DE

r Err r Err r Err

2 1.8 4 0.6 20 3.0

FEA

Err

-13.5

Hier M Hier. Buff

RTA RTA Marie

r Err r Err r Err

5 6.6 5 9.8 10 2.2

Results for 7 Machine Flow Lines (Number of Iterations are Given at

All Errors in %

Throughput using Simulation: X = 0.8304

Choong

Err

0.0

siso M5

RTA FEA

r Err Err

6 7.4 -46.5

SISO B4, K = 2

RTA Marie FEA

r Err r Err Err

5 6.6 3 3.6 -25.0

Hier M Hier. Buff

RTA

r Err

11 0.4

RTA Marie

r Err r Err

4 0.2 9 7.1

Table 8.6: Results for 8 Machine Flow Line (Number of Iterations are Given at Top

Level)

State Space of (.ASI at SISO cuts

7Mach, M4 7Mach, B3 8Mach, B4 8Mach, 315

A,$1 AS2 AS1 AS_ A81 AS2 A81 AS7

2181 843 685 8133 9115 9793 32211 1429

Table 8.7: Tangible State Space for SISO Cuts at Long Flow Lines
131

denoted by .A_i. Obviously, the individual aggregated net systems for the hierarchical decomposition of the long lines have the same structure as in the three

machine case.

For the SISO cuts at the 7 machine line the quality of the approximation using

an iterative method (here K = 1) is quite good. The cut at B3 is superior to the

one at M4, due to the larger number of tokens in the circuit that is cut. Note, that

here the coefficient of variation of almost all machines is close to unity.

For the SISO cuts at the 8 machine flow line, the coefficient of variations of

the effective machining times are comparatively large which accounts for the error

at the SISO cut at 3Is. The cut at B4, is superior to the cut at 1_I5, because now

the number of customers is larger (C4 = 2) than in the cut at/1,Is. Again, Marie's

method yields the best SISO approximation while FEA is poor. In the 8 machine

example we did not use delay equivalence because of the high computational cost of

analyzing the underlying CTMC and the slow convergence of the method.

The results of the hierarchical decomposition are acceptable. Nevertheless

from just looking at the transfer line, it is not possible to infer which cuts (machines

or buffer) and which method (RTA or Marie's method) yields the best appro_mation.

From the above results it becomes clear that single cuts should be performed at

the buffers, because the number of customers (tokens) is usually higher than at the

machines. RTA often yields the fastest convergence, while Marie's method yields

the best results, although it sometimes fails to converge.

8.3 Uninterpreted Dataflow Graph

Figure 8.10 shows the structure of an uninterpreted dataflow as given in

[KBB87]. The net is MPMT and free-choice. For a physical interpretation of the

model, the marking has to be safe, nevertheless we analyze the net with the shown
132

.°-

+

(a) Cuts and Aggregated Net Systems

Original ne_ system

Level O: cut at B1

LeveI 1: cut at B2

(b) Binary Tree

Figure 8.8:3 Machine, 2 Buffer Hierarchical Decomposition

B_ (M_) S_ (,_,h) Bs (h/s) B7 (MT)

(S Machinelineonly)

(Level O)

(Level 1)

(Level 2)

Figure 8.9: Binary Tree for Aggr_ated Net Systems for Long Flow Lines
133

f

P18

................. ,_ '1"24

l__!Nr t P23 P24

IX) ( PI0

TI2 r" "I"29

PII ( T14

T13 _: I TI6 )PU

P13

Figure 8.10: MPMT-net with the Structure of Uninterpreted Dataflow Graph

(non-safe) in;tial marking. The interfiring times of the transitions are as foUows:

31 "_-- 34 --" 85 "-- $24 "- $25 = 1.0

36 ---_ 3"2' = $20 "-- "_21 "- 326 -- 2.0

311 -" 312 -- 313 "-- 314 _-" B15 = $16 "-- 3.0

317 "" 827 -" $28 "- 329 = 4.0

(8.11)

The probability switches at the immediate transitions is given by the following

probability rates:

t2 = 0.333333, L3 = 0.666667, ts = 0.857142, tlo = 0.142858 (8.12)
134

txs = 0.25, tls = 0.75, t22 = 0.50, t23 = 0.50

The vector of visit ratios can be computed according to equation (3.17), i.e., once

we know the throughput of any transition, we can compute the throughput of all

other transitions.

The visit ratio normalized for the throughput of Tx is given below:

TI (1.0000)

T4 (0.3333)

T5 (0.6667)

T6 (0.3333)

T_ (0.0556)

T11 (0.0556)

T12 (0.3333)

T13 (0.3333)

T14 (0.6667)

Tx5 (0.2500)

T_8 (0.7500)

T17 (1.0000)

T2o (0.2500)

T_I (0.7500)

T2_ (0.7500)

T25 (0.7500)

T26 (0.7500)

T2_ (0.7500)

T2s (1.5000)

(8.13)

T.. (0.7500)

In the firststep we apply flow equivalentaggregation at the subnet shown in

the dashed box in Figure 8.10. The subnet is a macroplace, i.e.,here the mean
135

TI5 TI6 ) P26

T17

"r28

Figure 8.11: Uninterpreted Dataflow Graph with Flow Equivalent Transition

completion time of a token does not depend on the interarrival process. Table 8.8

shows the state dependent service rates of rFEA in Figure 8.11.

In the second step, the resulting net system shown in Figure 8.11 is further

partitioned by _ to form SN, to the left of the cut and SN2 to the right of the cut.

By foUowing the SISO Decomposition rule (Section 4.3), we arrive at the aggregated

net systerm in Figure 8.12. The nets are already shown with a solution to LPP3,

here K - 3.

Table 8.9 shows the results of the approximation using Marie's method and

RTA. For both methods, the introduced error is under 2.0%. Again, Marie's method
136

f

_BA

PI

T1

PI4

q12

A81

q12

7"1

T29

Figure 8.12: Aggregated Net Systems for Uninterpreted Dataflow Graph
137

Table 8.8:

conditional throughput

tangible state space

k=l k=2

0.168224 0.280533

8 36

State Dependent Service Rates for rrs,_ in Dataflow Graph

Xe×ac t(T1) = 0.100859

RTA Marie

r Err r Err

3 -1.75% 4 -0.76%

Table 8.9: Iteration Results for Uninterpreted Dataflow Graph (Error in %)

shows improved accuracy at the expense of a higher number of iterations. The original net has 57015 states, while ,4,.91 has 261 states and ,4S2 has 84 states. Therefore,

the reduction of the state space is by over 2 orders of magnitude (57015/261 _ 264).

8.4 Summary

The results indicate that SISO cuts show good accuracy whenever the number

of tokens in the cat circuit is high. Potentially bad results can occur if K = 1.

For SISO cuts, in general Marie's method shows improved accuracy over RTA at

the expense of a higher number of iterations. Sometimes, Marie's method fails to

converge. Delay equivalence converges very slowly and does not show improved

accuracy over RTA or Marie's method.

As can be seen from the examples, FEA can lead to potentially bad results

because of two reasons:

1. Ifthe MCT depends on the interarri_zl process, the interaction between subsystems is ignored. This error occurs when cutting transfer lines at the machines.
138

2. The coefficientof variation of the servicetimes of transitionsstrongly influences the throughput (as could be seen at the 3 machine transferline with

reliablemachines example). But even the iterativemethod could not have

coped with that problem. For the particularcase considered the resultsusing

FEA or RTA would have been the same (Property 5.4.2).

Unfortunately, none of the presented methods is consistentlybetter than the

Choong and Gershwin method for the solutionof transferlines.Nevertheless,with

the above discussionitshould be clear that SISO cuts lead to reasonable accuracy

ifthe number of tokens in the cut circuitishigh.

The hierarchical decomposition shows varying degrees of accuracy and at

present it is not clear when it is advantageous to use SISO cuts or hierarchical

decomposition.
CHAPTER 9

Flow Equivalent Aggregation for SIiVIO-cuts in MPMT-nets

9.1 Introduction

In Chapter 7 we have introduced SISO cuts for MPMT-nets. In this chapter

we generalize SISO cuts for flow equivalent aggregation to SL_IO cuts. The basic

idea is to reduce a SIMO subnet to a state machine. We then formulate a reduced

net called the flow equivalent net (FEN) [JD91a, JD91b]. The FEN replicates the

input/output behavior of the SIMO subnet, as well as the expected delay a customer

suffers.

9.2 WeII-Formed SIMO MPMT Cut

Let us first formalize a well formed SIMO cut. Consider the net system with

the cut _ as shown in Figure 9.1.

, • q-j! ,

, ........... .............

Figure 9.1: MPMT-net with SIMO Cut _ and Interface Places

Definition 9.2.1 (_Vell-Formed S:h'VIO MPMT Cut) Let SN1 and SN2 be the

subnets generated by a SIMO cut _ to a MPMT-net, q12 the single (input) interface

139
140

and Q=I = with r = IQ=llthe multiple (output} interface. _ is

wetl-formediff."

1. IqT2l- 1 and Vq _ Q2_, Iq'l-- 1.

P. By the recursive reduction of macrotransitions and macroplaces, SN2 can be

reduced to a state machine.

Definition 9.2.1 (1) states that once a token has entered an interface place, its

flow is deterministic (the interface place ha only a single output transition), while

(2) essentially states that we are not aUowed to cut macrotransitions. Note that

the interface of a well formed SIMO cut satisfies the Product Form Decomposition

of Definition 2.3.1, i.e., once a token enters an interface, its routing is deterministic

and we are not allowed to cut at concurrent processes (macrotransitions).

SN2 can be structurally reduced to a state machine. Therefore, for the FEN we

can also choose any state machine representation, as long as there exists a directed

path from the input interface q12 to any of the output interface places in Q21, and

we do not violate condition (1) of Definition 9.2.1. Of course, we are interested in

a minimal representation in order to reduce the state space as much as possible.

Figure 9.2 shows two realizations.

q12 _ N_/ "t_ -qa.

-I "2 ?

(a)

•_ q_

q1:2//ff'_ .2

(b)

Figure 9.2: Two Equivalent Minimal Realizations for a S1MO Flow Equivalent Net

According to Theorem 3.5.1, both representations are equivalent. Note that

the realization in Figure 9.2.a introduces additional vanishing markings because P_l

is never marked for any nonzero period of time. The representation in Figure 9.2.a
141

directly shows the delay of the token (via the firing rate of r2) and the routing

probabilities (via the immediate transitions {t_l... t_x}). As we are interested in a

maximum reduction of the state space, we will use the realization shown in Figure

9.2.b which does not introduce vanishing markings.

Definition 9.2.2 (SIMO-MPMT Flow Equivalent Net) Let ¢V" = (P,T,F)

be an MPMT-net and _ a well formed SIMO-MPMT cut through the interface

places q12 and Q2x defining two subnets SNi = (Pi, Ti, F/) with i = 1,2, where

Q = {q12 o Q2x} with [Q2x[ = r as shown in Figure 9.1. The structure of the FEN

is given by:

= .. =

-- q21, i--l...r

(9.1)

as shown in Figure 9.2.

The goal of the quantitative analysis is to find the state dependent firing rates of

_'_, _(n), i = 1 ... r, n = 1... K, where K is the maximum number of customers

in SN2.

By reducing SN2 to the FEN, the original net system (H, Mo) leads to the

flow aggregated net system, _'S = (.T'.A/', Mo) as shown in Figure 9.3. Structurally

speaking from .A/', SN2 is reduced to the FEN (Definition 9.2.2). The structural

reduction process is formalized by the following rule.

Rule 3: SEVIO-FEA Reduction Rule

1. Structure: _jV" = (Px, T, F), is a flow aggregated net, where:

.P=P1

•
142

Figure 9.3:SN1 with Substituted Flow Equivalent Net Forming _'S

• P = F_u({q12} ×_)u(_ × Q2_); [_ q_ =" _,Q_ =_']

2. Marking:

Let &----"/" be a solution to the following linear programming problem:

maximize 7_7[(q12)

subject to 7f_ = Mo q- C • _ > 0

_>0, :2%>0

(LPP6)

where C is the incidence matrix of the canonical MPMT-net obtained from

the ori_nal net and cut. The initial marking for the flow aggregated net is

the projection of _ on _'Af (Definition 3.3.2 in Section 3.3).

The maximum number of customers K ira SN2 is given by the marking bound at

the single interface place K "- B(q12) = _(q12).

Property 9.2.1 (SIMO-MPMT Reduction Rule) Let (A/',.AAo} be a live

MPMT-net.

1. For the reduction from the original net system to the flow aggregated net system, the bounds of the places a r_ preserved:

B(p) = B(p), vp _ P,

_. Liveness in the flow aggregated net system is preserved.
143

Proof." Itisa direct consequence of the reduction of the SIMO subnet by recursive

application of the MP and MT rules,as well as Corollary 7.3.4. The transformation

of the marking empties the least-loadedpaths from the input interfaceto the output

interface places in the subnet which is being reduced, therefore we maintain the

marking bound of places. Thus, the livenessof the system isalso preserved. •

9.3 Quantitative Aspects

During the FEA aggregation, we replace a subnet SN2 by a flow equivalent net

(Definition 9.2.2). In the quantitative analysis, we have to determine the conditional

throughput through the output interface places of SN2 as a function of customers

n in the system, n - 1...K. The subnet is analyzed in short circuit by feeding

the tokens which exit through the output interface back into the input interface via

the immediate transitions t_l.., t_l as shown in Figure 9.4. This way we keep the

number of customers in SN2 constant.

....... :_

Figure 9.4: Feedback Construct for Flow Equivalent Net NFE N

Rule 4: SIMO-MPMT Feedback Construct Let _ = {t_...t_} as shown in

Figure 9.4. The feedback construct is given by:

1. Structure: A/FEN = (]_2, T, F), is a feedback construct, where:

(a) P =/'5

(b) _=T_u_
144

(c)__= _ u (Q_,x _)u_ x {q,_});(=_q_= _',Q_=*_)

i.e., "t_ = q_l, t_" = q12, i = 1...r as shown in Figure 9.4

= Marking:

Let _J" be a solution to the hnear programming problem LPP6. The initial

marking for the SEVlO-MPMT Feedback Construct is the projection of _ on

A/FE N with the exception of q12 (the marking of a single interface wiU be used

to vary the number of customers in the system).

We are now ready to formulate the algorithm for the quantitative analysis:

Algorithm 3: Quantitative Analysis of _Vell=Formed SIMO=MPMT Cuts

1. Select a well formed SIMO-MPMT cut

2. Generate the flow aggregated net systems _,5' (Figure 9.3) by using the SIMOFEA Reduction Rule and the feedback construct by using the SIMO-MPMT

Feedback Construct Rule as shown in Figure 9.4.

3. Analyze the feedback construct in Figure 9.4 for n = 1... K and obtain the

conditional throughputs Xi(n) of t_, i = 1... r and n = 1... K.

4. In _S, set the the firing rates /z_(n) equal to the conditional throughputs

obtained in step 3, i.e.,

Iz_(rt)=Xi(rt), i= l...r, n= l...K (9.2)

5. Analyze _'S by solving the underlying CTMC and obtain the desired performance measures.
145

Figure 9.5: Example of MPMT-Net with Indicated Well-Formed SIMO-Cut.

q12 = P35, Q21 = {p20,pl4,/hs}

9.4 Example for SIMO-MPMT Cut

Figure 9.5 shows the example of an MPMT-net (but not FC) without a physical

interpretation. The dashed box indicates the SIMO cut and the resulting SIMO

subnet SN2. Let us first verify that _ is indeed well-formed by eliminating the

macroplaces and macrotransitions until SN2 is reduced to a state machine. By

visually examining the net (or by using the algorithm outlined in [Si181]), it is

straight forward to check, that MT1 - {tu, t12, t.13} and MT2 - {tg, tl0} form

macrotransitions. After the reduction of the macroplace {P2, t2,p3, t3), the set of

transitions formed by MT3 - { tl, t4, ts, t6, tr} also forms a macrotransition. Figure

9.6 shows the structure of the resulting state machine. Note that the indicated cut

is the only possible well-formed cut to the system.

Let us now step through Algorithm 3: Quantitative Analysis of Well-Formed

SIMO-MPMT Cuts:

1. The cut is already selected and well-formed.

2. Before generating the flow aggregated system .T'S and the Feedback Construct,
146

MT1

f"_ l

MT2

MT_

Figure 9.6: Transformed Subnet SN2 in State Machine Form (Macrotransitions are

Shown Dashed)

vl ql 1 .,

_2 / // N .8

Figure 9.7: Flow Aggregated System _S for MPMT-Net with SIMO-Cut

(K- _T(q,2) - 4)

we have to solve LPP6. A possible solution is:

.

= 4, M(p.z)=M(ps)=M(pIo)=M(PIa) (9.3)

-- M(pls)=M(pls)=M(p:s)=M(pm)=M(p_) (9.4)

_'5" and the Feedback Construct with the computed initial marking from LPP6

are shown in Figure 9.7 and 9.8 respectively. Now the number of customers

MCq,:) = MCpas) = 4.

We now vary the number of customers in the system from n = 1... 4. Table 9.1

shows the conditional throughputs of t'2 obtained by varying the number of
q12

147

Figure 9.8: Feedback Construct for MPMT-Net with Sl_[O-Cut (Number of Customers Shown: M(ql_) - 1)

customers in the system, i.e., by varying/PI0q12 = 1... K, as well as the tangible state space (column 5).

1

2

3

4

0.167907

0.274374

0.036307

0.066655

0.036105

0.065204

0.337118 0.088924 0.085549

0.370327 0.102093 0.097113

tang. state space

52

168

376

68O

Table 9.1: Conditional Throughputs using Flow Equivalent Aggregation for SIMO

Cut at MPMT-net

4. In this step we substitute the conditional throughputs obtained in step 3 back

into _'S.

5. Table 9.2 shows the results of the ag_egation.

By ago_regating SN2 to a FEN, we have introduced very little error, while at the

same time reducing the tangible state space by a factor of roughly 37.
X.2l X_ X_ tang. state space

FEA 0.109755 0.024093 0.024274 88720

exact 0.108199 0.024497 0.024191 2424

error 1.4% -1.64% 0.3%

Table 9.2: Final Results Using Flow Equivalent Aggregation for SLMO Cut at

MPMT-net

9.5 Summary

In this chapter, we have introduced a new class of cuts to MPMT-nets, where

we allow the particular case of a multiple output interface. We require that the

interface has the characteristics of a server in a network that allows Product Form

Decomposition which was introduced in Definition 2.3.1.

_Ve have generalized the SISO interface for FEA to flow equivalent nets which

capture the input/output behavior of the SIMO subnet. For the shown example, the

accuracy of the method is good with a large reduction in the state space. However,

it has to be kept in mind, that good accuracy can by no means be guaranteed

especially if there exists strong dependence of the MCT on the interarrival times or

large coefficient of variation in the service time of transitions.
CHAPTER 10

Case Study of a Dual Arm Robotics System for Assembly

10.1 Introduction

In this chapter we present an application from the area of robotics as applied

to space activities. The demo consists of the insertion of a strut into a structure (i.e.,

two previously assembled struts). We will first describe the physical and hardware

configuration of the system. Then we will describe (in words) the task at hand and

present the Petri net model. We then apply flow equivalent aggregation which was

presented in the previous chapters.

The following description of the hardware and software components at the

Center for Intelligent Robotics for Space Exploration (CIRSSE) is adapted from

[LS91].

The Theory of Intelligent Machines, as proposed in [Sar79], describes a hierarchical organization of the functions of an autonomous robot into three levels: on

the lowest level is the Ezecution Level containing the hardware and basic control

functions, further up in the hierarchy is the Coordination Level integrating the capabilities of the intelligent machine across hardware systems, and an Organization

Level providing higher-level planning and reasoning capabilities. The nature of the

intelligent machine levels are different: The Execution Level provides the control

functions, the Coordination Level is characterized by scheduling and operations research issues, and the Organization Level employs artificial intelligence techniques

for task planning. A diagram of the intelligent machine is shown in Figure 10.1. The

model is organized according to the principle of Increasing Precision _q'th Decreasing Intelligence [SV77, SV88]. Detailed run-time information is maintained at the

lowest Execution Level and only relevant status information is propagated upward

149
through the hierarchy.

150

motion coordinator] [

motion controller I [

I manipulator hardware [

Organizer [

I

Dispatcher ]

Vision ] other [

coordinator [ coordinator [

Vision [ other controller [ controller

Vision hardware ] other hardware

Figure I0.1: Logical Model of Intelligent Machine

In the case study, the entire strut assembly operation is started by a single

assemble_strut command from the Organization Level to the Coordination Level

Dispatcher. Therefore, operation of the Organization Level is omitted from this case

study and only the execution and coordination level are considered.

10.2 Hardware and Software Configuration

The testbed hardware at CIRSSE consists of an 18-DOF manipulator system,

a 5 camera vision subsystem, their associated control computers, and several UNIX

workstations. The 18-DOF manipulator is built from two 6-DOF PUMA robots (a

PUMA 560 and a PUMA 600) mounted on a custom-built robot transporter with

two 3-DOF carts. The carts travel along a 12 foot linear track and provide 4-4-5 ° of

tilt and 4-150 ° of rotation. This manipulator subsystem is controlled by a Motion

Control System. For the experiment at hand, only one of the manipulators was used.
151

The vision subsystem has five cameras that may be used individually or pairwise, a laser scanner for pointing light, and a (VME-based) Datacube image processing system. Additional processing capabilities are provided by four UNIX workstations (predominantly Sun 4 and Sparc Stations) attached to an Ethernet which

connects all of the testbed subsystems.

As shown in Figure 10.1, the Coordination Level of the intelligent machine is

organized into a tree structure, with a Dispatcher at the root and multiple Coordinators at the leaves.

The Dispatcher is the first component of the intelligent machine that deals with

the machine as a )vhole. It coordinates actions across Execution Level functions,

e.g., move a manipulator to a position determined by visual sensing. The Dispatcher

defines the executions of the subtasks.

Petri nets are used to implement the event-driven environment of the dispatcher and the coordinators [wsg0]. In this case study, we concentrate on the

level of the hierarchy represented by the dispatcher.

10.3 Case Study

As a case study, the dispatcher realized the insertion of a strut into an existing

V-node. A schematic diagram of the experimental setup is shown in Figure 10.2.

In addition to the two cameras mounted on the wrist of the robot, two additional

cameras at the ceiling are used, which is not shown in the figure.

The task is as follows: After the initialization of the robot and the vision systern, the cameras mounted on the ceiling find the preassembled V-struts (essentially

two struts from a previous assembly operation). The robot then moves to the end

nodes of the V-strut lying on the table and determines the exact location of the

insertion point with the wrist cameras. The robot then proceeds to move to the

rack and picks up the strut to be inserted. After the pickup operation, the robot
152

on mov_ E car_

Assembly Table

Rack with Strut C

Figure 10.2: Setup for Strut Insertion

moves back to the table and inserts the strut into the V-strut to form a triangle.

Figure I0.3 shows a high level representation of the dispatcher. The four

Macrotransitions represent the following activities:

MTI: Initialize the robot and vision system and localize the V-strut (i.e., strut A

and B which have previously been assembled) with the ceiling camera.

MT2: Move to the nodes of the V-strut and use the wrist camera to obtain the exact

position.

MT3: Move to the rack, localize both ends of strut C with the wrist camera in order

to obtain its exact position.

MT4: Pick up strut C and insert it into the V-strut. Shut down the system.

As can be easily checked, the net in Figure 10.3 is not strongly connected. We

obtain a strongly connected net (an MPMT-net) by merging the places req_derno

and demo_complete. The net is now repetitive and the performance analysis can be
153

me CAM_done [

Figure 10.3: High Level Representation of Dispatcher

done. The obtained cycle time is the required time from the start to the finish of

the activities. Figure 10.4 shows a detailed representation of the ag_egated transitions. Note that all shown subnets with the exception of MTI are macrotransitions.

In MTI, place PPoready is a choice place. Transitions homed and not_home have

enabling functions attached to them, i.e., they will fire depending on the position of

the robot. Here we assume, that the robot is already homed before the demonstration. Therefore, the resulting model is a MG. The complete net can be obtained by

merging MT1 through MT4 at the places which bear the same label. As shown in

the figure, only places camera and req_demo are marked.

Table 10.1 gives a listing of all transitions, together with a brief description of

the associated activity and the required time to completion (i.e., the mean interfiring

time). The values were obtained e.xperimentally, by stepping the testbed through

the assembly operations and measuring the times.

The marking of the dispatcher is safe (i.e., 1-bounded) and no internal circuits

are present. We therefore choose flow equivalent aggregation for the approximate

analysis of the system. The dispatcher is partitioned into four subsystems MTi, i =

1...4. All cuts to the system are SISO. After the canonical transformation, a

solution to the linear programming problem LPP3 shows, that each of the subnets
154

should be analyzed with a single token.

Table 10.2 shows the results of the analysis. The original net has 62 tangible

states. The mean time to complete the demo was measured to be 207 seconds, while

the mean time as obtained by solving the underlying CTMC of the Petri net system

is 205.7 seconds. This is also the results of the flow equivalent aggregation therefore,

in this particular case the aggregation is exact.

10.4 Summary

From this case study, we can draw two conclusions:

• The agreement of the measured value of the completion time of the demo with

the value obtained by solving the CTMC is good. This substantiate the fact,

that we can use the stochastic Petri net model for the performance analysis.

In certain cases, FEA can lead to exact results. This comes as no surprise. In

the example in Section 5.2.3 we have already encountered a case where the

aggregation was exact. In that case, no internal loops or trapped tokens were

present, furthermore the marking was safe. This is exactly the same case here.

In this particular case, the MCT is independent of the interarrival process.

Furthermore, in cyclic queues with exponential servers and a single customer,

the cycle time is just the sum of the service times of the servers.

The analyzed case study is the simple task of inserting a strut into a previously existing structure. In the future, the testbed system wiU perform far more

complicated tasks. Therefore, the dispatcher will be more complex and its associated state space will grow large. The performance analysis will become increasingly

difficult, because of the large state space. By using the presented methodology, we

can predict the performance (i.e., the time required to execute a task) before the

system is actually implemented.
155

cameras CAM_avail ini_CAM CAM ready f'mdV

I_ ....." h°°_'i_ =+"-__ -

req..demo PP_avail init_PP PP_ready need home

(a) MTz

cala_apprl PP_.nod¢ 1 appr2 PP_node2 PP_rdy3

node l_path _._ nodel_ref-me_node2

rcf'mc .node 1 node2_pose

(b) MT_

no_2,__m m..,_m._rac_ mck.l.._p_ mfa__rackR Cam__me i CAM_c_e

e_mckL . mclr,R_pose a: k

- __ PP. rdy4_i PP rdy4

PP_rdy3 PP_makL

(c) MT_ f_ _

C.._M_donc spat CAM

© . - ___,_

.__ mo_..rm._ _._.._m.-,.+ mov._.m_ amt_kol+ _

"_:-_ ++.5/+"+_- ...,,2,_ - _o___.-_

+t_-->_ PP_shuulow'n

c_c_apprI PP_in.u_ PP_ff..,'ml PP_dome

(d) iT+

Figure 10.4: Exploded Composite Transitions 11'IT1, MT2, 3IT3 and iT4 of CIRSSE

Testbed
156

Transition time

start 0.0

init_CAM 0.8

init_ROB 11.2

init..PP 1.0

move_home 10.0

find_V 10.4

calc_apprl 0.8

PP_nodei 2.0

move_node1 13.3

calc_appr2 1.3

refine_node1 5.8

PP_node2 1.6

move_node9 10.3

refine_node2 5.8

rack_rdy 0.0

PP_rackL 1.7

move_rackL 20.0

refine_rackL 6.6

PP_rackR 1.5

move_rackR I0.0

refine_rackR 7.2

calc_apprR 1.7

PP_rack 1.7

move_rack 7.2

rack_done 0.0

pickup_strut 9.0

calc_apprI 1.9

PP_insert 1.7

move_insert 20.8

insert.strut 34.0

PP_final 2.0

move_final 10.7

shut_CAM 0.5

shut..ROB 13.4

finish 0.0

Interfiring times in seconds

Description

start the demo (immediate)

initialize cameras (wrist and ceiling)

initialize robot

initialize path planner

move robot to home position

find V-strut with ceiling camera

compute approach to V-strut (node 1)

plan path to node 1

move robot to node 1

compute approach to V-strut (node 2)

locate node 1 with wrist camera and refine location

plan path to node 2

move robot to node 2

locate node 2 with wrist camera and refine location

Ready to start activities at rack (immediate)

plan path to left node of strut on the rack

move robot to left node of strut on the rack

locate left node of strut on the rack with wrist camera

plan path to right node of strut on the rack

move robot to right node of strut on the rack

locate right node of strut on the rack with wrist camera

calculate approach for pickup of strut

plan path for pickup of strut

move robot to rack

activities at rack done (immediate)

pickup strut from rack

calculate approach for insert of strut into V-strut

plan path for insert of strut

move robot to insertion point

insert strut into V-strut

plan path to final position of robot

move robot to final position

shut down vision system

shut down robot

everything finished

Table 10.1: Description and Interfiring Times of Transitions in Dispatcher (Experimental Data)
157

Time unit in seconds

aggr. net X F tang. state space

MTI 0.044192 22.6283 8

MT2 0.026242 38.1068 12

MT3 0.017819 56.1199 11

I_IT4 0.011253 88.8652 31

Table 10.2: Results of the Flow Equivalent Aggregation of the Subnets Composing

the CIRSSE Testbed
CHAPTER 11

Conclusions

11.1 Discussion

In the present work, we have introduced the structural decomposition of

Marked Graphs (MGs) and Macroplace/Macrotransition nets (MPMT-nets), a subclass of Petri nets which allows limited choice and synchronizations. Single cuts lead

to aggregated net systems, where one of the subnets is reduced to a single transition

and the basic skeleton, where both subnets are reduced to a transition.

The cuts can be categorized according to their interface places, i.e., places

which both subnets have in common. Single Input/Single Output (SISO) cuts do

not introduce any synchronization constraints or marking bound changes and are

therefore preferred.

In MGs, Single Input/Multiple Output (SIMO/MISO) and Multiple Input/Multiple Output (M1MO) cuts introduce additional synchronization constraints, and can lead to a different net behavior. In some cases, the synchronization

of concurrent processes can lead to bad results.

The introduced cuts (with the exception of the SIMO cut in MPMT-nets)

lead to a product form representation of the basic skeleton, i.e., it can be solved by

analytic means (e.g., Mean Value Analysis).

Once the net is decomposed, a. variety of methods can be applied for the

approximate analysis.

• Response Time Approximation: [DJS92, JSS92b]

This method is introduced in the present work. From the analysis of the

aggregated net system, RTA only uses the throughput of the analysis of the

aggregated net system. Other information such as the token distribution in

158
159

the subnet isnot used. RTA isvery robust, converges quickly and shows good

accuracy.

• Marie's Method: [Mar79]

In Marie's method, we use information about the token distributionin the

ag_egated net systems. In allconsidered SISO cuts, the additional information leads to an improved accuracy over RTA, although convergence isusually

slower. In one particularcase,Marie's method failedto converge.

• Flow Equivalent Aggregation (FEA): [JD91a, LZGS84]

FEA is computationally very efficient, but has a severe drawback. If the mean

completion time of a subnet depends strongly on the interarrival process, the

aggregation can lead to very bad results as seen in Section 8.2.2. FEA should

be used with caution, and the subnets should be tested whether a strong

dependence of the mean completion time on the arrival process exists (as

outlined in Section 5.2.3).

• Delay Equivalence (DE): [LWgl, WL91]

Delay equivalence was introduced in the context of Petri nets by Woodside et

al. State dependent DE shows very poor convergence. In the presented e×amples, this method failed in most cases. State independent DE converges more

often, but still did not reach a fixed point solution in all cases. Furthermore,

the number of iterations is high compared to RTA or Marie's method. When

DE converges, the accuracy is similar to RTA. In DE, information about the

throughput and the token distribution in both subnets is used.

Based on our experimental results, we can now give guidelines for using the

different methods:

• Delay Equiralence shows no advantage over any of the other methods and

should not be used.
160

• Flow Equivalent A99regation should only be used when no internal cycles are

present, or it has been verified that the mean completion time of the subnet

does not depend on the arrival process (Section 5.2.3). In any case, FEA can

yield good initial values for Marie's method and RTA.

• Marie's Method is the method of choice when single SISO cuts are considered.

Although convergence is often slower than in RTA, the accuracy was better in

all considered single SISO cuts.

• Response Time Approzimation should be used when FEA is not applicable,

computation time is at a premium or Marie's does not converge. This represents the classical cost versus quality tradeoff.

Unfortunately, for the hierarchical decomposition we are not able to give such

guidelines as no scheme is consistently better.

In MPMT-nets, FEA was extended to SIMO cuts. This allowed the formulation of a flow equivalent server which captures the input/output behavior of the

subnet.

As a real life case study, a dual arm robotics tesi:bed for assembly operations

was analyzed. The results show, that the proposed aggregation is suitable in that

context.

11.2 Outlook

Based on the present work, we can identify several research directions:

1. If the customer load at the cut is low (e.g., K = 1), the presented methods

can lead to bad results. One approach could be to capture the higher moments of the probability distribution of the residence time of the tokens in the

interface places. This way, we would be able to use more information about

the aggregated net systems, which could lead to a better approximation.
161

2. At present, the choiceof the cuts is limited. By devising different basic skeletons, which take the multiple nature of the interface into account, we could

allow more generaltypesof cuts.

3. The almost product form decomposition in Petri nets can be further explored.

A first step in that direction was done in Chapter 9, where SIMO cuts in

MPMT-nets were introduced.
LITERATURE CITED

[ABS84]

[A J881

[AJD90a]

[AJD90b]

[AMBC+89]

[BBG86]

[BBG88]

[BC90]

[BCFR87]

S. C. Agrawal, J. P. Buzen, and A. W. Shum. Response time

preservation: a general technique for developing approximate

algorithms for queueing networks. In Proceedings of the 1984 A CM

Sigmetrics Conference on Measurment and Modeling of Computer

Systems, 1984.

R. Y. A1-Jaar. Performance Evaluation of Automated Manufacturing

Systems Using Generalized Stochastic Petri Nets. PhD thesis,

Department of Electrical, Computer, and System Engineering,

Rensselaer Polytechnic Institute, 1988.

R. Y. AI-Jaar and A. A. Desrochers. Advances in Robotics and

Automation, volume 2, Saridis, G. N. (ed), chapter Petri Nets in

Automation and Manufacturing, pages 153-225. JAI Press, 1990.

R. Y. A1-Jaar and A. A. Desrochers. Performance evaluation of

automated manufacturing systems using generalized stochastic Petri

nets. IEEE Transactions on Robotics and Automation, 6(6):621-639,

December 1990.

M. Ajmone Marsan, G. Balbo, G. Chiola, G. Conte, and A. Cumani.

The effect of execution policies on the semantics and analysis of

stochastic Petri nets. IEEE Transactions on Software Engineering,

7(15):832-846, July 1989.

G. Balbo, S. C. Bruell, and S. Ghanta. Combining queueing network

and generalized stochastic Petri net models for the analysis of some

software blocking phenomena. IEEE Transactions on Software

Engineering, 12(4):561-576, April 1986.

G. Balbo, S. C. Bruell, and S. Ghanta. Combining queueing networks

and generalized stochastic Petri net models for the solution of

complex models of system behaviour. [EEE Transactions on

Computers, Vol. 37, No. 10, 37(10):1251-1268, 1988.

G. Balbo and G. Chiola. Stochastic Petri net simulation. In

Proceedings of the 1990 Winter Simulation Conference, pages

266-276, 1990.

G. Balbo, G. Chiola, G. Franceschinis, and G. M. Roet. Generalized

stochastic Petri nets for the performance evaluation of FMS. In

162
[BCMP75]

[BCR87]

[BD90]

[B oSS]

[Bet85]

[Bra85]

[BT86]

[Cam90]

[Camgl]

[cccs89]

163

Proceedings of the 1987 IEEE International Conference on Robotics

and Automation, pages 191-198, Raleigh, North Carolina, 1987.

F. Baskett, M. K. Chandy, R. R. Muntz, and Fernando G. Palacios.

Open, closed and mixed networks of queues with different class of

customers. Journal of the Association of Computing Machinery,

22(2):248-260, 1975.

G. Balbo, G. Chiola, and M. G. Roet. On the efficient construction of

the tangible reachability graph of generalized stochastic Petri nets. In

Proceedings of the Second International Workshop on Petri Nets and

Performance Models, pages 136-145, Madison, Wi, 1987. IEEE

Computer Society Press.

B. Baynat and Y. Dallery. A unified view of product-form

approximation techniques for general closed queueing networks.

Technical Report 90.48, Lab. MASI, Universit& P. et lVl. Curie (Paris

6), Paris, France, October 1990.

C. Beounes. Stochastic Petri net modeling for dependability

evaluation of complex computer systems. In Proceedings of the 1985

Workshop on Timed Petri Nets, pages 191-198, Torino, Italy, July

1985.

G. Berthelot. Checking properties of nets using transformations. In

W. Brauer, W. Reisig, and G. Rozenberg, editors, Advances in Petri

Nets'85, volume 222 of LNCS, pages 19-40. Springer-Verlag, 1985.

A. Brandwajn. Equivalence and decomposition in queueing systems -

a unified approach. Performance Evaluation, 5:175-186, 1985.

A. Bobbio and K. S. Trivedi. An aggregation technique for the

transient analysis of stiff Markov chains. IEEE Transactions on

Computers, C-35(9):803-814, 1986.

J. Campos. Performance Bounds for Synchronized Queueing

Networks. PhD thesis, Departamento de Ingenieda El_ctrica e

Inform£tica, Universidad de Zaragoza, Spain, December 1990.

Research Report GISI-RR-90-20.

J. Campos. Performance analysis of live and bounded free choice

systems. In E. Best and J. Esparza, editors, Design Methods Based

on Nets, pages 38-48. GMD-Studien Nr. 198, Sankt Augustin,

Germany, September 1991.

J. Campos, G. Chiola, J. M. Colom, and M. Silva. Tight polynomial

bounds for steady-state performance of marked graphs. In
164

[cccs92]

[ccsgol

[ccsgza]

[CCS91 b]

[CGST]

[Chi85]

[Cou75]

[Cou77]

[cs7s]

[cs9o]

Proceedings of the Third International Workshop on Petri Nets and

Performance Models, pages 200-209, Kyoto, Japan, December 1989.

IEEE Computer Society Press.

J. Campos, G. Chiola, J. M. Colom, and M. Silva. Properties and

performance bounds for timed marked graphs. IEEE Transactions on

Circuits and Systems, 39(5), May 1992.

J. Campos, J. M. Colom, and M. Silva. Performance evaluation of

repetitive automated manufacturing systems. In Proceedings of

Rensselaer's Second International Conference on Computer Integrated

Manufacturing, pages 74-81, Rensselaer Polytechnic Institute, Troy,

NY, USA, May 1990. IEEE Computer Society Press.

J. Campos, G. Chiola, and M. Silva. Ergodicity and throughput

bounds of Petri nets with unique consistent firing count vector. IEEE

Transactions on Software Engineering, 17(2):117-125, February 1991.

J. Campos, G. Chiola, and M. Silva. Properties and performance

bounds for closed free choice synchronized monoclass queueing

networks. IEEE Transactions on Automatic Control,

36(12): 1368-1382, December 1991.

Y. F. Choong and S. B. Gershwin. A decomposition method for the

approximate evaluation of capacitated transfer lines with unreliable

machines and random processing times. IIE Transactions,

19(2):150-159, June 1987.

G. Chiola. A software package for the analysis of generalized

stochastic Petri nets. In Proceedings of the I985 Workshop on Timed

Petri Nets, pages 136-143, Torino, Italy, July 1985.

P.J. Courtois. Decomposability, instabilities and saturation in

multiprogramming systems. Communications of the A CM,

18(5):371-377, July 1975.

P.J. Courtois. Decomposability, Queuing and Computer System

Applications. Academic Press, 1977.

M. K. Chandy and C. H. Sauer. Aproximate methods for analyzing

queueing network models of computing systems. Computing Surveys,

10(3):281-317, September 1978.

J. M. Colom and M. Silva. Improving the linearly based

characterization of P/T nets. In W. Brauer, W. Reisig, and

G. Rozenberg, editors, Advances in Petri Nets'90, volume 483 of

LNCS, pages 113-14.5. Springer-Verlag, 1990.
[CT91a]

[CTgtb]

[DBCT85]

[DDL89]

[Deo74]

[DG91]

[DJS92]

[DLT90]

[DLT91]

[ES90a]

[ES90b]

165

G. Ciardo and K. S. Trivedi. A decomposition approach for stochastic

Petri net models. In Proceedings of the Fourth International

Workshop on Petri Nets and Performance _/[odels, pages 74-83,

Melbourne, Australia, 1991. IEEE Computer Society Press.

G. Ciardo and K. S. Trivedi. Solution of large GSPN models. In

W. Stewart, editor, Numerical Solution of Markov Chains. Marcel

Dekker, New York, 1991.

J. B. Dugan, A. Bobbio, G. Ciardo, and K. Trivedi. The design of a

unified package for the solution of stochastic Petri net models. In

Proceedings of the 1985 Workshop on Timed Petri Nets, pages 6-13,

Torino, Italy, July 1985.

Y. DaUery, R. David, and Xie X. L. Approximate analysis of transfer

lines with unreliable machines and finite buffers. IEEE Transactions

on Automatic Control, 34(9):943-953, September 1989.

N. Deo. Graph Theory with Applications to Engineering and

Computer Science. Prentice-Hall, Englewood Cfiffs, N J, 1974.

Y. Dallery and S. B. Gershwin. Manufacturing flow line systems: A

review of models and analytical results. Technical Report 91.18, Lab.

MASI, Universit_ P. et M. Curie (Paris 6), Paris, France, March 1991.

A.A. Desrochers, H. Jungnitz, and M. Silva. An approximation

method for the performance analysis of manufacturing systems based

on GSPNs. In Proceedings of Renssalear's Third International

Conference on Computer Integrated Manufacturing, 1992.

Y. DaUery, Z. Liu, and D. Towsley. Equivalence, reversibility and

symmetry properties in fork/join queueing networks with blocking.

Technical Report M.A.S.I. 90.32, Lab. MASI, Universit_ P. et M.

Curie (Paris 6), Paris, France, = June 1990.

Y. Dallery, Z. Liu, and D. Towsley. Reversibility in fork/join queuing

networks with blocking after service, 1991. In preparation.

J. Esparza and M. Silva. On the analysis and synthesis of free choice

systems. In Grzegorz Rozenberg, editor, Advances in Petri Nets

1987, pages 243-286. Springer-Verlag, 1990.

J. Esparza and M. Silva. Top-down synthesis of live and bounded free

choice nets. In Proceedings of the 11th [nternational Conference on

Application and Theory of Petri Nets, pages 63-83, Paris, France,

June 1990.
[GB81]

[GDZ90]

[GH85]

[GN671

[Hac72]

[HC79]

[HC83]

[HPTD90]

[HS89]

[HT90]

[HV85]

[Jac57]

[Jac63]

166

S.B. Gershwin and O. Berman. Analysis of transfer lines consisting of

two unreliable machines with random processing times and finite

storage buffers. AIIE Transactions, 13(1):2-11, March 1981.

D. Guo, F. DiCesare, and M. Zhou. A monent generating function

based approach for evaluating arbitrary stochastic Petri nets, 1990.

Unpublished.

D. Gross and C.M. Harris. Fundamentals of Queueing Theory. John

Wiley &: Sons Inc., 1985.

W. J. Gordon and G. F. Newell. Closed queuing systems with

exponential servers. Operations Research, 15:254-265, 1967.

M.H.T. Hack. Analysis of production schemata by Petri nets.

Technical Report TR-94, Massachusetts Institute of Technology,

Cambridge, Massachusetts, 1972.

Y. C. Ho and T. T. Chien. A gradient technique for general buffer

storage design in a production line. International Journal of

Production Research, 17(6):557-580, 1979.

Y. C. Ho and T. T. Chien. A new approach to determine parameter

sensitivities of transfer lines. Management Science, 29(6):700-714,

1983.

W. Henderson, C. M. Pearce, P. G. Taylor, and N. M. Djik. Closed

queueing networks with. batch services. Queueing Systems, 6:59-70,

1990.

P.J. Haas and G.S. Shedler. Stochastic Petri net representation of

discrete event simulation. IEEE Transactions on Software

Engineering, 15(4):381-393, April 1989.

W. Henderson, , and P. G. Taylor. Product form networks of queues

with batch arrivals. Q,ueueing Systems, 6:71-87, 1990.

M. A. Holliday and M. K. Vernon. A generalized Petri net model for

performance analysis. In Proceedings of the i985 Workshop on Timed

Petri Nets, pages 181-190, Torino, Italy, July 1985.

J. R. Jackson. Network of waiting lines. Operations Research,

5:518-521, 1957.

J. R. Jackson. Jobshop like queueing systems. 3Ianagement Science,

10:131-142, 1963.
[JD91a]

[JD91b]

[JGD91]

[JSS92a]

[JSS92b]

[Kar84]

[KBB87]

[KDDSS]

[Kle75]

[Koe59]

[LS91]

167

H. Jungnitz and A. A. Desrochers. Flow equivalent nets for the

performance analysis of flexible manufacturing systems. In

Proceedings of the IEEE Robotics and Automation Conference 1991,

pages 122-127, 1991.

H. Jungnitz and A. A. Desrochers. State space reduction techniques

for discrete event dynamic systems. In Proceedings of the IMACS

Symposium MCTS 1991, pages 799-805, Lille, France, 1991.

H. Jungnitz, A. Giua, and A. Desrochers. An integration based

method for the solution of continuous time Markov chains. In

Proceedings of the 1991 IEEE International Conference on Systems,

Man, and Cybernetics, pages 385-390, Charlottesville, VA, USA,

1991.

H. Jungnitz, B. Sanchez, and M. Silva. Response time approximation

for the performance analysis of manufacturing systems modeled with

stochastic marked graphs. In Proceedings of the 19912 IEEE

International Conference on Robotics and Automation, Nice, France,

1992.

H. Jungnitz, B. Sanchez, and M. Silva. Response time approximation

for throughput computation of stochastic marked graphs. Journal of

Parallel and Distributed Computing, 1992. Accepted.

N. Karmakar. A new polynomial time algorithm for linear

programming. Combinatorica, 4:373-507, 1984.

i

K.M. Kavi, B.P. Buckles, and U.N. Bhat. Isomorphism between Petri

nets and dataflow graphs. IEEE Transactions on Software

Engineering, 13(10):1127-1133, October 1987.

E. Kasturia, F. DiCesare, and A. Desrochers. Real time control of

multilevel manufacturing systems using coloured Petri nets. In

Proceedings of the I988 IEEE International Conference on Robotics

and Automation, pages 1114-1119, Philadelphia, PA, 1988.

L. Kleinrock. Queueing Systems, volume 1,2. Wiley Interscience

Publications, 1975.

E. Koenigsberg. Production lines and internal storage - a review.

l_¢[anagement Science, 5:410-433, 1959.

D.R. Lefebv're and G.N. Saridis. A computer architecture for

intelligent machines. Technical Report CIRSSE-108, Rensselaer

Polytechnic Institute, Center for Intelligent Robotics for Space
168

[LW91]

[LZGS84]

[Mar71]

[Mar79]

[MarS9]

[MFDD89]

[MZS8]

[Mo182]

[Mur77]

[Mur89]

[NRKT89]

Exploration (CIRSSE), R.ensselaer Polytechnic Institute, Troy, NY

12180-3590, December 1991.

Y. Li and C. M. Woodside. Iterative decomposition and aggregation

of stochastic marked graph Petri nets. In Proceedings of the l_h

International Workshop on Application and Theory of Petri Nets,

Aarhus, Denmark, June 1991.

E. D. Lazows "l'Ika,J. Zahorjan, G. S. Graham, and K. C. Sevcik.

Quantitative Systems Performance: Computer System Analysis Using

Queueing Network Models. Prentice Hall, Inc., 1984.

C. W. MarhaU. Applied Graph Theory. John Wiley gc Sons, New

York, 1971.

R. Marie. An approximate analytical method for general queueing

networks. IEEE Transactions on Software Engineering,

SE-5(5):530-538, September 1979.

A. Marsan. Stochastic Petri nets: An elementary introduction. In

Grzegorz Rozenberg, editor, Advances in Petri Nets 1989, pages 1-29.

Springer-Verlag, 1989.

M. Di Mascolo, M.Y. Frein, Y. Dallery, and R. David. Modeling of

Kanban systems using Petri nets. In Proceedings of the Third

ORSA/TIMS Conference on Flezible Manufacturing Systems, pages

307-312. Elsevier Science publishers B.V. (North Holland), 1989.

M.Silva and J.M.Colom. On the computation of structural

synchronic invariants in p/t nets. In W. Brauer, W. Reisig, and

G. Rozenberg, editors, Advances in Petri Nets'88 - Part [, volume

340 of LNCS, pages 386-417. Springer-Verlag, 1988.

M. K. Molloy. Performance analysis using stochastic Petri nets. IEEE

Transactions on Computers, Vol. C-31, No. 9, pages 913-917, 1982.

T. Murata. Circuit theoretic analysis and synthesis of marked _aphs.

[EEE Transactions on Circuits and Systems, 24(7):400-405, July

1977.

T. Murata. Petri nets: Properties, analysis, and applications.

Proceedings of the IEEE, 77(4):541-580, April 1989.

G.L. Nemhauser, A.H.G. Rinnooy Kan, and M.J. Todd. Handbooks in

Operation Research and Management Science. North-Holland, 1989.
169

[0P86] R. Onvural and H. G. Perros. On equivalencies of blocking

mechanism in queuing networks with blocking. Operation Research

Letters, 5-6:293-298, 1986.

[Pet81] J. L. Peterson. Petri /Vet Theory and the Modeling of Systems.

Prentice-Hall, Englewood Cliffs, N J, 1981.

[Ram74] C. Ramchandani. Analysis of asynchronous Concurrent Systems by

Petri nets. PhD thesis, Massachusetts Institute of Technology,

Cambridge, Massachusetts, 1974.

[RL80]

[Ro883]

M. Reiser and S.S. Lavenberg. Mean value analysis of closed

queueing networks. Journal of the Association for Computing

Machinery, 27(2):313-323, 1980.

S.M. Ross. Stochastic Processes. John Wiley & Sons, New York,

1983.

[RP84]

[Sar79]

[sn811

[si185]

[Sur89]

[sv771

R. R. Razouk and C. V. Phelps. Performance analysis using timed

Petri nets. In Proceedings of the International Conference on Parallel

Processing, pages 126-128. IEEE Computer Society Press, 1984.

G.N. Saridis. Toward the realization of intelligent controls.

Proceedings of the IEEE, 67(8):34-39, 1979.

M. Silva. Sur le concept de macroplace et son utilisation pour

l'analyse des reseaux de petri. RAIRO-Systems Analysis and Control,

15(4):57-67, 1981.

M. Silva. Las Redes de Petri: en la Automatica y la [nformatica.

Editorial AC, Madrid, Spain, 1985. In Spanish.

R. Suri. Perturbation analysis: The state of the art and research

issues explained via the GI/G/1 queue. Proceedings of the IEEE,

77(1):114-137, January 1989.

G.N. Saridis and K.P. Valavanis. A hierarchical approach to the

control of a prosthetic arm. IEEE Transactions on Systems, il[an and

Cybernetics, 7:407-420, 1977.

[svs81

[sv90]

G.N. Saridis and K.P. Valavanis. Analytical design of intelligent

machines. Automatica: the Journal of IF.4C, 24(2):123-I33, 1988.

M. Silva and R. Valette. Petri nets and flexible manufacturing. In

G. Rozenberg, editor, Advances in Petri Nets'89, volume 266 of

LNCS, pages 375-417. Springer-Vertag, 1990.
[Vaa78]

[VZL87]

[V_O92a]

[_VD92b]

[WDF85]

[w c91]

[wL91]

[wsg0]

[ZubSb]

170

H. Vantilborgh. Exact aggregation in exponential queuing networks.

Journal of the Association for Computing Machinery, 25(4):620-629,

October 1978.

M. Vernon, J. Zahorjan, and E. D. Lazowska. A comparison of

performance Petri net models and queueing network models. In

S. Fidia and G. Pujole, editors, Modelling Techniques and

Performance Evaluation, pages 191-202. Elsevier Science PubLishers

B. V. (North Holland), 1987.

J. F. Watson, III and A. A. Desrochers. Methods for estimating

state-space size of Petri nets. In Proceedings of the I99 o- IEEE

Robotics and Automation Conference, May 1992.

J. F. _Vatson, Ill and A. A. Desrochers. State-space size estimation

of conservative Petri nets. In Proceedings of the 1998 IEEE Robotics

and Automation Conference, May 1992.

C. Y. Wong, T. S. Dillon, and K. E. Forward. Timed place PetH nets

with stochastic representation of place time. In Proceedings of the

1985 Workshop on Timed Petri Nets, pages 96-103, Torino, Italy,

July 1985.

F. Wang, H. Jungnitz, and K. Gildea. Performance analysis of MMS

using GSPN. In Proceedings of the 1991 IEEE International

Conference on Robotics and Automation, pages 1573-1578, 1991.

C.M. Woodside and Y. Li. Performance Petri net analysis of

communications protocol software by delay-equivalent aggregation.

Technical Report SCE-91-10, Telecommunications Research Institute

of Ontario, Ontario, Canada, 1991.

F. Wang and G. Saridis. A coordination theory for intelligent

machines. Automatica, 26(5):833-844, 1990.

W. M. Zuberek. Performance evaluation using extended timed Petri

nets. In Proceedings of the 1985 Workshop on Timed Petri Nets,

pages 272-278, Torino, Italy, July I985.