Throughput upper bounds for Markovian Petri nets: embedded subnets and queueing networks

Addresses the computation of upper bounds for the steady-state throughput of stochastic Petri nets with immediate and exponentially distributed service times of transitions. The authors try to deeply bridge stochastic Petri net theory to untimed Petri net and queueing network theories. Previous results for general service time distributions are improved for the case of Markovian nets by considering the slowest embedded subnet (generated by the support of left annullers of the incidence matrix of the net). The obtained results for the case of live and bounded free choice nets are of special interest. For such nets, the subnets generated by the left annullers of the incidence matrix can be seen as embedded product-form closed monoclass queueing networks, and efficient algorithms exist for their analysis