0 引言

混合流水车间调度问题(hybrid flow-shop scheduling problem, HFSP)[1]具有现实的制造业背景，涉及多设备、多阶段、多工件的加工，属于NP-hard问题。传统HFSP可以分为相同并行机[2]、均匀并行机、不相关并行机调度问题[3]。

求解HFSP常用遍历式算法和启发式算法。遍历式算法能够得到该类问题的精确解，但受限于计算速度，该算法只用于小规模问题的求解[4]，而不适用于复杂大系统问题。近年来，启发式算法的研究不断取得突破，遗传算法[5]、蚁群算法[6]、模拟退火算法等相继被提出并用于求解HFSP，但运算速度还是差强人意，因此人工鱼群算法[7]、蜂群算法[8]、二元分布估计算法[9]等一些搜索速度更快、迭代过程更简单且有效的算法被提出。启发式算法能够在短时间内给出大规模问题的解，但这个解在通常情况下是满意解而非精确解。

编码与解码是将模型问题融入算法的一个关键过程，编码决定着输入，解码决定着输出。PAN等[10]提出基于自适应搜索策略的离散人工蜂群算法；王凌等[11]提出基于排列的编码和解码的方法，用人工蜂群算法很好地实现了不相关并行机HFSP的求解。

相较于上述算法，果蝇优化算法[12]拥有更好的自适应和自组织能力，具有迭代过程简单、全局收敛性强、算法执行时间短的特点。笔者在果蝇优化算法的更新规则上加入权重系数，对权重的编码方式进行改进，使得算法的随机搜索能力更强，编码和种群迭代过程更加简单。

1 不相关并行机混合流水车间调度

1.1 问题描述

不相关并行机HFSP的假设如下：①n个工件在流水线上进行S个阶段的加工；②每个阶段至少有1台机器；③至少有一个阶段存在并行机；④任意一个阶段上的设备都能完成工件的一个工序；⑤工件需要在每个阶段完成一道工序；⑥各机器的加工时间不完全相同，已知n个工件各道工序在各设备上的加工时间，要求确定n个工件的加工顺序以及每一阶段上设备的分配情况，使得某一调度指标最小。混合流水车间调度模型如图1所示。

1.2 数学模型

对于不相关并行机HFSP有：工件的编号为i(i=1，2，…，n)；n个工件需要在S个阶段上加工；ti,j,k为工件i在第j(j=1，2，…，S)个阶段的第k台设备的加工时间；mj为第j个阶段的设备数量；si,j,k为第个i工件在第j个阶段的第k台设备的开始加工时间；Pi,j,k为第i个工件在第j个阶段第k台设备上的加工完成时间；xi,α为0-1变量，工件i被排在第α个位置等待加工时，xi,α=1；Ci为工件Ji的加工完成时间，所有工件加工完成所需的最大完成时间为各工件加工完成时间的最大值，即最大完工时间Cmax=max{C1，C2，…，Cn}；L为足够大的数[13],具体的数字模型如下：

min Cmax

(1)

(2)

(3)

(4)

Pi,j,k=si,j,k+ti,j,k

(5)

j=1,2,…,s

Pi,β,k≤si,β+1,k2

(6)

k=1,2,…,mβ β=1,2,…,S-1 k2=1,2,…,mβ+1

(7)

γ=1,2,…,n-1 K=1,2,…,m1

(8)

l1≤l2 l1,l2=1,2,…,n

上述公式的含义如下：式(1)为目标函数；式(2)、式(3)保证优先级与工件对应关系的唯一性；式(4)保证工件在任意阶段只能在1台机器上加工；式(5)表示同一阶段上工件加工的开始时间和完成时间的关系；式(6)表示工件加工的先后关系；式(7)表示第一阶段排序靠前的工件先被加工；式(8)表示如果工件被分配在同一阶段的同一设备，排序靠前的工件先加工。不处于同一位置的工件在相同阶段的相同设备上加工时，足够大的数L保证式(8)恒成立。

