陈 少，吉卫喜,b，仇永涛，张国祥

(江南大学 a.机械工程学院；b.江苏省食品先进制造装备技术重点实验室，江苏 无锡 214122)

0 引言

柔性作业车间调度问题(Flexible Job Shop Problem, FJSP)[1]历年来一直是国内外研究的热点问题之一，研究已证明该类问题是典型的NP-hard问题。尽管近年来学者们已将诸如遗传算法[2]、蚁群算法[3-4]、粒子群算法[5]等人工智能算法应用到该问题上的求解上，并取得了一定的效果，但至今仍没有得出一套完全良好的解决方案，因此该问题仍具有很大的研究空间。

本文所研究的人工蜂群算法(Artificial Bee Colony, ABC)是由土耳其学者Karaboga[6]于2005年提出。该算法具有搜索速度快、精度高、参数少、鲁棒性强等优点，文献[7]也指出它与GA、PSO等算法相比，所求得的解的质量相对较好。而在车间调度问题上，近年来的ABC算法研究大多集中在流水车间的问题上[8-9]，在柔性作业车间调度问题上，田野等[10]虽有一定研究，但仍存在易陷入“早熟”收敛特性、局部搜索能力较弱、收敛速度较慢等缺陷，故该算法仍具有很大的改进空间。本文在介绍其标准算法的基础上，针对算法中三类蜜蜂的特点分别进行改进，使算法能适用于FJSP问题求解的同时，具有较快搜索速度和良好的跳出局部解的能力，最后选用标准算例求解并与其他算法结果对比证明该改进算法的有效性。

1 问题描述

FJSP问题可进行如下描述: 有n个工件，用Ji(i=1,2,…,n)表示第i个工件，每个工件之间相互独立，每个工件都有Oi道工序组成，Oij表示工件Ji的第j道加工工序。n个工件需要在m台机床上进行加工，Mk(k=1,2,…,m)表示第k台设备，每个工件的加工工序是确定的。……