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

来源：计算机应用研究杂志2020年第8期北京时间：

作者：李博,张晓,颜靖艺,

单位：1.西北工业大学a.计算机学院;b.管理学院,西安710129；2.工信部大数据存储与管理重点实验室,西安710129；

摘要：针对当前算法求解多处理机调度问题的不足，从剪枝策略的角度提出了一种笨人算法。笨人算法的思路是：不断排除最差解，直到剩下唯一解。这种剪枝算法至少保证当前的选择不是最差的，并且对计算过程的最大复杂度作了一个估计。经过实验分析，对于N×N的MSP，多数情况下，笨人算法比贪心算法、遗传算法、差分进化算法的表现更为稳定和优秀，是一种有效的算法，也为相关问题的研究提供了一种新的思路。

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

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