Online Learning for Job Scheduling on Heterogeneous Machines

Yufei Ruan, Ali Yekkehkhany, S. Rasoul Etesami

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2020 59th IEEE Conference on Decision and Control, CDC 2020
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages591-596
Number of pages6
ISBN (Electronic)9781728174471
DOIs
StatePublished - Dec 14 2020
Event59th IEEE Conference on Decision and Control, CDC 2020 - Virtual, Jeju Island, Korea, Republic of
Duration: Dec 14 2020Dec 18 2020

Publication series

NameProceedings of the IEEE Conference on Decision and Control
Volume2020-December
ISSN (Print)0743-1546
ISSN (Electronic)2576-2370

Conference

Conference59th IEEE Conference on Decision and Control, CDC 2020
Country/TerritoryKorea, Republic of
CityVirtual, Jeju Island
Period12/14/2012/18/20

Keywords

  • Explore-then-Exploit
  • Job scheduling
  • Market equilibrium
  • Online learning
  • Upper confidence bound

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint

Dive into the research topics of 'Online Learning for Job Scheduling on Heterogeneous Machines'. Together they form a unique fingerprint.

Cite this