论文标题
垃圾箱在两台分层机上迁移
Bin stretching with migration on two hierarchical machines
论文作者
论文摘要
在本文中，我们考虑在两台层次机器上迁移，目的是将Makepan迁移到两台分层机上。两台层次机器的含义是，其中一台机器可以运行任何作业，而另一台机器只能运行特定的作业。每个实例还具有固定的参数M \ GEQ 0，称为迁移因子。作业是一一呈现的。每个新作业到达时都必须分配给机器，同时，可以修改先前分配的作业的分配，从而使移动的作业的总尺寸不超过新作业大小的M倍。 这里研究的半隔线变体称为bin Stretching。在此问题中，提前向调度程序提供了最佳MakePAN。对于任何迁移因子M \ geq 0，这仍然是一个非平凡的变体。我们证明，对于任何迁移因子M的竞争比率，我们都具有紧密的界限，其中根据M的值和结果竞争比率，设计和分析被分为几种情况。与两台分层机迁移的在线变体不同，这种情况允许在线近似方案。
In this paper, we consider semi-online scheduling with migration on two hierarchical machines, with the purpose of minimizing the makespan. The meaning of two hierarchical machines is that one of the machines can run any job, while the other machine can only run specific jobs. Every instance also has a fixed parameter M \geq 0, known as the migration factor. Jobs are presented one by one. Each new job has to be assigned to a machine when it arrives, and at the same time it is possible to modify the assignment of previously assigned jobs, such that the moved jobs have a total size not exceeding M times the size of the new job. The semi-online variant studied here is called bin stretching. In this problem, the optimal makespan is provided to the scheduler in advance. This is still a non-trivial variant for any migration factor M \geq 0. We prove tight bounds on the competitive ratio for any migration factor M, where the design and analysis is split into several cases, based on the value of M, and the resulting competitive ratio. Unlike the online variant with migration for two hierarchical machines, this case allows an online approximation scheme.
