Single-machine scheduling with positional deadlines, time deadlines, and due date assignment for minimizing total weighted tardiness

In this article, we consider single-machine scheduling with positional deadlines and time deadlines to minimize the total weighted tardiness under the fixed due-date assumption or the due-date determination assumption. Specifically, we consider two models under the due-date determination assumption with the due date assignment cost: unrestricted due date assignment (DIF) and common due date assignment (CON). For each problem, we show that it is unary NP-hard. Moreover, we present the complexity classification for various subproblems subject to restrictions on the weights, due dates, processing times, or due date assignment cost.