带有不可用区间中断可恢复的平行机排序问题  

Parallel machine scheduling problem with a resumable availability constraint

作　　者：张琦[1] 罗成新[1] 

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

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

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

摘　　要：讨论带有不可用区间且工件中断可恢复的两台平行机排序问题。其中一台机器带有不可用区间,在不可用区间内不能加工工件。工件在加工时被不可用区间中断后,可以在不可用区间之后继续加工。目标是最小化加权总完工时间。这个问题是一般定义下NP-难的,因此需要寻找满足指定精确度的近似解。首先给出全多项式近似方案的定义,其次提出了一个动态规划的算法,最后利用划分程序的方法得到了一个全多项式近似方案(FPTAS),该近似方案的时间复杂性为O(n5 L5/ε4),其中:n为输入工件的个数;L为输入规模;ε>0为误差精度。This paper considers a scheduling problem of two parallel machines with a resumable availability constraint. The machine is unavailable between T2 and S2. We call a job resumable if it cannot finish before the unavailable period of a machine and can continue after the machine is available again. The objective is to minimize the sum of weighted completion times. The problem is NP-hard in the ordinary sense. Therefore, we need to find an approximate solution that fulfills the required error bound. Firstly we propose the definition of the fully polynomial-time approximation scheme. Secondly we give a dynamic programming algorithm. Finally we obtain a fully polynomial-time approximation scheme （FPTAS） by procedure partition. Its running time is O（n^5L^5/ε^4 ）, where n is the number of jobs, L is the input size and e is the required error bound.

关 键 词：平行机排序 不可用区间 中断可恢复 NP-难 全多项式近似方案 

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