求解流水车间调度问题的混合粒子群算法  

Hybrid particle swarm optimization algorithm for flow shop scheduling problem

作　　者：齐学梅[1,2] 罗永龙[1,2] 赵诚[1,2] 

机构地区：[1]安徽师范大学数学计算机科学学院,安徽芜湖241003 [2]安徽师范大学网络与信息安全工程技术研究中心,安徽芜湖241003

出　　处：《计算机工程与应用》2012年第9期33-36,39,共5页Computer Engineering and Applications

基　　金：国家自然科学基金(No.60703071);安徽省自然科学基金(No.070412043);安徽省优秀青年科技基金项目(No.08040106806)

摘　　要：针对最小化流水车间调度总完工时间问题,提出了一种混合的粒子群优化算法(Hybrid Particle Swarm Algorithm,HPSA),采用启发式算法产生初始种群,将粒子群算法、遗传操作以及局部搜索策略有效地结合在一起。用Taillard’s基准程序随机产生大量实例,实验结果显示:HPSA通过对种群选取方法的改进和搜索范围的扩大提高了解的质量,在性能上均优于目前较有效的启发式算法和混合的禁忌搜索算法,产生最好解的平均百分比偏差和标准偏差均显著下降,最优解所占比例大幅度提高。A Hybrid Particle Swarm optimization Algorithm（HPSA） is presented to solve the flow shop scheduling problem with total flowtime minimization. The initial particle swarms are generated by heuristics. It combines the particle swarm optimization algorithm, genetic operators and local search strategies together. Taillard＇ s benchmark program is used to generate a large number of random in- stances. The experimental results indicate that the quality of solutions is improved using HPSA through the improvement of the option mode of population and a bigger searching scope： The performance of the proposed method is superior to the efficient heuristics current- ly used and hybrid tabu search algorithms. The average relation percentage deviation and standard deviation are reduced evidently, and the percent of optimal solutions increases obviously.

关 键 词：粒子群优化 流水车间调度 局部搜索:总完工时间 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]