论文标题
在相关机器上的沟通意识安排。
Communication-Aware Scheduling of Precedence-Constrained Tasks on Related Machines
论文作者
论文摘要
安排优先限制的任务是一个经典问题，已经研究了五十多年。但是，在任务之间存在通信延迟的环境中几乎没有进展。相同机器的情况是将近30年前得出的结果，但是相关机器的结果尚未遵循。在这项工作中，我们首先提出了一个新的调度程序，最早的时间（GETF），并提供了第一个可证明的，最差的近似近似保证金，以最大程度地限制MakePAN和任务的总加权完成时间，并具有与机器相关通信时间的相关机器上的优先限制。
Scheduling precedence-constrained tasks is a classical problem that has been studied for more than fifty years. However, little progress has been made in the setting where there are communication delays between tasks. Results for the case of identical machines were derived nearly thirty years ago, and yet no results for related machines have followed. In this work, we propose a new scheduler, Generalized Earliest Time First (GETF), and provide the first provable, worst-case approximation guarantees for the goals of minimizing both the makespan and total weighted completion time of tasks with precedence constraints on related machines with machine-dependent communication times.
