预先知道工件最大加工时间的带机器费用的排序

对大多数排序问题来说，机器集往往是事先给定的，而且在算法进行过程中，机器集是不变的。Imreh和Noga第一次提出了在排序中考虑机器费用的模型。他们研究了所谓的List Model problem，并给出了竞争比为（1＋5的平方根）／2≈1．618的在线算法，同时证明了该模型的任意在线算法的竞争比至少是4／3。本文研究List Model problem的一个半在线情形，我们假设工件的最大加工时间预先知道，我们将给出一个竞争比为19／12≈1．583的半在线算法，同时证明对该问题的这一半在线情形，任意半在线算法的竞争比至少是4／3。这表明部分信息有利于设计更好的算法。     

预先知道总加工时间的一类特殊的三台平行同类机在线排序

研究三台平行同类机在线排序问题的一种特殊情形,即三台同类机的加工速度分别为s1=s2=1,s3=s≥1．利用“总加工时间”这一部分信息来设计算法,证明了该算法的竞争比为(s 2)/s~(1/2)．结合文献中曾有的关于此问题在线算法的下界,可以知道当S≥2时,该算法比可能有的最好的在线算法在性能上要好．     

预先知道最大请求的两条线路带宽分派问题

研究两条线路带宽问题,利用“预先知道所有请求中最大的那一个请求的大小”这一部分信息来设计算法,该算法比可能有的最好的在线算法在性能上要好得多,同时在某些情况下,该算法是可能有的最好的半在线算法.     

三台平行同型机的一个半在线排序算法

本文研究三台平行同型机的一个半在线排序算法，我们假设工作的最大加工时间预先知道，我们将给出一个竞争比为（1＋√73)/6≈1.5907的半在线算法，同时证明对该问题的这一半在线情形，任意半在线算法的竞争比至少是√2.     

三台同类机在线排序问题一种特殊情形的研究

研究三台平行同类机排序问题的一种特殊情形,即三台同类机的加工速度分别为s1=s2=s≥1,s3=1.证明了对该问题来说,经典的LS算法的竞争比为min42ss 11,3s2 s1;同时证明当s≥3,该问题的下界为3s2 s1,从而说明了LS算法是可能存在的最好的在线算法.此外,对1≤s<3时问题的下界也做了一些讨论,这时虽然不能确定LS算法仍然是可能存在的最好的在线算法,但可知道这时LS算法与可能存在的最好的在线算法在竞争比上相差少于0.4299.     

两台机在线均衡调度算法的改进

研究两台平行同型机的在线均衡调度问题，利用两个不同的部分信息分别设计出两个算法，这两个算法比可能有的最好的在线算法在性能上都要好。同时还证明，就这两个部分信息来说，给出的算法是可能有的最好的算法。