平行机的实时到达on-line算法下界的改进

本文考虑了平行机实时到达的在线问题．模型中，工件是陆续到达的，工件的个数、到达时间是事先未知的，而且只有当工件到达，才知其加工时间，目标是使所有工件都加工完的时间达到最小．Ｃｈｅｎ与Ｖｅｓｔｊｅｎｓ（１９９６年）证明了该在线问题不存在性能比小于１．３４７３的ｏｎ－ｌｉｎｅ算法．本文将此界改进为（５－５）／２．

超载实时系统的算法

近年来，超载实时系统ｏｎ－ｌｉｎｅ排序已被许多作者研究过，对单台机问题，Ｓ．Ｂａｒｕａｈ等给出了一个最坏性能比的上界１／（１＋√Ｋ）~２，其中Ｋ为重要性比，Ｇ．Ｋｏｒｅｎ等提出了一个达到此界的最优算法（Ｄ－ｏｖｅｒ算法），对多台机问题，Ｍ． Ｄｅｒｔｏｕｚｏｓ等证明即使在非超载情况下也不存在最优算法． Ｆ． Ｗａｎｇ等证明不可能存在竞争因子大于１／２的算法，并提出了一个算法，在Ｋ＝１及没有松弛时问的条件下，达到了１／２．对一般情况，他们证明任一Ｏｎ－ｌｉｎｅ算法的竞争因子均不会大于１／ａ，其中．对多台机情况，虽已发现了一些有用的性质，但如何构造一个较好的算法仍有待于进一步的研究．