第Ⅰ类双边装配线平衡问题的改进蚁群算法

本资料包含pdf文件1个，下载需要1积分

Improved Ant Colony Algorithmfor Two-Sided Assembly Line Balancing Problem of Type IZHANG Zeqiang ， HU Junyi ， CHENG Wenming(1.School of Mechanical Engineering，Southwest Jiaotong University，Chengdu 61003 1，China；2.CSR QishuyanInstitute Co.Ltd.，Changzhou 21301 1，China)Abstract：To overcome the disadvantages of traditional algorithms in solving large-scale two-sidedassembly line balancing problems(TALBPs)，such as long computing time and unstable results，animproved ant colony algorithm(ACO)was proposed for solving the TALBP of type I.In the proposedalgorithm，a task sequence was generated first，and a feasible solution was then obtained by theheuristic assignment method；in addition，the pheromone summation rule and a global pheromoneupdating rule were adopted to avoid the ants falling into the locally optimal solutions. A series ofnumerical experiments were conducted on 30 test problems of different size using the proposed ACOalgorithm ，the standard ant colony algorithm，and the tabu search algorithm for comparison. Theresults indicate that the proposed ACO algorithm obtained 29 optimal solutions for the 30 test problems，and obtained 6 and 3 more optimal solutions than the standard ant colony algorithm and the tabu searchalgorithm，respectively.Finally，the proposed ACO algorithm was applied to a real car assembly lineand obtained the satisfactory solutions within 21.01 S，saving 9.14 S and improving the computationalefficiency by 30.3% when compared with the traditional ACO under the same line efficiency。

Key words：two-sided assembly lines；ant colony algorithm；optimization与单边装配线相比，双边装配线具有缩短装配线长度、减少原材料运输与工人移动成本、降低工收稿 日期：基金项目：作者简介：具和夹具费用等优点 ，被广泛应用于汽车、装载机、卡车等中大型产品的装配生产过程，能产生明2011.12-20国家自然科学基金资助项 目(51205328)；教育部人文社会科学研究青年基金资助项目(12YJCZH296)；高等学校博士学科点专项科研基金资助项目(200806131014)；中央高校基本科研业务费专项资金资助项 目(SWJTUO9CX022，2010ZT03)张则强(1978-)，男，副教授，博士，研究方向为制造系统与智能优化，电话：028-87601692，E-mail：zhangzeqiang###gmail.coln第4期 张则强等：第1类双边装配线平衡问题的改进蚁群算法 725显的经济效益。

随着双边装配线广泛应用，双边装配线平衡问题 (two-sided assembly lines balancing problem，TALBP)亦随之而生.装配线平衡问题作为 NP-Hard难题 j，难以在合理的时间内精确求解.与单边装配线相比，由于 TALBP装配线布局形式的改变，在分配任务时，除满足操作方位的要求，还需综合考虑不同操作方位的前序任务对自身开始装配时间的影响.因此，TALBP较单边装配线平衡问题更复杂.鉴于双边装配线平衡问题的实际应用价值和求解难度，近年来 TALBP受到了企业界和学术界的广泛关注 。

文献[1]针对 TALBP提出了-种任务成组分配方法，并采用多个启发式规则，以降低左右工位任务之间的相关度，该方法具有简单易于实现等优点，但往往会增加双边装配线需开启工位的数量；文献 [4]提出 了-种基 于 COMSOAL(computermethod of sequencing operations for assemb ly lines)的启发式方法，用于求解大规模双边装配线平衡问题；文献[6]针对随机型双边装配线平衡问题，提出了-种启发式算法，该算法具有简单快速等优点，但求解质量有待提高。

近年来，运用智能优化算法求解 TALBP成为- 个重要趋势.文献[7]提出了-种求解双边装配线平衡问题的遗传算法；文献[8]提出了双边装配线平衡问题的-种基于任务序列的改进遗传算法，采用基于序列、任务及其分配方位组合的编码方法，运用可行的交叉与变异算子，使搜索过程仅在可行解空间内进行，提高了效率；文献[9]提出了求解双边装配线平衡问题的禁忌搜索算法，该算法在求解效率与求解质量方面都有较好表现，但求解时间较长，测试问题计算用时最长达到 2 100 S；文献[10]提出了-种蜂群算法求解带区域约束的双边装配线平衡问题。

通过模仿蚁群觅食行为发展起来的蚁群算法(ant colony optimization，ACO)，在求解诸多组合优化问题时表现出优异的求解能力1-12]，对装配线平衡问题 H 求解速度快、平衡率高.鉴于ACO求解装配线平衡问题的优越性能，已有应用 ACO求解双边装配线平衡问题.文献[15]提出了求解双边装配线平衡问题的-种蚁群优化算法，其特点是两队蚂蚁协同工作，分别在装配线的两边构造平衡解，具有较优的求解性能。

