首页 | 本学科首页   官方微博 | 高级检索  
     

求解车间调度问题的自适应混合粒子群算法
引用本文:张长胜,孙吉贵,欧阳丹彤,张永刚.求解车间调度问题的自适应混合粒子群算法[J].计算机学报,2009,32(11).
作者姓名:张长胜  孙吉贵  欧阳丹彤  张永刚
作者单位:1. 东北大学信息科学与工程学院,沈阳,110004
2. 吉林大学计算机科学与技术学院符号计算与知识工程教育部重点实验室,长春,130012
基金项目:国家自然科学基金重大项目,国家自然科学基金,新世纪优秀人才支持计划项目基金、吉林省科技发展计划项目基金,吉林省青年科研基金,东北师范大学自然科学青年基金 
摘    要:针对最小完工时间的流水车间作业调度问题,提出了一种自适应混合粒子群进化算法--AHPSO,将遗传操作有效地结合到粒子群算法中.定义了粒子相似度及粒子能量,粒子相似度阈值随迭代次数动态自适应变化,而粒子能量阈值与群体进化程度及其自身进化速度相关.此外,针对算法运行后期进化速度慢的缺点,提出了一种基于邻域的随机贪心策略进一步提高算法的性能.最后将此算法在不同规模的实例上进行了测试,并与其他几种具有代表性的算法进行了比较,实验结果表明,无论是在求解质量还是稳定性方面都优于其他几种算法,并且能够有效求解大规模车间作业问题.

关 键 词:粒子群优化  车间调度  粒子相似度  粒子能量  贪心策略

A Self-Adaptive Hybrid Particle Swarm Optimization Algorithm for Flow Shop Scheduling Problem
ZHANG Chang-Sheng,SUN Ji-Gui,OUYANG Dan-Tong,ZHANG Yong-Gang.A Self-Adaptive Hybrid Particle Swarm Optimization Algorithm for Flow Shop Scheduling Problem[J].Chinese Journal of Computers,2009,32(11).
Authors:ZHANG Chang-Sheng  SUN Ji-Gui  OUYANG Dan-Tong  ZHANG Yong-Gang
Abstract:A hybrid self-adaptive algorithm is proposed to solve the flow shop scheduling problem with the objective of minimizing makespan, which combined the particle swarm optimization algo-rithm and genetic operators together. The particle similarity and particle energy are defined. The threshold of particle similarity dynamically changes with iterations and the particle energy de-pends on the swarm evolving degree and the particle's evolving speed. In order to improve the proposed algorithm performance further, a neighborhood based random greedy search strategy is introduced to overcome the shortcoming of evolving slowly in the later running phase. Finally, the proposed algorithm is tested on different scale benchmarks and compared with the recently proposed efficient algorithms. The result shows that the solution quality and the stability of the HPGA both precede the other two algorithms. It can be used to solve large scale flow shop sched-uling problem.
Keywords:particle swarm optimization  flow shop scheduling  particle similarity  particle ener-gy  greedy strategy
本文献已被 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号