求解混合流水线调度问题的离散人工蜂群算法

摘要：本文给出了一种离散的人工蜂群算法（HDABC）用于求解混合流水车间调度（HFS）问题。采用工件排序的编码方式，并设计了四种邻域结构。雇佣蜂依次分派到解集中每个解，采用结合问题特征的局部搜索策略完成挖掘搜索工作。跟随蜂随机选择两个解并挑选较优者作为当前解，完成进一步的探优过程。侦察蜂采用三种策略跳出局部极小。通过34个同构并行机HFS问题和2个异构并行机HFS实际调度问题的实验，并与当前文献中的典型算法对比，验证了本文提出的算法无论在算法时间还是在求解质量上，都具备良好的性能。

关键词：混合流水车间调度；人工蜂群；局部搜索；邻域结构

中图分类号：TP18

文章标识码：A

文章编号：1007-3221（2015）01-0157-07

引言

调度问题是工业工程领域中关键技术问题，混合流水线（Hybrid Flow Shop，HFS）调度问题属于NP一难问题，是调度问题的一个特例，由于其广泛存在于生产流程中，已成为近年来的研究热点。在HFS中，加工流程划分为几个阶段，每个加工阶段由若干同型或异构机床组成，任何一个工件需要严格按照相同的加工顺序依次流经每个加工阶段，到达任意阶段时，可以从多个并行机床中选择一个进行加工。文献是最早采用分支一定界法求解HFS问题的文献，之后出现了许多不同的算法。按照加工阶段的不同，HFS -般分为三种类型：2-阶段HFS、3-阶段HFS和m-阶段HFS。当前，m-阶段HFS由于更贴近生产实际而成为研究热点。研究m-阶段HFS的主要文献有：1998年，Portman设计了一种遗传算法和分支一定界相结合的方法；Neron给出了在5-阶段下求解HFS问题的优化算法；Oguz则设计了一种基于遗传算法的混合方法；Ruiz等针对顺序决定的准备时间的HFS开发了一种基于遗传算法的方法；Janiak则采用基于禁忌搜索和模拟退火的启发式方法；此外，Niu等设计了量子启发式免疫算法；Kahrama设计了一种并行贪婪优化算法；Liao等提出了一种结合瓶颈机床的粒子群优化算法。

上述优化算法用于求解HFS问题，有些收敛能力不足，有些则易于陷入局部极小。人工蜂群（Artificial Bee Colony，ABC）算法是一种新的群体智能优化方法，由Karaboga等于2005年首次提出，主要应用于求解连续函数优化问题。文献针对ABC方法应用到离散问题领域，提出了离散人工蜂群算法，并应用求解流水线调度。文献则把离散ABC方法应用到求解柔性作业车间调度（FlexibleJob Shop scheduling Problem，FJSP）问题中。上述文献表明，ABC算法由于有效平衡了全局搜索和局部搜索能力，可以有效应用于求解复杂调度问题。本文结合ABC算法的特点，提出了一种求解HFS问题的离散ABC方法。

1 问题描述与定义

HFS问题如下：假设有M个机床个工件和s个加工阶段。每个加工阶段si包含mi个同型或异构的并行机床，每个工件Ji通过加工阶段si时，可任选其中一个机床进行加工。为构建HFS问题模型，定义如下符号：Mi为加工阶段i中的并行机床集合；pijk为工件j在加工阶段i选择机床k的加工时间（pijk≥0）；sij为工件j在加工阶段i的开工时间；cij为工件j在加工阶段i的完工时间；L为极大数。

如果在加工阶段i工件j选择机床k进行加工

否则

在加工阶段i，如果工件j和h在同一机床上加工，并且j是h的紧前工作

否则

有了上述符号，HFS问题的模型如下：

其中，不等式约束（2）描述同一工件的工序间的先后约束关系，不等式约束（3）限制同一个机床上有紧前关系的工件间不允许出现加工时间重叠，等式约束（4）定义每个工件的每个加工阶段只能选择一个机床加工。

2 基本人工蜂群算法

