State-dependent importance sampling for a slowdown tandem queue


Miretskiy, D.I. and Scheinhardt, W.R.W. and Mandjes, M.R.H. (2011) State-dependent importance sampling for a slowdown tandem queue. Annals of Operations Research, 189 (1). pp. 299-329. ISSN 0254-5330

[img] PDF
Restricted to UT campus only
: Request a copy
Abstract:In this paper we investigate an advanced variant of the classical (Jackson) tandem queue, viz. a two-node system with server slowdown. By this mechanism, the service speed of the upstream queue is reduced as soon as the number of jobs in the downstream queue reaches some pre-specified threshold. We focus on the estimation of the probability of overflow in the downstream queue before the system becomes empty, starting from any given state in the state space. The principal contribution of this paper is that we construct importance sampling schemes to estimate these probabilities in case they are small; in particular: (1)We use powerful heuristics to identify the exponential decay rate of the probability under consideration, and verify this result by applying sample-path large deviations techniques. (2) Based on these heuristics we develop a change of measure to be used in importance sampling. (3) We prove that this scheme is asymptotically efficient, using a shorter and more straightforward method than usually provided in the literature. Unfortunately, this scheme is difficult to use in practice, therefore (4) we propose an algorithm that offers considerable computational advantage over the first scheme. For this scheme we provide a proof of asymptotic efficiency for certain parameter settings, as well as numerical results showing that the scheme works well for all parameters.
Item Type:Article
Additional information:Part of this research has been funded by the Dutch BSIK/BRICKS project. Part of this work was done while M.R.H. Mandjes was at Stanford University, Stanford, CA 94305, US.
Copyright:© 2011 Springer
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page