同类机半在线排序问题及其近似算法

？研究两台同类机系统两个半在线排序问题.第一个为总加工时间已知,第二个为最大工件加工时间已知.对这两个问题,文章给出了各自的近似算法,证明了它们的最坏情况界分别为3和3/2.文章还研究了上述问题的下界并与我们的算法的最坏情况界进行了比较.