为探索解决问题的新途径，本文提出了-种先构造任务排列序列，后采用改进启发式规则产生具体工作站分配方案的蚁群算法.该方法采用了在任务及其排列序列中可能位置之间释放信息素的方法，并引入带信息素总合规则的混合搜索机制，针对 TALBP问题特征，提出了新的启发式规则.最后对多个不同规模的实例进行了验证，表明了算法的有效性。

1 双边装配线平衡问题1.1 双边装配线双边装配线是在单边装配线的基础上，将原本单-的生产线分成左右两侧.如图 1所示，在装配线的两侧并行完成同-产品的不同装配任务，互对的两工位称为成对工位，其中-个为另-个的伴随工位，如工位 1和工位2.在双边装配线中，可供分配的任务按其操作位置偏向性可分为3种：适左型任务( )、适右型任务(R)、无偏向型任务(E，即两边皆可操作).故在双边装配线问题中，除需考虑任务之间的先后约束关系外，还需考虑任务的操作方位约束，图2中圈内数字表示任务编号，圈外字母表示任务的操作方位约束，树状图体现了任务之间的先后操作顺序的约束关系。

位置1 位置2 传达带 位置 -1) 位置n图 1 双边装配线示例Fig.1 Typical example of two-sided assembly line图2 优先顺序图示例Fig.2 Example of a precedence diagram1.2 第 1类双边装配线平衡问题的数学模型第 1类双边装配线平衡问题(TALBP-I)定义为：在给定生产节拍，并满足任务先后约束关系的条件下，将-组任务旧能均衡地分配到各个工位的左右两边装配线中，以最携装配线长度.其TALBP.I数学模型如下。

726 西 南 交 通 大 学 学 报 第48卷设，为任务集，，1，2，，N；，D为按操作方位分割的任务集，DL，R，E； ，为工位 和上分配的任务集；tTjt01为工位的总操作时间及延迟时间；t"为工位 的总操作时间；t。 为工位 的延迟时间；P( )为任务 i的所有前序任务集；S为所有 P( )为空的任务 i的集合，即可选任务集合；W为未分配任务集合；n为开启的位置总数；Ns为开启的工位总数；r1， 任务i分配到位置 上， 操作方位为 ， ∈L，R，0， 否则。

目标函数为min n， (1)约束条件为若 f以1，贝0 妇 0，h∈P( )， g， l，2，，n，且g> ；∑戈 1，k E ，R1，i∈，， (2)V ， 2u-1， 2u， (3)：，：Z xiu妇kt i；' k R，) I∈f IfT∑ J即所有装配任务的-个排列序列.随后用启发式分配规则调用此排列，并产生-个完整的双边工位分配方案，即-个可行解.为较快形成仅考虑先后约束关系的排列，采用候选任务集方法，仅在可选任务列表中进行任务选择，以减少问题的搜索空间，提高搜索速度。

考虑任务的先后约束关系，若-个未分配任务 i的所有前序任务都已分配，则任务 i是可选任务.再考虑优先顺序约束和节拍约束，在任务排列序列中确定当前位置的可选任务集合 ，即候选任务集合 。

蚂蚁在访问每个序列位置时，都将面对-个可选任务集合 ，蚂蚁需根据每项任务的选择概率选择-项任务，并进入此排列的下-个位置，直至访问整个序列完毕.图3表示图2所示问题的-个任务排列序列，图3中数字表示任务编号，字母代表任务操作偏向性。

堡 l塑 I I 墨l!墨 I塑 I 墨l 墨 I!墨图 3 -个完整的任务排列序列Fig.3 A ful task sequence of assignment(4) 2. 3 改进的信息素搜索规则tT，tD，≤C， tT，rtD ≤C， V . (5)式(1)表示最携装配线长度；式(2)表示任务安排满足优先顺序关系约束；式(3)表示任-任务必须且只能分配到-个位置 u上，且分配后操作方位为左边或右边；式(4)中t 、t ，分别表示在某位置 u时工位 与 的总操作时间；式(5)表示任意位置 的双边工位作业时间必须满足节拍约束。

2 TALBP-I的改进蚁群算法2.1 蚁群算法蚁群算法l-钊在诸多组合优化问题中得到了应用 J，并表现出优异的求解性能.在应用此算法解决工程问题时，需先将问题抽象为若干个节点或步骤，在每个节点或步骤需进行构造解元素的多种选择.人工蚂蚁在节点图中搜索前进，每遍历-次节点，就构成问题的-个完整解.通过信息素的正反馈作用，最后收敛到最优解.本文提出求解TALBP的改进蚁群算法包括4个主要内容：构造任务排列序列、改进的信息素搜索规则、启发式分配规则产生解的具体分配方案、信息素更新规则。

