.png){kind=icon}
返回
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
摘要
En 中文
我们考虑在由m台均匀相关机器组成的并行机上执行在线速度鲁棒调度。大小任意的作业逐一到达，需要立即且在不了解机器速度信息的情况下分配到固定数量M = m的袋中。当作业序列完成后，算法会收到速度列表，并将所有袋分配给机器。对于每个袋，分配到该袋的所有作业都分配到同一台机器。在离线问题变体中，作业序列以集合形式给出，但速度信息也仅在创建袋后才会揭示。算法的质量衡量方式类似于近似算法和在线算法，我们研究了两个目标：最短完成时间最小化和最小负载最大化。尽管允许作业逐一到达，但我们达到了与离线速度鲁棒最短完成时间最小化问题已知最佳结果相匹配的成果。对于我们研究的多数情况，我们证明了比标准在线问题对应情况显著更好的结果，其中每个新作业被不可撤销地分配给一台机器。然而，我们表明并非所有情况都能获得此类改进结果。部分结果被扩展到可以使用M > m袋的情形。最后，我们考虑两台机器和三类作业的离线问题，该问题在先前研究中被探讨。我们证明，对于两台机器和两个袋，任意大小的作业与单位大小作业不同，尽管单位作业大小的已知结果与无穷小作业相同。此外，我们证明对于三类作业，三个袋下的最佳可能结果各不相同。这是首个表明任意大小作业情况可能比单位大小更困难的变体。
Keyword:
Uniformly related machines
Speed-robust
Makespan minimization
