Scheduling multiprocessor UET tasks of two sizes

In this paper we study task scheduling problems on m identical parallel processors, where each task has unit execution time, and needs either a single processor, or q processors concurrently, and it has a release date and a due date. Under the assumption that the release dates and due dates of the q-processor tasks are agreeable, we describe a polynomial time algorithm for minimising the number of tardy tasks. In addition, we apply this result for minimising the maximum lateness, and the maximum tardiness. We also discuss the combinatorial background of the polynomial time solvability of all these problems under the ‘agreeable’ assumption.