Unary NP-hardness of minimizing the number of tardy jobs with deadlines

For single machine scheduling to minimize the number of tardy jobs with deadlines, Lawler showed in 1983 that the problem is binary NP‐hard. But the exact complexity (unary NP‐hard or pseudo‐polynomial‐time solvability) is a long‐ standing open problem. We show in this paper that the problem is unary NP‐hard. Our research also implies that the scheduling problem for finding an optimal schedule to minimize the number of tardy jobs that also satisfies the restriction of deadlines is unary NP‐hard. As a consequence, some multi‐agent scheduling problems related to minimizing the number of tardy jobs and maximum lateness are unary NP‐hard.