Routing jobs to servers with deterministic service times

• 成果类型: Article
• 署名作者: van der Laan, D
• 署名单位: Vrije Universiteit Amsterdam
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1040.0131
• 发表日期: 2005
• 页码: 195-224
• 关键词: symbolic dynamics; SEQUENCES; optimization

摘要

In this paper we consider the problem of routing deterministic arriving jobs to parallel servers with deterministic (distinct) service times, where we assume that the arrival rate of the jobs is equal to the total service capacity of the servers. Our goal is to find routing policies that minimize the long-run average waiting time of the arriving jobs. We give lower and upper bounds for the minimal long-run average waiting time, and we present results on the structure of optimal policies. We derive mathematical programming problems that can be solved to obtain optimal routing policies, and for a single queue we have results on routing according to a regular sequence to that queue. Finally, we discuss several algorithms to obtain within reasonable time good but generally not optimal deterministic routing policies.