Stochastic Load Balancing on Unrelated Machines
Stochastic Load Balancing on Unrelated Machines
复制标题
DOI：
10.1137/1.9781611975031.83
复制
发表时间：
2018-01
期刊：
影响因子：
--
通讯作者：
Anupam Gupta;Amit Kumar;V. Nagarajan;Xiangkun Shen
中科院分区：
文献类型：
--
作者：
Anupam Gupta;Amit Kumar;V. Nagarajan;Xiangkun Shen
本文研究了工件尺寸随机时不相关机器的最小完工时间问题。目标是找到一个固定的分配工作的机器，以最小化的期望值的最大负载在所有的机器。对于相同机器的特殊情况下，当一个工作的大小是相同的所有机器，常数因子近似算法早已知道。我们的主要结果是第一个常数因子近似算法的一般情况下不相关的机器。这是通过（i）制定一个下界使用指数大小的线性规划，是有效的计算和（ii）四舍五入这个线性规划，同时只满足一个特定的子集的约束，仍然足以约束预期的完工时间。我们还考虑两个概括。第一个是预算最大完工时间最小化问题，目标是在调度目标数量（或奖励）的工件的情况下，最小化预期的最大完工时间。我们扩展我们的主要结果，以获得这个问题的常数因子近似算法。第二个问题涉及q范数目标，我们希望最小化机器负载的期望q范数。这里我们给出一个[公式：见正文]-近似算法，它是对任何固定q的常数因子近似。
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 [Formula: see text]-approximation algorithm, which is a constant-factor approximation for any fixed q.