2.2 构造任务排列序列先产生-列仅考虑任务先后约束关系的排列，在任务序列构造过程中，蚂蚁每周游-次即构造出-个完整任务排列序列.构造出最优解所对应任务序列的蚂蚁在所经路径上释放信息素，以吸引后续蚂蚁跟随.基本蚁群算法在寻优过程中，易受早期发现的较好解的影响而陷人局部最优。

为避免算法搜索停滞现象并保持其搜索范围，即在利用”信息素的同时保持较大的随机性，本文借鉴了文献[13]的改进信息素规则，即增加-个随机搜索以避免陷人局部最优，综合考虑了利用现有信息和随机搜索两种规则，构造出如下2种方式的混合搜索机制：(∑.r )P - 生， o≤ r≤ r1，∑(∑丁 )vj 1 随机选择 i∈ ，rl

启发式规则采用了位置权重，综合考虑了作业时间和后续作业数，是2种规则的结合.在该启发式规则的指引下，对后续任务较多且作业时间较长的任务优先分配的概率更大。

根据式(6)，按照概率选择使用 2个策略中的某个规则，从候选任务集 中选择-项任务：(1)利用.若随机数 r满足 0≤r≤r ，则以概率P ，从候选任务集 中选择-项任务。

(2)随机选择.若随机数 r满足r1

从信息素搜索规则看，改进的信息素搜索规则根据随机数 r值选择用 P 或者随机方式选择任务.根据当前位置可选任务集，由式(6)计算出每个任务的位置权重系数以及信息素矩阵.普通蚁群算法按照每项任务信息素积累值大续行概率选择，而改进蚁群算法具有更强的搜索能力。

2.4 启发式分配规则将蚁群搜索构造的-个任务序列生成可行的双边分配方案，本文提出新的分配规则，步骤如下：(1)开启新工位，并记录工位数。

(2)检查任务序列 g处任务是否满足左右工位任-边的节拍约束，转步骤(3)。

(4)查找是否有处于同-工位的紧前任务，是则进人步骤(4.1)，否则进入步骤(4.2)。

(4.1)找出同-工位中所有紧前任务的最晚结束时刻，并与此边结束时刻对比，选择较大者与序列 g处任务装配时间相加，判断是否满足节拍约束.若满足令qg1，并更新左边工位(当为型任务时)或右边工位(当为R型任务时)的结束时刻，转步骤(6)，否则转步骤(1)。

(4.2)查看是否满足节拍约束，若满足令qg1，并更新左边工位(当为 型任务时)或右边工位(当为R型任务时)的结束时刻，转步骤(6)，否则转步骤(1)。

(5)查找是否有处于同-工位的紧前任务，若有转步骤(5.1)，否则转步骤(5.2)。

(5.1)查找处于同-工位中紧前任务的最晚结束时刻，判断是否满足节拍约束，若满足令gq1，并且放人同-边，并更新此边工位结束时刻，转步骤(6)，否则返回步骤(1)开启新的工位。

(5.2)在左右两边中选择能使其最早开始的- 边，若左右两边结束时刻相同，则随机选择-边，更新此边结束时刻，转步骤(6)。

(6)查看任务是否全部分配完毕，若是转步骤(7)，否则返回步骤(2)。

(7)记录此任务排列的工位数量，作为适应度值储存，至此任务序列分配完毕。

2.5 信息素更新规则局部信息素更新，当蚂蚁将任务i分配到序列位置 ，边 上的信息素 按式(8)进行更新，f (1-p1)f pl下o， (8)式中：P。为局部信息素蒸发系数，0

3 算法测试与分析本文采用 MATLAB7.8对此改进蚁群算法(P-ACO)与普通蚁群算法(ACO)分别编写了实验程序.在处理器为e5300、主频2.6 GHz、内存2.0 GB的硬件环境下，进行了算法测试.分别对 Lee、Kim和Bartholdi双边装配线平衡问题进行求解，问题规模为P9、P12、P24、P65、P148和 P205.普通蚁群算法与改进蚁群算法采用相同参数设置： 1，/32，P10.1，P20.9，r0.9。

设蚂蚁数为60、迭代次数为20，对所测试问题能找到大部分最优解.引用文献[9]中的禁忌搜索(tabu search，TS)作为对比算例，表 1给出了30个728 西 南 交 通 大 学 学 报 第48卷测试问题的测试结果及其对比.表 1中，Ⅳ为问题的任务规模，C为节拍时间，ACO为普通蚁群算法，p-ACO为本文提出的改进蚁群算法。

表 1 测试结果及其对比Tab.1 Performance comparison for three algorithms当求解 Lee-P65问题的节拍时间为 490 S时，在蚂蚁数为60条件下，采用普通蚁群算法与改进蚁群算法分别运算 l0次.普通蚁群算法平均在第7代找到最优解，而改进蚁群算法在第2代找到最优解，改进蚁群算法平均比普通蚁群算法可更快收敛至最优解.图4为改进蚁群算法与普通蚁群算法迭代收敛的对比。

