摘要：文中研究了两点混合环上负载均衡问题的两种半在线情形。给定一个两点混合环和若干流量需求,寻找合适的流量运输方式,使得环上的最大负载尽可能地小。当存在一个容量为K的缓冲区时,证明了该半在线情形的下界为4/3。特别地,当K=1时,证明了下界为3/2,并给出了一个竞争比至多为8/5的半在线算法。当所有流的需求之和已知时,设计了一个竞争比为3/2的最优半在线算法。

摘要：论文提出了带等级约束的多重工件排序问题,每个客户提交多个加工时间和等级相同的工件。目标是寻找一个调度方案,使得机器的最大完工时间最小。当客户的信息未知时,论文设计了一个竞争比为5/3的在线算法。当所有工件的加工时间总和已知时,论文设计了一个竞争比为3/2的半在线算法。这些结论对经典带等级约束的两台平行机排序问题进行了推广。

摘要：对大多数排序问题来说 ,机器集往往是事先给定的 ,而且在算法进行过程中 ,机器集是不变的 .　Imreh和Noga[2 ] 第一次提出了在排序中考虑机器费用的模型 .他们研究了所谓的ListModelproblem ,并给出了　　竞争比为 (1+5 ) / 2≈ 1.6 18的在线算法 ,同时证明了该模型的任意在线算法的竞争比至少是 4 / 3.本文研究　ListModelproblem的一个半 在线情形 ,我们假设工件的最大加工时间预先知道 ,我们将给出一个竞争比为　　19/ 12≈ 1.5 83的半在线算法 ,同时证明对该问题的这一半在线情形 ,任意半在线算法的竞争比至少是 4 / 3.