附带翻转工位双边装配线蚁群算法优化设计

朱小平，张则强

1.浙江交通职业技术学院机电学院，杭州 311112

2.西南交通大学机械工程学院，成都 610031

附带翻转工位双边装配线蚁群算法优化设计

朱小平1，张则强2

1.浙江交通职业技术学院机电学院，杭州 311112

2.西南交通大学机械工程学院，成都 610031

双边装配线应用广泛，翻转工位操作能有效降低部分零件装配难度与操作风险，但增加了设计难度。基于此，研究了附带翻转工位操作的挖掘机底盘双边装配线规划设计问题，针对该问题提出了一种改进蚁群算法求解。给出了问题求解的启发式任务分配规则，提出可采用启发式任务选择规则以提高算法收敛速率。进而分析某型挖掘机底盘装配线得出先后约束关系图，将问题抽象为双边装配线优化设计问题。随后，采用两种蚁群算法进行附带翻转工位的装配线优化，分析比较了两种算法因结构差异对优化结果所造成的影响。

蚁群算法；双边装配线；翻转工位；优化；群智能

1 引言

在大型机械装备中，由于多个部件可在两侧同时装配，可有效缩短装配时间，因此对如何有效组织和设计双边装配线工位提出了要求，双边装配线平衡问题（Two-sided Assembly Lines Balancing Problem，TALBP）也随之产生。双边装配线与单边装配线相比具有很多优点：如可压缩装配线长度、减少配件运输距离与工人移动成本、降低工位布置成本等[1-2]，因此被广泛应用于汽车工业、工程机械、武器装备等中大型产品的装配生产过程，具有显著的经济效益。履带挖掘机的底盘对称规则，行走机构、控制、制动系统对称分布两侧，非常适合采用双边装配线进行组装。

双边装配线优点众多，但由于其设计与布局形式较单边装配线复杂，具体表现在：TALBP装配线布局需考虑装配任务的左右操作方位；更需要注意不同侧装配任务之间的先后约束关系。由于双边装配线的应用前景和设计难度，近年来受到了企业界和学术界的关注[3-4]。而装配线平衡问题作为NP-Hard型难题[5]，难以在合理的时间内精确求解，因此常采用启发式算法求解。目前国际上对标准的TALBP问题，已经有Kim等[6]提出的一种遗传算法；吴尔飞等[7]提出的一种基于任务序列的改进遗传算法；Özcan和Toklu[8]提出的禁忌搜索算法等；且近期有逐渐向多目标优化方向发展趋势[9-10]。而对于贴近实际应用的TALBP问题，如附带区域约束的TALBP，由于更加复杂，目前能提供的文献较少[5，11-12]。由模仿蚁群觅食行为发展起来的蚁群算法（Ant Colony Optimization，ACO），在求解简单装配线平衡问题表现出了优异性能[13-14]，且已成功应用至含区域约束问题的TALBP[5]。

前述所涉及的问题均集中于研究常规双边装配线平衡问题，而实际装配线存在着一类特殊装配约束。以某挖掘机底盘装配线为例，该装配线存在某些特殊装配任务，为方便装配作业需翻转整个工作台；因此，要在此任务装配前增加翻转作业时间，而翻转作业过程需中断装配作业，增加判别翻转时前序装配任务是否完毕，同时需增加判别后续分配任务是否为非特殊型任务，是否需要再次翻转作业。对于此问题，求解关键在于将此特殊型装配任务合理聚集，减少翻转作业时间。而当前，对于包含此类特殊装配任务的TALBP问题，尚未有相关求解算法。基于此，本文开展该问题研究。

针对该新问题，结合TALBP问题特征，提出了一种融合启发式选择和分配规则的蚁群算法，该算法借鉴文献[4]的信息素混合搜索机制、信息素积累与耗散规则；针对所研究的特殊问题，提出了启发式任务分配规则解决任务分配问题；为提高算法效率，提出了启发式任务选择规则合并特殊操作任务。最后将算法应用于某液压驱动挖掘机底盘的装配线设计中，说明算法增加改进措施有效性。

2 附带翻转工位双边装配线平衡问题

2.1 双边装配线与特殊装配任务

双边装配线两侧可同时进行装配作业。如图1所示：两侧并行运行不同装配任务，一对工位处于同一位置的称为成对工位，如工位1和2都属于位置1，且互为伴随工位。任务按操作方位偏向分三类：左型（L）、右型（R）、无偏向型（E，两边皆可），而对于本文研究的特殊任务，操作前需翻转工作台，因此需增加操作翻转属性（F，正面装配为0，反面装配为1）。因此求解双边装配线问题需综合考虑任务间的先后约束、任务操作方位约束和特殊操作约束，图1中任务2的开始时间为3，任务2和任务1之间的等待时间为翻转工位时间，任务3前面的等待时间为由于任务先后关系约束导致的等待时间。图2树状图标识了任务之间的操作先后顺序，并同时标出了操作方位、特殊操作约束。

