LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times
LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times
复制标题
DOI：
10.1007/11830924_15
复制
发表时间：
2006-08
期刊：
影响因子：
--
通讯作者：
A. Grigoriev;M. Sviridenko;M. Uetz
中科院分区：
文献类型：
--
作者：
A. Grigoriev;M. Sviridenko;M. Uetz
我们考虑不相关的并行机器上的调度问题，其目标是最小化完工时间。除了机器依赖性之外，任何作业的处理时间还取决于稀缺可再生资源的使用情况，例如水。工人。可以随时将给定数量的资源分配给正在进行的作业。分配给作业的资源越多，其处理时间就越短。该模型通过添加时间资源权衡来概括经典的不相关并行机调度问题。它也是 Shmoys 和 Tardos 研究的广义分配问题的自然变体。基于问题（松弛）问题的整数线性规划公式，我们采用 Kumar 等人的随机 LP 舍入技术。 （FOCS 2005）以获得接近最优的确定性积分 LP 解。我们展示了如何使用此舍入过程来导出调度问题的确定性 3.75 近似算法。这改进了之前的结果，即确定性 6.83 近似值和随机 4 近似值。这一改进归功于更好的 LP 舍入和新的调度算法，该算法可以被视为装箱谐波算法的受限版本。
We consider a scheduling problem on unrelated parallel machines with the objective to minimize the makespan. In addition to its machine dependence, the processing time of any job is dependent on the usage of a scarce renewable resource, e.g. workers. A given amount of that resource can be distributed over the jobs in process at any time. The more of the resource is allocated to a job, the smaller is its processing time. This model generalizes the classical unrelated parallel machine scheduling problem by adding a time-resource tradeoff. It is also a natural variant of a generalized assignment problem studied by Shmoys and Tardos. On the basis of an integer linear programming formulation for (a relaxation of) the problem, we adopt a randomized LP rounding technique from Kumar et al. (FOCS 2005) in order to obtain a deterministic, integral LP solution that is close to optimum. We show how this rounding procedure can be used to derive a deterministic 3.75-approximation algorithm for the scheduling problem. This improves upon previous results, namely a deterministic 6.83-approximation, and a randomized 4-approximation. The improvement is due to the better LP rounding and a new scheduling algorithm that can be viewed as a restricted version of the harmonic algorithm for bin packing.