This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Ingolfsson, A. Articles by Wu, X. Search for Related Content

A Survey and Experimental Comparison of Service-Level-Approximation Methods for Nonstationary M(t)/M/s(t) Queueing Systems with Exhaustive Discipline

School of Business, University of Alberta, Edmonton, Alberta T6G 2R6, Canada
School of Business, University of Alberta, Edmonton, Alberta T6G 2R6, Canada
School of Business, University of Alberta, Edmonton, Alberta T6G 2R6, Canada
School of Business, University of Alberta, Edmonton, Alberta T6G 2R6, Canada
Department of Computing Science, University of Alberta, Edmonton, Alberta T6G 2R6, Canada
armann.ingolfsson{at}ualberta.ca
elvira{at}ualberta.ca
sbudge{at}ualberta.ca
yongyue{at}ualberta.ca
xudong{at}cs.ualberta.ca

We compare the performance of seven methods in computing or approximating service levels for nonstationary M(t)/M/s(t) queueing systems: an exact method (a Runge-Kutta ordinary-differential-equation solver), the randomization method, a closure (or surrogate-distribution) approximation, a direct infinite-server approximation, a modified-offered-load infinite-server approximation, an effective-arrival-rate approximation, and a lagged stationary approximation. We assume an exhaustive service discipline, where service in progress when a server is scheduled to leave is completed before the server leaves. We used all of the methods to solve the same set of 640 test problems. The randomization method was almost as accurate as the exact method and used about half the computational time. The closure approximation was less accurate, and usually slower, than the randomization method. The two infinite-server-based approximations, the effective-arrival-rate approximation, and the lagged stationary approximation were less accurate but had computation times that were far shorter and less problem-dependent than the other three methods.

Key words: queues; nonstationary; queues; algorithms; queues; approximations
History: received June 2002; revised May 2005; accepted July 2005.