TY - GEN
T1 - Online Learning for Job Scheduling on Heterogeneous Machines
AU - Ruan, Yufei
AU - Yekkehkhany, Ali
AU - Etesami, S. Rasoul
N1 - Publisher Copyright:
© 2020 IEEE.
PY - 2020/12/14
Y1 - 2020/12/14
N2 - Motivated by the fair allocation of goods in an offline market, we propose and study a new model for online job scheduling on heterogeneous machines. In this model, the goal is to schedule jobs on a set of machines in an online fashion with the overall quality of service as close as possible to an optimal offline benchmark. More precisely, we consider a job scheduling system consisting of a set of machines and indivisible jobs that arrive sequentially over time. When a job arrives, it must be scheduled and processed on a single machine where the utility received for such an assignment depends on the job-machine pair. It is assumed that each machine has a different power/energy budget and its welfare is proportional to the product of its power and its cumulative utilities. The goal is to maximize the total quality of service that is the sum of all the machines' welfare. However, in practice, the power budgets of machines often are not known and must be learned over time. To tackle this issue, we first propose a simple Explore-then-Exploit scheduling algorithm that achieves a sub-linear regret of (T2/3), where T is the total number of jobs. Here the regret is defined as the expected difference between the total quality of service obtained by the algorithm and its maximum value had we known the \mathcal{O}power budgets a priori. We then enhance this result by providing an Upper Confidence Bound (UCB) algorithm with only logarithmic regret \mathcal{O} (log T). Numerical results are conducted to evaluate the performance of the proposed algorithms for various ranges of parameters.
AB - Motivated by the fair allocation of goods in an offline market, we propose and study a new model for online job scheduling on heterogeneous machines. In this model, the goal is to schedule jobs on a set of machines in an online fashion with the overall quality of service as close as possible to an optimal offline benchmark. More precisely, we consider a job scheduling system consisting of a set of machines and indivisible jobs that arrive sequentially over time. When a job arrives, it must be scheduled and processed on a single machine where the utility received for such an assignment depends on the job-machine pair. It is assumed that each machine has a different power/energy budget and its welfare is proportional to the product of its power and its cumulative utilities. The goal is to maximize the total quality of service that is the sum of all the machines' welfare. However, in practice, the power budgets of machines often are not known and must be learned over time. To tackle this issue, we first propose a simple Explore-then-Exploit scheduling algorithm that achieves a sub-linear regret of (T2/3), where T is the total number of jobs. Here the regret is defined as the expected difference between the total quality of service obtained by the algorithm and its maximum value had we known the \mathcal{O}power budgets a priori. We then enhance this result by providing an Upper Confidence Bound (UCB) algorithm with only logarithmic regret \mathcal{O} (log T). Numerical results are conducted to evaluate the performance of the proposed algorithms for various ranges of parameters.
KW - Explore-then-Exploit
KW - Job scheduling
KW - Market equilibrium
KW - Online learning
KW - Upper confidence bound
UR - http://www.scopus.com/inward/record.url?scp=85099880678&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85099880678&partnerID=8YFLogxK
U2 - 10.1109/CDC42340.2020.9303733
DO - 10.1109/CDC42340.2020.9303733
M3 - Conference contribution
AN - SCOPUS:85099880678
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 591
EP - 596
BT - 2020 59th IEEE Conference on Decision and Control, CDC 2020
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 59th IEEE Conference on Decision and Control, CDC 2020
Y2 - 14 December 2020 through 18 December 2020
ER -