Stochastic Scheduling of Heavy-tailed Jobs
Stochastic Scheduling of Heavy-tailed Jobs
复制标题
重尾作业的随机调度
DOI：
10.4230/lipics.stacs.2015.474
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
K. Pruhs
中科院分区：
文献类型：
--
作者：
Sungjin Im;Benjamin Moseley;K. Pruhs
为了使m台相同的机器P \mid\mid\mathbb{E}\sum C＿j的总完成时间最小，我们重新研究了标准三域调度表法中n个作业的非抢先调度的经典随机调度问题。以前，只有在作业大小具有低可变性的情况下，才知道如何获得合理的近似。然而，在实践中通常出现的分布具有很高的可变性，并且在最大可能的作业规模中，这些分布的先前算法的近似比率的上界甚至可以是逆多项式。我们从这个开始
自然列表调度算法最短预期处理时间（SEPT）对于高可变性作业具有较差的近似比。我们观察到，自然线性规划松弛的简单随机四舍五入是(1+ \epsilon)-机器O(1)-近似值，假设机器的数量在作业数量上至少是对数的。在机器数量有限的情况下，我们开发了一个近似为O（\log ^2 n + m \log n）的列表调度算法。我们的结果共同暗示了(1+ \epsilon)-机器O(\log ^2 n)-对任意数量的机器的近似。直观地，我们的列表调度算法找到的排序不仅考虑了作业的预期大小，而且还考虑了作业很大的概率。
We revisit the classical stochastic scheduling problem of nonpreemptively scheduling n jobs so as to minimize total completion time on m identical machines, P \mid \mid \mathbb{E} \sum C_j in the standard 3-field scheduling notation. Previously it was only known how to obtain reasonable approximation if jobs sizes have low variability. However, distributions commonly arising in practice have high variability, and the upper bounds on the approximation ratio for the previous algorithms for such distributions can be even inverse-polynomial in the maximum possible job size. We start by showing that
the natural list scheduling algorithm Shortest Expected Processing Time (SEPT) has a bad approximation ratio for high variability jobs. We observe that a simple randomized rounding of a natural linear programming relaxation is a (1+\epsilon)-machine O(1)-approximation assuming the number of machines is at least logarithmic in the number of jobs. Turning to the case of a modest number of machines, we develop a list scheduling algorithm that is O(\log^2 n + m \log n)-approximate. Our results together imply a (1+\epsilon)-machine O(\log^2 n )-approximation for an arbitrary number of machines. Intuitively our list scheduling algorithm finds an ordering that not only takes the expected size of a job into account, but also takes into account the probability that job will be big.