图1 双边装配线甘特图示例

图2 先后约束关系图

2.2 问题的数学模型

带翻转工位双边装配线第一类平衡问题定义：限定生产节拍，任务分配需同时满足先后约束、操作方位和翻转操作约束，将所有任务均衡分配到双边工位，并使成对工位数（位置数）最小，简称TALBP-F-I（F：带翻转操作任务），模型如下：

模型变量：I为包含所有任务的集合，I={1，2，…，N}s；ID为按任务操作方位分割I，D=L（左）、R（右）或E（两边）；IF为按特殊操作分割I，D=0（正面）、1（反面）；Ij、Ij′为分配到工位j和j′上的任务集；Tj、DLj为工位j的累计操作时间与累计延迟时间，j′表示伴随工位；P(i)为任务i的前序任务集；AS为此集合中任意任务i的P(i)为空；W为未分配到位置中的任务集合；n为装配线长度，即开启位置数量；NS为开启的工位数量；tis、tie分别表示任务i开始与结束时间；xiuk：若任务i已分配于位置u，操作方位k也已确定为L或R，则xiuk=1，其余xiuk=0。

式（1）表示任务先后关系约束；式（2）表示所有任务必须且只能在一个位置中出现一次，且只能分配到左或右工位；式（3）Tj、Tj′分别为位置u中工位j与j′的累计操作时间；式（4）表示任意位置的工位时间和必须小于等于节拍；式（5）表示特殊任务约束，即正常操作任务不能和特殊操作任务同时操作；式（6）目标为求最小装配线长度。

3 TALBP-F-I的改进蚁群算法

3.1 TALBP-F-I蚁群算法简介

在TALBP-F-I问题解的构造过程中，需按任务间的先后约束关系依次选择任务置于生产线的相应工位，与蚂蚁在向目标搜索过程中选择可选路径相似。因此蚁群算法的机理与装配线平衡问题求解机理相似。本文蚁群算法先运用成熟的综合信息素搜索规则得到待分配任务，随之采用启发式任务分配规则完成任务操作方位判别、任务前序附加操作判别（是否需翻转工位）并根据前序任务的结束时间和当前双边工位任务完成时间决定此任务的开始和结束时间。完成单个任务分配后更新局部信息素，完成单个解的构造后更新全局信息素。本文借鉴了文献[4]的综合信息素搜索和信息素更新规则。图3为蚁群算法流程图。

图3 蚁群算法流程图

可供分配的任务集合AS：考虑先后关系约束，只有前序任务集为空或前序任务均已分配完毕的任务。改进的信息素搜索规则增加一个随机搜索以脱离陷入局部最优，综合考虑了利用信息素搜索和随机搜索两种规则，从集合AS中选择任务，是一种混合搜索策略[4]。依次选择任务排入工位，直到所有任务分配完毕，整个过程构成图4任务链。即2.1节图2约束关系的一个任务排列序列，任务序号、操作方位、特殊操作信息集成于一格。

图4 一个完整的任务排列序列

3.2 启发式任务分配规则

将蚁群搜索选择的一个任务分配到具体工位，为实现特殊型任务的分配，本文提出改进的分配规则，规则的整体框架如图5。

图5 启发式分配规则整体框架

规则1为确认位置双工位中：（1）此任务所有前序任务最晚结束时间；（2）此工位当前结束时间；（3）伴随工位末端任务开始与结束时间；（4）确定任务序列前一任务分配时是否引起翻转操作，并记录此工位的伴随工位。若项点4成立且本工位与项点4翻转工位相同，此任务开始时间为项点3中任务结束时间；若项点4成立且本工位与项点4伴随工位相同，则任务开始时间为项点3任务开始时间加翻转操作时间；否则，任务开始时间为1和2中较大者。

规则2为确认位置双工位中：（1）此任务所有前序任务中最晚结束时间；（2）此操作方位工位末端任务结束时间。此任务开始时间为1和2中较大者。

