On the average waiting time for regular routing to deterministic queues

• 成果类型: Article
• 署名作者: Hordijk, A; van der Laan, D
• 署名单位: Leiden University - Excl LUMC; Leiden University; Vrije Universiteit Amsterdam
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1040.0135
• 发表日期: 2005
• 页码: 521-544
• 关键词: Optimization; convexity

摘要

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.