改进人工蜂群算法求解无等待柔性流水车间调度问题

毕孝儒，杨　柳，张黎黎，贺　拴（四川外国语大学重庆南方翻译学院管理学院，重庆401120）

改进人工蜂群算法求解无等待柔性流水车间调度问题

毕孝儒，杨柳，张黎黎，贺拴
（四川外国语大学重庆南方翻译学院管理学院，重庆401120）

为了解决无等待柔性流水车间调度问题，提出一种改进人工蜂群算法。在算法初始阶段采用混沌算子初始化种群以增强其多样性；在蜜源搜索阶段运用自适应全局最优蜜源搜索策略以平衡人工蜂群算法的“探索与开发”能力，避免算法在搜索后期易于陷入局部最优。将改进算法用于求解无等待柔性流水车间调度问题，仿真实验验证改进算法的有效性和优越性。

人工蜂群算法；无等待柔性车间调度；混沌算子；搜索能力

四川外国语大学重庆南方翻译学院科研项目（No.ky2014004）

0　引言

柔性流水车间调度（Flexible Flow Shop Scheduling Problem，FFSP）是传统流水车间调度问题的扩展，是复杂的组合优化问题。其最大特点是允许加工的工序存在并行机器。在FFSP中，若工件开始加工后不允许等待，直到该工件加工完毕为止，则称为无等待柔性流水车间调度问题（No-wait FFSP，NWFFSP）。在求解该类问题方法上，群体智能优化算法是当前的研究热点，其以种群的个体代表问题的可行解，根据个体适应度值，通过群体搜索寻最优解。如文献[1]采用遗传算法求解无等待柔性流水车间调度问题，文献[2]将遗传算法运用于具有时间窗的无等待柔性流水车间调度问题求解中，文献[3]针对工件加工无等待特点，设计了分阶段实现的无等待算法，并采用粒子群算法对无等待柔性流水车间调度问题进行了求解，文献[4]提出了一种混合粒子群-NEH算法以求解无等待柔性流水车间调度问题。

本文针对人工蜂群算法存在易陷入局部最优、算法后期熟练速度较慢和搜索精度不高问题，提出一种改进人工蜂群算法，并将其用于解决无等待柔性流水车间调度问题，与其他算法比较，改进算法提高了最优解的精度和收敛速度。

1　问题描述与模型

NWFFSP可以描述为n个工件{J0，J1，…，Jn-1}连续在r道工序以相同的顺序加工，所有工件的工艺路线相同，r道工序中至少有一道工序存在多台并行机器，工件开始加工后不允许等待直至完成加工。设m为加工机器总数，第k道工序的并行机器数为qk（k=0，1，…，r-1），0＜qk＜m；Tik为工件Ji（j=0，1，…，n-1）在工序k上的运行时间；Sik为工件Ji在工序k上的开始加工时间；Cik为工件Ji在工序k上的完工时间；问题最大化完工时间为Cmax。

2　改进人工蜂群算法

2.1标准人工蜂群算法

在ABC算法中，人工蜂群按照分工可分为3种，即采蜜蜂、跟随蜂和侦查蜂，其中采蜜蜂和跟随蜂各占蜂群总数的一半，并且每一个蜜源仅有一个采蜜蜂工作。算法初始化时首先按式随机生成NF个初始解xm=（xm1，xm2，…，xmd），并计算每个蜜源位置的花粉量或者适应度值，同时记录全局最优值。其中，xmi为蜜源位置，m=1，2，…，SN，i∈d；Li和Ui分别是蜂群搜索的下界和上界。适应度值计算公式为：

其中f（xm）为蜜源xm目标函数值。之后按照以下步骤搜索最优解：（1）采蜜蜂对蜜源进行搜索并记忆蜜源的花蜜量，即问题解的质量（适应度）；（2）跟随蜂根据从采蜜蜂处获得的蜜源信息通过判断收益率来选择一个蜜源，而后对记忆的位置进行更新；（3）当蜜源因蜂蜜开采完而被放弃时，产生侦察蜂并搜索新的蜜源来替代旧蜜源。在算法中，为了根据蜜源位置xm产生一个新的候选位置vm，采用式

进行更新。根据蜜源的蜂蜜量，跟随蜂选择某个蜜源的概率为：

若经过“limit”次后，蜜源位置没有更新，则放弃该位置，而该位置采蜜蜂转换为侦查蜂并按照式（1）产生新蜜源。

2.2改进人工蜂群算法

（1）混沌算子初始化蜂群

混沌是自然界中广泛存在的一种非线性现象，利用混沌序列的遍历性、随机性和规律性特点进行种群初始化以增强ABC算法的种群多样性。本文采用广泛应用的Logistic映射表达式：

其中，T是预设的最大混沌迭代次数，rt为区间[0，1]上均匀分布的随机数且r0不包含{0，0.25，0.5，0.75，1}，u是混沌控制参数，当u=4时，系统将处于完全混沌状态。利用式产生一组混沌变量rt，并运用混沌序列依次将NF个d维食物源向量Fi按照式：

映射到混沌区间[Li，Ui]内，最后计算出每个食物源对应的适应度值。

（2）采蜜蜂自适应全局搜索方程

