摘要
针对最小完工时间的流水车间作业调度问题,提出了一种自适应混合粒子群进化算法——AHPSO,将遗传操作有效地结合到粒子群算法中.定义了粒子相似度及粒子能量,粒子相似度阈值随迭代次数动态自适应变化,而粒子能量阈值与群体进化程度及其自身进化速度相关.此外,针对算法运行后期进化速度慢的缺点,提出了一种基于邻域的随机贪心策略进一步提高算法的性能.最后将此算法在不同规模的实例上进行了测试,并与其他几种具有代表性的算法进行了比较,实验结果表明,无论是在求解质量还是稳定性方面都优于其他几种算法,并且能够有效求解大规模车间作业问题.
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 algorithm 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 depends 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 scheduling problem.
出处
《计算机学报》
EI
CSCD
北大核心
2009年第11期2137-2146,共10页
Chinese Journal of Computers
基金
国家自然科学基金重大项目(60496320
60496321)
国家自然科学基金(60773097
60873148)
新世纪优秀人才支持计划项目基金
吉林省科技发展计划项目基金(20060532
20080107)
吉林省青年科研基金(20080107
20080617)
东北师范大学自然科学青年基金(20081003)资助
关键词
粒子群优化
车间调度
粒子相似度
粒子能量
贪心策略
particle swarm optimization
flow shop scheduling
particle similarity
particle energy
greedy strategy
