QUEUING WITH FUTURE INFORMATION

• 成果类型: Article
• 署名作者: Spencer, Joel; Sudan, Madhu; Xu, Kuang
• 署名单位: New York University; Microsoft; Massachusetts Institute of Technology (MIT)
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/13-AAP973
• 发表日期: 2014
• 页码: 2091-2142
• 关键词: optimality; admission; Servers

摘要

study an admissions control problem, where a queue with service rate 1 - p receives incoming jobs at rate lambda epsilon (1 - p, 1), and the decision maker is allowed to redirect away jobs up to a rate of p, with the objective of minimizing the time-average queue length. We show that the amount of information about the future has a significant impact on system performance, in the heavy-traffic regime. When the future is unknown, the optimal average queue length diverges at rate similar to log(1)/(1-p) 1/1-lambda, as lambda -> 1. In sharp contrast, when all future arrival and service times are revealed beforehand, the optimal average queue length converges to a finite constant, (1 - p)/p, as lambda -> 1. We further show that the finite limit of (1 - p)/ p can be achieved using only a finite lookahead window starting from the current time frame, whose length scales asO (log 1/1-lambda), as lambda -> 1. This leads to the conjecture of an interesting duality between queuing delay and the amount of information about the future.