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

On the worst-case ratio of algorithm SPT for two uniform machines scheduling with minisum criteria

作　　者：龚铭炀 谈之奕[1] 严羽洁 GONG Mingyang;TAN Zhiyi;YAN Yujie(School of Mathematical Science,Zhejiang University,Hangzhou 310027,Zhejiang,China)

机构地区：[1]浙江大学数学科学学院,浙江杭州310027

出　　处：《运筹学学报》2022年第3期92-108,共17页Operations Research Transactions

基　　金：National Natural Science Foundation of China(No.12071427)。

摘　　要：本文研究以工件总完工时间为目标函数的两台同类机排序问题,给出了SPT算法以两台机器速度比为参数的最坏情况比,使该算法的常数最坏情况比上界与下界的差距由0.4305减小到0.0147。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.4305 to 0.0147.

关 键 词：排序 最坏情况比 同类机 混乱代价 

分 类 号：O22[理学—运筹学与控制论]