| 有限期作业调度问题的最优化算法 |
| |
| 引用本文： | 周玉林. 有限期作业调度问题的最优化算法[J]. 上饶师范学院学报, 2004, 24(6): 73-75 |
| |
| 作者姓名： | 周玉林 |
| |
| 作者单位： | 上饶师范学院,江西,上饶,334001 |
| |
| 摘 要： | 本文讨论了有限期作业调度问题,用计数排序、分离森林中的有效路径压缩、按秩合并方法,得到了有限期作业调度最优化算法,其时间复杂性为O(na(m,n)),m=O(n),在实际应用中是一个线性时间复杂性算法,是渐近性能最佳的算法.
|
| 关 键 词： | 作业调度 计数排序 分离森林 路径压缩 按秩合并 矩阵胚 |
| 文章编号： | 1004-2237(2004)06-0073-03 |
| 修稿时间： | 2004-08-31 |
An Optimally Algorithm on the Task-scheduling Problem with Deadlines |
| |
| ZHOU Yu-lin. An Optimally Algorithm on the Task-scheduling Problem with Deadlines[J]. Journal of Shangrao Normal College, 2004, 24(6): 73-75 |
| |
| Authors: | ZHOU Yu-lin |
| |
| Abstract: | This paper investigates the optimally algorithm on the task-scheduling problem with deadlines, in which we used the counting sort, the union by rank, and the path compression in the disjoint-set forests, and we gain the new optimally algorithm on the task-scheduling problem with deadlines, the time of the algorithm is O(na(m,n)),m=O(n),the running time is linear for all practical purposes, the asymptotic efficiency of the algorithm is the best. |
| |
| Keywords: | Task scheduling countin -sort disjoint set path compression union by rank motriod |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
