退化工件2台机器异序车间作业排序问题

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

Two-machine job shop scheduling with deteriorating jobs

This paper considers two-machine job shop scheduling problems with deteriorating Jobs. In job shop environment, each job consists of a number of operations, and the number of operations is not necessarily equal to the number of machines. Moreover, each job has its own sequence of processing, and it can visit a certain machine more than once or may not visit some machines at all. It is assumed that the actual processing time of the job is a proportional function of its starting time. The objective is to minimize the makespan. We show firstly that the problem with arbitrary operations is NP-hard in the strong sense. Then we introduce a polynomial-time algorithm for the problem with at most two operations. Finally, we prove that the problem with two operations and release times or deadlines is NP--hard in the ordinary sense.