Learning While Scheduling in Multi-Server Systems With Unknown Statistics: MaxWeight with Discounted UCB
Learning While Scheduling in Multi-Server Systems With Unknown Statistics: MaxWeight with Discounted UCB
复制标题
DOI：
--
复制
发表时间：
2022-09
期刊：
影响因子：
--
通讯作者：
Zixi Yang;R. Srikant;Lei Ying
中科院分区：
文献类型：
--
作者：
Zixi Yang;R. Srikant;Lei Ying
多服务器排队系统是机器学习、无线网络、众包和医疗保健系统中广泛使用的作业调度模型。研究了具有多个服务器和多种作业类型的多服务器系统，其中不同的作业类型在不同的服务器上需要不同的处理时间。目标是在不知道处理时间统计信息的情况下在服务器上调度作业。为了充分利用服务器的处理能力，众所周知，至少必须了解不同服务器上不同作业类型的服务速率。以前关于这个主题的工作将学习和调度阶段分离，这要么导致过度探索，要么导致极大的作业延迟。我们提出了一种新的算法，它将MaxWeight调度策略与折扣置信限(UCB)相结合，同时学习统计数据并将作业调度到服务器上。我们证明了在我们的算法下，渐近平均排队长度为1除以交通松弛，这是按顺序最优的。我们还得到了任意时间排队长度的指数衰减概率尾界。这些结果对固定和非固定服务费率都适用。仿真结果表明，该算法的时延性能比以前提出的算法高出几个数量级。
Multi-server queueing systems are widely used models for job scheduling in machine learning, wireless networks, crowdsourcing, and healthcare systems. This paper considers a multi-server system with multiple servers and multiple types of jobs, where different job types require different amounts of processing time at different servers. The goal is to schedule jobs on servers without knowing the statistics of the processing times. To fully utilize the processing power of the servers, it is known that one has to at least learn the service rates of different job types on different servers. Prior works on this topic decouple the learning and scheduling phases which leads to either excessive exploration or extremely large job delays. We propose a new algorithm, which combines the MaxWeight scheduling policy with discounted upper confidence bound (UCB), to simultaneously learn the statistics and schedule jobs to servers. We prove that under our algorithm the asymptotic average queue length is bounded by one divided by the traffic slackness, which is order-wise optimal. We also obtain an exponentially decaying probability tail bound for any-time queue length. These results hold for both stationary and nonstationary service rates. Simulations confirm that the delay performance of our algorithm is several orders of magnitude better than previously proposed algorithms.