求解Job-shop问题的改进混合离散粒子群优化算法  

Study on an Improved Hybrid Discrete PSO for Job-shop Problems

作　　者：王书锋[1] 肖小城[1] 冯冬青[1] 

机构地区：[1]郑州大学电气工程学院,河南郑州450001

出　　处：《郑州大学学报（工学版）》2010年第4期44-47,共4页Journal of Zhengzhou University（Engineering Science）

基　　金：国家自然科学基金资助项目(60774059)

摘　　要：在详尽分析粒子群优化机理和作业车间调度问题的基础上,提出了结合遗传思想的混合离散粒子群优化算法.算法中增加了异于粒子个体极值点和全局极值点的第三参考点,使得粒子在更新过程中有更多的信息量调整自身状态.在粒子更新模型中引入了调整因子来调节收敛代数;在算法陷入局部最优时用模拟退火跳出局部最优,从而使算法收敛到全局最优.最后,对多个标准JSP问题进行了仿真测试,结果验证了改进算法的可行性和有效性.On the basis of a detailed analysis of the principle of particle swarm optimization（PSO）and characteristics of job-shop scheduling problems,this study presents a new hybrid discrete PSO integrating the genetic strategy.The third reference,which differs from the individual and global extremum,is added to the proposed algorithm for providing more information to adjust particle＇s position in the updating process;in the updated particle model,adjusting factors are introduced to regulate the generation of convergence;while getting into the local extremum,simulated annealing is used to step out of the local extremum and then converge at the global extremum.Finally,the proposed algorithm is tested on a set of benchmark instances,and the results obtained show the effectiveness and feasibility of the algorithm.

关 键 词：作业车间调度 离散粒子群优化 模拟退火 第三参考点 调整因子 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP301.6[自动化与计算机技术—控制科学与工程]