求解车间调度问题的自适应混合粒子群算法

《求解车间调度问题的自适应混合粒子群算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３２卷第１１期计算机学报Ｖｏｌ．３２Ｎｏ．１１２００９年１１月ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＮｏｖ．２００９求解车间调度问题的自适应混合粒子群算法张长胜１）孙吉贵２）欧阳丹彤２）张永刚２）１）（东北大学信息科学与工程学院沈阳１１０００４）２）（吉林大学计算机科学与技术学院符号计算与知识工程教育部重点实验室长春１３００１２）摘要针对最小完工时间的流水车间作业调度问题，提出了一种自适应混合粒子群进化算法———ＡＨＰＳＯ，将遗传操作有效地结合到粒子群算法中．定义了粒子相似度及粒子能量，粒子相似度阈值随迭代次数动态自适应变化，而粒子能量阈值与群

2、体进化程度及其自身进化速度相关．此外，针对算法运行后期进化速度慢的缺点，提出了一种基于邻域的随机贪心策略进一步提高算法的性能．最后将此算法在不同规模的实例上进行了测试，并与其他几种具有代表性的算法进行了比较，实验结果表明，无论是在求解质量还是稳定性方面都优于其他几种算法，并且能够有效求解大规模车间作业问题．关键词粒子群优化；车间调度；粒子相似度；粒子能量；贪心策略中图法分类号ＴＰ３０１犇犗犐号：１０．３７２４／ＳＰ．Ｊ．１０１６．２００９．０２１３７犃犛犲犾犳犃犱犪狆狋犻狏犲犎狔犫狉犻犱犘犪狉狋犻犮犾犲犛狑犪狉犿犗狆狋犻犿犻狕犪狋犻狅狀犃犾犵狅狉犻狋犺犿犳

3、狅狉犉犾狅狑犛犺狅狆犛犮犺犲犱狌犾犻狀犵犘狉狅犫犾犲犿ＺＨＡＮＧＣｈａｎｇＳｈｅｎｇ１）ＳＵＮＪｉＧｕｉ２）ＯＵＹＡＮＧＤａｎＴｏｎｇ２）ＺＨＡＮＧＹｏｎｇＧａｎｇ２）１）（犛犮犺狅狅犾狅犳犐狀犳狅狉犿犪狋犻狅狀犛犮犻犲狀犮犲犪狀犱犈狀犵犻狀犲犲狉犻狀犵，犖狅狉狋犺犲犪狊狋犲狉狀犝狀犻狏犲狉狊犻狋狔，犛犺犲狀狔犪狀犵１１０００４）２）（犓犲狔犔犪犫狅狉犪狋狅狉狔狅犳犛狔犿犫狅犾犆狅犿狆狌狋犪狋犻狅狀犪狀犱犓狀狅狑犾犲犱犵犲犈狀犵犻狀犲犲狉犻狀犵狅犳狋犺犲犕犻狀犻狊狋狉狔狅犳犈犱狌犮犪狋犻狅狀，犆狅犾犾犲犵犲狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲牔犜犲犮犺

4、狀狅犾狅犵狔，犑犻犾犻狀犝狀犻狏犲狉狊犻狋狔，犆犺犪狀犵犮犺狌狀１３００１２）犃犫狊狋狉犪犮狋Ａｈｙｂｒｉｄｓｅｌｆａｄａｐｔｉｖｅａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄｔｏｓｏｌｖｅｔｈｅｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｗｉｔｈｔｈｅｏｂｊｅｃｔｉｖｅｏｆｍｉｎｉｍｉｚｉｎｇｍａｋｅｓｐａｎ，ｗｈｉｃｈｃｏｍｂｉｎｅｄｔｈｅｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍａｎｄｇｅｎｅｔｉｃｏｐｅｒａｔｏｒｓｔｏｇｅｔｈｅｒ．Ｔｈｅｐａｒｔｉｃｌｅｓｉｍｉｌａｒｉｔｙａｎｄｐａｒｔｉｃｌｅｅｎｅｒｇｙａｒｅｄｅｆｉ

5、ｎｅｄ．Ｔｈｅｔｈｒｅｓｈｏｌｄｏｆｐａｒｔｉｃｌｅｓｉｍｉｌａｒｉｔｙｄｙｎａｍｉｃａｌｌｙｃｈａｎｇｅｓｗｉｔｈｉｔｅｒａｔｉｏｎｓａｎｄｔｈｅｐａｒｔｉｃｌｅｅｎｅｒｇｙｄｅｐｅｎｄｓｏｎｔｈｅｓｗａｒｍｅｖｏｌｖｉｎｇｄｅｇｒｅｅａｎｄｔｈｅｐａｒｔｉｃｌｅ’ｓｅｖｏｌｖｉｎｇｓｐｅｅｄ．Ｉｎｏｒｄｅｒｔｏｉｍｐｒｏｖｅｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｐｅｒｆｏｒｍａｎｃｅｆｕｒｔｈｅｒ，ａｎｅｉｇｈｂｏｒｈｏｏｄｂａｓｅｄｒａｎｄｏｍｇｒｅｅｄｙｓｅａｒｃｈｓｔｒａｔｅｇｙｉｓｉｎｔｒｏｄｕｃｅｄｔｏｏｖｅｒｃｏｍｅｔｈｅｓｈｏｒｔｃｏｍ

6、ｉｎｇｏｆｅｖｏｌｖｉｎｇｓｌｏｗｌｙｉｎｔｈｅｌａｔｅｒｒｕｎｎｉｎｇｐｈａｓｅ．Ｆｉｎａｌｌｙ，ｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｉｓｔｅｓｔｅｄｏｎｄｉｆｆｅｒｅｎｔｓｃａｌｅｂｅｎｃｈｍａｒｋｓａｎｄｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｒｅｃｅｎｔｌｙｐｒｏｐｏｓｅｄｅｆｆｉｃｉｅｎｔａｌｇｏｒｉｔｈｍｓ．ＴｈｅｒｅｓｕｌｔｓｈｏｗｓｔｈａｔｔｈｅｓｏｌｕｔｉｏｎｑｕａｌｉｔｙａｎｄｔｈｅｓｔａｂｉｌｉｔｙｏｆｔｈｅＨＰＧＡｂｏｔｈｐｒｅｃｅｄｅｔｈｅｏｔｈｅｒｔｗｏａｌｇｏｒｉｔｈｍｓ．Ｉｔｃａｎｂｅｕｓｅｄｔｏｓｏｌｖｅｌａｒｇｅｓｃａｌｅｆｌｏ

7、ｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍ．犓犲狔狑狅狉犱狊ｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎ；ｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇ；ｐａｒｔｉｃｌｅｓｉｍｉｌａｒｉｔｙ；ｐａｒｔｉｃｌｅｅｎｅｒｇｙ；ｇｒｅｅｄｙｓｔｒａｔｅｇｙ收稿日期：２００７１０１８；最终修改稿收到日期：２００８１２１０．本课题得到国家自然科学基金重大项目（６０４９６３２０，６０４９６３２１）、国家自然科学基金（６０７７３０９７，６０８７３１４８）、新世纪优秀人才支持计划项目基金、吉林省科技发展计划项目基金（２００６０５３２，２００８０１０７）、吉林省青年

8、科研基金（２００８０１０７，２００８０６１７）及东北