Stochastic Load Balancing on Unrelated Machines

• 成果类型: Article
• 署名作者: Gupta, Anupam; Kumar, Amit; Nagarajan, Viswanath; Shen, Xiangkun
• 署名单位: Carnegie Mellon University; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi; University of Michigan System; University of Michigan
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2019.1049
• 发表日期: 2021
• 页码: 115-133
• 关键词: approximation algorithms; bandwidth

摘要

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