讨论了在$m$台同型平行机上, 加工带强制工期的$n$个可中断工件, 在机器可空闲条件下, 确定一个工件排序, 使得提前完工时间和最小. 先考虑了问题的复杂性, 通过3-划分问题归约, 证明了其是强NP-hard的. 而后, 讨论了强制工期相等的特殊情形, 由于工件不允许延迟, 问题可能会无可行排序. 先讨论了可行性, 接着针对可行问题, 提出一个算法在多项式时间内获得最优排序.

This paper discusses the problem that $n$ jobs with their own deadlines have to be processed on  identical machines considering the idle insert. The objective is to find a preemptive job sequence so  as to minimize the total earliness. The complexity is considered firstly,  and the problem is proved
  strongly NP-hard through the induction of 3-partition problem. Then,  the special case of common deadline  is discussed. Since tardy jobs are prohibited,  it's possible that there is no feasible sequence for the  problem. The feasibility is considered primarily. If the problem is feasible,  a polynomial time algorithm
     is developed to achieve optimality.