Managing Queues with Different Resource Requirements

• 成果类型: Article
• 署名作者: Zychlinski, Noa; Chan, Carri W.; Dong, Jing
• 署名单位: Technion Israel Institute of Technology; Columbia University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2284
• 发表日期: 2023
• 页码: 1387-1413
• 关键词: convex delay costs; Asymptotic Optimality; strategic idleness; customers require; random number; many-server; multiclass; workload; SYSTEM; prioritization

摘要

Queueing models that are used to capture various service settings typically assume that customers require a single unit of resource (server) to be processed. However, there are many service settings where such an assumption may fail to capture the heterogeneity in resource requirements of different customers. We propose a multiserver queueing model with multiple customer classes in which customers from different classes may require different amounts of resources to be served. We study the optimal scheduling policy for such systems. To balance holding costs, service rates, resource requirement, and priority-induced idleness, we develop an index-based policy that we refer to as the idle-avoid c mu/m rule. For a two-class two-server model, where policy-induced idleness can have a big impact on system performance, we characterize cases where the idle-avoid c mu/m rule is optimal. In other cases, we establish a uniform performance bound on the amount of suboptimality incurred by the idle-avoid c mu/m rule. For general multiclass multiserver queues, we establish the asymptotic optimality of the idle-avoid c mu/m rule in the many-server regime. For long-time horizons, we show that the idle-avoid c mu/m is throughput optimal. Our theoretical results, along with numerical experiments, provide support for the good and robust performance of the proposed policy.