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

第３７卷第８期计算机应用研究Ｖｏｌ３７Ｎｏ８

２０２０年８月ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓＡｕｇ．２０２０

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

１ａ，２１ａ，２１ｂ

李博，张晓，颜靖艺

（１．西北工业大学ａ．计算机学院；ｂ．管理学院，西安７１０１２９；２．工信部大数据存储与管理重点实验室，西安

７１０１２９）

摘要：针对当前算法求解多处理机调度问题的不足，从剪枝策略的角度提出了一种笨人算法。笨人算法的思

路是：不断排除最差解，直到剩下唯一解。这种剪枝算法至少保证当前的选择不是最差的，并且对计算过程的最

大复杂度作了一个估计。经过实验分析，对于Ｎ×Ｎ的ＭＳＰ，多数情况下，笨人算法比贪心算法、遗传算法、差分

进化算法的表现更为稳定和优秀，是一种有效的算法，也为相关问题的研究提供了一种新的思路。

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

中图分类号：ＴＰ３０１．６文献标志码：Ａ文章编号：１００１３６９５（２０２０）０８０３０２３８６０４

ｄｏｉ：１０．１９７３４／ｊ．ｉｓｓｎ．１００１３６９５．２０１９．０２．００６４

Ａｌｇｏｒｉｔｈｍｒｅｓｅａｒｃｈｏｆｓｏｌｖｉｎｇｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓｃｈｅｄｕｌｉｎｇ

ｐｒｏｂｌｅｍｂａｓｅｄｏｎｐｒｕｎｉｎｇａｌｇｏｒｉｔｈｍ

１ａ，２１ａ，２１ｂ

ＬｉＢｏ，ＺｈａｎｇＸｉａｏ，ＹａｎＪｉｎｇｙｉ

（１．ａ．ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ｂ．ＳｃｈｏｏｌｏｆＭａｎａｇｅｍｅｎｔ，ＮｏｒｔｈｗｅｓｔｅｒｎＰｏｌｙｔｅｃｈｎｉｃａｌＵｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｎ７１０１２９，Ｃｈｉｎａ；２．Ｍｉｎｉｓｔｒｙｏｆ

ＣｏｍｍｕｎｉｃａｔｉｏｎｓＫｅｙＬａｂｏｒａｔｏｒｙｏｆＢｉｇＤａｔａＳｔｏｒａｇｅ＆Ｍａｎａｇｅｍｅｎｔ，Ｘｉ’ａｎ７１０１２９，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：Ｔｏｏｖｅｒｃｏｍｅｔｈｅｓｈｏｒｔｃｏｍｉｎｇｓｏｆｃｕｒｒｅｎｔａｌｇｏｒｉｔｈｍｓｉｎｓｏｌｖｉｎｇｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｓ，ｔｈｉｓｐａｐｅｒｐｒｏ

ｐｏｓｅｄａｆｏｏｌａｌｇｏｒｉｔｈｍｆｒｏｍｔｈｅｐｅｒｓｐｅｃｔｉｖｅｏｆｐｒｕｎｉｎｇｓｔｒａｔｅｇｙ．Ｔｈｅｉｄｅａｏｆｔｈｅｆｏｏｌａｌｇｏｒｉｔｈｍａｌｗａｙｓｅｘｃｌｕｄｅｄｔｈｅｗｏｒｓｔｓｏｌｕｔｉｏｎ

ｕｎｔｉｌｔｈｅｒｅｗａｓｏｎｌｙｏｎｅｓｏｌｕｔｉｏｎｌｅｆｔ．Ｔｈｉｓｐｒｕｎｉｎｇａｌｇｏｒｉｔｈｍｅｎｓｕｒｅｄｔｈａｔｔｈｅｃｕｒｒｅｎｔｓｅｌｅｃｔｉｏｎｗａｓｎｏｔｔｈｅｗｏｒｓｔａｎｄｅｓｔｍｉａｔｅｄ

ｔｈｅｍａｘｍｉｕｍｃｏｍｐｌｅｘｉｔｙｏｆｔｈｅｃａｌｃｕｌａｔｉｏｎｐｒｏｃｅｓｓ．Ｔｈｒｏｕｇｈｅｘｐｅｒｍｉｅｎｔａｌａｎａｌｙｓｉｓ，ｆｏｒｔｈｅＮ×ＮＭＳＰ，ｉｎｍｏｓｔｃａｓｅｓ，ｔｈｅｐｅｒ

ｆｏｒｍａｎｃｅｏｆｔｈｅｆｏｏｌａｌｇｏｒｉｔｈｍｉｓｍｏｒｅｓｔａｂｌｅａｎｄｅｘｃｅｌｌｅｎｔｔｈａｎｇｒｅｅｄｙａｌｇｏｒｉｔｈｍ，ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍａｎｄｄｉｆｆｅｒｅｎｔｉａｌｅｖｏｌｕｔｉｏｎａｌ

ｇｏｒｉｔｈｍ．Ｉｔｉｓａｎｅｆｆｅｃｔｉｖｅａｌｇｏｒｉｔｈｍ，ａｎｄａｌｓｏｐｒｏｖｉｄｅｓａｎｅｗｗａｙｏｆｔｈｉｎｋｉｎｇｆｏｒｔｈｅｒｅｓｅａｒｃｈｏｆｒｅｌａｔｅｄｐｒｏｂｌｅｍｓ．

Ｋｅｙｗｏｒｄｓ：ｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓｃｈｅｄｕｌｉｎｇｐ