Performance analysis of queueing networks via robust optimization

DOI10.1287/OPRE.1100.0879zbMATH Open1233.90110arXiv1009.3948OpenAlexW2065240885MaRDI QIDQ3098770FDOQ3098770

Authors: David Gamarnik, Alexander Anatoliy Rikun, Dimitris Bertsimas 

Publication date: 18 November 2011

Published in: Operations Research (Search for Journal in Brave)

Abstract: Performance analysis of queueing networks is one of the most challenging areas of queueing theory. Barring very specialized models such as product-form type queueing networks, there exist very few results which provide provable non-asymptotic upper and lower bounds on key performance measures. In this paper we propose a new performance analysis method, which is based on the robust optimization. The basic premise of our approach is as follows: rather than assuming that the stochastic primitives of a queueing model satisfy certain probability laws, such as, for example, i.i.d. interarrival and service times distributions, we assume that the underlying primitives are deterministic and satisfy the implications of such probability laws. These implications take the form of simple linear constraints, namely, those motivated by the Law of the Iterated Logarithm (LIL). Using this approach we are able to obtain performance bounds on some key performance measures. Furthermore, these performance bounds imply similar bounds in the underlying stochastic queueing models. We demonstrate our approach on two types of queueing networks: a) Tandem Single Class queue- ing network and b) Multiclass Single Server queueing network. In both cases, using the proposed robust optimization approach, we are able to obtain explicit upper bounds on some steady-state performance measures. For example, for the case of TSC system we obtain a bound of the form $fracC1-holnln(1/(1-ho))$ on the expected steady-state sojourn time, where C is an explicit constant and $ho$ is the bottleneck traffic intensity. This qualitatively agrees with the correct heavy traffic scaling of this performance measure up to the $lnln(1/(1-ho))$ correction factor.

Full work available at URL: https://arxiv.org/abs/1009.3948

Recommendations

• Robust queueing theory
• Robustness of queuing network formulas
• Optimization of multiclass queueing networks: Polyhedral and nonlinear characterizations of achievable performance
• Near‐optimal analysis of homogeneous central‐server queueing networks
• New linear program performance bounds for queueing networks

zbMATH Keywords

law of the iterated logarithmtandem queuesmulticlass queueing network

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Stochastic network models in operations research (90B15)

Cited In (16)

• Robust queueing theory: an initial study using imprecise probabilities
• Characterization and Optimization of Achievable Performance in General Queueing Systems
• Robust Inventory Management: An Optimal Control Approach
• Robust bounds and optimization at the large deviations scale for queueing models via Rényi divergence
• Tractable stochastic analysis in high dimensions via robust optimization
• A hybrid method for performance analysis of \(G/G/m\) queueing networks
• Robust transient analysis of multi-server queueing systems and feed-forward networks
• A robust queueing network analyzer based on indices of dispersion
• Queueing network controls via deep reinforcement learning
• Measurement and optimization of robust stability of multiclass queueing networks: applications in dynamic supply chains
• Robustness of queuing network formulas
• Recent advances in robust optimization: an overview
• Robust queueing theory
• Time-varying robust queueing
• Robust optimal service analysis of single-server re-entrant queues
• Data-driven robust optimization

This page was built for publication: Performance analysis of queueing networks via robust optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3098770)