刘　韵，胡　毅，罗　企，房　超

(1.中国科学院大学，北京　100049；2.中国科学院 沈阳计算技术研究所 高档数控国家工程研究中心，沈阳　110168；3.沈阳高精数控技术有限公司，沈阳　110168)



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

刘韵1，2，胡毅2，3，罗企1，2，房超1,2

(1.中国科学院大学，北京100049；2.中国科学院 沈阳计算技术研究所 高档数控国家工程研究中心，沈阳110168；3.沈阳高精数控技术有限公司，沈阳110168)

摘要：柔性车间作业调度问题(FJSP)作为经典车间作业调度问题(JSP)的扩展，早在上个世纪已经被证明为是NP-难的问题。目前启发式搜索方法作为解决NP-难问题的一个重要方法，已经被广泛用于解决车间调度问题。文章提出了一种基于启发式搜索的粒子群优化算法(PSO)，用以解决柔性车间作业调度问题，旨在获得最优的最小总工作时间。实验的结果与基于分布式估计算法(BEDA)以及改进后的遗传算法(GA)比较，证明本文提出的PSO算法，可以有效处理FJSP问题。

关键词：车间作业调度；启发式；粒子群；NP-难

0引言

在现实车间生产中，作业调度的好坏直接影响着生产效率。车间作业调度问题作为组合优化问题的一个典型代表加上它与生俱来的特点，导致其必然很难解决，事实上其也被证明为是NP-难问题。过去五十多年的研究中，科学家们尝试了各种方法[1]，最早的是一些确定性算法，典型的如分支界定算法，不过随着作业和机器数量的增加，问题的复杂性呈指数增长，这些算法无法满足解决问题的需求。鉴于此，大多数科学家开始尝试使用非确定性算法，比如遗传算法[2-3]等。……