基于果蝇算法的第二类装配线平衡问题

杜利珍 王运发 王 震 余联庆 李新宇

1.武汉纺织大学机械工程与自动化学院,武汉,430073 2.华中科技大学机械科学与工程学院，武汉，430074

0 引言

装配线平衡问题研究主要集中在三个方面：①给定生产节拍，优化最小工作站数；②给定最小工作站数，最小化生产节拍；③工作站数和生产节拍已定，平衡工作负荷[1]。近20年来，许多学者围绕智能算法进行了深入研究，将它们运用到装配线平衡问题的求解，取得了比较好的效果，其中，代表性的算法有遗传算法[2]、蚁群算法[3]、粒子群算法[4]等。遗传算法容易早熟，更新规则较复杂，涉及大量个体的计算，稳定性较差；蚁群算法收敛速度慢，易陷入局部最优；粒子群算法容易早熟收敛，局部寻优能力较差。综上所述，本文采用一种新的智能算法——果蝇算法来解决第二类装配线平衡问题。

在经典的果蝇算法中，种群中的果蝇基于气味搜索和视觉搜索,能够在一定的时间段中优化搜索空间[5]。近年来，果蝇算法较多地被运用在网络拍卖、物流服务、多维背包问题等问题优化中。

1 问题描述和数学模型

1.1 问题描述

本文研究第二类装配线平衡问题，即生产线的工作站数量已定，同时设定了几个生产约束条件。在此基础上，将有限的工序按照一种特定模式在各个不同的工作站内进行分配，最终目的是使生产节拍最小[6]，且工作负荷达到平衡。

整个生产过程中，生产节拍受到生产工艺、场地以及各种工具的限制，因此需要考虑不同工序的优先顺序等问题[7]。在满足生产约束条件之后，需要在整条装配线上对工作站进行生产工序的分配，使各工作站保持一个比较均衡的作业负荷，从而实现生产节拍的最小化。

1.2 数学模型

在追求第二类装配线平衡时，需要将所有工序分配到各工作站中，最终使生产节拍T达到最小，并保证整个生产线中的不同工作站的加权平均负荷能够达到均衡，即不同工位的平均单件作业时间的标准方差最小。

依据上述分析，得到本次研究问题的目标函数。

(1)装配线的最小节拍：

minZ1=T

(1)

(2)为了平衡装配线上各工作站的工作负荷，将负载标准差最小化设置为第二个优化目标，即有

(2)

式中，Tk为第k个工作站中所有作业的时间总和。

因此，本文研究的第二类装配线平衡问题的优化目标由生产节拍最小化和负载标准差最小化共同组成，W1、W2分别代表这两个优化目标的权重，从而将多目标优化问题转化为单目标问题。因此，建立总目标函数为

minZ=W1Z1+W2Z2

(3)

对上述问题进行研究时，作如下假设[8]：①作业i的加工时间都是稳定的；②所有的作业都被分配到工作站k中去；③一个作业只能够分配到一个工作站；④装配线不能够实现并行处理。上述条件转化成为的表达式为

(4)

Sx∩Sy=∅x≠y;x,y=1,2,…,N

(5)

∀i∈Sx,j∈Sy,若Pij=1，则x≤y

(6)

其中，Sk为在第k个工作站中所有作业元素的集合；i、j表示作业元素，所有作业元素集合为M，即i，j∈M；Pij表示作业之间的顺序关系。

式(4)表示所有的作业都被分配到工站；式(5)表示每一个作业只能够被分配到一个工作站；式(6)表述在工作站划分过程中，遵循作业优先顺序。

2 算法设计

2.1 基本原理及步骤

果蝇算法[9]是根据果蝇群体依据空气中的气味分子实现觅食过程开发的，算法流程如下：

(1)采用迭代方法对种群的大小进行初始化。

(2)开始时，果蝇个体的位置是随机的，然后向不同的方位搜索。

(3)计算果蝇个体之间的距离d，将果蝇个体的味道浓度判定值Fi设置为间距的倒数。

(4)把Fi代入适应度函数，计算得到果蝇个体的味道浓度。

(5)寻找种群中味道浓度最大的果蝇个体。

(6)将最佳味道浓度值sbest在XY坐标系中的坐标进行记录、保存。

(7)对种群进行迭代，重复步骤(2)～步骤(5)。迭代后，比较迭代前后的味道浓度，查看是否得到了优化，然后将目前的迭代值与最大值进行比较，若迭代值较小，则执行步骤(6)，否则，结束该算法。

果蝇算法的算法流程如图1所示。

图1 果蝇算法流程图Fig.1 Algorithm flow chart of fruit fly algorithm

2.2 编码与解码

编程设计时，首先对可行解的序列进行编码，将其转换成为浮点型向量。本次设计中，使用优先权重[10]的方法对程序进行编码、解码，在对果蝇个体的位置进行编码时，首先依据作业的优先关系图将浮点型向量转化成为可行序列。浮点型向量中的每一个元素为0、1中的随机数，其中，第j个元素表示的是该作业的优先权重，值越大，作业元素排序越靠前，解码算法流程如下：

