Minimizing Maximum Flowtime of Jobs with Arbitrary Parallelizability
Minimizing Maximum Flowtime of Jobs with Arbitrary Parallelizability
复制标题
通过任意并行性最小化作业的最大流程时间
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
N. Schabanel
中科院分区：
文献类型：
--
作者：
K. Pruhs;Julien Robert;N. Schabanel
本文研究了以最小化最大流量为目标的非盲眼作业调度问题，这些作业随时间推移到达，并且具有不同的大小和并行度。我们对可实现的竞争力给出了严格的限制。更具体地说，我们表明每个确定性非透视算法的竞争比率很高，即对于n个工作Ω（√n）。但是有一个简单的批处理算法是(1 + O)-处理器O(log n)-竞争的。这个简单的批处理算法是最优竞争的，因为对于任何常数s，没有确定性的非洞察力算法可以是s-处理器o（log n）竞争的。
We consider the problem of nonclairvoyantly scheduling jobs, which arrive over time and have varying sizes and degrees of parallelizability, with the objective of minimizing the maximum flow. We give essentially tight bounds on the achievable competitiveness. More specifically we show that the competitive ratio of every deterministic nonclairvoyant algorithm is high, namely Ω(√n) for n jobs. But there is a simple batching algorithm that is (1 + ɛ)-processor O(log n)-competitive. And this simple batching algorithm is optimally competitive as no deterministic nonclairvoyant algorithm can be s-processor o(log n)-competitive for any constant s.