#
Queueing Petri Nets (QPNs)

In the QPN formalism the timing aspects of a coloured GSPN are
extended by the option of integrating queues into places. Such a timed
place consists of a queue and a depository for served tokens. Tokens
being added to a timed place, after a transition firing, are inserted
into the queue according to the queue's scheduling strategy. Each
colour of tokens has an associated individual service time
distribution of Coxian type. After service the corresponding token
moves to a depository, where it is available to the place's output
transitions. Tokens in a queue are not available for firing.
Every QPN can be analysed with respect to qualitative and quantitative
aspects. The qualitative analysis of a QPN is completely based on the
QPN's underlying coloured Petri net, where all timing aspects are
neglected. The basis for a quantitative analysis of a QPN is its
corresponding Markov chain. Every QPN describes a stochastic process.
A state of this process is determined by the cartesian product of the
state descriptors of all timed places and the number of coloured
tokens within ordinary places. The initial marking of the QPN defines
the initial state of its stochastic process under the assumption that
initially all tokens contained in timed places are situated on the
corresponding depository. The state space is partitioned into two
types of states similar to GSPNs: vanishing and tangible.
A quantitative analysis can be performed with conventional techniques.
The complexity of a quantitative analysis is significantly reduced if
the QPN has a hierarchical structure, which led to an extension of the
model formalism towards Hierarchically Combined Queueing Petri Nets
(HQPNs).

Falko Bause, Peter Buchholz, Peter Kemper
LS Informatik IV , Universität Dortmund