Efficient heuristics for simulating rare events in queuing networks

T.S. Zaburnenko

Abstract

In this thesis we propose state-dependent importance sampling heuristics to estimate the probability of population overflow in queuing networks. These heuristics capture state-dependence along the boundaries (when one or more queues are almost empty) which is crucial for the asymptotic efficiency of the change of measure. The approach does not require difficult (and often intractable) mathematical analysis or costly optimization involved in adaptive importance sampling methodologies. Experimental results on tandem, parallel, feed-forward, and a 2-node feedback Jackson queuing networks as well as a 2-node tandem non-Markovian network suggest that the proposed heuristics yield asymptotically efficient estimators, sometimes with bounded relative error. For these queuing networks no state-independent importance sampling techniques are known to be efficient.
Original languageUndefined
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Haverkort, Boudewijn R.H.M., Supervisor
  • de Boer, Pieter-Tjerk , Advisor
Sponsors
Date of Award25 Jan 2008
Place of PublicationEnschede
Publisher
Print ISBNs978-90-365-2622-7
DOIs
StatePublished - 25 Jan 2008

Fingerprint

Heuristics
Methodology

Keywords

  • IR-58768
  • METIS-251056
  • EWI-13013

Cite this

Zaburnenko, T. S. (2008). Efficient heuristics for simulating rare events in queuing networks Enschede: Centre for Telematics and Information Technology (CTIT) DOI: 10.3990/1.9789036526227
Zaburnenko, T.S.. / Efficient heuristics for simulating rare events in queuing networks. Enschede : Centre for Telematics and Information Technology (CTIT), 2008. 172 p.
@misc{1a215037e58341689efdb796bf6cdc62,
title = "Efficient heuristics for simulating rare events in queuing networks",
abstract = "In this thesis we propose state-dependent importance sampling heuristics to estimate the probability of population overflow in queuing networks. These heuristics capture state-dependence along the boundaries (when one or more queues are almost empty) which is crucial for the asymptotic efficiency of the change of measure. The approach does not require difficult (and often intractable) mathematical analysis or costly optimization involved in adaptive importance sampling methodologies. Experimental results on tandem, parallel, feed-forward, and a 2-node feedback Jackson queuing networks as well as a 2-node tandem non-Markovian network suggest that the proposed heuristics yield asymptotically efficient estimators, sometimes with bounded relative error. For these queuing networks no state-independent importance sampling techniques are known to be efficient.",
keywords = "IR-58768, METIS-251056, EWI-13013",
author = "T.S. Zaburnenko",
year = "2008",
month = "1",
doi = "10.3990/1.9789036526227",
isbn = "978-90-365-2622-7",
publisher = "Centre for Telematics and Information Technology (CTIT)",
address = "Netherlands",
school = "University of Twente",

}

Zaburnenko, TS 2008, 'Efficient heuristics for simulating rare events in queuing networks', University of Twente, Enschede. DOI: 10.3990/1.9789036526227

Efficient heuristics for simulating rare events in queuing networks. / Zaburnenko, T.S.

Enschede : Centre for Telematics and Information Technology (CTIT), 2008. 172 p.

Research output: Scientific › PhD Thesis - Research UT, graduation UT

TY - THES

T1 - Efficient heuristics for simulating rare events in queuing networks

AU - Zaburnenko,T.S.

PY - 2008/1/25

Y1 - 2008/1/25

N2 - In this thesis we propose state-dependent importance sampling heuristics to estimate the probability of population overflow in queuing networks. These heuristics capture state-dependence along the boundaries (when one or more queues are almost empty) which is crucial for the asymptotic efficiency of the change of measure. The approach does not require difficult (and often intractable) mathematical analysis or costly optimization involved in adaptive importance sampling methodologies. Experimental results on tandem, parallel, feed-forward, and a 2-node feedback Jackson queuing networks as well as a 2-node tandem non-Markovian network suggest that the proposed heuristics yield asymptotically efficient estimators, sometimes with bounded relative error. For these queuing networks no state-independent importance sampling techniques are known to be efficient.

AB - In this thesis we propose state-dependent importance sampling heuristics to estimate the probability of population overflow in queuing networks. These heuristics capture state-dependence along the boundaries (when one or more queues are almost empty) which is crucial for the asymptotic efficiency of the change of measure. The approach does not require difficult (and often intractable) mathematical analysis or costly optimization involved in adaptive importance sampling methodologies. Experimental results on tandem, parallel, feed-forward, and a 2-node feedback Jackson queuing networks as well as a 2-node tandem non-Markovian network suggest that the proposed heuristics yield asymptotically efficient estimators, sometimes with bounded relative error. For these queuing networks no state-independent importance sampling techniques are known to be efficient.

KW - IR-58768

KW - METIS-251056

KW - EWI-13013

U2 - 10.3990/1.9789036526227

DO - 10.3990/1.9789036526227

M3 - PhD Thesis - Research UT, graduation UT

SN - 978-90-365-2622-7

PB - Centre for Telematics and Information Technology (CTIT)

ER -

Zaburnenko TS. Efficient heuristics for simulating rare events in queuing networks. Enschede: Centre for Telematics and Information Technology (CTIT), 2008. 172 p. Available from, DOI: 10.3990/1.9789036526227

Access to Document