Shortest-Job-First Scheduling in Many-Server Queues with Impatient Customers and Noisy Service-Time Estimates

• 成果类型: Article; Early Access
• 署名作者: Dong, Jing; Ibrahim, Rouba
• 署名单位: Columbia University; University of London; University College London
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.310
• 发表日期: 2024
• 关键词: SJF; impatience; noisy service times; many-server queues

摘要

Size-based scheduling has been extensively studied yet almost exclusively in single-server queues with infinitely patient jobs and perfectly known service times. Much less is known about its performance in many-server queues, particularly under noisy service-time information. In this paper, we derive theoretical results that quantify the performance of the nonpreemptive shortest-job-first (SJF) policy in many-server queues with abandonment and noisy service-time estimates. In particular, we consider the M/GI/s + GI queue and service-time estimates that have either a discrete distribution with finite support or a continuous distribution. In the discrete case, we prove that the SJF policy asymptotically maximizes the throughput in the system among all nonpreemptive scheduling disciplines that use that noisy service-time information. In the continuous case, we prove that a discretized version of SJF, which classifies customers into a finite number of priority classes based on their noisy service-time predictions, asymptotically maximizes the throughput in the system as well when the number of priority classes increases without bound. By taking this limit, performance under the SJF policy is, asymptotically, indistinguishable from performance under a carefully designed two-class priority rule, in which customers with short predicted service times (below a threshold) are served without wait, whereas customers with long predicted service times (above the threshold) eventually abandon without service.