排序问题是组合优化领域中的一类重要问题，它是利用一些处理机、机器或者资源最优地完成一批给定的任务或作业。本文研究了在线排序的一种新的模型——工件有任意到达时间的（半）在线排序，又称之为订单排序模型。该模型是由李荣珩教授在新加坡国立大学做访问学者期间（2000-2004）提出的，并给出了一个近似比不超过2.9392的启发式算法。美国《Math．Rev．》评论认为该排序模型将会引起所有排序研究工件者的兴趣。本文首先简单地介绍了排序问题的相关定义、记号及相关知识，描述了（半）在线排序和工件有任意到达时间的在线排序模型的一些特性。第二部分研究了工件有任意到达时间的在线排序模型，讨论了单台机上有最小的最坏性能比为2的LS算法。对在线模型的MLS算法的性能比的上界由2.939201推进到了2.924191第三部分研究了工件有任意到达时间的半在线排序模型。对于工件按加工时间非增的顺序到达的单台机半在线排序给出了任意算法下界和LS算法为3／2的紧界，另外对带缓冲区的半在线模型给出了一个BLS算法。文章末，对工件有任意到达时间的排序问题做出总结和研究展望。
本文来源: https://www.lw50.cn/article/535c76d2f3b13ee44c7c86d7.html