On the Average Waiting Time for Regular Routing to Deterministic Queues

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

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of operations research 2005-05, Vol.30 (2), p.521-544
Main Authors: Hordijk, Arie, van der Laan, Dinard
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Arithmetic mean
average waiting time
continued fraction expansion
Continued fractions
Determinism
Farey interval
Management science
Mathematical intervals
Mathematical sequences
Mathematical theorems
Operations research
optimal routing
parallel queues
Queuing theory
Rational numbers
regular sequence
Studies
Waiting period
Workloads
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0364-765X
1526-5471
DOI:10.1287/moor.1040.0135