具有禁用区间的平行机排序时间表长问题的全多项式近似方案  

Fully polynomial time approximation scheme for makespan minimization problem on two-machine with a fixed non-availability interval

作　　者：乔钰[1] 罗成新[1] 

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

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

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

摘　　要：近几年来,排序问题由于其深刻的实际背景和广泛的应用前景而受到关注,其自身也在不断的发展变化当中。传统模型通常假设机器是可以连续使用的,但实际上机器在加工期间也需要维护,所以有许多人考虑了机器具有禁用区间的排序模型,并指出了当机器具有多个不可用区间时是强NP-难的问题。对于普通NP-难的问题,他们提出了有效的动态规划算法或多项式时间近似算法。研究工件在两台平行机上加工的排序问题,其中第一台机器上有一段禁用区间,另一台机器是可以连续使用的。在整个加工过程中,工件不允许中断,目标函数是极小化时间表长,该问题是NP-难的。给出这一问题的一个全多项式时间近似方案,算法的时间复杂性是O(n4/ε3),其中n是工件的数量,ε是误差界。In recent years, scheduling problem has attracted great attention because of its deep background in the real world and bright future in various application environments. It has changed by itself continuously. The classical scheduling problem usually assumes that the machines are available simultaneously at all time. However, machines also need maintenance during the processing period. So many people considered the scheduling problems with a fixed non-availability interval on machines, and they have shown that the problem is NP-hard in the strong sense when machine possesses multiple periods of maintenance. They also proposed effective dynamic algorithms and polynomial time approximation scheme （PTAS） for the NP-hard problem in the ordinary sense. In this paper, we consider the problem of two parallel machines where one has a fixed non-availability constraint interval and the other is available at all time. During the processing of the jobs, preemption is not allowed, and the objective is to minimize the makespan. This problem is NP-hard, and a fully polynomial-time approximation scheme （FPTAS） is proposed in this paper. The FPTAS has O（ n4/83） time complexity, where n is the number of jobs and 8 is the required error bound.

关 键 词：排序 禁用区间 时间表长 全多项式近似方案 

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