改进捕鱼算法求解柔性作业车间调度问题

杨剑勇

摘 要： 传统基于精确算法求解柔性作业车间调度问题时，仅能对小量柔性作业车间调度问题实施求解，具有一定的局限性。针对该问题，采用改进捕鱼算法求解柔性作业车间调度问题，在分析经典捕鱼算法存在弊端的基础上，提出改进捕鱼算法，融入渔夫的自身感知性能以及捕鱼经验，分析鱼浓度高的区域，并不断趋向该区域区间，通过概率分布原理对渔夫撒网方案实施优化。分析求解柔性作业车间调度问题的描述以及性能指标，将性能指标作为改进捕鱼算法的输入，通过运算获取最佳的调度结果。实验结果说明，所提算法具有较高的调度效率和精度，并且确保作业车间能耗的最小化。

关键词： 改进捕鱼算法； 求解； 柔性作业； 车间； 调度问题

中图分类号： TN911.1?34； TP301.6 文献标识码： A 文章编号： 1004?373X（2017）21?0128?04

Improved fishing algorithm for solution of flexible job?workshop scheduling problem

YANG Jianyong

（School of Computer Science and Engineering， Changshu Institute of Technology， Changshu 215500， China）

Abstract： The traditional precise algorithm for the solution of the flexible job?shop scheduling problem can only solve the small amounts of the flexible job?shop scheduling problem， and has a certain limitation. In order to eliminate the above problems， the improved fishing algorithm is used to solve the flexible job?shop scheduling problem. On the basis of analyzing the shortcomings of the classical fishing algorithm， the improved fishing algorithm is put forward， and the perceived performance and fishing experience of the fisherman itself are integrated into it to analyze the area with high concentration of fish， and tend to the area range constantly. The principle of probability distribution is used to optimize the net casting scheme of fisherman. The description of the flexible job?workshop scheduling problem solution and performance index are analyzed. The performance index is taken as the input of the improved fishing algorithm， and then operated to get the optimal dispatching result. The experimental results show that the proposed algorithm has high scheduling efficiency and precision， and can ensure the minimum energy consumption of the job workshop.

Keywords： improved fishing algorithm； solution； flexible job； workshop； scheduling problem

0 引 言

以前的车间调度过程中各道工序仅通过一台明确的机器进行加工，柔性作业车间调度问题能够解决该种资源约束，使得不同工序在一台或多台机器中进行加工，提高了可行解的检索区域，使得作业车间调度效率提高[1]。因此，求解柔性作业车间的高质量调度问题成为研究的重点。传统方法主要采用精确算法求解柔性作业车间调度问题，但是该方法仅能对小量柔性作业车间调度问题实施求解，具有一定的局限性。针对该现象，本文采用改进捕鱼算法求解柔性作业车间调度问题，实现调度的高效率和高精度，提高作业车间产量和质量。

1 改进捕鱼算法求解柔性作业车间调度

1.1 基本捕鱼算法

基于渔夫捕鱼行为以及习惯的启发，采用依据模拟渔夫捕鱼的智能优化算法，设置渔夫捕鱼作业区的范围是[D=D1×D2×…×Dn，]其用于描述作业车间控制变量组的取值域，[K]个渔夫用于描述[K]个控制变量组，各渔夫位置的状态量是[X=（x1，x2，…，xn）]，其用于描述一个控制变量组，[D]内鱼的密度函数是[f（X）]，用于描述求解静态电压稳定裕度的目标函数[λmax，]将获取鱼密度最高以及所处位置过程看成是獲取最高[λmax]和状态变量最佳组合的过程。

收缩检索，通过[m]次移动搜索后[2]，渔夫[i]将即刻位置当成中心塑造方体，获取撒网点集：

[Ωim=Xim=（ti1，ti2，…，tin）tij∈ximj-l-j，ximj，ximj+l+j， j=1，2，…，n] （1）endprint

