  This paper resolves a long-standing open question in bicriteria scheduling
regarding the complexity of a single machine scheduling problem which combines
the number of tardy jobs and the maximal tardiness criteria. We use the
lexicographic approach with the maximal tardiness being the primary criterion.
Accordingly, the objective is to find, among all solutions minimizing the
maximal tardiness, the one which has the minimum number of tardy jobs. The
complexity of this problem has been open for over thirty years, and has been
known since then to be one of the most challenging open questions in
multicriteria scheduling. We resolve this question by proving that the problem
is strongly NP-hard. We also prove that the problem is at least weakly NP-hard
when we switch roles between the two criteria (i.e., when the number of tardy
jobs is the primary criterion). Finally, we provide hardness results for two
other approaches (constraint and a priori approaches) to deal with these two
criteria.
