摘要
提出了一种离散粒子群调度算法,采用基于工序的编码方式及相应的位置和速度更新方法,使具有连续本质的粒子群算法直接适用于调度问题。针对粒子群算法容易陷入局部最优的缺陷,将其与模拟退火算法结合,得到了粒子群-模拟退火算法、改进的粒子群算法、粒子群-模拟退火交替算法以及粒子群-模拟退火协同算法等4种混合调度算法。仿真结果表明,混合算法均具有较高的求解质量。
A discrete particle swarm optimization （PSO） algorithm was presented for Job Shop scheduling problem. In the algorithm, an operation--based representation was developed, and a new method was used to update position of particles with operation based ：representation. So PSO can be easily applied to all classes of scheduling problems. But pure PSO may produce premature and poor re sults. Based on the complementary strengths of PSO and simulated annealing （SA） algorithm, four hybrid procedures were put forward by combining the PSO and SA, Numerical simulation demonstrates that within the framework of the newly designed hybrid algorithm, the NP-hard classic Job Shop scheduling problem can be efficiently solved with higher quality.
出处
《中国机械工程》
EI
CAS
CSCD
北大核心
2006年第10期1044-1046,1064,共4页
China Mechanical Engineering
基金
国家自然科学基金资助项目(50275078)
山东省自然科学基金资助项目(2004ZX14)
关键词
JOB
Shop调度问题
粒子群优化
模拟退火算法
混合算法
Job Shop scheduling problem
particle swarm optimization
simulated annealing algorithm
hybrid procedure
