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.
