摘要
介绍了调度问题中常用的level算法并分析其特点.在应用level算法求解调度问题Pm|pj=1,intree|∑Cj所得到的调度结果的基础上,构造出求解该问题的时间复杂度为O(nlogn)的标号level算法.给出了可得到更好的调度结果的时间复杂度为O(n2logn)的兄弟因子搜索算法.大量的实例分析表明,兄弟因子搜索算法在绝大部分情况下都可以得到很好的调度结果.
The level-Algorithm usually used in scheduling problems is introduced and some of its properties are analyzed. Based on the schedule result obtained by using level-Algorithm for scheduling problem Pm｜pj=1,intree｜∑Cj, an O（nlogn） Labelling level-Algorithm is proposed for this scheduling problem. Some insufficiencies of Labelling level-Algorithm are presented with some examples. And Brother Factor Algorithm by which better scheduling results can be obtained are proposed, its computational complexity is O（n^2logn）. By analyzing a lot of instances, it is shown that good scheduling results can be obtained by using Brother Factor Algorithm.
出处
《北京师范大学学报（自然科学版）》
CAS
CSCD
北大核心
2006年第2期134-138,共5页
Journal of Beijing Normal University(Natural Science)
基金
国家自然科学基金资助项目(60474023)
教育部博士点基金资助项目(20020027013)
教育部科学技术重点项目(03184)
"九七三"国家重大基础研究计划资助项目(2002CB312200)