人工蜂群算法是由Karaboga等于2005年提出的一种新的群体智能优化算法，是模拟蜜蜂寻找食物的过程而演化的仿生过程。在基本ABC中，食物源（food source）和人工蜜蜂（artificial bees）是基本构成要素。人工蜜蜂又被分为三种，即雇佣蜂（Employed bees）、跟随蜂（Onlooker bees）和侦察蜂（Scoutbees）。雇佣蜂的任务是在随机食物源周围进一步挖掘，以便找到更好的食物源；在雇佣蜂把挖掘后的信息带回后，守在蜂巢中的跟随蜂按照一定概率选择较好的食物，进一步搜索挖掘；当某些食物在经过一定周期后，未曾发生改变，则派出侦察蜂随机搜索新的食物源。ABC算法中基本控制参数包括：解集大小SN，解无更新而被丢弃的周期大小Ls，雇佣蜂数目E，，跟随蜂数目os，侦察蜂数目Ss和终止条件。

3 混合算法框架

基本ABC用于求解连续优化问题，因而，应用于求解离散调度问题需要进行离散化。结合问题特征，本文对基本ABC算法进行离散化设计。

3.1 问题编码

本文采用简单工序排列编码方式。假设问题加工时间和各个加工阶段机床分配情况如表l所示。给定一个解{4，1，2，5，3}，其含义如下：在第一个加工阶段，按照各工件在解中的位置次序先后调度，首先调度工件J4，之后J3，最后调度工件J3。由于解中没有包含机床选择策略，各个工件按照最早完工机床原则选择相应机床加工：如果有多个机床空闲可用于加工，则选择加工时间最短的；如果只有一个空闲机床，则直接开始在该机床上加工。经过后面各个加工阶段时，各个工件按照在上一个加工阶段完工时间的先后次序，选择相应机床进行加工。对应表1的HFS例子，其最优的调度甘特图如图2所示。图中，每个工件由一对数字表示，第一个数字对应工件编号，第二个对应加工阶段序号。例如，在机床M1上，第一个加工的是（4，1），对应工件J4在第一个加工阶段选择机床M1。图中，最后一个完工的工件J5，其完工时间是30，表示该解对应的最优目标值是30。

3.2 初始解集的建立

为了提高初始解集的多样性，避免解集的趋同性，本文采用如下随机解集产生策略：

步骤1 Cnt=1；

步骤2 如果Cnt=SN，终止初始过程，否则，随机产生一个解；

步骤3如果产生的新解不同于当前解集中的任何解，则插入到当前解集，并设置Cnt=nt+1；否则，忽略该解；

步骤4跳转到步骤2。

3.3 邻域结构

结合问题结构特点，本文设计了4种邻域结构，定义如下：

交换邻域，记为Ⅳ，。产生策略为：在解的长度范围内随机生成两个位置，记为r1和r2，交换r1和r2对应的工件编号；

前插邻域，记为N2。产生策略为：在解的长度范围内随机生成两个位置，记为r1和r2（r1

翻转邻域，记为N3。产生策略为：在解的长度范围内随机生成两个位置，记为r1和r2（r1

序对交换邻域，记为N4。产生策略为：（1）在解的长度范围内随机生成两个位置，记为r1和r2，令i=r1，j=r2；（2）交换位置i和j对应的工件编号，令i=i+1，j=j-l，如果i>=j，则停止，否则，循环执行步骤（2）。

3.4 局部搜索策略

本文给出了一种局部搜索策略，用于在给定解周围挖掘可能的较优解。该局部搜索策略用于雇佣蜂、跟随蜂以及侦察蜂搜索食物的过程，具体描述如图3所示。

3.5 雇佣蜂阶段

雇佣蜂的主要任务是在分配的食物上开展挖掘工作，搜索更好的食物源。基本ABC中雇佣蜂的操作算子不适合于调度问题。本文给出的离散ABC算法中，雇佣蜂的策略如下：

步骤1 为当前解集中每个食物源分配一个雇佣蜂；

步骤2 以指定解为当前解Sc在3.3节中给定的四种邻域结构中随机选择邻域结构Nc，执行3.4节的局部搜索策略，得到更新后的解Sc；

步骤3 用Sc替换给定的解。

3.6 跟随蜂阶段

在雇佣蜂挖掘工作结束后，守候着蜂巢的跟随蜂在更新后的解集中以概率选择的方式挑选较优解进一步挖掘搜索。采用赌注选择方式，需要比较解集中每个解的目标值的大小，因而时间复杂度较高。为了提高算法效率，本文给出了一种简单的跟随蜂的选择策略，具体描述如下：