2 果蝇优化算法

果蝇优化算法利用果蝇觅食的原理不断进行种群的迭代，最终找到所求问题的最优解。如图2所示，果蝇优化算法基本步骤如下[14]：

(1)参数初始化。对中心果蝇位置、种群规模、算法迭代次数进行初始化。

(2)嗅觉搜索。在中心果蝇个体的周围产生其他果蝇个体，计算种群每个果蝇个体的适应度，用于评价每个果蝇个体。

(3)视觉搜索。选择适应度最大的果蝇作为下一次迭代的种群中心，利用种群更新公式进行新一代种群更新。

(4)判断是否满足迭代终止条件。若满足则结束迭代，输出最优结果；否则转至步骤(2)。

3 果蝇优化算法的求解

3.1 编码

本文采用基于权重的编码方式，将离散系统的求解转化成连续系统的求解。工件的加工顺序根据权重的大小依次排列，每种排列表示一个可行解，例如权重(0.20，0.18，0.36，0.25，0.64，0.57)对应的工件排列顺序为(5，6，3，4，1，2)，该排序表示工件5先加工，其次是工件6，最后是工件2。这种编码方式能够便于种群的更新操作。

3.2 解码

解码采用基于排列的方式[15]，主要分为工件的排序和设备的选择。工件排序的规则：第一阶段，按照初始的工件排序依次进行加工，后面阶段的工件按照前一阶段加工完成时间先后顺序进行加工；多个工件的加工完成时间相同时，随机选择其中一个工件进行加工。设备的选择规则：根据工件i在阶段j上的加工顺序，判断每个工件在第k台设备上的最早允许加工时间，即设备k释放时间Pk与工件i在上一阶段的完成时间Ri,j-1的较大者max(Pk, Ri,j-1)；然后对工件i根据公式max(Pk, Ri,j-1)+ti，j，k选择值小的机器k作为工件i的加工设备。重复以上步骤直到所有工件完成S个阶段的加工。

3.3 种群初始化

初始化种群规模psize，采用产生随机数的方式来产生初始解Qz，根据Qz对工件的加工进行排序。矩阵Qz的元素是0～1之间的随机数，可保证初始解的随机性。

3.4 嗅觉操作

通过产生随机数的方式产生与初始解相同维度的随机数矩阵Ly，则果蝇种群X(i)=Qz+Ly，对种群中的每一个果蝇个体X(i)以最大完成时间最小作为评价指标进行计算。单目标适应度函数为

F(x)=min Cmax

(9)

果蝇优化算法种群初始化及嗅觉操作伪代码如下。

输入：工件在各机器上的加工时间表

输出：最优的排序

Gj=[1,2,3,4,5,6];

∥工件排序

Sizepop=5；

∥初始化种群个数

K=6；

∥种群个体维度

Qz=rand(1，k)；

∥随机初始种群中心权重

FOR i=1：sizepop；

X(i)=B1Qz+B2normrnd；

∥种群权重

END FOR

FOR i=1：sizepop

a=[Gj’,X(i,:)]；

∥工件顺序按照权重重排

F(i)=f(a);

∥计算种群个体适应度

Besta=arg min(F(i));

∥选择适应值最小的排序

END FOR

3.5 视觉操作

选取嗅觉操作中的最优果蝇个体作为下一个种群的中心果蝇，其他果蝇向该果蝇移动，从而产生新的种群。种群的更新方式与嗅觉操作方式相同，改进果蝇优化算法更新规则为

X(i)= B1Qbest+ B2Nr

(10)

式中，B1表示果蝇中心对果蝇种群的影响程度；B2表示种群领域随机搜索能力对种群的影响程度；X(i)(i=1，2，…，psize)为果蝇个体权重矩阵，几何上表示果蝇个体位置，下同； Qbest为中心果蝇权重矩阵；Nr为随机权重矩阵。

