The Power of Migration in Online Machine Minimization
The Power of Migration in Online Machine Minimization
复制标题
DOI：
10.1145/2935764.2935786
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
Lin Chen;Nicole Megow;Kevin Schewior
中科院分区：
文献类型：
--
作者：
Lin Chen;Nicole Megow;Kevin Schewior
在本文中，我们调查了多台平行机上在线计划中迁移的力量。问题是在最少数量的机器上安排可享受的工作日期和截止日期。我们表明，迁移，也就是说，允许在另一台机器上继续进行先发制人的工作，对时间表的性能产生了巨大影响。更确切地说，让m为迁移解决方案所需的机器数量；然后，在M中不受限制地不受限制的机器数量的增加。这与此问题的变体有关以前的结果与以前的结果进行了补充。在离线变体和允许额外速度的模型中，迁移的力量受到限制，因为机器数量和速度的增加可以通过一个小常数来界定。在本文中，我们还根据非移民在线计划的竞争比率得出了第一个非平凡界限，以最大程度地减少机器数量而没有额外的速度。我们表明，通常没有在线算法可以达到F（M），对于任何功能F，并给出Omega（log N）的下限。对于具有“宽松”作业的可愉快的实例和实例，我们给出了o（1） - 竞争算法，对于层流实例，我们得出了O（log M） - 竞争算法。
In this paper we investigate the power of migration in online scheduling on multiple parallel machines. The problem is to schedule preemptable jobs with release dates and deadlines on a minimum number of machines. We show that migration, that is, allowing that a preempted job is continued on a different machine, has a huge impact on the performance of a schedule. More precisely, let m be the number of machines required by a migratory solution; then the increase in the number of machines when disallowing migration is unbounded in m. This complements and strongly contrasts previous results on variants of this problem. In both the offline variant and a model allowing extra speed, the power of migration is limited as the increase of number of machines and speed, respectively, can be bounded by a small constant. In this paper, we also derive the first non-trivial bounds on the competitive ratio for non-migratory online scheduling to minimize the number of machines without extra speed. We show that in general no online algorithm can achieve a competitive ratio of f(m), for any function f, and give a lower bound of Omega(log n). For agreeable instances and instances with "loose" jobs, we give O(1)-competitive algorithms and, for laminar instances, we derive an O(log m)-competitive algorithm.