两台同类机排序问题SPT算法的最坏情况比 |
| |
引用本文: | 龚铭炀,谈之奕,严羽洁. 两台同类机排序问题SPT算法的最坏情况比[J]. 运筹学学报, 2022, 26(3): 92-108. DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.007 |
| |
作者姓名: | 龚铭炀 谈之奕 严羽洁 |
| |
作者单位: | 1. 浙江大学数学科学学院, 浙江杭州 310027 |
| |
摘 要: | 本文研究以工件总完工时间为目标函数的两台同类机排序问题, 给出了SPT算法以两台机器速度比为参数的最坏情况比, 使该算法的常数最坏情况比上界与下界的差距由0.430 5减小到0.014 7。
|
关 键 词: | 排序 最坏情况比 同类机 混乱代价 |
收稿时间: | 2022-01-31 |
On the worst-case ratio of algorithm SPT for two uniform machines scheduling with minisum criteria |
| |
Affiliation: | 1. School of Mathematical Science, Zhejiang University, Hangzhou 310027, Zhejiang, China |
| |
Abstract: | This paper studies the scheduling problem on two uniform machines with objective of minimizing the total completion time. The parametric worst-case ratio of the algorithm SPT is investigated. The gap between the overall upper bound and lower bound decreases from 0.430 5 to 0.014 7. |
| |
Keywords: | scheduling worst-case ratio uniform machines price of anarchyc |
|
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
|
点击此处可从《运筹学学报》下载免费的PDF全文 |