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.