与原始算法更新公式X(i)=Qbest+Nr相比，改进后的更新公式增加了变量B1、B2，提高了算法的随机搜索能力。

4 仿真测试和比较

标杆实例1[16] 12个工件的加工工序为车、刨、磨，现有3台车床、2台刨床、4台磨床，每台机床的加工能力不同，工件在设备M1～M9上的加工时间如表1所示。

标杆实例2[17] 某工厂需要加工6个工件，每个工件都需要经过铣、车、磨三道工序。现有3台铣床、2台车床、3台磨床，设备用M1～M8表示。工件的加工时间如表2所示。

标杆实例3[18] 某钢铁生产包含炼钢、精炼、连钢、轧制四个步骤，完成这些工序需要3台炼钢炉、3台精炼炉、2台铸机、2台轧机，用M1～M10表示。工件在设备上的加工时间如表3所示。

4.1 参数讨论

对该果蝇优化算法的种群规模psize、中心果蝇重要程度参数B1、随机搜索能力参数B2进行测试。将评价次数3 000作为每种参数组合运行的终止条件，对每一种参数组合独立运行20次，程序使用MATLAB编程，在4G内存、3.20 GHz CPU上运行，得到最大完成时间的平均值和标准差，如表4所示。

统计实例1在不同参数组合条件下运行时的均值和极值，如图3所示。以标杆案例1为例，对算法参数进行分析可知， B1<B2时，算法寻优能力更强，且增强了算法的全局搜索能力。B1=B2=1表示原始果蝇优化算法的种群迭代规则，由表4可以看出，B1、B2对算法寻优能力产生了一定的影响。综合以上实验数据及分析，当B1=0.2，B2=0.8，psize=10时，算法既找到最优解，又能稳定运行。

对实例2在2 000次评价，实例3在6 000次评价的条件下设计同样的实验，得到3种规模的最优参数组合，如表5所示。

4.2 实验结果对比

为了进一步说明果蝇优化算法(fruit fly optimization algorithm，FOA)的优越性，将该算法与遗传算法(GA)[16]和差分进化(differential evolution，DE)算法[18]进行对比。将评价次数10 000作为算法运行终止条件，得到的结果如表6所示。文献[16]给出了一种改进的编码方式，这种编码方式能够保证个体编码的合法性。文献[18]通过特殊的编码方案，结合基于DE算法的进化搜索和局部搜索，增强探索和开发能力。

由表6可以看出，GA不够稳定，未能找到最优解24，DE算法能8次找到最优解24，而FOA能够100%找到最优解24，因此在相同的评价次数中，FOA的稳定性更好，其最优解甘特图为图4，图中方框内的数据为工件序号，收敛曲线如图5所示。

实例2的实验结果对比如表7所示，将FOA与PBIL[17](population-based incremental learning)、EDA[17](estimation of distribution algorithm)进行对比。将评价次数3 000作为算法运行终止条件。在相同评价次数中，FOA能100%找到最优解13.5，其他2个算法没能找到最优解，从而验证了算法的有效性和鲁棒性。实例3的实验结果对比如表8所示，将评价次数18 000作为算法运行终止条件，10次独立运行中，FOA能6次找到最优解297，且结果优于DE算法的结果[19]，再一次证明了算法了有效性。

5 结论

在原始果蝇优化算法的基础上，增加了中心果蝇影响程度参数B1和领域搜索能力参数B2，通过实验考察了2个参数对算法的影响。在相同的实验条件下，改进果蝇优化算法更容易找到最优解，且不容易陷入局部最优。与GA、EDA、DE算法进行对比，改进果蝇优化算法表现出了极好的随机搜索能力和鲁棒性。

参考文献：

[1] CASTRO P M, MOSTAFAEI H. Product-centric Continuous-time Formulation for Pipeline Scheduling[J]. Computers & Chemical Engineering, 2017, 104(2): 283-295.

