一种求解典型JSP的改进离散粒子群优化算法  

Improved discrete particle swarm optimization algorithm for typical Job-Shop scheduling problem

作　　者：吴正佳[1] 罗月胜[1] 周玉琼[1] 黄绍雄[1] 

机构地区：[1]三峡大学机械与材料学院

出　　处：《计算机应用研究》2013年第8期2405-2409,共5页Application Research of Computers

摘　　要：针对NP-hard性质的作业车间调度问题,设计了一种改进的离散粒子群优化算法。引入遗传算法交叉算子和变异算子来实现粒子的更新,并将变异思想和模拟退火算法思想融入该算法中对全局最优粒子的邻域进行局部搜索,很好地防止了算法出现早熟收敛。通过将该算法和标准粒子群优化算法用于求解典型JSP,计算结果对比表明,改进的算法具有很强的全局寻优能力;就综合解的质量和计算效率而言,改进算法优于标准粒子群优化算法。同时,将该算法结果与文献中其他相关算法结果进行比较,验证了该改进算法的有效性。该算法能够有效地、高质量地解决作业车间调度问题。According to the Job-Shop scheduling problem which contained NP-hard feature, this paper designed a kind of im- proved discrete particle swarm optimization algorithm. It introduced the crossover operator and the mutation operator of genetic algorithm to realize the particle updating. It embodied the thought of the variation and simulated annealing algorithm into this algorithm to achieve local search for the global optimal particle neighborhood, which prevented premature convergence of the algorithm well. To solve typical JSP through using the improved algorithm and standard particle swarm optimization algorithm, the calculation results showed that the improved algorithm had a strong capability of global optimization. As for the quality and computation efficiency of integrated solution, the improved algorithm was better than the standard particle swarm optimization algorithm. At the same time, comparing the result of the improved algorithm with other related algorithms in literature, it veri- fied the effectiveness of the improved algorithm. This algorithm can solve the JSP in high quality and effectively.

关 键 词：改进离散粒子群 作业车间调度 遗传算法 模拟退火 局部搜索 

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