步骤1 在当前解集中随机选择两个解S1和S2；

步骤2 在选中的解中挑选较优解作为当前解Sc；

步骤3 随机选择邻域结构Nc；

步骤4 执行3.4节中的局部搜索策略，找到更新后的解Sc，并替换当前选中的解。

3.7 侦查蜂阶段

结合HFS问题特征，本文给出了三种侦察蜂策略，具体描述如下：

策略一，随机解策略。若解集中某个解在指定时间间隔内没有更新，生成一个随机解替换该解，并派出侦察蜂进一步挖掘。

策略二，丢弃解策略。在某个解在指定时间间隔内没有更新时，对该丢弃解进行10次邻域扰动，然后派出侦察蜂在扰动后的解上进一步挖掘搜索。

策略三，最好解策略。对最好解进行10次邻域扰动，用扰动后的最好解替换该解，然后派出侦察蜂进一步挖掘搜索。

侦察蜂挖掘搜素的过程如下：

步骤1 随机选择邻域结构Nc；

步骤2执行3.4节中的局部搜索策略，找到更新后的解Sc，并替换当前选中的解。

3.8 HDABC框架流程

本文给出的HDABC算法流程如下：

步骤1 初始化实验参数，生产初始解集；

步骤2 若终止条件满足，则结束算法，否则，执行步骤3～6；

步骤3 给当前解集中每个解分派雇佣蜂，执行挖掘搜索工作；

步骤4 分派跟随蜂，进一步挖掘更新后的解集；

步骤5 ：如果满足派出侦察蜂的条件，则随机选择一种侦察蜂策略，开展进一步强化搜索。

步骤6 ：返回步骤2。

4 实验分析

4.1 实验设置

以VC++6.0为开发环境，采用Intel Core i5 3.3 GHZ、4GB RAM的PC机，针对34个同构HFS经典算例和2个异构并行机炼钢连铸现实生产的HFS问题，验证所得算法的性能，问题规模从10个工件5个加工阶段到30个工件5个加工阶段。算法参数设置如下：

初始解集大小=10；

雇佣蜂数量= 10；

跟随蜂数量=10；

侦查蜂数量=1；

侦察蜂派出时机：某个解超过10秒没有更新；

局部搜索策略相关参数：雇佣蜂、跟随蜂循环次数Ti=10，侦察蜂循环次数Ti=50，邻域解集大小Tn=10；

结束条件：运行时间超过150秒。

4.2 同型并行机实验结果分析

本节我们从77个Carlier和Neron的经典算例中选取了24个较难的算例，并与四种典型算法做了对比，比较结果如表2所示。表中第一列给出了算例问题，包括12个10工件问题和12个15工件问题，每个算例由三个字符和三个整数表示，这三个字符含义如下：“j”表示工件，“c”表示加工阶段，第三个字符表示并行机的布局方式，其含义如下为：（1）“c”表示中间加工阶段有两台机床，其余阶段有三台机床；（2）“d”表示每个加工阶段有三台并行机床。例如，“jlOc5cl”表示该问题有10个工件和5个加工阶段，其并行机布局方式是中间阶段有两台机床，其余阶段有三台机床并行。

表2给出了求解上述24个经典算例的结果，比较算法包括PSO，AIS，ACO和B&B四种算法。表中第二列给出了每个算例的下界值。每个算法的结果包括两列：第一列给出了该算法经过20次独立运行找到的最好目标值，即makespan值；第二列给出了算法平均计算时间，单位为秒。最后五列则给出了每种算法所找到的目标值相对于最优值的偏差。由表2可见：（1） HDABC算法具备最好的求解速度，其平均运行时间仅为2.8秒，而其余比较算法花费的时间大大超过HDABC算法，即使考虑机器性能的差异性，比较结果也足以证明HDABC算法的效率；（2）从求解质量来看，PSO算法在求解24个算例中表现了良好的性能，其偏差为2.85，HDABC算法在求解”jlOc5c3”和”j10c5d2”两个算例稍差于PSO算法，但整体性能强于其他三种算法；（3）综合考虑算法耗费时间和求解质量，HDABC在求解中等规模HFS问题中表现了良好的性能。