[2] 何倩男. 面向离散生产线的相同并行机混合流水车间调度问题研究[D]. 天津：天津理工大学, 2017.

HE Qiannan. Research on the Same Parallel Machine Hybrid Flow Shop Scheduling Problem for Discrete Production Lines[D]. Tianjin: Tianjin University of Technology, 2017.

[3] 韩忠华, 董晓婷, 史海波,等. 改进DE算法求解混合流水车间负荷平衡问题[J].计算机集成制造系统, 2016, 22(2): 547-557.

HAN Zhonghua, DONG Xiaoting, SHI Haibo, et al. Improved DE Algorithm for Load Balancing in Hybrid Flow Shops[J]. Computer Integrated Manufacturing Systems, 2016, 22(2): 547-557.

[4] 明廷堂.二叉树的遍历算法[J]. 电脑编程技巧与维护，2014(5):16-22.

MING Tingtang. Binary Tree Traversal Algorithm[J]. Computer Programming Techniques and Maintenance, 2014(5):16-22.

[5] 姚丽丽, 史海波, 刘昶,等. 基于遗传算法的混合流水线车间调度多目标求解[J]. 计算机应用研究, 2011, 28(9): 3265-3266.

YAO Lili, SHI Haibo, LIU Chang, et al. Multi-objective Solution of Hybrid Assembly Shop Scheduling Based on Genetic Algorithm[J]. Journal of Computer Applications, 2011, 28(9): 3265-3266.

[6] 黄华, 肖菁, 张军. 改进并行蚁群算法求解置换流水线调度问题[J]. 计算机工程与设计, 2010, 31(3): 583-585.

HUANG Hua, XIAO Jing, ZHANG Jun. Improved Parallel Ant Colony Algorithm for Permutation Pipeline Scheduling Problem[J]. Computer Engineering and Design, 2010, 31(3): 583-585.

[7] 赵敏, 殷欢, 孙棣华,等. 基于改进人工鱼群算法的柔性作业车间调度[J]. 中国机械工程, 2016, 27(8): 1059-1065.

ZHAO Min, YIN Huan, SUN Dihua, et al. Flexible Job Shop Scheduling Based on Improved Artificial Fish Swarm Algorithm[J]. China Mechanical Engineering, 2016, 27(8): 1059-1065.

[8] 桑红燕,高亮,李新宇.求解批量流水线调度问题的离散蜂群算法[J].中国机械工程, 2011, 22(18): 2195-2202.

SANG Hongyan, GAO Liang, LI Xinyu. A Discrete Bee Colony Algorithm for Solving Batch Pipeline Scheduling Problem[J]. China Mechanical Engineering, 2011, 22(18): 2195-2202.

[9] 裴小兵, 赵衡. 基于二元分布估计算法的置换流水车间调度方法[J]. 中国机械工程, 2017, 28(22): 2752-2755.

PEI Xiaobing, ZHAO Heng. Displacement Flow Shop Scheduling Method Based on Binary Distribution Estimation Algorithm[J]. China Mechanical Engineering, 2017, 28(22): 2752-2755.

[10] PAN Q K, TASGETIREN M F, SUGANTHAN P N, et al. A Discrete Artificial Bee Colony Algorithm for the Lotstreaming Flow Shop Scheduling Problem[J]. Information Sciences, 2011,181(12): 2455-2468.

[11] 王凌, 周刚, 许烨,等. 求解不相关并行机混合流水线调度问题的人工蜂群算法[J].控制理论与应用, 2012, 29(12): 1551-1557.

WANG Ling, ZHOU Gang, XU Ye, et al. Artificial Bee Colony Algorithm for Solving Hybrid Pipeline Scheduling Problem of Uncorrelated Parallel Machines[J]. Control Theory & Applications, 2012, 29(12): 1551-1557 .

