Deliverable D14

Approximation Techniques in Stochastic Petri Nets

• Introduction to the deliverable
• Contents of the deliverable

Introduction to Deliverable D14

The research in the computational aspects of performance evaluation using Petri Net models goes in three directions: exact analysis, bounds and approximations, simulations.

The first aspect is the topic of deliverable D13 and of many papers appearing in the Proceedings of the Workshop of Torino on Solution Methods (CWI Tracts #105 and 106, O.J. Boxma and G.M. Koole (eds.), 1994). The second aspect is the topic of D16a, which has already been delivered. Both aspects are still the purpose of an intense ongoing research within the project.

Approximation techniques are used when exact models are not mathematically tractable, or, when they are, not solvable numerically due to the size of the problem, inaccuracies of instabilities. One may distinguish three different approaches for obtaining approximate results for quantitative measures of stochastic Petri Nets, such as throughputs and average response times.

The decomposition/aggregation

techniques, in which a complex system is divided into smaller sub-systems which can be solved more easily. The partial results are then collected to construct the global performance measure. The exploitation of the structure of the system is crucial in order to obtain good results. When analyzing Stochastic Petri Nets with exponential firing times, this principle can be applied at two levels.

One idea is to try to aggregate the states of the Markov chain representing the evolution of the net, using quasi-lumpability properties. This idea has been applied in deliverable D12-3, where, in actually, performance bounds are obtained.

Another idea is to exploit the structure of the net to identify subnets reducible to elementary components. It can be coupled with fixed point ideas to obtain iterative approximation algorithms. This approach is used in deliverables D14-1, D14-3 and D14-4.

The task graph

approach, which applies to the Petri Nets of the Event Graph subclass. It consists in representing the evolution of the Petri Net by a stochastic (PERT) graph, and apply approximation techniques for these objects. A survey of such ideas is provided as deliverable D14-2. This topic is also addressed in the invited paper of F. Hartleb: ``Stochastic Graph Models for Performance Evaluation of Parallel Programs and the Evaluation Tool PEPP'', which appears in D1 (the proceedings of the Erlangen Workshop).

The performance bounds

approach, which consists in building computable lower and upper bounds for the performance measures of interest. The bounds themselves may already give a good approximation, and when they do not, combining them in a simple way sometimes gives a much better estimate. Once again, the structure of the net analyzed plays an important role in the technique used for obtaining these bounds and their accuracy. Bounds may be obtained using stochastic monotonicity and convexity ideas, or using some conservation laws and a fine analysis of the dynamics of the system, coupled with linear programming. Several papers using this sort of approach successfully have been provided in deliverable D12 (Bounds for Networks), and more are in preparation.

Contents of the Deliverable

D14-1

Approximation Techniques for Stochastic Macroplace/Macrotransition Nets, by H. Jungnitz, A. Desrochers and M. Silva.

In chapter 3 of the Proceedings of the Sophia-Antipolis Workshop on Stochastic Petri Nets.

D14-2

A Survey on Solution Methods for Task Graph Models, by F. Baccelli, A. Jean-Marie and Z. Liu.

In chapter 3 of the Proceedings of the Erlangen Workshop on Formalisms (D 1).

D14-3

Approximate Throughput Computation of Stochastic Marked Graphs, by J. Campos, J.M. Colom, H. Jungnitz, and M. Silva (front page).

In the Proceedings of the Torino Workshop on Solution Methods. This paper appears in the IEEE Transactions on Software Engineering,vol. 20, no. 7, pp. 526-535, July 1994.

D14-4

Approximate Performance Analysis on Petri Net Based Models of Manufacturing Systems, by M. Tilgner and M. Silva (front page).

This paper appears in Proceedings of the 1994 IEEE International Conference on Robotics and Automation, San Diego, California, May 1994.