一种求解作业车间调度的文化粒子群算法  

Cultural particle swarm optimization algorithm for Job-Shop scheduling problem

作　　者：朱霞[1] 

机构地区：[1]南京航空航天大学航空导航学院,南京210016

出　　处：《计算机应用研究》2012年第4期1234-1236,1240,共4页Application Research of Computers

基　　金：淮安市科技计划资助项目(SN1045);淮安市科技局资助项目(HAG09052)

摘　　要：提出了一种文化粒子群算法用于求解置换流水车间调度问题中的最小化最大完成时间。算法设置了群体空间和信念空间两类独立空间,群体空间采用自适应粒子群算法完成进化,信念空间通过更新函数来进行演化。算法中群体空间的粒子群不但通过跟踪个体极值和全局极值来更新自己,实现群体演化,而且通过不断与信念空间中的优秀个体交互,加快群体的收敛速度。该算法在不同规模的问题实例上与其他几个具有代表性的算法的比较结果表明,该算法具有较快的收敛速度,无论是在求解质量还是稳定性方面都优于比较的算法。This paper proposed an algorithm for the minimization of the makespan in permutation flow shop scheduling problem（FSSP）,which combined cultural particle swarm optimization（CPSO）.The algorithm set two kinds of spaces,population space and belief space.The population space was evolved with adaptive PSO strategy,and the belief space was evolved with update function.Particles of population space not only tracked individual extreme and global extreme to update themselves,but also exchanged with good individuals of belief space to speed up the convergence speed.The proposed algorithm was tested on different scale benchmarks and compared with the other representative algorithms.The result shows that CPSO has faster convergence speed and is better than those algorithms in not only the solution quality but also the stability.

关 键 词：粒子群算法 文化算法 作业车间调度 

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