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

李俊青 ， 潘全科 ， 王法涛

(1.聊城大学 计算机学院,山东 聊城 252059; 2.东北大学 流程工业综合自动化国家重点实验室,辽宁 沈阳 110819； 3.北京邮电大学 经济管理学院,北京 100876)



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

李俊青1,2， 潘全科1,2， 王法涛1,3

(1.聊城大学 计算机学院,山东 聊城 252059; 2.东北大学 流程工业综合自动化国家重点实验室,辽宁 沈阳 110819； 3.北京邮电大学 经济管理学院,北京 100876)

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

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

0 引言

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

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

1 问题描述与定义

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

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

图1HFS问题定义

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

2 基本人工蜂群算法

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

3 混合算法框架

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

表1 HFS示例

3.1 问题编码

图2 HFS问题甘特图

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

3.2 初始解集的建立

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

步骤1Cnt=1；

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

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

步骤4 跳转到步骤2。

3.3 邻域结构

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

交换邻域，记为N1。产生策略为：在解的长度范围内随机生成两个位置，记为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-1，如果i>=j，则停止，否则，循环执行步骤(2)。

3.4 局部搜索策略

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

图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.8HDABC框架流程

本文给出的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的经典算例[10,16]中选取了24个较难的算例，并与四种典型算法做了对比，比较结果如表2所示。表中第一列给出了算例问题，包括12个10工件问题和12个15工件问题，每个算例由三个字符和三个整数表示，这三个字符含义如下：“j”表示工件，“c”表示加工阶段，第三个字符表示并行机的布局方式，其含义如下为：(1)“c” 表示中间加工阶段有两台机床，其余阶段有三台机床；(2)“d” 表示每个加工阶段有三台并行机床。例如，“ j10c5c1”表示该问题有10个工件和5个加工阶段，其并行机布局方式是中间阶段有两台机床，其余阶段有三台机床并行。

表2 24个Carlier和Neron算例对比

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

为进一步验证算法在求解较大规模HFS问题的性能，本文选取文献[10]中列出的10个较大规模算例进行对比分析，比较算法包括PSO和AIS两种算法。表3给出了比较结果。表中给出了每个算法求解问题的最好值(Min)、最差值(Max)、平均值(Avg)和平均耗费时间(CPU)。算法求解的最好值与最优值间的偏差也在表中给出。表中最后一列给出了每个算例的最优值，该最优值是三种对比算法所找到的最好解。

表3 10个大规模HFS问题比较

表3可见：(1)从最好解来看，在求解10个较大规模算例中，HDABC能找到所有10个算例的最好值，而其他两种算法的最好值明显次于HDABC。例如，对于”j30c5e10”问题，HDABC找到最优解是580，而PSO找到594，AIS的最好值是604；(2)从最差值的比较可见，HDABC对于所有10个大规模算例的最差解均优于其他两种比较算法，且有些最差解好于对比算法的最好解，进一步验证了算法的性能；(3)平均值的对比可见，HDABC平均性能明显优于两种对比算法。例如，对于”j30c5e1”问题，HDABC的平均值优于其他两种算法的最好值，验证了算法的鲁棒性；(4)平均耗费时间的比较可见，HDABC略优于PSO，而明显好于AIS算法；(5)结合算法耗费时间和最好值、最差值以及平均值的对比可见，HDABC算法在求解较大规模HFS问题中表现了明显的优势。

图4 求解j30c5e10问题收敛曲线

为了比较不同算法参数对算法性能的影响，本文选取三组实验参数进行比较分析：(1) ABC-I算法，参数设置同4.1节；(2) ABC-II算法，与ABC-I不同之处是：初始解集大小=5；雇佣蜂数量=5；跟随蜂数量=5；(3) ABC-III算法，与ABC-II不同之处是：Tn=5。图4给出了上述三种算法求解最大规模”j30c5e10”问题的收敛曲线，由图4可见，三种算法均具备良好的收敛能力，而ABC-I算法优于其他两种算法。上述比较结果证明：种群的大小设置应该适中，太小的种群搜索能力不足；局部搜索策略中，邻域解集不能太小，否则影响算法寻优能力。

4.3 异构并行机实验结果分析

异构并行机HFS相对于同构并行机HFS问题更贴近生产实际，因而更具备现实意义。为验证算法求解不相关并行机HFS问题的性能，本文选取两个实际生产调度问题实例，具体描述可参见文献[19]，比较算法包括AIS、SFLA和EDA三种算法[19]。由表4比较结果可见：

(1)求解两个现实生产调度问题，HDABC和EDA均取得了最好值，且明显优于其他两种算法；(2)在平均值方面，HDABC算法明显优于其他三种比较算法，验证了算法的平均性能；(3)算法求解两种调度算例，均可在1秒左右内完成，验证了算法的高效性。

表4 异构并行机HFS问题比较结果

5 结论

本文给出了一种混合离散人工蜂群算法用于求解混合流水车间调度问题，主要贡献包括：设计了性能良好的邻域结构；构建了新的雇佣蜂、跟随蜂和侦察蜂策略；设计的算法可有效用于求解同型并行机和异构并行机HFS问题。通过经典算例实验，并与当前文献典型算法做对比分析，验证了算法的有效性和稳定性。下一步的工作时继续优化提出的混合算法，并应用算法求解其他生产调度问题。

