摘要
平行机排序是一类重要的组合优化问题,列表在线排序是在线问题研究形成和发展的重要推手,也是成果最为丰富的在线问题之一.本文回顾以最大完工时间为目标的在线和半在线排序问题的最新进展,总结工件可拒绝、机器可增加及目标为机器负载的Lp范数等3类复杂目标在线排序问题的主要结果,介绍竞争比近似方案、带建议的在线算法和多样化算法性能指标等3个在线排序新课题.
Scheduling is one of the most fundamental combinatorial optimization problems. Online scheduling problems have received considerable research interest in the last three decades. In this paper, we summarize new results on online over list scheduling problems on parallel machines, including problems with an objective to minimize the makespan and the Lpnorm of machine loads, semi-online scheduling problems on identical, uniform and hierarchial machines, scheduling with rejection and scheduling with machine costs. We also introduce several new directions of online scheduling.
作者
林凌
谈之奕
Ling Lin;Zhiyi Tan
出处
《中国科学：数学》
CSCD
北大核心
2020年第9期1183-1200,共18页
Scientia Sinica：Mathematica
基金
国家自然科学基金(批准号:11801505和11671356)
浙江省教育厅科研项目基金(批准号:Y201533189)资助项目。
关键词
排序
在线
竞争比
scheduling
online
competitive ratio
