摘要
本文介绍了一种UET系统中有效的调度算法,其时间复杂性函数为O(na(n)+e)。该算法对m=2台处理机的调度为最优,而对m≥3台处理机上的未确定调度子问题,其解与最优解之比的最小上界为2-2/m,它也是一个近似程度相当好的有效算法。
This paper introduces an effective scheduling algorithm in UET (Unit Execution Time) system, its time complexity function being O (na(n) + e). The scheduling list made by the algorithm for m = 2 processors is an optimal scheduling list; and for those open scheduling subproblems, the minimal upper bound of the ratio between its solution and optimal solution is g-2/m, a much better approximation.and hence, also showing the effec- tiveness of the algorithm.
出处
《西南交通大学学报》
EI
CSCD
北大核心
1990年第4期46-51,共6页
Journal of Southwest Jiaotong University
关键词
调度算法
算法分析
NP完全性
scheduling algorithm
algorithm analysis
NP-completeness
