Single Machine Earliness-Tardiness Scheduling Problems Using the Equal-Slack Rule
研究了等松弛规则下单机调度问题，其中每个作业的截止日期与加工时间相关，目标是最小化提前和延迟惩罚之和，发现无限制情况可多项式求解，而限制情况是NP难的。
The purpose of this paper is to analyse a special case of the non-pre-emptive single machine scheduling problem where the distinct due dates for each job are related to processing times according to the Equal-Slack rule.The scheduling objective is to minimize the sum of earliness and tardiness penalties.After determining some properties of the problem, the unrestricted case is shown to be equivalent to a polynomial time solvable problem, whereas the restricted case is shown to be NP-hard, and suggestions are made for further research.