Properties and performance bounds for closed free choice synchronized monoclass queueing networks

Abstract

It is shown that many monoclass queuing networks (QN) with synchronizations can naturally be modeled with a subclass of Petri nets (PN) called free-choice nets (FC), for which a wide gamut of qualitative behavioral and structural results have been derived. Some of these net theoretic results are used to characterize the ergodicity, boundedness, and liveness of closed free-choice synchronized QNs. Upper and lower throughput bounds are defined based on the mean value of the service times, without any assumption on the probability distributions (thus including both the deterministic and the stochastic cases). It is shown that monotonicity properties exist between the throughput bounds and the parameters of the model in terms of population and service times. Proposed are (theoretically polynomial and practically linear complexity) algorithms for the computation of these bounds, based on linear programming problems defined on the incidence matrix of the underlying FC net. Using classical laws from queuing theory, bounds are provided for mean queue lengths and response time.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>