工件从大到小到达的带处理器费用的半在线调度算法

对大多数调度问题来说 ,处理器集往往是事先给定的 ,而且在算法进行过程中 ,它是不变的 .Imreh和Noga第一次提出了在调度中考虑处理器有费用的模型 .他们研究了所谓的ListModel问题 ,给出了竞争比为 1.6 18的在线算法 ,同时证明了任意在线算法的竞争比至少是4 / 3.该文研究ListModel问题的一个半在线情形 ,即假设工件是从大到小到达的 ,给出一个竞争比为 3/ 2的半在线算法 .同时证明对该问题的这一半在线情形 ,任意半在线算法的竞争比至少是 4 / 3.

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

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

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

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

带机器准备时间的机器覆盖问题的在线、半在线算法

研究以极大化最小机器负载为目标的机器带准备时间的同型机排序问题.证明了LS算法是求解该问题的最好的在线算法,它的最坏情况界为1/m.同时给出了求解两台机的预先知道工件最大加工时间,预先知道工件集的总加工时间以及预先知道工件从大到小到达这三种情形下最好的半在线算法,这三个算法的最坏情况界分别为2/3,2/3以及3/4.

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

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

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

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

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

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

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

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