Minimizing the Weighted Number of Tardy Jobs is W[1]-hard

We consider the $1\mathrm{\mid }\mathrm{\mid }\sum w_J{U}_j$ problem, the problem of minimizing the weighted number of tardy jobs on a single machine. This problem is one of the most basic and fundamental problems in scheduling theory, with several different applications both in theory and practice. We prove that $1\mathrm{\mid }\mathrm{\mid }\sum w_J{U}_j$ is W[1]-hard with respect to the number $p_{\mathrm{\#}}$ of different processing times in the input, as well as with respect to the number $w_{\mathrm{\#}}$ of different weights in the input. This, along with previous work, provides a complete picture for $1\mathrm{\mid }\mathrm{\mid }\sum w_J{U}_j$ from the perspective of parameterized complexity, as well as almost tight complexity bounds for the problem under the Exponential Time Hypothesis (ETH).