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 Hordijk, A. Articles by van der Laan, D. Search for Related Content

On the Average Waiting Time for Regular Routing to Deterministic Queues

Mathematical Institute, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands
Department of Econometrics and Operations Research, Vrije Universiteit, De Boelelaan 1105, 1081 HV Amsterdam, The Netherlands
hordijk{at}math.leidenuniv.nl
dalaan{at}feweb.vu.nl

We consider a deterministic queueing system in which N 2 servers of different speeds operate in parallel. Each service in queue i takes the deterministic time S_i. Identical customers arrive exactly one per time unit, and it is desirable to route them to the queues so that the average waiting time (we consider as waiting time the time a customer waits in the buffer of a queue, and thus the service time is not included in this) is minimized. We provide an algorithm to compute lower and upper bounds on this quantity. The upper bound is found by showing that there is a periodic policy for which the average waiting time is no greater than the lower bound plus (N / 2) – 1. Thus, the bounds coincide when N = 2. For obtaining the lower bound, we give explicit formulae for the average waiting time in case of regular routing to a deterministic queue.

Key Words: parallel queues; average waiting time; optimal routing; regular sequence; continued fraction expansion; Farey interval
History: Received: January 23, 2003; revision received: June 28, 2003;revision received: January 20, 2004;revision received: August 23, 2004;