基于剪枝算法解决多处理机调度问题的算法研究  

Algorithm research of solving multiprocessor scheduling problem based on pruning algorithm

作　　者：李博[1,3] 张晓 颜靖艺[2] Li Bo;Zhang Xiao;Yan Jingyi(School of Computer Science,Northwestern Polytechnical University,Xi’an 710129,China;School of Management,Northwestern Polytechnical University,Xi’an 710129,China;Ministry of Communications Key Laboratory of Big Data Storage&Management,Xi’an 710129,China)

机构地区：[1]西北工业大学计算机学院,西安710129 [2]西北工业大学管理学院,西安710129 [3]工信部大数据存储与管理重点实验室,西安710129

出　　处：《计算机应用研究》2020年第8期2386-2389,共4页Application Research of Computers

基　　金：国家重点研发计划资助项目(2018YFB1003403,2018YFB1004401)。

摘　　要：针对当前算法求解多处理机调度问题的不足,从剪枝策略的角度提出了一种笨人算法。笨人算法的思路是:不断排除最差解,直到剩下唯一解。这种剪枝算法至少保证当前的选择不是最差的,并且对计算过程的最大复杂度作了一个估计。经过实验分析,对于N×N的MSP,多数情况下,笨人算法比贪心算法、遗传算法、差分进化算法的表现更为稳定和优秀,是一种有效的算法,也为相关问题的研究提供了一种新的思路。To overcome the shortcomings of current algorithms in solving multiprocessor scheduling problems,this paper proposed a fool algorithm from the perspective of pruning strategy.The idea of the fool algorithm always excluded the worst solution until there was only one solution left.This pruning algorithm ensured that the current selection was not the worst and estimated the maximum complexity of the calculation process.Through experimental analysis,for the N × N MSP,in most cases,the performance of the fool algorithm is more stable and excellent than greedy algorithm,genetic algorithm and differential evolution algorithm.It is an effective algorithm,and also provides a new way of thinking for the research of related problems.

关 键 词：多处理机调度问题 剪枝算法 笨人算法 贪心算法 遗传算法 差分进化算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]