Stochastic Load Balancing on Unrelated Machines

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 i...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-04
Main Authors: Gupta, Anupam, Kumar, Amit, Nagarajan, Viswanath, Shen, Xiangkun
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Job shops
Linear programming
Load balancing
Lower bounds
Mathematical analysis
Optimization
Production scheduling
Rounding
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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\).
ISSN:2331-8422