[1] Ruiz R, Vázquez Rodríguez J A. The hybrid flow shop scheduling problem[J]. European Journal of Operational Research, 2010, 205: 1-18.

[2] Gupta J N D. Two-stage, hybrid flow shop scheduling problem[J]. Journal of the Operational Research Society, 1988, 39: 359-364.

[3] Portmann M C, Vignier A, Dardilhac D, Dezalay D. Branch and bound crossed with GA to solve hybrid flowshops[J]. European Journal of Operational Research, 1998, 107: 389- 400.

[4] Neron E, Baptiste P, Gupta J N D. Solving hybrid flow shop problem using energetic reasoning and global operations[J]. Omega-International Journal of Management Science, 2001, 29: 501-511.

[5] Oguz C, Ercan M. A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks[J]. Journal of Scheduling,2005, 8: 323-351.

[6] Ribas I, Leisten R, Framinan J M. Review and classification of hybrid flow shop scheduling problems from a production systems and a soluntions procedure perspective[J]. Computers & Operations Research, 2010, 37: 1439-1454.

[7] Janiak A, Kozan E, Lichtenstein M, Oguz C. Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion[J]. International Journal of Production Economics, 2007, 105: 407- 424.

[8] Niu Q, Zhou T, Ma S. A quantum-inspired immune algorithm for hybrid flow shop with makespan criterion[J]. Journal of Universal Computer Science, 2009, 15: 765-785.

[9] Kahraman C, Enginb O, Kaya I，Öztürk R E. Multiprocessor task scheduling in multistage hybrid flow-shops: a parallel greedy algorithm approach[J]. Applied Soft Computing, 2010, 10: 1293-1300.

[10] Liao C J, Tjandradjaja E, Chung T P. An approach using particle swarm optimization and bottleneck heuristic to solve hybrid flow shop scheduling problem[J]. Applied Soft Computing, 2012, 12: 1755-1764.

[11] Karaboga D. An idea based on honey bee swarm for numerical optimization[R]. Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.

[12] Karaboga D, Basturk B. On the performance of artificial bee colony(ABC)algorithm[J]. Applied Soft Computing, 2008, 8 (1):687- 697.

[13] Pan Q K, Tasgetiren M F, Suganthan P N, Chua T J. A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem[J]. Information Sciences, 2010, 181(12): 2455-2468.

[14] Pan Q K, Wang L, Mao K, Zhao J H, Zhang M. An effective artificial bee colony algorithm for a real-world hybrid flowshop problem in steelmaking process[J]. IEEE Transactions on automation science and engineering, doi: 10.1109/TASE.2012.2204874.

[15] Li J Q, Pan Q K, Gao K Z. Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems[J]. International Journal of Advanced Manufacturing Technology, 2011, 55(9-12): 1159-1169.

[16] Carlier J, Neron E. An exact method for solving the multi-processor flowshop[J]. RAIRO Operations Research, 2000, 34: 1-25.

[17] Engin O, Doyen A. A new approach to solve hybrid flow shop scheduling problems by artificial immune system[J]. Future Generation Computer Systems, 2004, 20(6): 1083-1095.

[18] Alaykyran K, Engin O, Doyen A. Using ant colony optimization to solve hybrid flow shop scheduling problems[J]. International Journal of Advanced Manufacturing Technology, 2007, 35(5-6): 541-550.

[19] 王圣尧，王凌，许烨，周刚.求解混合流水车间调度问题的分布估计算法[J].自动化学报，2012，38(3):437- 443.

Solving Hybrid Flow-shop Scheduling Problems by a Hybrid Discrete Artificial Bee Colony Algorithm

LI Jun-qing1,2, PAN Quan-ke1,2, WANG Fa-tao1,3

(1.SchoolofComputerScience,LiaochengUniversity，Liaocheng252059，China; 2.StateKeyLaboratoryofSyntheticalAutomationforProcessIndustries,NortheasternUniversity,Shenyang110819,China; 3.SchoolofEconomicsandManagement,BeijingUniversityofPostsandTelecommunications,Beijing100876,China)

In this paper, we propose a hybrid discrete artificial bee colony(HDABC)algorithm for solving the hybrid flow-shop scheduling(HFS)problems. In the hybrid algorithm, each solution is coded by a job-permutation mechanism. Four neighborhood structures are designed. The employed bees are assigned to each solution in the population set, to complete the local search task with a detailed designed local search approach. Onlooker bees randomly fetch two updated solutions and select the better one as the current solution, and then complete a further exploitation process. The scouts help the algorithm jump out of the local best by applying three different approaches. Then, the proposed algorithm is tested on the 34 identical parallel machines HFS and two un-related parallel machines HFS problems. The performance comparisons with other efficient algorithms are provided. It is concluded that the proposed algorithm is competitive to the compared existing algorithms for the problem considered, in terms of searching quality, diversity, robustness and convergence ability.

hybrid flow shop scheduling; artificial bee colony algorithm; local search; neighborhood structure

2013- 05- 09

国家自然科学基金项目(61104179，61174187,61374187)

李俊青(1976-)，男，山东冠县人，博士研究生，副教授，主要从事计算智能、优化算法的研究；潘全科(1971-)，男，山东阳谷人，博士，教授，博士生导师，主要从事优化调度研究；王法涛(1980-)，男，山东德州人，讲师；北京邮电大学经济管理学院管理科学与工程专业博士研究生，研究方向：电子商务与供应链管理。

TP18

A

1007-3221(2015)01- 0157- 07