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

摘要：

讨论带有不可用区间且工件中断可恢复的两台平行机排序问题.其中一台机器带有不可用区间,在不可用区间内不能加工工件.工件在加工时被不可用区间中断后,可以在不可用区间之后继续加工.目标是最小化加权总完工时间.这个问题是一般定义下NP-难的,因此需要寻找满足指定精确度的近似解.首先给出全多项式近似方案的定义,其次提出了一个动态规划的算法,最后利用划分程序的方法得到了一个全多项式近似方案(FPTAS),该近似方案的时间复杂性为O(n5 L5/ε4),其中:n为输入工件的个数;L为输入规模;ε＞0为误差精度.

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

所属期刊栏目：32

分类号：O223(运筹学)

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

在线出版日期：2015-01-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：466-470