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