论文部分内容阅读
：文章讨论退化工件2台机器异序车间作业排序问题。在异序车间作业环境中，每个工件由一些工序组成，工序的个数未必与机器数相同。此外，每个工件有各自的工序加工顺序。工件可能多次在某些机器上加工，也可能根本不在某些机器上加工。假设工件的实际加工时间是其开始时间的比例函数，目标函数是极小化最大完工时间。首先证明了具有任意工序的问题是强意义下NP-难的；然后对每个工件最多只有2个工序的问题给出了多项式算法；最后证明了只有2个工序具有准备时间或截止工期的问题是普通意义NP-难的。