This paper deals with scheduling problems in multiprocessor environments. Many scheduling problems are known to be NP-complete if minimum finish time is demanded. In many practical cases, however, the guarantee of keeping certain deadlines is sufficient. This situation is typical for real-time processing environments, for example. Thus, the authors’ problem is relevant: Is it possible to preemptively schedule n jobs in such a way that every job is complete by its given due time?

Following a very brief introduction to some results relating to scheduling problems, the authors derive a necessary and sufficient condition for a feasible schedule. They then develop an O(q² × n + n × log n) algorithm to obtain a preemptive schedule for n jobs given their due times and memory requirements. The algorithm minimizes maximum lateness and contains at most O(q × n) preemptions. The value of the minimum maximum lateness can itself be found in O(q × n + n × log n) time.

In spite of the practical relevance of their algorithm, the authors have not helped the reader by describing their solution in a manner that eases transformation into an executable computer program. The usage of mnemonic identifiers and the inclusion of scheduling examples would have helped to gain insight into the algorithm more rapidly. Nevertheless, the paper is valuable for the specialist interested in scheduling problems.