Scheduling UET tasks on parallel machines: strength of priority algorithms

Abstract

The paper is concerned with the problem of scheduling a partially ordered set of unit execution time tasks on parallel identical machines in ordered to minimize the criterion of maximum lateness, which plays one of the central roles in scheduling theory. It is well known that the considered scheduling problem is NP-hard in the strong sense, and therefore various polynomial-time algorithms, developed for this problem, are usually characterized by their worst-case performance. For a broad class of scheduling algorithms, the paper introduces a notion of a strength, characterizing their worst-case performance, and within this formal framework gives a positive answer to the question of the existence of a strongest algorithm, i.e. an algorithm with the best worst-case performance.