论文部分内容阅读
近年来,超载实时系统on-line排序已被许多作者研究过,对单台机问题,S.Baruah等给出了一个最坏性能比的上界1/(1+√K)~2,其中K为重要性比,G.Koren等提出了一个达到此界的最优算法(D-over算法),对多台机问题,M. Dertouzos等证明即使在非超载情况下也不存在最优算法. F. Wang等证明不可能存在竞争因子大于1/2的算法,并提出了一个算法,在K=1及没有松弛时问的条件下,达到了1/2.对一般情况,他们证明任一On-line算法的竞争因子均不会大于1/a,其中.对多台机情