规则3确认：（1）双边工位中此任务所有前序任务的最晚结束时间；（2）双工位末端任务开始与结束时间；（3）确定任务序列前一任务分配时是否引起翻转操作，并记录此工位的伴随工位。分为如下几种情形：①项点1时间均小于等于项点2中结束时间：若项点3不成立，则任务开始时间为项点2中较小时间，否则为项点2中翻转任务开始时间加上翻转操作时间；②项点1时间介于项点2两项结束时间之间（不含相等），若项点3不成立，则任务开始时间为项点1时间，否则为项点2中翻转任务开始时间加上翻转操作时间；③项点1时间等于项点2中最晚结束时间：则任务开始时间项点1时间，此任务可随机选择一边放入。

规则4确认：（1）双工位末端任务结束时间。任务开始时间为项点1中较大时间，若项点1中两结束时间相等，可随机选择一边。规则5确认此任务是否满足节拍约束，若满足约束则将任务放入对应工位，重新生成AS；否则将其从AS中剔除。规则6确认此任务是否满足节拍约束，若满足约束则将任务放入对应工位，并在此工位标注翻转操作标示，重新生成AS；否则将其从AS中剔除。

3.3 启发式任务选择规则

为提高算法求解的速度，考虑将特殊操作任务合理聚集，使得特殊任务在集合AS中集中选择分配，增加了以下规则：

（1）若集合AS中同时包含特殊任务属性0和1的任务，则将属性与当前工位状态相反的任务放入暂时禁忌集合，进入步骤（3）；（2）若集合AS中仅含特殊任务属性0或仅包含1的任务，进入步骤（3）；（3）采用文献[4]的混合搜索机制选择任务。

4 挖掘机底盘装配关系分析

某型挖掘机底盘装配线特点：（1）底盘装配可按照双边装配线形式布局，两边可同时进行装配任务；（2）针对翻转操作需配备底盘翻转设备；（3）为提高装配效率，采用助力机械手臂、自动扭矩拧紧机、抓取机等设备；（4）所有喷漆配件均喷漆后装配，对于装配过程中对漆层磕碰、划伤，在装配线末端设置补漆工序。

生产线的年产量规划为11 500台，按单班工作制规划，每班工作8 h计，全年工作300 d，则生产线节拍时间需小于13 min。表1为任务操作信息汇总表，包含任务时间t，操作方位d，是否为特殊型任务f。图6为任务之间先后约束关系图。

5 装配线优化设计实例

本文采用MATLAB7.8对本文算法编写了实验程序，称同时采用了两种启发式方法的蚁群算法为改进蚁群算法（pro-ACO），称仅采用启发式任务分配规则的为蚁群算法（ACO）。设定的实验条件为蚂蚁数20、迭代次数10，参数设置：α=1，β=2，ρ1=0.1，ρ2=0.9，r=0.9。在Intel core i3-2120计算平台上，进行测试，所有问题均在不到6 s内即求得较优解。将节拍时间分为8 min、9 min、10 min、11 min、12 min五种情况，所得的分配结果见表2。表2中，m1代表计算得到的开启位置数量，n1代表运算10次的平均收敛代数；LB代表计算得到的最优平衡率（注：表2中，计算平衡率时，将翻转操作时间也累计为装配时间，因此针对开启相同位置数的结果，平衡率越低，则特殊操作时间越少，即所需投入底盘翻转设备也越少，更具优越性）。分析表2数据可知，由于采用了更多的约束条件，所以使得算法在每次选择时剔除了更多选择，提高了改进蚁群算法的迭代收敛性。而未采用此规则的蚁群算法之探索能力更好（相同位置数目下能得出更优的平衡方案），因算法每次可选择任务更多，因此也增加了算法搜索时间。节拍为660的分配方案见表3。

表1 任务操作时间及操作方位

图6 任务优先关系图

表2 五种节拍时间优化结果对比

表3为当节拍时间为660时所得的优化结果，此优化结果的平衡率为83.26%。

6 结束语

挖掘机底盘是典型的可两侧同时装配的产品，同时为方便装配作业而附加翻转工位操作，但以往双边装配线规划设计算法未将需翻转工位任务纳入研究范围。翻转工位操作增加了双边装配线规划设计的难度，在原有双边装配线平衡问题工位内部任务先后约束、双边工位任务交叉影响、任务操作方位选择等基础约束条件上，附加任务的翻转操作判断，因此本文作了以下工作：（1）提出了启发式任务分配规则解决需翻转工位任务的分配问题。（2）为提高算法求解速度，提出了启发式任务选择规则。（3）将两种规则融入蚁群算法，并将所提算法应用至某挖掘机底盘总装线中，通过对比分析两种蚁群算法优化结果，取得了良好成效。

表3 双边装配线实例优化结果

