A note on scheduling tall/small multiprocessor tasks with unit processing time to minimize maximum tardiness

We study the scheduling situation where n tasks, subjected to release dates and due dates, have to be scheduled on m parallel processors. We show that, when tasks have unit processing times and either require l or m processors simultaneously, the minimum maximal tardiness can be computed in polynomial time. Two algorithms are described. The first one is based on a linear programming formulation of the problem while the second one is a combinatorial algorithm. The complexity status of this ‘tall/small’ task scheduling problem P|ri, pi=1, sizei ∈ {1, m}|Tmax was unknown before, even for two processors.