Baptiste, Philippe; Schieber, Baruch A note on scheduling tall/small multiprocessor tasks with unit processing time to minimize maximum tardiness. (English) Zbl 1027.90027 J. Sched. 6, No. 4, 395-404 (2003). Summary: 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 1 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|r_{i},p_i=1\), size\(_i \in \{1, m\}|T_{\max}\) was unknown before, even for two processors. Cited in 1 ReviewCited in 6 Documents MSC: 90B35 Deterministic scheduling theory in operations research 90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) Keywords:multiprocessor task scheduling; linear programming; unit processing times PDFBibTeX XMLCite \textit{P. Baptiste} and \textit{B. Schieber}, J. Sched. 6, No. 4, 395--404 (2003; Zbl 1027.90027) Full Text: DOI