若[f（Xim）=maxXi∈Ωimf（Xi）

[Ωim+1=Xim+1=（ti1，ti2，…，tin）tij∈ximj-l-j，ximj，ximj+l+j， j=1，2，…，n] （2）

式中：[l-j=αl-j，l+j=αl+j，0<α<1，][α]表示方体边长的收缩系数。

若在收缩搜索过程时获取最高鱼密度位置，将渔夫位置当成中心，塑造新方体实施搜索，同时运行收缩搜索。设置搜索阈值确保搜索过程顺利进行。

1.2 改进捕鱼算法

上述分析的基本捕鱼算法过程中的渔夫缺乏对自身以及环境的感知能力，仅凭对方体的运算变换撒网位置，捕鱼效率以及精度较低，因此采用改进捕鱼算法对基本捕鱼算法进行改进[4]，融入渔夫的自身感知性能以及捕鱼经验，分析鱼浓度高的区域，并不断趋向该区域区间，通过概率分布原理改进渔夫撒网方案，提高捕鱼效率和精度。

设置[t]时刻的全局最佳位置以及最优点是[G（t）=][（g1（t），g2（t），…，gn（t））]以及[Bi（t）=bi1（t），bi2（t），…，bin（t）]，该种情况下第[i]个渔夫的位置是[Xi（t）=xi1（t），xi2（t），…，xin（t），]若存在[Xi≠G（t），]则该渔夫采用[N]個探测点的方案为：

[Pij（t+1）=Xi（t）+rjIβjQj（t+1）Qj（t+1）] （3）

[rj=（1-βj）G（t）-X（t）G（t）-X（t）] （4）

式中：[j=1，2，…，N；][i]表示撒网半径；[Qj（t+1）]表示随机数。

基于概率分布原理可得，若[Xi=G（t），]则该渔夫采用[N]个探测点的方案是：

[Pij（t+2）=Xi（t+1）+rjIQj（t+2）Qj（t+2）] （5）

设置[Pibest（t+1）=bestPij（t+1）：1≤j≤N，]如果[Pibest（t+1）]比[Xi（t）]好，则第[i]个渔夫将变换到位置[Pibest（t+1）]，同时存在[Xi（t+1）=Pibest（t+1）]。如果[Pibest（t+1）]比[Xi（t）]差，则当[Xi（t）=G（t）]时第[i]个渔夫的运行捕鱼位置固定，否则其位置调整规范是：

[Xij（t+1）=Xij（t）+rbij（t）-xij（t）+r2?exp-gj（t）-xij（t）gj（t）-xij（t）gj（t）-xij（t）] （6）

2 求解柔性作业车间调度问题

2.1 柔性作业车间调度问题描述

柔性作业车间调度问题描述：若作业车间存在[n]个待加工的工件，工件集是[J={J1，J2，…，Jn}]。工件[Ji（i=1，2，…，n）]包括[ni]个工序，并且其加工顺序是确定的，工件[Ji]中的第[j]个工序是[Oij，]存在[m]台可进行加工的机器，机器集是[M=M1，M2，…，Mm]；工序[Oij]能够在任意候选机器中加工，候选机器集是[Mij，]且有[Mij?M，]工序在各态机器中的加工时间事先已经设置好，并且这些时间存在一定的差异。作业车间调度的目的是对各工序选择加工的机器以及机器中的加工顺序实施调控[5]，得到确保目标函数最高的调度策略。加工时应确保某时刻一台机器仅可加工一个工序，某时刻一个工序仅能在一台机器中进行，不同工件工序不相交，加工过程中的工序无法中断，全部工件具有一致的优先级。

基于候选机器集将柔性作业车间调度问题划分成局部柔性作业车间调度问题和全部柔性作业车间调度问题，其中前者要求至少存在一个工序的可选择加工机器集为局部机器[6]，则有[Mij?M；]而后者要求作业车间调度过程中各工序都能够采用随机的一台机器实施加工，则有[Mij=M，]量子柔性作业车间调度问题的实例分别如表1和表2所示。实际生产时对机器选择过程中受到相关条件的制约，局部柔性作业车间调度问题的应用价值更高，但是其具有较高的检索范围和运算量。

表1中描述的部分柔性作业车间调度问题的加工机器以及加工时间表共存在2个工件以及4台机器，其中“—”用于描述该工序无法采用相关的机器加工。

2.2 柔性作业车间调度问题性能指标和求解

求解2.1节分析的部分柔性作业车间调度问题以及全部柔性作业车间调度问题过程中存在较多的性能评估指标，先设置柔性作业车间中工件数和机器数是[n]和[m，][ni]是[Ji]的工序数，工件[Ji]的完成时间是[Ci，]工序[Oij]在[Mk]中的加工时间是[pijk，][xijk=1]或0用于描述工序[xijk=1]在和不在机器[Mk]中加工。

求解柔性作业车间调度问题采用的性能指标如下：

（1） 最高完工时间最低。完工时间是各工件的全部工序都加工完成耗费的时间，最后被加工工序的完成时间是最高完工时间，其描述了产品的生产时间的最小值。最高完工时间最低是评估柔性作业车间调度方案优劣的基本指标[7]，其目标函数为：

[f1=minmax1≤i≤n（Ci）] （7）

（2） 总机器负载最低。总机器负载是全部机器加工时间的汇总，工序在不同候选机器中的加工时间存在一定的差异，因此不同柔性作业车间调度策略中总机器负载与不同工序选择加工机器相关[8]，若最高完工时间一致，则选择总机器负载最低的调度指标，其目标函数是：

[f2=mink=1mi=1nj=1njpijkxijk] （8）

（3） 最高机器负载最小。机器负载是机器在总体加工时的全部加工时间，部分柔性作业车间调度以及全部柔性作业车间调度过程中，不同机器负载同工序以及加工机器相关，为了增强调度策略质量，应确保不同机器负载的均衡性，则目标函数为：

[f3=minmax1≤k≤mi=1nj=1njpijkxijk] （9）

（4） 提前/拖期最低。实际柔性作业车间调度过程中，生产任务提前以及滞后完成需要耗费相应的成本，在求解柔性作业车间调度问题过程中重复分析交货期问题[9]。基于最高完工时间以及交货期的差值描述工件交货期的提前/拖期时间，工件[Ji]的交货期和完工时间为[di]和[Ci，]工件的最高提前时间是[Ei=maxdi-Ci，0]，最高拖延时间是[Ti=maxCi-di，0]，则目标函数为：

[f4=minmax1≤i≤n（Ei）] （10）

[f5=minmax1≤i≤n（Ti）] （11）

基于这些指标，将这些指标作为改进捕鱼算法[t]时刻的全局最佳位置以及最优点，通过改进捕鱼算法获取[N]个探测点的方案，也就是最佳的捕鱼方案，完成柔性作业车间调度问题的优化求解。

3 实验分析

3.1 调度效果测试

实验为了检测本文提出的基于改进捕鱼算法求解柔性作业车间调度的性能，算法通过软件VS2015、操作系统Windows 10，通过C++编程实现，实验采用文献[7]中的数据实施分析，将8×8柔性作业车间调度问题作为算例求解生产周期。8×8实例中的机器和工件数都是8，各工件存在3～4个工序，是包括27个工序的部分柔性车间作业调度问题。设置人工鱼群的规模为10，初始视野是工件数和工序数的乘积，拥挤度阈值是初始视野的[14]，最高迭代次数是5，分别采用本文算法和基本捕鱼算法实施10次运算，获取的甘特图如图1，图2所示。

分析图1，图2可得，本文算法的寻优性能以及精确度高于基本捕鱼算法，主要是由于本文算法融入渔夫的自身感知性能以及捕鱼经验，分析鱼浓度高的区域，并不断趋向该区域区间，通过概率分布原理对渔夫撒网方式实施优化，极大增强了算法的寻优精确度。

分析图1能够看出，本文算法获取的最高完工时间最低的周期是14，实验对比分析不同方法调度下的作业车间生产周期，结果如表3所示，能够看出本文算法取得的结果最优，缩短了生产周期。

实验采用不同算法对柔性作业车间调度Kacem基准函数实施求解。该函数由10×10实例构成，其中10×10实例中的机器和工件数都是10，各工件存在3个工序，是包括30个工序的全部柔性车间作业调度问题。采用本文算法实施10次运算，获取各基准函数的最佳解甘特图如图3所示。实验统计不同算法对Kacem基准函数的检测结果，见表4。其中的目标函数是2.2节分析的柔性作业车间的调度相关性能指标。

分析图3和表4可得，对于不同目标函数，本文算法的检测结果都优于其他算法，对10×10算例的平均解比基本捕鱼算法佳，实现了柔性作业车间的合理调度。

3.2 能耗测试

实验检测本文算法对某模具车间实施调度的能耗情况，该模具作业车间包括14个工件，12台机器，78道工序，实验将最小化完工时间以及最小化加工能耗当成分析不同调度方法的指标，其中12台机器的能耗情况见表5。

模具车间中抛光工序采用人工进行，则表5中的抛光机器[M′12]的能耗是0。

基于表5中描述的不同机器的能耗参数，采用本文算法和基本捕鱼算法获取目标包含最小化最大完工时间[f1]、最小化加工能耗[f3，]结果如表6所示。

分析表6中的[f1]以及[f3]值，能夠看出本文算法获取的[f1]以及[f3]值低于基本捕鱼算法，说明本文算法在优化求解柔性作业车间调度过程最小化最大完工时间以及最小化加工能耗两个目标过程具有较强的性能，能够更好地确保作业车间能耗的最小化。

4 结 论

本文采用改进捕鱼算法求解柔性作业车间调度问题，将性能指标作为改进捕鱼算法的输入，获取最优的柔性作业车间调度结果，提高作业车间调度效率和精度。

参考文献

[1] 吴秀丽，张志强，杜彦华，等.改进细菌觅食算法求解柔性作业车间调度问题[J].计算机集成制造系统，2015，21（5）：1262?1270.

[2] 彭建刚，刘明周，张铭鑫，等.多目标柔性作业车间调度算法研究综述[J].中国机械工程，2014，25（23）：3244?3254.

[3] 程子安，童鹰，申丽娟，等.双种群混合遗传算法求解柔性作业车间调度问题[J].计算机工程与设计，2016，37（6）：1636?1642.

[4] 伍大清，郑建国，邵明，等.求解柔性作业车间调度的动态群智能优化算法[J].数学的实践与认识，2014，44（13）：48?57.

[5] 何春林.基于蚁群拥挤度跃阶调整的交互信息调度算法[J].科技通报，2015，31（8）：69?71.

[6] 项响琴，张沪寅.渔夫捕鱼优化算法的认知无线电频谱分配[J].计算机工程与应用，2014，50（6）：72?76.

[7] 李景洋，王勇，李春雷.自调整的捕鱼策略优化算法[J].计算机工程与科学，2014，36（5）：923?929.

[8] 周恺，纪志成.关于柔性作业车间调度问题的仿真研究[J].计算机仿真，2016，33（3）：282?287.

[8] 田娜，纪志成.改进量子粒子群求解多目标柔性作业车间调度[J].系统仿真学报，2015，27（12）：2948?2957.endprint