文件名称：带有不可用区间中断可恢复的平行机排序问题 (2014年)
文件大小：888KB
文件格式：PDF
更新时间：2024-06-07 18:38:09
自然科学 论文
讨论带有不可用区间且工件中断可恢复的两台平行机排序问题。其中一台机器带有不可用区间，在不可用区间内不能加工工件。工件在加工时被不可用区间中断后，可以在不可用区间之后继续加工。目标是最小化加权总完工时间。这个问题是一般定义下NP-难的，因此需要寻找满足指定精确度的近似解。首先给出全多项式近似方案的定义，其次提出了一个动态规划的算法，最后利用划分程序的方法得到了一个全多项式近似方案(FPTAS)，该近似方案的时间复杂性为O(n5L5/ε4)，其中:n为输入工件的个数；L为输入规模；ε＞0为误差精度。