TY - JOUR

T1 - State-dependent importance sampling for a slowdown tandem queue

AU - Miretskiy, D.I.

AU - Scheinhardt, Willem R.W.

AU - Mandjes, M.R.H.

N1 - 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.

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - EWI-21159

KW - METIS-285221

KW - IR-79190

U2 - 10.1007/s10479-010-0823-x

DO - 10.1007/s10479-010-0823-x

M3 - Article

VL - 189

SP - 299

EP - 329

JO - Annals of operations research

JF - Annals of operations research

SN - 0254-5330

IS - 1

ER -