Title: Superposition of generalized stochastic Petri nets 
       and its impact on performance analysis

Author: Peter Kemper

Publisher:	Krehl Verlag, Muenster, 1997
		ISBN 3-931546-06-3, 131 pages

to obtain a copy, please contact:
	Krehl-Verlag, Postfach 510142, 48163 Muenster, Germany
	Tel/Fax +49 2501 261550
	Email krehl-verlag@t-online.de

Abstract:

Generalized stochastic Petri nets (GSPNs) are a suitable formalism
for modeling discrete event dynamic systems, especially if concurrency is
observed. A GSPN can be analyzed to gain insight into its functional properties
as well as into its behaviour with respect to time. 
The latter is known as performance analysis and it can be performed
by numerical solution of the associated continous time Markov chain (CTMC).
The well known state space explosion problem often prohibits analysis
of interesting CTMCs. Extremely large state spaces mainly cause a space
problem due to the -- usually very sparse -- generator matrix of the CTMC.

Composing GSPNs via superposition (merging of transitions) can relief
this problem. The corresponding net class is called superposed GSPNs
and allows for marking dependent weight functions to a certain extent.
Its compositional structure induces a similar structure at CTMC level, 
which yields a  representation of the generator matrix by a set of relatively 
small matrices which are combined by Kronecker/tensor operations. 

The approach presented in this thesis considers this matrix structure
in detail and with respect to algorithms for the computation of steady
state and transient distributions. The structured matrix
representation implies the possibility of unreachable states.
Unreachable states can impose a severe drawback on the
Kronecker/tensor approach. Hence several means to minimize the impact
of unreachable states are presented, which include algorithms for
state space exploration based on the structured matrix representation,
permutation of the state space according to reachability
(TRS-permutation), and reduction of component state spaces among others.

Several examples are exercised in order to demonstrate
effectiveness of the proposed algorithms.

Contents:

1 Introduction							1

2 GSPNs, a modeling formalism					7
2.1 Formal definitions and preliminary results for GSPNs	7
2.2 Definitions in the context of Markov chains			10
2.3 Superposition of GSPNs					14

3 Performance analysis of GSPNs					19
3.1. Numerical methods for steady state analysis		20
3.2. Transient analysis						26

4 Structured representations of generator matrices		29
4.1. Definition of tensor operations				30
4.2. Structured representation of SGSPNs			32
4.3. Structured representation of other formalisms		38

5 Reachability in structured representations			45
5.1. Constraints imposed by superposition 			48
5.2. State space exploration and permutations			53
5.3. Exploration of TRS and generation of P			56
5.4. Improvements for state space exploration 			60

6 Steady state analysis						67
6.1. Vector matrix multiplication with a tensor product		71
6.2. Vector matrix multiplication including a TRS-permutation	73
6.3. Integration of diagonal values into iteration 		78
6.4. Gauss-Seidel method for structured representation		79

7 Transient analysis						81
7.1. Randomization with respect to active states		83
7.2. Randomization with respect to reachable states		85
7.3. Comparison of approaches					88

8 Application examples						91
8.1. A flexible manufacturing system 				92
8.2. The benchnet and benchprod models				101
8.3. Kanban Systems						109
8.4. A Courier protocol software				115

9 Conclusions							121