Stochastic load balancing on unrelated machines

Anupam Gupta, Amit Kumar, Viswanath Nagarajan, Xiangkun Shen

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


We consider the problem of makespan minimization: i.e., scheduling jobs on machines to minimize the maximum load. For the deterministic case, good approximations are known even when the machines are unrelated. However, the problem is not well-understood when there is uncertainty in the job sizes. In our setting the job sizes are stochastic, i.e., the size of a job j on machine i is a random variable Xij, whose distribution is known. (Sizes of different jobs are independent of each other.) The goal is to find a fixed assignment of jobs to machines, to minimize the expected makespan|i.e., the expected value of the maximum load over the m 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. However, the problem has remained open even for the next-harder related machines case. Our main result is a constant-factor approximation for the most general case of unrelated machines. The main technical challenge we overcome is obtaining an efficiently computable lower bound for the optimal solution. We give an exponential-sized LP that we argue gives a strong lower bound. Then we show how to round any fractional solution to satisfy only a small subset of the constraints, which are enough to bound the expected makespan of our solution. We then consider two generalizations. The first is the budgeted makespan minimization problem, where the goal is to minimize the makespan subject to scheduling any subset of jobs whose reward is at least some target reward R. We extend our above result to a constant-factor approximation here using polyhedral properties of the bipartite matching polytope. The second problem is the q-norm minimization problem, where we want to minimize the expected 'q-norm of the load vectors. Here we give an O(q= log q)-approximation algorithm using a reduction to the deterministic q-norm problem with side constraints.

Original languageEnglish (US)
Title of host publication29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
EditorsArtur Czumaj
PublisherAssociation for Computing Machinery
Number of pages12
ISBN (Electronic)9781611975031
StatePublished - 2018
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States
Duration: Jan 7 2018Jan 10 2018

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Country/TerritoryUnited States
CityNew Orleans

ASJC Scopus subject areas

  • Software
  • General Mathematics


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

Cite this