基于粒子群优化和变邻域搜索的混合调度算法

提出了用于解决作业车间调度问题的离散版粒子群算法.该算法采用基于工序的编码和新的位置更新策略,使具有连续本质的粒子群算法直接适用于调度问题.同时,针对粒子群算法容易陷入局部最优的缺陷,利用粒子群算法和变邻域搜索算法的互补性能,设计了粒子群-变邻域搜索算法、改进的粒子群算法、粒子群-变邻域搜索交替算法和粒子群-变邻域搜索协同算法4种混合调度算法.仿真结果表明,混合算法能够有效地、高质量地解决作业车间调度问题.

Hybrid heuristics based on particle swarm optimization and variable neighborhood search for Job Shop scheduling

A discrete Particle Swarm Optimization(PSO) algorithm was presented for Job Shop scheduling problem.In the algorithm,a sequence-based code and update strategy for new positions were applied so as to make PSO more suitable for scheduling problems.Aiming at the shortcoming of premature and poor resulted from pure PSO,based on the complementary strengths of PSO and Variable Neighborhood Search(VNS) algorithm,four hybrid procedures were put forward.They were first PSO then VNS(PV) algorithm,Enhanced PSO(EPSO) algorithm,PSO and VNS in Turn(PVT) algorithm,and PSO and VNS Cooperative algorithm(PVC).Numerical simulation demonstrated that within the framework of the newly designed hybrid algorithm,the NP-hard classic Job shop scheduling problem could be solved efficiently.