SCHEDULING PARALLEL SERVERS IN THE NONDEGENERATE SLOWDOWN DIFFUSION REGIME: ASYMPTOTIC OPTIMALITY RESULTS

• 成果类型: Article
• 署名作者: Atar, Rami; Gurvich, Itai
• 署名单位: Technion Israel Institute of Technology; Northwestern University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/13-AAP935
• 发表日期: 2014
• 页码: 760-810
• 关键词: threshold policy; queuing-systems; heavy; queues; LIMITS

摘要

We consider the problem of minimizing queue-length costs in a system with heterogenous parallel servers, operating in a many-server heavy-traffic regime with nondegenerate slowdown. This regime is distinct from the well-studied heavy traffic diffusion regimes, namely the (single server) conventional regime and the (many-server) Halfin-Whitt regime. It has the distinguishing property that waiting times and service times are of comparable magnitudes. We establish an asymptotic lower bound on the cost and devise a sequence of policies that asymptotically attain this bound. As in the conventional regime, the asymptotics can be described by means of a Brownian control problem, the solution of which exhibits a state space collapse.