同类平行机下工件有任意到达时间的在线排序  

Online scheduling for jobs with arbitrary release times on uniform machines

作　　者：成夏炎[1] 赵聪聪 马丽娜 李荣珩 Xiayan Cheng;Congcong Zhao;Lina Ma;Rongheng Li

机构地区：[1]湖南第一师范学院数学与统计学院,长沙410205 [2]湖南师范大学数学与统计学院,长沙410081 [3]湖南省沅陵县第一中学,怀化419600 [4]云南财经大学统计与数学学院,昆明650221 [5]湖南师范大学数学与统计学院计算与随机数学教育部重点实验室,复杂系统的控制与优化湖南省高校重点实验室,长沙410081

出　　处：《中国科学:数学》2025年第2期221-236,共16页Scientia Sinica:Mathematica

基　　金：国家自然科学基金(批准号:12471303);湖南省教育厅科学研究(批准号:16A126)资助项目。

摘　　要：本文研究同类平行机环境下的在线排序问题,其中工件具有任意到达时间,目标为最小化最大完工时间.所讨论机器的速度,除了最后一台为s(s>1)外,其余m−1台机器的速度均为1.本文分析了列表(list scheduling,LS)算法的性能,得到了机器数m=2及m≥3时LS算法的竞争比分别为2/3+√5和4−4/m+1,并在一般情形下设计了一个竞争比不超过3.8626的更好的算法—改良列表(modified list scheduling,MLS)算法.In this paper,we study the problem of online scheduling on uniform machines,in which the jobs have arbitrary release times and the objective function is to minimize the maximum completion time.The speeds of the machines are 1 for the first m−1 machines,but the last one’s is s(s>1).The performance of the LS(list scheduling)algorithm is analyzed.When the numbers of machines are m=2 and m≥3,it is presented that the competitive ratios of the LS algorithm are 2/3+√5 and 4−4/m+1,respectively.In general,a better algorithm called MLS(modified list scheduling)is also designed for the problem and it is shown that the competitive ratio of the MLS is no more than 3.8626.

关 键 词：在线排序 同类平行机 到达时间 算法 竞争比 

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