加工时间与等待时间线性相关的流水作业问题

在流水作业中，每个工件在一个机器上加工完毕之后直至在下一合机８１开始加工的时间，被称为等待时间。在所研究的问题中，等待时间使该工件的加工时间产生线性延伸，要求找出时间表使加工全长最小化。在两合机器的情况下，当延伸系数允许取两个不同值时，该问题已被证明是难问题。文献上曾指出，当延伸系数只取同一值时，该问题的计算复杂性尚未判定。本文证明，在上述限制下，该问题也是难问题。