- State-dependent importance sampling for a slowdown tandem queue
- Annals of Operations Research
- Volume | Issue number
- 189 | 1
- Pages (from-to)
- Document type
- Faculty of Science (FNWI)
- Korteweg-de Vries Institute for Mathematics (KdVI)
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.
- go to publisher's site
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.