| 两台同类机排序问题SPT算法的最坏情况比 |
| |
| 引用本文： | 龚铭炀,谈之奕,严羽洁.两台同类机排序问题SPT算法的最坏情况比[J].运筹学学报,2022,26(3):92-108. |
| |
| 作者姓名： | 龚铭炀 谈之奕 严羽洁 |
| |
| 作者单位： | 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 |
| |
| Institution: | 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全文 |