对于一个群体智能优化算法而言，如何权衡算法的“探索与开发”能力决定了算法的优化性能。开发能力是指在某个特定区域内搜索并能够提炼出较好解的能力，而探索能力是指算法探究搜索空间的不同区域以便确定一个较好解的能力。ABC算法的蜜源搜索方程因其选择的随机性而具有较强的探索能力。但同时可以发现，ABC算法的开发能力较差，因而存在收敛速度慢、搜索精度差的问题。针对这一问题，本文结合文献[5]在研究粒子群算法时所提出的自适应思想，提出了自适应蜜源搜索方程：

3　改进人工蜂群算法用于求解NWFFSP

3.1种群编码和解码

根据柔性车间调度问题的特点，不仅要确定所有工序的加工顺序，而且还要为每道工序选择一台合适的机器，因而本文采用基于工序和机器的两段编码方法。该编码由两部分组成：前半段是基于工序的编码，编码长度与工序数一致，表示蜜蜂对所有工序的遍历，每个码位记录该工序所属的工件号i，则工件Ji出现迄今为止出现的次数j代表了工序Oij。后半段是基于机器的编码，该段按照工序顺序，在每个码位记录加工该工序的设备在可选设备集M中的顺序编号（并非机器号）。

表1　可行解编码示例

表1为一个可行解编码，其中，E编码段中的E6=3表示工件J3的第二道工序O32，G编码段中的G7=1表示工序O32在第二台设备M3上加工。在解码阶段，由工序编码段E可得各个工件的加工序号，由机器编码段G可知每个工序的加工设备编号，在按照时间约束将工序安排在适当时间，生成调度方案。

3.2算法描述

输入：待调度的工件、工序和可用设备集合；采蜜蜂转成侦查蜂的循环最大次数limit；

输出：调度最优解；

（1）初始化参数种群数目NF，算法循环最大次数NC，n=0，count=0，使用混沌算子公式（6）初始化食物源P={x1，x2，…，xNF}；

（3）重复步骤（2），如果count=limit且fit（Vgbesti）值未发生变化，则依据式（7）寻找新蜜源，count=0；如果n=NC，输出调度最优解。

4　实验与分析

为检验算法有效性，在标准算例集XWdata中选取8×8（8工件8机器）、10×10（10工件10机器）、15×10（15工件10机器）的不同规模问题仿真实验。利用本文提出的IABC算法对8×8问题迭代15次得到问题最优值14，对10×10问题迭代17次得到问题最优值7，其最优解的甘特图如图1所示。

由表2可知，与其他几种典型算法，本文提出的IABC算法在迭代次数和最小完工时间方面均有一定的优势。

5　结语

为了解决无等待柔性流水车间调度问题，本文提出了改进的人工蜂群算法，在求解过程中引入混沌算子初始化种群；并采用自适应全局最优蜜源搜索策略以平衡人工蜂群算法的“探索与开发”能力，通过不同实例测试证明，本文提出的算法能够有效求解无等待柔性流水车间调度问题。

图1　　10×10（10工件10机器）问题最优解甘特图

表2　三种算法实验对比结果

[1]李建祥，唐立新等.带运输和设置时间的无等待并行流水车间调度问题研究[J].系统工程理论与实践，2006，26（1）:18～25

[2]Jolai F，Sheikh S，Rabbani M，et al.A Genetic Algorithm for Solving No-Wait Flexible Flow Lines with Due Window and Job Rejection[J].International Journal of Advanced Manufacturing Technology，2009，42（5-6）:523～532

[3]Song Jiwei，Tang Jiafu.No-Wait Hybrid Flow Shop Scheduling Method Based on Discrete Particle Swarm Optimization[J].Journal of System Simulation，2010，22（10）:2257～2261

[4]张其亮，陈永生.基于混合粒子群-NEH算法求解无等待流水车间调度问题[J].系统工程理论与实践，2014，34（3）:802～809

[5]吴建辉，章兢，李仁发等.多子种群微粒群免疫算法及其在函数优化中的应用[J].计算机研究与发展，2012，49（9）:1883～1898

毕孝儒（1975-），硕士，网络工程师，研究方向为计算机网络安全与集成

杨柳（1982-），讲师，研究方向为数据挖掘

张黎黎（1982-），讲师，研究方向为软件理论与技术

贺拴（1982-），助教，研究方向为数据挖掘

Artificial Bee Colony Algorithm;NWFFSP;Chaotic Mechanism;Searching Ability

Improved Artificial Bee Colony Algorithm for Solving No-wait Flexible Flow Shop Scheduling Problem

BI Xiao-ru，YANG liu，ZHANG Li-li，HE shuan
（School of Management，College of Chongqing South Translation，University of SISU，Chongqing 401120）

To solve NWFFSP,proposes an improved artificial bee colony algorithm.Adopts chaotic mechanism to initialize each individual of the swarm for it's diversity;in the phase of search for nectar source,applies self-adaptive global searching strategy to balance ability of the algorithm for exploring and development for avoiding local optimization of end phase of search.Uses improved artificial bee colony algorithm for solving NWFFSP and proves the validity and superiority of the algorithm by simulation experiment.

1007-1423（2015）14-0014-04

10.3969/j.issn.1007-1423.2015.14.004

2015-03-17

2015-04-27