Managing Queues with Different Resource Requirements

作     者：Zychlinski, Noa Chan, Carri W. Dong, Jing 

作者机构：Techn Israel Inst Technol Fac Ind Engn & Management IL-32000 Haifa Israel Columbia Business Sch Div Decis Risk & Operat New York NY 10027 USA 

出 版 物：《OPERATIONS RESEARCH》 (Oper Res)

年 卷 期：2023年第71卷第4期

页      面：1387-1413页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：National Science Foundation [CMMI-1762544] Eric and Wendy Schmidt Postdoctoral Award for Women in Mathematical and Computing Sciences Israeli Council for Higher Education 

主　　题：queue scheduling different resource requirements coupling competitive analysis asymptotic optimality 

摘      要：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.