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

Two-machine job shop scheduling with deteriorating jobs

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

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.