[12] 王凌, 郑晓龙. 果蝇优化算法研究进展[J].控制理论与应用, 2017, 34(5):557-563.

WANG Ling, ZHENG Xiaolong. Research Progress of Fruit Fly Optimization Algorithm[J]. Control Theory & Applications, 2017, 34(5): 557-563.

[13] 胡能发. 演化式果蝇优化算法及其应用研究[J].计算机技术与发展, 2013,23(7):131-133.

HU Nengfa. Evolutionary Fruit Algorithm and Its Application[J]. Computer Technology and Development, 2013, 23(7):131-133.

[14] 吴楚格, 王凌, 郑晓龙. 求解不相关并行机调度的一种自适应分布估计算法[J]. 控制与决策, 2016, 31(12): 2177-2182.

WU Chuge, WANG Ling, ZHENG Xiaolong. An Adaptive Estimation Algorithm for Solving Uncorrelated Parallel Machine Scheduling[J]. Control and Decision, 2016, 31(12): 2177-2182.

[15] WANG Ling. Differential Evolution Algorithm for Hybrid Flow-shop Scheduling Problems[J].System Engineering and Electronics, 2011, 22(5):794-798.

[16] 周辉仁, 唐万生, 魏颖辉. 柔性Flow-shop调度的遗传算法优化[J]. 计算机工程与应用, 2009, 45(30):224-226.

ZHOU Huiren, TANG Wansheng, WEI Yinghui. Genetic Algorithm Optimization for Flexible Flow-shop Scheduling[J]. Computer Engineering and Applications,2009, 45(30): 224-226.

[17] 张凤超. 改进的分布估计算法求解混合流水车间调度问题研究[J]. 软件导刊, 2014(8):23-26.

ZHANG Fengchao. Improved Distribution Estimation Algorithm for Solving Mixed-flow Shop Scheduling Problem[J]. Software Guide, 2014(8):23-26.

[18] 崔建双, 李铁克, 张文新. 混合流水车间调度模型及其遗传算法[J]. 工程科学学报, 2005, 27(5): 623-626.

CUI Jianshuang, LI Tieke, ZHANG Wenxin. Mixed Flow Shop Scheduling Model and Its Genetic Algorithm[J]. Journal of Engineering Science, 2005, 27(5): 623-626.

[19] XU Y, WANG L. Differential Evolution Algorithm for Hybrid Flow-shop Scheduling Problems[J]. Journal of Systems Engineering and Electronics, 2011, 22(5): 794-798.

Fruit Fly Optimization Algorithm for Solving Hybrid Flow-shop Scheduling Problems

DU Lizhen1 WANG Zhen1 KE Shanfu1 XIONG Zixue1 LI Xinyu2

1.School of Mechanical Engineering and Automation, Wuhan Textile University, Wuhan, 430073 2.School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan, 430074

Abstract:To deal with hybrid flow-shop scheduling problems with unrelated parallel machines, weighted encoding was used for coding operations, according to the characteristics of population update method of fruit fly optimization algorithm. Weighting coefficients were added to improve random search ability of the algorithm. The algorithm parameters were analyzed, and the optimal parameter combination was obtained. Benchmarking examples were used for simulation verification, and the effectiveness of the fruit fly optimization algorithm was verified by comparison with classical algorithms.

Key words: uncorrelated parallel machine; hybrid flow-shop scheduling problem; fruit fly optimization algorithm; weight coefficient

中图分类号：T9

DOI：10.3969/j.issn.1004-132X.2019.12.015 开放科学(资源服务)标识码(OSID)：

收稿日期：2018-08-27

基金项目：国家自然科学基金资助项目(51375004)；湖北省数字化纺织装备重点实验室2017年度开放基金资助项目(DTL2017010)

(编辑 张 洋)

作者简介：杜利珍，女，1975年生，副教授。研究方向为智能调度、系统建模仿真与优化。发表论文30余篇。E-mail:dlzay@wtu.edu.cn