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

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

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

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

出 版 物：《中国科学:数学》 (Scientia Sinica:Mathematica)

年 卷 期：2025年第55卷第2期

页      码：221-236页

摘      要：本文研究同类平行机环境下的在线排序问题,其中工件具有任意到达时间,目标为最小化最大完工时间.所讨论机器的速度,除了最后一台为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)算法.

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

学科分类：08[工学] 0812[工学-测绘类] 

核心收录：

D　O　I：10.1360/SSM-2024-0095

馆 藏 号：203157095...