超载实时系统的算法

摘要

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