作者：
Mallach, SvenUniv Bonn
High Performance Comp & Analyt Lab Friedrich Hirzebruch Allee 8 D-53115 Bonn Germany
There is some evidence that labeling schemes as employed for instance in the famous coffman-graham algorithm may provide superior worst-case approximation guarantees than purely path-or level-based list schedules in t...
详细信息
There is some evidence that labeling schemes as employed for instance in the famous coffman-graham algorithm may provide superior worst-case approximation guarantees than purely path-or level-based list schedules in the presence of (delayed) precedence constraints. In 1989, Bernstein, Rodeh, and Gertner proved that this also holds true for their labeling scheme targeting unit execution time tasks on a single processor provided that all delays imposed by a single task on all of its successors are uniformly either zero or some fixed positive integer. They further conjectured that this superiority is preserved when allowing the delays imposed by a task to differ successor-wise. It is shown in this note however that their labeling scheme as well as more general ones may perform as bad as any list schedule in this case. Moreover, a new lower bound on the worst-case performance of labeling methods in the multiprocessor setting is derived. (C) 2021 Elsevier Inc. All rights reserved.
This paper is concerned with the problem of scheduling on two processors tasks with 1- or 2-unit execution time and having arbitrary precedence constraints. An analysis is made of the algorithm (called f LPTS-schedule...
详细信息
暂无评论