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

Two-machine job shop scheduling with deteriorating jobs

作　　者：赵传立[1] 唐恒永[1] 

机构地区：[1]沈阳师范大学数学与系统科学学院,沈阳110034

出　　处：《沈阳师范大学学报（自然科学版）》2013年第1期28-33,共6页Journal of Shenyang Normal University:Natural Science Edition

基　　金：国家自然科学基金资助项目(10471096)

摘　　要：文章讨论退化工件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.

关 键 词：排序 异序车间作业 退化工件 最大完工时间 

分 类 号：O223[理学—运筹学与控制论]