Learning While Scheduling in Multi-Server Systems with Unknown Statistics: MaxWeight with Discounted UCB
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.
Code (0)
등록된 구현이 없습니다.
Tasks
SchedulingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Scheduling Servers with Stochastic Bilinear Rewards
We address a control system optimization problem that arises in multi-class, multi-server queueing system scheduling with uncertainty. In this scenario, jobs incur holding costs while awaiting completion, and job-server …
SchedulingUpdate Estimation and Scheduling for Over-the-Air Federated Learning with Energy Harvesting Devices
We study over-the-air (OTA) federated learning (FL) for energy harvesting devices with heterogeneous data distribution over wireless fading multiple access channel (MAC). To address the impact of low energy arrivals and …
Federated LearningSchedulingMinimal-order Appointed-time Unknown Input Observers: Design and Applications
This paper presents a framework on minimal-order appointed-time unknown input observers for linear systems based on the pairwise observer structure. A minimal-order appointed-time observer is first proposed for the linea…
State EstimationHigher-order sliding mode observer design for linear time-invariant multivariable systems based on a new observer normal form
In various applications in the field of control engineering the estimation of the state variables of dynamic systems in the presence of unknown inputs plays an important role. Existing methods require the so-called obser…
FormUnknown Input Observer Design for Linear Time-Invariant Systems -- A Unifying Framework
This paper presents a new observer design approach for linear time invariant multivariable systems subject to unknown inputs. The design is based on a transformation to the so-called special coordinate basis. This form r…