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

【Abstract】 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.更多还原