基于改进人工蜂群算法的柔性作业车间调度*

王玉芳，马铭阳，葛嘉荣，缪 昇

(南京信息工程大学 a.江苏省大气环境与装备技术协同创新中心；b.自动化学院;c.江苏省大数据分析技术重点实验室，南京 210044)

0 引言

上世纪90年代，Brucker P[1]首次提出柔性作业车间调度问题 (Flexible Job Shop Problem, FJSP) 的概念。柔性作业车间调度问题是传统作业车间调度的扩展，突破了资源唯一性限制，每道工序可在多台不同的机器上加工，从而使作业车间调度问题更加贴合实际生产，所以一直是国内外的研究热点。

黄海松等[2]提出一种改进的模拟退火的方法解决柔性调度问题，采用个体调换和局部颠倒两种不同的搜索方式，避免算法陷入“早熟”。靳彬锋等[3]提出一种模拟退火结合遗传算子的混合算法，采用拉普拉斯交叉算子和逆转变异，结合模拟退火的局部搜索能力，提高问题的求解速度与质量。近年来，因具有搜索速度快，参数少，鲁棒性强等特点[4-6]，人工蜂群(Artificial Bee Colony，ABC)算法也应用到调度问题求解中。陈少等[7]在ABC算法中引入了相似度概念对种群进行分类，采用不同的搜索策略，观察蜂选择操作用锦标赛代替轮盘赌改善算法过早收敛现象。田野等[8]提出一种离散的ABC算法，采用自适应变异策略降低早熟收敛的可能性。Leila Asadzadeh[9]提出的并行ABC采用动态迁移策略与其他种群进行交流，结果与其他算法相比，算法的收敛速度较快。Arit Thammano等[10]提出混合ABC算法，采用迭代搜索和分散搜索进行局部搜索，利用模拟退火算法跳出局部最优解，验证结果表明该算法能够找到最优解或近似最优解。……