| 单台机以总完工时间为目标的批排序问题 |
| |
| 引用本文： | 严羽洁.单台机以总完工时间为目标的批排序问题[J].高校应用数学学报(A辑),2017,32(4). |
| |
| 作者姓名： | 严羽洁 |
| |
| 作者单位： | 浙江大学数学科学学院,浙江杭州,310027 |
| |
| 摘 要： | 研究单台机,工件加工时间相等,大小不同的批排序问题,给出了一个最坏情况界为9+3~(1/2)/6≈1.7817的多项式时间近似算法,并证明了即使工件总大小不超过2,该问题也不存在FPTAS,除非P=NP.
|
| 关 键 词： | 组合优化 批排序问题 多项式时间近似算法 计算复杂性 |
Study for batch scheduling on single machine |
| |
| YAN Yu-jie.Study for batch scheduling on single machine[J].Applied Mathematics A Journal of Chinese Universities,2017,32(4). |
| |
| Authors: | YAN Yu-jie |
| |
| Abstract: | For the problem of minimizing total completion time on single machine with unit processing time, an approximation algorithm with a performance ratio smaller than 9+√3/6 ≈1.7817 is given. The paper showed that there dose not exist any fully polynomial time approximation schedule unless P =NP , even if the total size of the jobs is smaller than 2. |
| |
| Keywords: | combinatorial optimization batch scheduling approximation algorithm computa-tional complexity |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
