Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios
Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios
复制标题
DOI：
10.1137/1.9781611974782.175
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
Christos Kalaitzis;O. Svensson;Jakub Tarnawski
中科院分区：
文献类型：
--
作者：
Christos Kalaitzis;O. Svensson;Jakub Tarnawski
考虑了一类经典的排序问题，目标函数为极小化完工时间的加权和。最近，对于一个小常数e > 0，Bansal等人给出了一个（3/2 − e）-近似算法，改进了独立随机舍入的“自然”障碍3/2。简单地说，他们的结果是通过增强独立随机舍入通过强负相关特性。在这项工作中，我们采取了不同的方法，并建议使用相同的优雅的舍入计划的加权完成时间的目标，由Shmoys和Tardos设计优化的线性函数的最大完工时间的限制。我们的主要结果是一个1.21近似算法的自然特殊情况下，一个工作的重量是成比例的处理时间（具体来说，所有的工作有相同的史密斯比），这表示的概念，每个工作单位有相同的权重。此外，作为舍入的直接结果，我们的算法也实现了一个双标准2-近似的最大完工时间目标。我们的技术贡献是一个严格的分析相比，由简化LP松弛的解决方案的预期成本-我们减少这项任务，以了解某些最坏的情况下，这是简单的分析。
We consider the classic problem of scheduling jobs on unrelated machines so as to minimize the weighted sum of completion times. Recently, for a small constant e > 0, Bansal et al. gave a (3/2 − e)-approximation algorithm improving upon the "natural" barrier of 3/2 which follows from independent randomized rounding. In simplified terms, their result is obtained by an enhancement of independent randomized rounding via strong negative correlation properties. In this work, we take a different approach and propose to use the same elegant rounding scheme for the weighted completion time objective as devised by Shmoys and Tardos for optimizing a linear function subject to makespan constraints. Our main result is a 1.21-approximation algorithm for the natural special case where the weight of a job is proportional to its processing time (specifically, all jobs have the same Smith ratio), which expresses the notion that each unit of work has the same weight. In addition, as a direct consequence of the rounding, our algorithm also achieves a bi-criteria 2-approximation for the makespan objective. Our technical contribution is a tight analysis of the expected cost of the solution compared to the one given by the Configuration-LP relaxation - we reduce this task to that of understanding certain worst-case instances which are simple to analyze.