混合花朵授粉算法在作业车间调度中的应用

唐丽君, 彭石燕

(柳州铁道职业技术学院，柳州 545616)

作业车间调度问题(Job-shop Scheduling Problem,JSP)已被证明是一个NP-hard 问题，因此它不能在合理的计算时间内被精确地求解。由于其具有许多实际应用背景，对其研究一直是学者们关注的共同课题，研究如何有效求解JSP 具有重要的理论意义和实际意义。目前，求解JSP 的方法主要有两种，一种是精确方法，另一种是智能算法。精确方法如线性规划法、枚举法、分支定界法等是求解小规模JSP 的常用方法。近年来，人们开发了许多求解JSP 的近似方法。这些方法能在合理的时间内找到最优解或近似解，弥补了传统方法无法达到近似解的缺陷。智能算法主要包括：文献[1]提出一种改进并行遗传算法求解作业车间调度问题，种群规模较大，迭代次数较多；
文献[2]提出改进差分进化算法的作业车间调度优化策略，求解效果较差；
文献[3]提出一种改进型蝙蝠算法并用于作业车间调度问题，效果较好，但迭代次数较多；
文献[4–5]分别提出基于改进粒子群算法作业车间调度问题的优化和新型教与同伴学习粒子群算法求解作业车间调度问题，求解效果较差；
文献[6]提出模拟退火下布谷鸟算法求解车间作业调度问题，求解效果较差；
文献[7]提出求解作业车间调度问题的改进灰狼优化算法，求解效果较差；
文献[8]提出作业车间问题的杂草优化算法求解等方法，求解效果较差；
文献[9–11]利用关键路径移动较好地解决了作业车间调度问题；
文献[12]提出一种改进的带有序列映射机制的混合复杂进化算法求解作业车间调度问题，求解效果较好。

针对上述问题，本文提出一种花朵授粉算法和遗传算法的混合算法求解作业车间调度问题。通过26 个经典的基准算例仿真实验，并与近5 年的6 种算法比较，结果表明所提算法在求解作业车间调度问题具有一定优势。

JSP 可描述为：给定n个作业和m台机器，每个作业包含m道工序，需依次在m台机器上加工。加工过程满足约束条件：

1) 每个作业都有机器约束和时间约束；

2) 同一时刻一台机器只能加工一道工序；

3) 同一时刻一道工序只能在一台机器上加工；

4) 工序一旦开始加工则不能间断。

因此，JSP 的数学模型为

其中i,j= 1,2,··· ,n, h,k= 1,2,··· ,m。式(1)为优化目标，式(2)和式(3)分别表示每个工件各工序的操作顺序和每台机器上加工工件顺序的要求，式(4)为加工时间约束。Pik为加工时间，Cik为完工时间，T取值为相当大的正数，Xihk和Yijk为0-1 变量。

2.1 花朵授粉算法

花朵授粉算法(Flower Pollination Algorithm, FPA)是由Yang[13]提出，该算法模拟自然界自花授粉和异花授粉过程，设计算法之初是为了解决连续优化问题，然而针对JSP 离散问题不适用，必须重新编码及定义计算公式。

2.1.1 编码与解码

编码是算法设计中首当其冲的问题，其关系后续算法计算的定义。以3×3 JSP 问题为例，采用基于工序编码方式，其编码方式如表1 所示，花粉个体中每个值为作业号，每个作业出现的顺序为第几道工序，如第1 个3 则工序为1，其在第3 台机器上加工，加工时间为2，其余依次类推。

表1 基于工序编码方式

2.1.2 重新定义花朵全局搜索

在基本花朵授粉算法的全局搜索过程中，采用

2.1.3 重新定义花朵局部搜索

局部搜索采用交换、逆序和插入操作，如图1 所示。

图1 局部搜索的说明

2.2 遗传算法

2.2.1 选择操作

采用轮盘赌选择，同时保留种群最优解。

2.2.2 交叉操作

在JSP 问题中，采用文献[14]中的优先交叉方式，其示意图如图2 所示。从种群中任意选择两个父类：父类1 和父类2。将作业集合划分为2 个非空集合，保持父类中一个作业号不变，交换其他作业号，产生两个子类：子类1 和子类2。

图2 优先交叉方式

2.2.3 变异操作

变异操作为防止种群进化停滞不前的主要手段，采取任意两点间元素的逆序操作，如图1(b)所示。

2.3 混合算法(FPA-GA)步骤

步骤1 设置种群规模、转换概率和最大迭代次数等参数，导入机器约束和时间约束数据；

步骤2 使用表1 方式初始化种群，利用式(1)计算最优值及对应解；

