一种解决柔性车间作业调度问题的粒子群优化算法∗

摘要

柔性车间作业调度问题( FJSP)作为经典车间作业调度问题( JSP)的扩展，早在上个世纪已经被证明为是NP-难的问题。目前启发式搜索方法作为解决NP-难问题的一个重要方法，已经被广泛用于解决车间调度问题。文章提出了一种基于启发式搜索的粒子群优化算法( PSO)，用以解决柔性车间作业调度问题，旨在获得最优的最小总工作时间。实验的结果与基于分布式估计算法( BEDA)以及改进后的遗传算法( GA)比较，证明本文提出的PSO算法，可以有效处理FJSP问题。%Flexible Job Shop Scheduling Problem ( JSP) , which as an extension of Classical Job Shop Sched-uling Problem, had been proved as NP-Hard problem since last century. As one of the most popular approa-ches, heuristic search has been widely used for solving Job Shop Scheduling Problem. In this paper, we pro-pose an Particle Swarm Optimization( PSO) Algorithm, which based on heuristic search, to solve the Flexi-ble Job Shop Scheduling Problem. Compared with Based Estimation of Distribution Algorithm and Improved Genetic Algorithm proves that the algorithm we proposed can solve the FJSP effectively.