| 具有禁用区间的平行机排序时间表长问题的全多项式近似方案 |
| |
| 引用本文： | 乔钰,罗成新.具有禁用区间的平行机排序时间表长问题的全多项式近似方案[J].沈阳师范大学学报(自然科学版),2012,30(1):12-15. |
| |
| 作者姓名： | 乔钰 罗成新 |
| |
| 作者单位： | 沈阳师范大学数学与系统科学学院,沈阳,110034 |
| |
| 摘 要： | 近几年来,排序问题由于其深刻的实际背景和广泛的应用前景而受到关注,其自身也在不断的发展变化当中。传统模型通常假设机器是可以连续使用的,但实际上机器在加工期间也需要维护,所以有许多人考虑了机器具有禁用区间的排序模型,并指出了当机器具有多个不可用区间时是强NP-难的问题。对于普通NP-难的问题,他们提出了有效的动态规划算法或多项式时间近似算法。研究工件在两台平行机上加工的排序问题,其中第一台机器上有一段禁用区间,另一台机器是可以连续使用的。在整个加工过程中,工件不允许中断,目标函数是极小化时间表长,该问题是NP-难的。给出这一问题的一个全多项式时间近似方案,算法的时间复杂性是O(n4/ε3),其中n是工件的数量,ε是误差界。
|
| 关 键 词： | 排序 禁用区间 时间表长 全多项式近似方案 |
Fully polynomial time approximation scheme for makespan minimization problem on two-machine with a fixed non-availability interval |
| |
| QIAO Yu
,
LUO Cheng-xin.Fully polynomial time approximation scheme for makespan minimization problem on two-machine with a fixed non-availability interval[J].Journal of Shenyang Normal University: Nat Sci Ed,2012,30(1):12-15. |
| |
| Authors: | QIAO Yu LUO Cheng-xin |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
