Dynamic Scheduling of Multiclass Many-Server Queues with Abandonment: The Generalized cμ/h Rule

• 成果类型: Article
• 署名作者: Long, Zhenghua; Shimkin, Nahum; Zhang, Hailun; Zhang, Jiheng
• 署名单位: Nanjing University; Technion Israel Institute of Technology; The Chinese University of Hong Kong, Shenzhen; Hong Kong University of Science & Technology
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1908
• 发表日期: 2020
• 页码: 1218-1230
• 关键词: multiclass queue; ABANDONMENT; fluid model; dynamic scheduling; knapsack problem

摘要

We study the fluid model of a many-server queue with multiple customer classes and obtain optimality results for this model. For the purpose of minimizing the long-run average queue-length costs and abandon penalties, we propose three scheduling policies to cope with any general cost functions and general patience-time distributions. First, we introduce the target-allocation policy, which assigns higher priority to customer classes with larger deviation from the desired allocation of the service capacity and prove its optimality for any general queue-length cost functions and patience-time distributions. The Gc mu/h rule, which extends the well-known Gc mu rule by taking abandonment into account, is shown to be optimal for the case of convex queue-length costs and nonincreasing hazard rates of patience. For the case of concave queue-length costs but nondecreasing hazard rates of patience, it is optimal to apply a fixed-priority policy, and a knapsack-like problem is developed to determine the optimal priority order efficiently. As a motivating example of the operations of emergency departments, a hybrid of the Gc mu/h rule and the fixed-priority policy is suggested to reduce crowding and queue abandonment. Numerical experiments show that this hybrid policy performs satisfactorily. We also prove the asymptotic optimality of policies in the original queueing system using the fluid results.