摘要: 证明了成组加工的单机延误工件个数问题是强ＮＰ困难的，即使限定所有工件有单位加工时间且所有组间调整时间为零也是如此。对同组工件是相同工期的限制情形给出了一个多项式算法。关于同组工件既有相同工期，又有相同加工时间的进一步限制情形，由于输入规模的减少，证明了其是普通意义下ＮＰ困难的。