[1]Lee T O，Kim Y，Kim Y K.Two-sided assembly line balancing to maximize work relatedness and slackness[J].Computers and Industrial Engineering，2001，40（3）：273-292.

[2]Özcan U，Toklu B.Multiple-criteria decision-making in twosided assembly line balancing：a goal programming anda fuzzy goal programming models[J].Computers&Operations Research，2009，36（6）：1955-1965.

[3]童科娜，徐克林，郑永前.基于结构式译码遗传算法平衡多人共站装配线[J].计算机工程与应用，2013，49（6）：267-270.

[4]张则强，胡俊逸，程文明.求解带区域约束的双边装配线平衡问题的一种改进蚁群算法[J].现代制造工程，2013（4）：19-25.

[5]Scholl A，Becker C.State-of-the-art exact and heuristic solution procedures for simple assembly line balancing[J]. European Journal of Operational Research，2006，168（3）：666-693.

[6]Kim Y K，Song W S，Kim J H.A mathematical model and a genetic algorithm for two-sided assembly line balancing[J].Computers&Operations Research，2009，36（3）：853-865.

[7]吴尔飞，金烨，续爱民，等.基于改进遗传算法的双边装配线平衡[J].计算机集成制造系统，2007，13（2）：268-274.

[8]ÖZcan U，Toklu B.A tabu search algorithm for two-sided assembly line balancing[J].The International Journal of Advanced Manufacturing Technology，2009，43（7/8）：822-829.

[9]Roshani A，Fattahi P，Roshani A，et al.Cost-oriented twosided assembly line balancing problem：a simulated annealing approach[J].International Journal of Computer Integrated Manufacturing，2012，25（8）：689-715.

[10]Chutima P，Chimklai P.Multi-objective two-sided mixedmodel assembly line balancing using particle swarm optimisation with negative knowledge[J].Computersand Industrial Engineering，2012，62（1）：39-55.

[11]Tapkan P，Ozbakir L，Baykasoglu A.Modeling and solving constrained two-sided assembly line balancing problem via bee algorithms[J].Applied Soft Computing，2012，12（11）：3343-3355.

[12]Tapkan P，Ozbakir L，Baykasoglu A.Bees algorithm for constrained fuzzy multi-objective two-sided assembly line balancing problem[J].Optimization Letters，2012，6（6）：1039-1049.

[13]张则强，程文明，钟斌，等.求解装配线平衡问题的一种改进蚁群算法[J].计算机集成制造系统，2007，13（8）：1632-1638.

[14]张则强，程文明，钟斌，等.混合品种装配线平衡问题的一种混合搜索机制的蚁群算法[J].机械工程学报，2009，45（5）：95-101.

[15]Dorigo M，Blum C.Ant colony optimization theory：a survey[J].Theoretical Computer Science，2005，344（2/3）：243-278.

ZHU Xiaoping1,ZHANG Zeqiang2

1.School of Mechanical and Electrical Engineering,Zhejiang Institute of Communications,Hangzhou 311112,China
2.School of Mechanical Engineering,Southwest Jiaotong University,Chengdu 610031,China

An improved ant colony optimization is proposed for solving the two sided excavator chassis’s assembly lines with station flipping tasks.The flipping task can decrease the assembly difficulty and operational risk but will greatly increase the planning and design difficulty.A heuristic task assignment method is presented for solving distributing the station flipping tasks.The heuristic task selection method is used to accelerate to find a feasible solution.The tasks’priority diagram is proposed after studying the assembly relationship between the tasks and the problem is abstracted into two sided assembly line balancing problem.The standard and improved ant colony algorithms are used for contradistinction on solving this problem.And this paper studies the inference brought by the inner structure of this two algorithms.

Ant Colony Optimization（ACO）;two-sided assembly lines;station flipping task;optimization;swarm intelligence

A

TP301.6；TH165

10.3778/j.issn.1002-8331.1310-0291

ZHU Xiaoping,ZHANG Zeqiang.Ant Colony Optimization for two sided assembly line balancing with station flipping task.Computer Engineering and Applications,2014,50（6）：240-245.

国家自然科学基金（No.51205328）；高等学校博士学科点专项科研基金资助课题（No.200806131014）；教育部人文社会科学研究青年基金项目（No.12YJCZH296）；中央高校基本科研业务费专项资金资助项目（No.SWJTU09CX022）。

朱小平（1957—），男，副教授，研究方向：制造装备机械设计；张则强（1978—），通讯作者，男，博士，副教授，研究方向：制造系统与智能优化等。E-mail：zhangzeqiang@gmail.com

2013-10-23

2013-12-09

1002-8331（2014）06-0240-06