周  昊

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

摘  要：文章研究了平行机上的一个半在线排序问题.假定预先已知所有工件的加工时间总和，工件的加工可中断，目标是极大化最小的机器完工时间和极小化最大的机器完工时间.针对这两种目标情形，分别给出了竞争比为1的半在线算法，从而是最优的.

关键词：半在线；可中断排序；竞争比

中图分类号：O223       文献标志码：A         文章编号：1671-2714(2015)01-0046-03