周  昊

（浙江树人大学 基础部，浙江 杭州 310015）

摘  要：研究了两台同类机上目标函数为极小化最大工件开工时间的在线排序问题.证明了贪心(Greedy)算法是最优的在线算法，竞争比为1+s， 其中s是两台机器间的速度比.

关键词：排序；竞争比；在线算法

中图分类号：O223        文献标志码：A         文章编号：1671-2714(2011)02-0049-03