Approximate mean value analysis for large multi-class multi-server queueing networks

Product form queueing networks with multiple customer classes and multiple server stations arise when modeling the performance of computer-communication systems, flexible manufacturing systems, logistics systems and other real domains. Large size models of this type cannot be solved by the classical Mean Value Analysis (MVA) algorithm (1980), due to the exponential computational complexity in the number of customer classes. In the last three decades, consolidated polynomial approximation methods have been proposed in literature, but they only apply to (fixed-rate) single-server stations. These approximations are based on the transformation of the recursive MVA equations in a system of nonlinear equations to be solved iteratively. They are used in practice even though theoretical convergence remains an open problem. Here we propose a new two-level fixed-point iterative procedure for solving large size multi-class networks with multi-server stations under a first-come-first-served discipline. The inner level uses the current estimate of the marginal queue length probabilities and returns to the outer level the average network throughput per class, by using a fixed-point procedure based on the Bard-Schweitzer proportional estimation method as for the average queue length at each station. The network throughput per class is used by the outer level to aggregate all customer classes into a unique representative and solve a single-class MVA to update the marginal queue length probabilities. Hence, the representative class is updated by iteratively refining the network throughput per class until outer convergence on marginal probabilities is achieved. For a sample of suitably defined queueing networks, with one or two bottleneck stations, no convergence problems have been encountered and results have been successfully validated against those obtained by the exact MVA solution. Besides numerical experiments, we also show that the Bard-Schweitzer proportional estimation method may be derived from a semi-Markov assumption on the stochastic process describing customer circulation within the network of service stations.