论文标题
在统一机器上的在线负载平衡，迁移有限
Online Load Balancing on Uniform Machines with Limited Migration
论文作者
论文摘要
在与统一相关的机器和有限迁移的统一相关机器上平衡的问题，作业接一个地在线到达，必须立即将其放置在一套给定的机器之一上，而无需以后可能到达的工作。每个作业都有一个尺寸，每台机器都有一个速度，并且通过将第一个值除以第二个值而获得的负载是获得机器的。目标是最大程度地减少任何机器收到的最大总负载。但是，与纯在线案例不同，每次新工作到达时，迁移潜力等于其大小和一定的迁移因素。可以将这种潜力用于立即重新分配工作（未赎回的情况）或任何以后的时间（摊销案例）。已经对这种口味的半对线模型进行了深入的研究，例如几个基本问题，例如，在相同的机器和垃圾箱包装上的负载平衡，但迄今尚未考虑统一相关的机器。在本文中，在统一相关机器上的经典加倍策略与迁移相结合，以实现$（8/3+\ varepsilon）$ - 竞争算法和$（4+ \ varepsilon）$ - 竞争算法的$ O（1/\ varepsilon $ amortive amortative amortative amortative amortative at Anemiity promiiania promiiania promioratiia promiiania promiate promiiania promiate promiate a puratizior purairia puratize promioratiiial cutiora，相应的竞赛，相应大约$ 5.828 $。
In the problem of online load balancing on uniformly related machines with bounded migration, jobs arrive online one after another and have to be immediately placed on one of a given set of machines without knowledge about jobs that may arrive later on. Each job has a size and each machine has a speed, and the load due to a job assigned to a machine is obtained by dividing the first value by the second. The goal is to minimize the maximum overall load any machine receives. However, unlike in the pure online case, each time a new job arrives it contributes a migration potential equal to the product of its size and a certain migration factor. This potential can be spend to reassign jobs either right away (non-amortized case) or at any later time (amortized case). Semi-online models of this flavor have been studied intensively for several fundamental problems, e.g., load balancing on identical machines and bin packing, but uniformly related machines have not been considered up to now. In the present paper, the classical doubling strategy on uniformly related machines is combined with migration to achieve an $(8/3+\varepsilon)$-competitive algorithm and a $(4+\varepsilon)$-competitive algorithm with $O(1/\varepsilon)$ amortized and non-amortized migration, respectively, while the best known competitive ratio in the pure online setting is roughly $5.828$.
