Stochastic load balancing on unrelated machines

Anupam Gupta, Amit Kumar, Viswanath Nagarajan, Xiangkun Shen

Research output: Contribution to journalArticlepeer-review


We consider the problem of makespan minimization on unrelated machines when job sizes are stochastic. The goal is to find a fixed assignment of jobs to machines, to minimize the expected value of the maximum load over all the machines. For the identical-machines special case when the size of a job is the same across all machines, a constant-factor approximation algorithm has long been known. Our main result is the first constant-factor approximation algorithm for the general case of unrelated machines. This is achieved by (i) formulating a lower bound using an exponential-size linear program that is efficiently computable and (ii) rounding this linear program while satisfying only a specific subset of the constraints that still suffice to bound the expected makespan. We also consider two generalizations. The first is the budgeted makespan minimization problem, where the goal is to minimize the expected makespan subject to scheduling a target number (or reward) of jobs. We extend our main result to obtain a constant-factor approximation algorithm for this problem. The second problem involves q-norm objectives, where we want to minimize the expected q-norm of the machine loads. Here we give an O(q/log q)-approximation algorithm, which is a constant-factor approximation for any fixed q.

Original languageEnglish (US)
Pages (from-to)115-133
Number of pages19
JournalMathematics of Operations Research
Issue number1
StatePublished - Feb 2021


  • Approximation algorithms
  • Scheduling
  • Stochastic optimization

ASJC Scopus subject areas

  • General Mathematics
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Stochastic load balancing on unrelated machines'. Together they form a unique fingerprint.

Cite this