Performance of Critical Path Type Algorithms for Scheduling on Parallel Processors

Abstract

In this paper, two well-known NP-hard problems with parallel processors, precedence constraints, unit execution time task systems, and the criterion of maximum lateness, are considered. The first problem has an additional restriction that a task may occupy more than one processor simultaneously, and the second considered problem is a unit communication delay problem. For both problems the worst-case performance of critical path type algorithms is analyzed. All performance guarantees presented are tight for arbitrary large instances of the respective problems.