Single‐Machine Scheduling With Positional Deadlines, Time Deadlines, and due Date Assignment for Minimizing Total Weighted Tardiness

ABSTRACT 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 ‐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.