摘要
提出了用于解决作业车间调度问题的离散版粒子群算法。该算法采用基于工序的编码和新的位置更新策略,使具有连续本质的粒子群算法直接适用于调度问题。同时,针对粒子群算法容易陷入局部最优的缺陷,利用粒子群算法和变邻域搜索算法的互补性能,设计了粒子群-变邻域搜索算法、改进的粒子群算法、粒子群-变邻域搜索交替算法和粒子群-变邻域搜索协同算法4种混合调度算法。仿真结果表明,混合算法能够有效地、高质量地解决作业车间调度问题。
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 PS（）, 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.
出处
《计算机集成制造系统》
EI
CSCD
北大核心
2007年第2期323-328,共6页
Computer Integrated Manufacturing Systems
基金
山东省自然科学基金资助项目(2004ZX14)。~~
关键词
作业车间调度问题
粒子群优化
变邻域搜索算法
混合算法
Job Shop scheduling problem
particle swarm optimization
variable neighborhood search algorithm
hybrid heuristics