步骤3 判断循环变量是否达到最大迭代次数，如果是输出最优值与最优解，否则对每个花粉个体判断随机数是否大于转换概率p，如果大于则利用式(8)进行全局搜索；
否则利用图1 所示进行局部搜索。重新评估此时的目标函数值，并与之前最优值进行比较，如果小于则替换最优值和最优解。然后再执行遗传算法的选择、优先交叉和变异操作并评估此时最优值和最优解，如果较之前优越则替换；

步骤4 循环变量加1，进入步骤3。

为测试FPA-GA 算法的有效性和优越性，我们选择标准的JSP 算例进行测试，其中包括23 个LA 问题和3 个FT 问题。CPU 为i7-9750H 2.60 GHz，内存8 G 的Windows 10平台上，采用Matlab 编程实现。算法的参数设置为：种群数目为10，最大迭代次数为200，交叉概率为0.85(经验值)，转换概率为0.8(为原FPA 论文中参数值)。本算法对26 个JSP 测试算例独立运行10 次的最优解与其他算法比较结果，如表2 所示，表中“–”表示算法未对该算例进行测试。算例FT10、LA16 和LA23 的调度甘特图，如图3 至图5 所示，图的横坐标表示时间，纵坐标表示机器号，图中“3-1”表示第3 个作业第1 道工序，其余依次类推。

图3 FT10 甘特图(Tm=967)

图5 LA23 甘特图(Tm=1 032)

由表2 中文献[15]的求解结果可知，仅求解了9 个算例，其中有6 个达到已知最优解；
而本文算法测试同样的9 个算例中有7 个达到已知最优解，其余2 个未达到已知最优解的算例LA17 和LA20 也优于它。由表2 中文献[8]的求解结果可知，仅求解了11 个算例，其中有8 个达到已知最优解；
而本文算法测试同样的11 个算例有10 个达到已知最优解，其余1 个未达到已知最优解的LA20 也优于它。由表2 中文献[3]的求解结果可知，共测试了23 个算例，其中有19 个达到已知最优解；
而本文算法测试同样的23 个算例有17 个达到已知最优解，其中算例LA18 和LA19 稍差，但算例FT10、FT20、LA16 和LA20 优于它。由表2 中文献[2]的求解结果可知，仅测试了10 个算例，其中有3 个达到已知最优解；
而本文算法测试同样的10 个算例中有9 个达到已知最优解，其中1 个未达到已知最优解的算例FT10 也优于它。由表2 中文献[5]的求解结果可知，仅测试了7 个算例，其中有3 个达到已知最优解；
而本文算法测试同样的7 个算例中有3 个达到已知最优解，其余4 个未达到已知最优解的算例FT10、FT20、LA16 和LA21 优于它。由表2 中文献[4]的求解结果可知，仅测试了7 个算例，其中有4 个达到已知最优解；
而本文算法测试同样的7 个算例中有4 个达到已知最优解，其余3 个未达到已知最优解的算例FT10、FT20 和LA16 优于它。由表2 中文献[4]的求解结果可知，本文算法求解的最优解仅算例LA23 较其优越，其他算例均较其差。

表2 不同算法求解结果对比

图4 LA16 甘特图(Tm=956)

本文针对最小化最大完工时间的作业车间调度问题，提出一种花朵授粉算法和遗传算法的混合算法，首先离散化基本花朵授粉算法，再融入遗传算法的选择、优先交叉和变异操作。通过26 个经典的基准算例仿真实验，并与近5 年的6 种算法比较，结果表明所提算法在求解作业车间调度问题具有一定优势。但离散花朵授粉算法的交换和逆序操作有时可能是无效，如何设计有效的局部操作是下一步研究方向。

猜你喜欢算例车间花朵100MW光伏车间自动化改造方案设计智能制造(2021年4期)2021-11-04死亡花朵文苑(2020年6期)2020-06-22近场脉冲地震下自复位中心支撑钢框架结构抗震性能评估苏州科技大学学报(工程技术版)(2019年4期)2020-01-04招工啦小学生学习指导(中年级)(2018年11期)2018-11-29降压节能调节下的主动配电网运行优化策略电子技术与软件工程(2018年10期)2018-07-16“扶贫车间”拔穷根农村农业农民·B版(2018年11期)2018-01-28我们依赖花朵散文诗(2017年17期)2017-08-15把农业搬进车间中国老区建设(2016年12期)2017-01-15基于振荡能量的低频振荡分析与振荡源定位（二）振荡源定位方法与算例中国学术期刊文摘(2016年2期)2016-02-13互补问题算例分析新乡学院学报(2015年6期)2015-11-06