Using duplication for scheduling unitary tasks on m processors with unit communication delays

AbstractThis paper introduces a new list scheduling algorithm that uses greedy duplication to solve a scheduling problem with communication delays and resource limitations. We prove that, for any priority list, its worst-case relative performance is bounded by 2 − 1m and that this bound is tight