两台同类机排序问题SPT算法的最坏情况比（英文）

作者：龚铭炀; 谈之奕^*; 严羽洁

来源：运筹学学报, 2022, 26(03): 92-108.

DOI：10.15960/j.cnki.issn.1007-6093.2022.03.007

• 排序
• 最坏情况比
• 同类机
• 混乱代价

本文研究以工件总完工时间为目标函数的两台同类机排序问题,给出了SPT算法以两台机器速度比为参数的最坏情况比,使该算法的常数最坏情况比上界与下界的差距由0.430 5减小到0.014 7。

• 单位
  浙江大学