(1)依据作业优先图，寻找出入度为0的作业，并将其组合成为集合V。

(2)通过V来寻找其中权重值最大的向量元素j。

(3)把寻找到的j放置到作业序列SP，并在作业顺序图中删除作业j，然后判断作业序列中作业个数是否为n，若作业个数达到n，则编码结束，否则，执行步骤(1)。

2.3 作业分配方案的生成

上述算法运行后能生成拓扑排序，但一个SP有很多个分配方案，因此在进行作业分配之前还需对方案进行分析、选择，利用最佳方案对作业进行分配。本次设计中使用的是KIM等[11]研发的方法，通过该方法对作业进行分配，经过不断的迭代，使所有的作业都能均匀地分配到工作站中，算法流程[12]如下：

(1)计算最小节拍Tbest=max(Tsum/N,maxTk)，其中，Tsum为所有作业时间的总和。

(2)得到生产节拍理论值Tbest后，在满足最小节拍的同时，将作业内容尽可能地分配到前N-1个工作站中，将没有分配的作业分配到最后的工作站。

(3)计算每一个工作站内各作业时间的总和。

(4)取Tw=max(T1，T2，…，TN)，若Tw>Tbest，则回到步骤(2)重新计算；若Tw

3 标杆案例

3.1 双产品装配时间测定

以某实验教学仪器装配线为例[13]，A、B产品按照2∶1的比例进行混合生产，对每道工序的作业时间进行了8次测量，取8次测量时间的平均值为产品每道工序的稳定作业时间，得到各工序的加工时间，如表1所示。

3.2 双产品优先关系图

A、B产品作业优先关系如图2所示。

参考文献[13]的自适应遗传算法求解得到的工作站划分，如表2所示。

表1 混合装配线各工序加工时间ti

图2 某公司A、B产品装配线作业优先关系图Fig.2 A、B product assembly line job priority diagram for a company

工作站N工序i时间(s)11、2、3、27324228、29、30、35、3632234、5、6、3130649、10、14、15、3331657、22、23312611、16、24、32、34、37、3832778、17、18、19、20、39310812、13、21、25、26315

因此可知，标杆案例中装配线的生产节拍为327 s，根据生产线平衡率计算公式可计算出装配线平衡率：

3.3 利用果蝇算法求解并仿真

(1)生产节拍的确定。该厂生产A、B产品的计划月产量分别为3 740、1 870(每月工作天数以22计)，每天有效工作时间为8 h。A、B两型产品以2∶1的比例混合装配，则理论生产节拍TT应为

(2)理论最小工作站数的确定。在满足作业元素先后关系和生产节拍的前提下，将所有生产作业元素分配到装配线的各工作站，并使所分配的工作站数为最小。理论最小工作站数可以直观评价所求优化方案是否达最优，其值为

N=(859×2+814)/339=7.5≈8

(3)编码及模型求解。本文采用基于权重编码方式，对A、B产品利用优先权重编码的过程进行分析，随机初始化作业单元的优先权重为X=(0.63，0.45，0.51，0.37，0.42，0.46，0.53，0.48，0.59，0.49，0.53，0.54，0.66，0.54，0.59，0.70，0.12，0.85，0.65，0.23，0.54，0.26，0.87，0.58，0.16，0.34，0.67，0.52，0.69，0.46，0.19，0.55，0.75，0.42，0.63，0.52，0.41，0.85，0.62)。

根据果蝇算法的求解步骤，用MATLAB进行仿真求解，算法对相关参数设置如下：最大迭代次数130，种群规模100。求解得到的最优果蝇个体为(14, 22, 27, 36, 15, 23, 35, 28, 29, 30, 32, 1, 9, 2, 33, 24, 16, 17, 20, 19, 10, 11, 3, 4, 6, 5, 18, 21, 25, 26, 7, 8, 12, 13, 37, 31, 34, 38, 39)，收敛曲线如图3所示。

图3 收敛曲线图Fig.3 Convergent curve of objective function

采用果蝇算法对工作站分配模型进行求解，其工作站作业内容如表3所示，目标函数值324 s，即优化后的生产节拍T=324 s，装配线各工作站内作业元素如表3所示。由表3可以计算出优化后装配线平衡率α为97.68%。

表3 果蝇算法优化后各工作站划分情况

标杆案例采用自适应遗传算法和本文采用果蝇算法求解的优化结果，如表4所示。

表4 GA与FOA求解结果对比表

由表4可知，本文采用果蝇算法的优化结果与标杆案例的优化结果相比，生产节拍缩短了3 s，装配线平衡率提升了0.9%，负载标准差降低了2.32 s。利用果蝇算法求解的工站工时趋于平稳。

4 结语

本论文针对第二类装配线平衡问题，综合考虑生产节拍和各工作站平均负荷，建立双目标优化模型，并采用果蝇优化算法求解，通过对标杆案例进行分析验证，果蝇算法在获取全局最优解的能力上非常强，有效解决了在计算过程中陷入局部最优、更新规则复杂、计算量大等问题，验证表明本文提出的优化模型和果蝇算法对于解决第二类装配线平衡问题具有有效性和可行性。