多模式资源受限项目调度问题的混合遗传算法 - 东南大学学报.pdf

第３８卷第４期 东南大学学报（自然科 学版 ） Ｖｏｌ３８Ｎｏ４ 　 ２００８年７月 ＪＯＵＲＮＡＬＯＦＳＯＵＴＨＥＡＳＴＵＮＩＶＥＲＳＩＴＹ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ） 　 Ｊｕｌｙ２００８ 　　　　　　 多模式资源受限项目调度问题的混合遗传算法 喻　瑛 （东南大学经济管理学院，南京２１００９６） 摘要：多模式资源受限项目调度问题是一种ＮＰ难的组合优化问题．提出了与基于关键链的启发 式算法相结合的二层混合遗传算法对该问题进行求解．在由上层算法确定的调度顺序下，下层遗 传算法结合基于关键链的启发式算法，对系统资源重新优化配置，使算法加速向最优解区域收 敛，并在下层设计了随迭代代数增加的可变变异概率，以避免早熟收敛．利用标准问题库对算法 进行测试，分析问题参数与算法参数对算法结果的影响，发现实验结果的绩效随迭代数的增加而 提高，算法耗时随任务数和迭代数的增加而增加．数值测试结果验证了算法的可行性和可靠性． 关键词：多模式；资源受限项目调度；二层混合遗传算法；关键链 中图分类号：Ｃ９３４　　文献标识码：Ａ　　文章编号：１００１－０５０５（２００８）０４０７３６０５ Ｈｙｂｒｉｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｍｕｌｔｉｍｏｄｅｒｅｓｏｕｒｃｅｃｏｎｓｔｒａｉｎｅｄ ｐｒｏｊｅｃｔｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｓ ＹｕＹｉｎｇ （ＳｃｈｏｏｌｏｆＥｃｏｎｏｍｉｃｓａｎｄＭａｎａｇｅｍｅｎｔ，ＳｏｕｔｈｅａｓｔＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ２１００９６，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：ＴｈｅｍｕｌｔｉｍｏｄｅｒｅｓｏｕｒｃｅｃｏｎｓｔｒａｉｎｅｄｐｒｏｊｅｃｔｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｉｓａｋｉｎｄｏｆＮＰｈａｒｄ ｃｏｍｂｉｎａｔｉｏｎｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍ．Ｔｏｓｏｌｖｅｉｔａｂｉｌｅｖｅｌｈｙｂｒｉｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｃｏｍｂｉｎｅｄｗｉｔｈａ ｃｒｉｔｉｃａｌｃｈａｉｎｂａｓｅｄｈｅｕｒｉｓｔｉｃｉｓｐｒｏｐｏｓｅｄ．Ｕｎｄｅｒｔｈｅｇｉｖｅｎｐｒｏｊｅｃｔｓｃｈｅｄｕｌｉｎｇｓｐｅｃｉｆｉｅｄｂｙｔｈｅｕｐｐｅｒ ｌｅｖｅｌａｌｇｏｒｉｔｈｍ，ｃｏｍｂｉｎｅｄｗｉｔｈａｃｒｉｔｉｃａｌｃｈａｉｎｂａｓｅｄｈｅｕｒｉｓｔｉｃ，ｔｈｅｌｏｗｅｒｌｅｖｅｌｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｒｅ ａｌｌｏｃａｔｅｓｔｈｅｒｅｓｏｕｒｃｅｓｔｏｓｈｏｒｔｅｎｔｈｅｐｒｏｊｅｃｔｄｕｒａｔｉｏｎｓｏｔｈａｔｔｈｅｒａｔｅｏｆｃｏｎｖｅｒｇｉｎｇｔｏｔｈｅｇｌｏｂａｌｏｐｔｉ ｍｕｍｄｉｓｔｒｉｃｔｉｓｉｍｐｒｏｖｅｄ，ａｎｄａｖａｒｉａｂｌｅｍｕｔａｔｉｏｎｐｒｏｂａｂｉｌｉｔｙｉｓｄｅｖｅｌｏｐｅｄｔｏａｖｏｉｄｐｒｅｍａｔｕｒｅｃｏｎ ｖｅｒｇｅｎｃｅ．Ｆｉｎａｌｌｙ，ａｃｏｍｐｕｔａｔｉｏｎａｌｓｔｕｄｙｆｏｒａｓｔａｎｄａｒｄｓｅｔｏｆｐｒｏｊｅｃｔｉｎｓｔａｎｃｅｓｉｓｃａｒｒｉｅｄｏｕｔｔｏｔｅｓｔ ｔｈｅｖａｌｉｄｉｔｙｏｆｔｈｅａｌｇｏｒｉｔｈｍ，ａｎｄｔｈｅｅｆｆｅｃｔｓｏｆｔｈｅｐｒｏｂｌｅｍｐａｒａｍｅｔｅｒｓａｎｄａｌｇｏｒｉｔｈｍｐａｒａｍｅｔｅｒｓｏｎ ｔｈｅｒｅｓｕｌｔｓａｒｅａｎａｌｙｚｅｄ．Ｉｔｃａｎｂｅｆｏｕｎｄｔｈａｔｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｉｍｐｒｏｖｅｓ ｗｉｔｈｔｈｅｉｎｃｒｅｍｅｎｔｏｆｔｈｅｇｅｎｅｒａｔｉｏｎｓ，ａｎｄｔｈｅａｌｇｏｒｉｔｈｍｔａｋｅｓｍｏｒｅＣＰＵｔｉｍｅｗｈｅｎｔｈｅｔａｓｋｎｕｍ ｂｅｒｓｏｒｔｈｅｇｅｎｅｒａｔｉｏｎｓｉｎｃｒｅａｓｅ．Ｎｕｍｅｒｉｃａｌｅｘａｍｐｌｅｓｔｅｓｔｉｆｙｔｈｅｆｅａｓｉｂｉｌｉｔｙａｎｄｒｅｌｉａｂｉｌｉｔｙｏｆｔｈｅａｌｇｏ ｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ：ｍｕｌｔｉｍｏｄｅ；ｒｅｓｏｕｒｃｅｃ