分析表 1中数据，在30个测试算例中，普通蚁群算法共求得23个最优解；禁忌搜索算法共求得26个最优解；本文的改进蚁群算法求得 29个最优解，用时最长 284.69 s，并在较大规模 问题 (Lee。

P205)的求解中有显著优势.从文献[9]知，TSA求得26个最优解.可见，由于采用改进的信息素搜索规则和改进的全局信息素更新规则等改进措施，相对普通蚁群算法、TSA算法，改进蚁群算法能对更大规模问题求得最优解。

图4 Lee-P65迭代收敛对比Fig.4 The convergent iterative comparison for Lee-P654 算法工程应用对某公司的微型车双边装配线进行规划设计，经实际调研，将该双边装配线操作任务合并为85项.任务优先关系如图 5～7所示 ，为简化图的复杂度拆分成 3个图显示.可综合图5-7得到任务之间的优先关系。

图 5 优先顺序图(I)Fig.5 Precedence diagram(I)表2(第1栏为任务编号)为任务的操作时间、操作方位汇总(为节省篇幅，省略了操作名称及说明).采用本文的改进蚁群算法，对此双边装配线进行优化设计，参数设置为Od1， 2，P 0.1，P 0.9，r0.9，蚂蚁数目为40，迭代次数为20。

普通蚁群算法和改进蚁群算法在相同参数设置下各运算10次求解该实例.当节拍时间为620 S时，优化结果 (表 3)的平衡率为 87.07%，平滑系数第4期 张则强等：第1类双边装配线平衡问题的改进蚁群算法 729为 92.10，平衡效果较好。

图 6 优先顺序图(I)Fig.6 Precedence diagram(I)图7 优先顺序图(Ⅲ)Fig.7 Precedence diagram(II)表 2 任务操作时间及操作方位Tab.2 Operation time and position of tasks编号 ∥方位 编号 ∥方位 编号 ∥方位 编号 ∥方位1 75/ 23 70/ 45 73/ 67 213，R2 78/E 24 74，L 46 1s，L 68 70/3 150/ 25 73/R 47 143/R 69 71/R4 73/E 26 73/R 48 14，L 70 70/s s，L 27 73/ 49 13，L 71 73/R6 1s/R 28 75/ 50 71/R 72 70/1 ，L 29 73/R 51 71/R 73 70/R8 75/ 30 73/ 52 150/L 74 1Q，L9 75/R 31 75/ 53 75/R 75 70，L1O 15O/ 32 108/R 54 75/L 76 73/L11 75/E 33 73/ 55 71/R 77 70，L12 71/E 34 1O，L 56 73/ 78 130，R13 69/E 35 67/ 57 71/ 79 75/L14 74，R 36 67/ 58 146，R 80 106/15 75/ 37 70/R 59 71/ 81 106/16 75/ 38 70/ 60 71儿 82 69/R17 68/E 39 126，R 61 67/ 83 75/18 75/ 40 126儿 62 286/R 84 7l/R19 73/E 41 70/ 63 73/ 85 67/20 75/E 42 73/E 64 146，L21 71/E 43 73/R 65 210/R22 67/ 44 s，R 66 286/L注 ：-/-表示作业时间/操作方位表3 双边装配线实例优化结果Tab.3 Optimal solution for the real-world example of two-sided assembly line注：-(-，-)表示任务序号(开始作业时间，完成作业时间)，作业时间单位：s改进蚁群算法平均在迭代次数 17.2次时找到的总位置数为7的较优解，而普通蚁群算法针对该实例则仅有 1次求得的总位置数为7的解.同时，在算法求解速度上，改进蚁群算法平均耗时21.01 s，而普通蚁群算法则耗时3O.15 s，节省了9.14 s，计算效率提高了30.3%.由此可见，本文提出的改进蚁群算法较普通蚁群算法在求解质量和求解速度方面均表现出更优越的性能。

730 西 南 交 通 大 学 学 报 第48卷5 结束语针对 TALBP问题提出了-种改进蚁群算法，提出-种新的启发式分配规则以产生可行解.采用在任务与任务序列位置之间释放信息素的策略，并引入综合信息素搜索规则与全局信息素更新策略，可有效脱离陷入局部最优解.通过大量不同规模问题算例，对比普通蚁群算法和禁忌搜索算法，改进蚁群算法对不同规模问题的求解质量和速度更优，验证了该算法的有效性.应用改进蚁群算法求解某汽车双边装配线任务分配问题，取得了良好的求解效果。

下-步研究可将 ACO算法拓展应用至更接近实际的TALBP，例如，考虑复杂区域约束、不确定环境下存在多种随机因素等情形下的TALBP。