论文部分内容阅读
摘要： 为克服传统算法求解大规模双边装配线平衡问题计算时间长、性能不稳定的缺陷，针对第Ⅰ类双边装配线平衡问题，应用综合信息素搜索规则与全局信息素更新规则，提出了一种先产生任务排列序列、后按启发式分配规则产生可行解的蚁群算法，可有效脱离陷入局部最优解.用改进蚁群算法对30个不同规模的问题进行求解，并与标准蚁群算法和禁忌搜索算法进行了对比.结果表明：改进蚁群算法求出29个最优解，比普通蚁群算法、禁忌搜索算法分别能多求得6个和3个最优解；应用于汽车双边装配线算例，在保持平衡效率的条件下，改进蚁群算法计算时间为21.01 s，比普通蚁群算法减少了9.14 s，计算效率提高了30.3%.
关键词： 双边装配线；蚁群算法；优化
中图分类号： TH165文献标志码： AImproved Ant Colony Algorithm
for TwoSided Assembly Line Balancing Problem of Type IZHANG Zeqiang1，HU Junyi1，2，CHENG Wenming1
（1. School of Mechanical Engineering， Southwest Jiaotong University， Chengdu 610031， China； 2. CSR Qishuyan Institute Co. Ltd.， Changzhou 213011， China）
Abstract：To overcome the disadvantages of traditional algorithms in solving largescale twosided assembly line balancing problems （TALBPs）， such as long computing time and unstable results， an improved ant colony algorithm （ACO） was proposed for solving the TALBP of type I. In the proposed algorithm， a task sequence was generated first， and a feasible solution was then obtained by the heuristic assignment method； in addition， the pheromone summation rule and a global pheromone updating rule were adopted to avoid the ants falling into the locally optimal solutions. A series of numerical experiments were conducted on 30 test problems of different size using the proposed ACO algorithm， the standard ant colony algorithm， and the tabu search algorithm for comparison. The results 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 search algorithm， respectively. Finally， the proposed ACO algorithm was applied to a real car assembly line and obtained the satisfactory solutions within 21.01 s， saving 9.14 s and improving the computational efficiency by 30.3% when compared with the traditional ACO under the same line efficiency.
Key words：twosided assembly lines； ant colony algorithm； optimization
与单边装配线相比，双边装配线具有缩短装配线长度、减少原材料运输与工人移动成本、降低工具和夹具费用等优点[1]，被广泛应用于汽车、装载机、卡车等中大型产品的装配生产过程，能产生明显的经济效益.
随着双边装配线广泛应用，双边装配线平衡问题（twosided assembly lines balancing problem， TALBP）亦随之而生.装配线平衡问题作为NPHard难题[2]，难以在合理的时间内精确求解.与单边装配线相比，由于TALBP装配线布局形式的改变，在分配任务时，除满足操作方位的要求，还需综合考虑不同操作方位的前序任务对自身开始装配时间的影响.因此， TALBP较单边装配线平衡问题更复杂.鉴于双边装配线平衡问题的实际应用价值和求解难度，近年来TALBP受到了企业界和学术界的广泛关注[1，35].
文献[1]针对TALBP提出了一种任务成组分配方法，并采用多个启发式规则，以降低左右工位任务之间的相关度，该方法具有简单易于实现等优点，但往往会增加双边装配线需开启工位的数量；文献[4]提出了一种基于COMSOAL（computer method of sequencing operations for assembly lines）的启发式方法，用于求解大规模双边装配线平衡问题；文献[6]针对随机型双边装配线平衡问题，提出了一种启发式算法，该算法具有简单快速等优点，但求解质量有待提高. 近年来，运用智能优化算法求解TALBP成为一个重要趋势.文献[7]提出了一种求解双边装配线平衡问题的遗传算法；文献[8]提出了双边装配线平衡问题的一种基于任务序列的改进遗传算法，采用基于序列、任务及其分配方位组合的编码方法，运用可行的交叉与变异算子，使搜索过程仅在可行解空间内进西南交通大学学报第48卷第4期张则强等：第Ⅰ类双边装配线平衡问题的改进蚁群算法行，提高了效率；文献[9]提出了求解双边装配线平衡问题的禁忌搜索算法，该算法在求解效率与求解质量方面都有较好表现，但求解时间较长，测试问题计算用时最长达到2 100 s；文献[10]提出了一种蜂群算法求解带区域约束的双边装配线平衡问题.
通过模仿蚁群觅食行为发展起来的蚁群算法（ant colony optimization， ACO），在求解诸多组合优化问题时表现出优异的求解能力[1112]，对装配线平衡问题[1314]求解速度快、平衡率高.鉴于ACO求解装配线平衡问题的优越性能，已有应用ACO求解双边装配线平衡问题.文献[15]提出了求解双边装配线平衡问题的一种蚁群优化算法，其特点是两队蚂蚁协同工作，分别在装配线的两边构造平衡解，具有较优的求解性能.
为探索解决问题的新途径，本文提出了一种先构造任务排列序列，后采用改进启发式规则产生具体工作站分配方案的蚁群算法.该方法采用了在任务及其排列序列中可能位置之间释放信息素的方法，并引入带信息素总合规则的混合搜索机制，针对TALBP问题特征，提出了新的启发式规则.最后对多个不同规模的实例进行了验证，表明了算法的有效性.1双边装配线平衡问题1.1 双边装配线双边装配线是在单边装配线的基础上，将原本单一的生产线分成左右两侧.如图1所示，在装配线的两侧并行完成同一产品的不同装配任务，互对的两工位称为成对工位，其中一个为另一个的伴随工位，如工位1和工位2. 在双边装配线中，可供分配的任务按其操作位置偏向性可分为3种：适左型任务（L）、适右型任务（R）、无偏向型任务（E，即两边皆可操作）.故在双边装配线问题中，除需考虑任务之间的先后约束关系外，还需考虑任务的操作方位约束，图2中圈内数字表示任务编号，圈外字母表示任务的操作方位约束，树状图体现了任务之间的先后操作顺序的约束关系.
图1双边装配线示例
Fig.1Typical example of twosided assembly line图2优先顺序图示例
Fig.2Example of a precedence diagram
1.2第Ⅰ类双边装配线平衡问题的数学模型第Ⅰ类双边装配线平衡问题（TALBPⅠ）定义为：在给定生产节拍，并满足任务先后约束关系的条件下，将一组任务尽可能均衡地分配到各个工位的左右两边装配线中，以最小化装配线长度.其TALBPⅠ数学模型如下.
设I为任务集， I={1，2，…，N}； ID为按操作方位分割的任务集， D=L，R，E； Ij、Ij′为工位j和j′上分配的任务集； tT j、tD j为工位j的总操作时间及延迟时间； tT j′为工位j′的总操作时间； tD j′为工位j′的延迟时间； P（i）为任务i的所有前序任务集； S为所有P（i）为空的任务i的集合，即可选任务集合； W为未分配任务集合； n为开启的位置总数； NS为开启的工位总数；
xiuk=1，任务i分配到位置u上，
操作方位为k，k∈{L，R}，
0，否则.
目标函数为
min n，（1）
约束条件为
若xiuk=1， 则xhgk=0，
h∈P（i），g，u=1，2，…，n，且g>u；
∑nu=1xiuk=1，k∈{L， R}，i∈I，（2）
u，j=2u-1，j′=2u，（3）
tT j=∑i∈Ixiukti，k=L，
tT j′=∑i∈Ixiukti，k=R，（4）
tT j+tD j≤C，tT j′+tD j′≤C，u.（5）
式（1）表示最小化装配线长度；式（2）表示任务安排满足优先顺序关系约束；式（3）表示任一任务必须且只能分配到一个位置u上，且分配后操作方位为左边或右边；式（4）中tT j、tT j′分别表示在某位置u时工位j与j′的总操作时间；式（5）表示任意位置u的双边工位作业时间必须满足节拍约束.2TALBPI的改进蚁群算法2.1 蚁群算法蚁群算法[16]在诸多组合优化问题中得到了应用[1112]，并表现出优异的求解性能.在应用此算法解决工程问题时，需先将问题抽象为若干个节点或步骤，在每个节点或步骤需进行构造解元素的多种选择.人工蚂蚁在节点图中搜索前进， 每遍历一次节点，就构成问题的一个完整解.通过信息素的正反馈作用，最后收敛到最优解.本文提出求解TALBP的改进蚁群算法包括4个主要内容：构造任务排列序列、改进的信息素搜索规则、启发式分配规则产生解的具体分配方案、信息素更新规则.2.2 构造任务排列序列先产生一列仅考虑任务先后约束关系的排列，即所有装配任务的一个排列序列. 随后用启发式分配规则调用此排列，并产生一个完整的双边工位分配方案，即一个可行解.为较快形成仅考虑先后约束关系的排列，采用候选任务集方法，仅在可选任务列表中进行任务选择，以减少问题的搜索空间，提高搜索速度.
考虑任务的先后约束关系，若一个未分配任务i的所有前序任务都已分配，则任务i是可选任务. 再考虑优先顺序约束和节拍约束，在任务排列序列中确定当前位置的可选任务集合，即候选任务集合Nj.
蚂蚁在访问每个序列位置时，都将面对一个可选任务集合Nj，蚂蚁需根据每项任务的选择概率选择一项任务，并进入此排列的下一个位置，直至访问整个序列完毕.图3表示图2所示问题的一个任务排列序列，图3中数字表示任务编号，字母代表任务操作偏向性. IE3R2E4L7E5R6L8R9L
图3一个完整的任务排列序列
Fig.3A full task sequence of assignment
2.3 改进的信息素搜索规则在任务序列构造过程中，蚂蚁每周游一次即构造出一个完整任务排列序列.构造出最优解所对应任务序列的蚂蚁在所经路径上释放信息素，以吸引后续蚂蚁跟随.基本蚁群算法在寻优过程中，易受早期发现的较好解的影响而陷入局部最优.
为避免算法搜索停滞现象并保持其搜索范围，即在“利用”信息素的同时保持较大的随机性，本文借鉴了文献[13]的改进信息素规则，即增加一个随机搜索以避免陷入局部最优，综合考虑了利用现有信息和随机搜索两种规则，构造出如下2种方式的混合搜索机制：
Pij=∑jh=1τihαηβi∑s∈Nj∑jh=1τshαηβs，0≤r≤r1，
随机选择i∈Nj， r1 式中： Pij为当前可选任务集合中的任务i在当前位置j的被选择的概率；
τih为任务i分配到位置h的信息素；
r为（0， 1）之间的随机数；
r1为用户定义的参数，满足0 Nj为蚂蚁在当前分配序列位置j的候选任务集；
α、 β为决定信息素强度和启发式信息相对重要性的参数；
ηi为任务i的启发式信息，选取该任务的位置权重wP i作为启发式信息：
ηi=wP i=ti+∑j∈Fitj，i=1，2，…，N，（7）
式中： Fi为任务i的后继任务集合.
启发式规则采用了位置权重，综合考虑了作业时间和后续作业数，是2种规则的结合.在该启发式规则的指引下，对后续任务较多且作业时间较长的任务优先分配的概率更大.
根据式（6），按照概率选择使用2个策略中的某个规则，从候选任务集Nj中选择一项任务：
（1） 利用.若随机数r满足0≤r≤r1，则以概率Pij从候选任务集Nj中选择一项任务.
（2） 随机选择.若随机数r满足r1 从信息素搜索规则看，改进的信息素搜索规则根据随机数r值选择用Pij或者随机方式选择任务. 根据当前位置可选任务集，由式（6）计算出每个任务的位置权重系数以及信息素矩阵.普通蚁群算法按照每项任务信息素积累值大小进行概率选择，而改进蚁群算法具有更强的搜索能力.2.4启发式分配规则将蚁群搜索构造的一个任务序列生成可行的双边分配方案，本文提出新的分配规则，步骤如下：
（1） 开启新工位，并记录工位数.
（2） 检查任务序列q处任务是否满足左右工位任一边的节拍约束，转步骤（3）.
（3） 任务为L型或R型进入步骤（4），为E型进入步骤（5）.
（4） 查找是否有处于同一工位的紧前任务，是则进入步骤（4.1），否则进入步骤（4.2）.
（4.1） 找出同一工位中所有紧前任务的最晚结束时刻，并与此边结束时刻对比，选择较大者与序列q处任务装配时间相加，判断是否满足节拍约束.若满足令q=q+1，并更新左边工位（当为L型任务时）或右边工位（当为R型任务时）的结束时刻，转步骤（6），否则转步骤（1）.
（4.2） 查看是否满足节拍约束，若满足令q=q+1，并更新左边工位（当为L型任务时）或右边工位（当为R型任务时）的结束时刻，转步骤（6），否则转步骤（1）.
（5） 查找是否有处于同一工位的紧前任务，若有转步骤（5.1），否则转步骤（5.2）.
（5.1） 查找处于同一工位中紧前任务的最晚结束时刻，判断是否满足节拍约束，若满足令q=q+1，并且放入同一边，并更新此边工位结束时刻，转步骤（6），否则返回步骤（1）开启新的工位.
（5.2） 在左右两边中选择能使其最早开始的一边，若左右两边结束时刻相同，则随机选择一边，更新此边结束时刻，转步骤（6）.
（6） 查看任务是否全部分配完毕，若是转步骤（7），否则返回步骤（2）.
（7） 记录此任务排列的工位数量，作为适应度值储存，至此任务序列分配完毕.2.5 信息素更新规则局部信息素更新，当蚂蚁将任务i分配到序列位置j，边ij上的信息素τij按式（8）进行更新，
τij←（1-ρ1）τij+ρ1τ0，（8）
式中： ρ1为局部信息素蒸发系数， 0<ρ1<1；
τ0为初始化信息素的值（一个很小的初始输入），
τ0=1NK*，K*=1C∑Ni=1ti.
当构建了一个完整解后，各任务至序列位置之间的信息素均按如下规则进行信息素全局更新，
τij←（1-ρ2）τij+ρ2Δτij，（9）
式中： ρ2为全局信息素蒸发系数， 0<ρ2<1；
Δτij=1Lgb，当前最优分配方案包含边（i，j），
0，否则，
式中： Lgb为当前最优分配序列（方案）所需的工作站数.3 算法测试与分析本文采用MATLAB7.8对此改进蚁群算法（pACO）与普通蚁群算法（ACO）分别编写了实验程序.在处理器为e5300、主频2.6 GHz、内存2.0 GB的硬件环境下，进行了算法测试.分别对Lee、Kim和Bartholdi双边装配线平衡问题进行求解，问题规模为P9、P12、P24、P65、P148和P205. 普通蚁群算法与改进蚁群算法采用相同参数设置： α=1， β=2， ρ1=0.1， ρ2=0.9， r=0.9.
设蚂蚁数为60、迭代次数为20，对所测试问题能找到大部分最优解.引用文献[9]中的禁忌搜索（tabu search， TS）作为对比算例，表1给出了30个测试问题的测试结果及其对比.表1中， N为问题的任务规模， C为节拍时间， ACO为普通蚁群算法， pACO为本文提出的改进蚁群算法. 表1测试结果及其对比
Tab.1Performance comparison for three algorithms
问题NC
/smmin
/个ACO
/个TS
/个pACO
/个Kim93333394333395222296222212533331263333127222212822222420444424253333243033332435232324402222Lee653818888654357777654906666655445665Bartholdi1483578988148408787714845967661485106666Lee2051 322111111112051 510910992051 69988982051 88888882052 07777772052 26677772052 45466662052 64356652052 8325565
当求解LeeP65问题的节拍时间为490 s时，在蚂蚁数为60条件下，采用普通蚁群算法与改进蚁群算法分别运算10次. 普通蚁群算法平均在第7代找到最优解，而改进蚁群算法在第2代找到最优解，改进蚁群算法平均比普通蚁群算法可更快收敛至最优解.图4为改进蚁群算法与普通蚁群算法迭代收敛的对比.
分析表1中数据，在30个测试算例中，普通蚁群算法共求得23个最优解；禁忌搜索算法共求得26个最优解；本文的改进蚁群算法求得29个最优解，用时最长284.69 s，并在较大规模问题（LeeP205）的求解中有显著优势.从文献[9]知， TSA求得26个最优解.可见，由于采用改进的信息素搜索规则和改进的全局信息素更新规则等改进措施，相对普通蚁群算法、TSA算法，改进蚁群算法能对更大规模问题求得最优解.
图4LeeP65迭代收敛对比
Fig.4The convergent iterative comparison for LeeP65 4算法工程应用对某公司的微型车双边装配线进行规划设计，经实际调研，将该双边装配线操作任务合并为85项.任务优先关系如图5～7所示，为简化图的复杂度拆分成3个图显示.可综合图5～7得到任务之间的优先关系.
图5优先顺序图（Ⅰ）
Fig.5Precedence diagram（Ⅰ）
表2（第1栏为任务编号）为任务的操作时间、操作方位汇总（为节省篇幅，省略了操作名称及说明）.采用本文的改进蚁群算法，对此双边装配线进行优化设计，参数设置为α=1， β=2， ρ1=0.1， ρ2=0.9， r=0.9，蚂蚁数目为40，迭代次数为20. 普通蚁群算法和改进蚁群算法在相同参数设置下各运算10次求解该实例.当节拍时间为620 s时，优化结果（表3）的平衡率为87.07%，平滑系数为92.10，平衡效果较好.
图6优先顺序图（Ⅱ）
Fig.6Precedence diagram（Ⅱ）图7优先顺序图（Ⅲ）
Fig.7Precedence diagram（Ⅲ）
表2任务操作时间及操作方位
Tab.2Operation time and position of taskss
编号t/方位编号t/方位编号t/方位编号t/方位175/R2370/L4573/L67213/R278/E2474/L4675/L6870/L3150/E2573/R47143/R6971/R473/E2673/R4874/L7070/L575/L2773/L4973/L7173/R675/R2875/L5071/R7270/L767/L2973/R5171/R7370/R875/L3073/R52150/L7470/L975/R3175/L5375/R7570/L10150/L32108/R5475/L7673/L1175/E3373/L5571/R7770/L1271/E3470/L5673/L78130/R1369/E3567/R5771/R7975/L1474/R3667/L58146/R80106/R1575/L3770/R5971/L81106/L1675/R3870/L6071/L8269/R1768/E39126/R6167/L8375/R1875/L40126/L62286/R8471/R1973/E4170/L6373/R8567/L2075/E4273/E64146/L2171/E4373/R65210/R2267/L4475/R66286/L注：—/—表示作业时间/操作方位.
表3双边装配线实例优化结果
Tab.3Optimal solution for the realworld example of twosided assembly line
位置工位任务分配情况1左边79（75，150）， 4（150，223）， 75（223，293），74（293，363），48（363，437）， 3（437，587）右边1（0，75）， 2（75，153）， 78（153，383），67（283，496）2左边7（0，67），5（67，142），49（143，216），10（216，366），68（366，436）， 22（436，503）右边47（0，143），9（143，218），65（218，428），11（428，503），73（503，573）3左边52（0，150），41（150，220），54（220，295），18（295，370），64（370，516），70（516，586）右边13（0，69），32（69，177），19（177，250），26（250，323），25（323，396），58（396，542），51（542，613）4左边23（0，70），27（70，143），8（143，218），28（218，293），66（293，579）右边71（0，73）， 6（73，148）， 16（148，223），63（223，296）， 62（296，582）5左边60（75，146），59（146，217），45（217，290），33（290，363），34（363，433），15（433，508），21（508，579）右边55（0，71），14（75，149），29（149，222），17（222，290），30（290，363），43（363，436），44（436，511），84（511，582）6左边56（0，73），24（73，147），72（147，217），76（217，290），46（290，365），61（365，432），77（432，502），36（502，569）右边55（0，71），57（147，218），39（218，344），35（344，411），80（502，608）7左边40（0，126），42（126，199），31（199，274），12（274，345），81（345，451），38（451，521），85（521，588）右边20（0，75），50（75，146），82（199，268），69（268，339），37（339，409），83（409，484）注：—（—，—）表示任务序号（开始作业时间，完成作业时间），作业时间单位： s. 改进蚁群算法平均在迭代次数17.2次时找到的总位置数为7的较优解，而普通蚁群算法针对该实例则仅有1次求得的总位置数为7的解.同时，在算法求解速度上，改进蚁群算法平均耗时21.01 s，而普通蚁群算法则耗时30.15 s，节省了9.14 s，计算效率提高了30.3%.由此可见，本文提出的改进蚁群算法较普通蚁群算法在求解质量和求解速度方面均表现出更优越的性能. 5 结束语针对TALBP问题提出了一种改进蚁群算法，提出一种新的启发式分配规则以产生可行解.采用在任务与任务序列位置之间释放信息素的策略，并引入综合信息素搜索规则与全局信息素更新策略，可有效脱离陷入局部最优解.通过大量不同规模问题算例，对比普通蚁群算法和禁忌搜索算法，改进蚁群算法对不同规模问题的求解质量和速度更优，验证了该算法的有效性.应用改进蚁群算法求解某汽车双边装配线任务分配问题，取得了良好的求解效果.
下一步研究可将ACO算法拓展应用至更接近实际的TALBP，例如，考虑复杂区域约束、不确定环境下存在多种随机因素等情形下的TALBP.参考文献：[1]LEE T O， KIM Y， KIM Y K. Twosided assembly line balancing to maximize work relatedness and slackness[J]. Computers and Industrial Engineering， 2001， 40（3）： 273292.
[2]SCHOLL A， BECKER C. Stateoftheart exact and heuristic solution procedures for simple assembly line balancing[J]. European Journal of Operational Research， 2006， 168（3）： 666693.
[3]OZCAN U， TOKLU B. Multiplecriteria decisionmaking in twosided assembly line balancing： a goal programming and a fuzzy goal programming models[J]. Computers & Operations Research， 2009， 36（6）： 19551965.
[4]OZCAN U， TOKLU B. Balancing twosided assembly lines with sequencedependent setup times[J]. International Journal of Production Research， 2010， 48（18）： 53635383.
[5]ZHANG Zeqiang， MURRAY C C. A corrected formulation for the double row layout problem[J]. International Journal of Production Research， 2012， 50（15）： 42204223.
[6]宋林，张则强，程文明，等. 随机型双边装配线平衡问题的一种启发式算法[J]. 工业工程，2011，14（4）： 129134.
SONG Lin， ZHANG Zeqiang， CHENG Wenming， et al. Heuristic for twosided stochastic assembly line balancing[J]. Industrial Engineering Journal， 2011， 14（4）： 129134
[7]KIM Y K， SONG W S， KIM J H. A mathematical model and a genetic algorithm for twosided assembly line balancing[J]. Computers & Operations Research， 2009， 36（3）： 853865.
[8]吴尔飞，金烨，续爱民，等. 基于改进遗传算法的双边装配线平衡[J]. 计算机集成制造系统，2007，13（2）： 268274.
WU Erfei， JIN Ye， XU Aimin， et al. Twosided assembly line balancing based on modified genetic algorithm[J]. Computer Integrated Manufacturing Systems， 2007， 13（2）： 268274.
[9]ZCAN U， TOKLU B. A tabu search algorithm for twosided assembly line balancing[J]. The International Journal of Advanced Manufacturing Technology， 2009， 43（7/8）： 822829.
[10]ZBAKIR L， TAPKAN P. Bee colony intelligence in zone constrained twosided assembly line balancing problem[J]. Expert Systems with Applications， 2011， 38（9）： 1194711957.
[11]DORIGO M， STTZLE T. Ant colony optimization： overview and recent advances[M]∥GENDREAU M， POTVIN J Y. Handbook of Metaheuristics. [S. l.]： Springer， 2010： 227263. [12]刘洁，刘丹，何彦锋. 带中转设施的垃圾收集VRP的改进蚁群算法[J]. 西南交通大学学报，2011，46（2）： 333339.
LIU Jie， LIU Dan， HE Yanfeng. Improved ant colony system algorithm for waste collection vehicle routing problem[J]. Journal of Southwest Jiaotong University， 2011， 46（2）： 333339.
[13]张则强，程文明，钟斌，等. 求解装配线平衡问题的一种改进蚁群算法[J]. 计算机集成制造系统，2007，13（8）： 16321638.
ZHANG Zeqiang， CHENG Wenming， ZHONG Bin， et al. Improved ant colony optimization for assembly line balancing problem[J]. Computer Integrated Manufacturing Systems， 2007， 13（8）： 16321638.
[14]张则强，程文明，钟斌，等. 混合品种装配线平衡问题的一种混合搜索机制的蚁群算法[J]. 机械工程学报，2009，45（5）： 95101.
ZHANG Zeqiang， CHENG Wenming， ZHONG Bin， et al. Hybrid behavior ant colony optimization for mixedmodel assembly line balancing problem[J]. Journal of Mechanical Engineering， 2009， 45（5）： 95101.
[15]SIMARIA A S， VILARINHO P M. 2ANTBAL： an ant colony optimization algorithm for balancing twosided assembly lines[J]. Computers & Industrial Engineering， 2009， 56（2）： 489506.
[16]DORIGO M， BLUM C. Ant colony optimization theory： a survey[J]. Theoretical Computer Science， 2005， 344（2/3）： 243278.
关键词： 双边装配线；蚁群算法；优化
中图分类号： TH165文献标志码： AImproved Ant Colony Algorithm
for TwoSided Assembly Line Balancing Problem of Type IZHANG Zeqiang1，HU Junyi1，2，CHENG Wenming1
（1. School of Mechanical Engineering， Southwest Jiaotong University， Chengdu 610031， China； 2. CSR Qishuyan Institute Co. Ltd.， Changzhou 213011， China）
Abstract：To overcome the disadvantages of traditional algorithms in solving largescale twosided assembly line balancing problems （TALBPs）， such as long computing time and unstable results， an improved ant colony algorithm （ACO） was proposed for solving the TALBP of type I. In the proposed algorithm， a task sequence was generated first， and a feasible solution was then obtained by the heuristic assignment method； in addition， the pheromone summation rule and a global pheromone updating rule were adopted to avoid the ants falling into the locally optimal solutions. A series of numerical experiments were conducted on 30 test problems of different size using the proposed ACO algorithm， the standard ant colony algorithm， and the tabu search algorithm for comparison. The results 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 search algorithm， respectively. Finally， the proposed ACO algorithm was applied to a real car assembly line and obtained the satisfactory solutions within 21.01 s， saving 9.14 s and improving the computational efficiency by 30.3% when compared with the traditional ACO under the same line efficiency.
Key words：twosided assembly lines； ant colony algorithm； optimization
与单边装配线相比，双边装配线具有缩短装配线长度、减少原材料运输与工人移动成本、降低工具和夹具费用等优点[1]，被广泛应用于汽车、装载机、卡车等中大型产品的装配生产过程，能产生明显的经济效益.
随着双边装配线广泛应用，双边装配线平衡问题（twosided assembly lines balancing problem， TALBP）亦随之而生.装配线平衡问题作为NPHard难题[2]，难以在合理的时间内精确求解.与单边装配线相比，由于TALBP装配线布局形式的改变，在分配任务时，除满足操作方位的要求，还需综合考虑不同操作方位的前序任务对自身开始装配时间的影响.因此， TALBP较单边装配线平衡问题更复杂.鉴于双边装配线平衡问题的实际应用价值和求解难度，近年来TALBP受到了企业界和学术界的广泛关注[1，35].
文献[1]针对TALBP提出了一种任务成组分配方法，并采用多个启发式规则，以降低左右工位任务之间的相关度，该方法具有简单易于实现等优点，但往往会增加双边装配线需开启工位的数量；文献[4]提出了一种基于COMSOAL（computer method of sequencing operations for assembly lines）的启发式方法，用于求解大规模双边装配线平衡问题；文献[6]针对随机型双边装配线平衡问题，提出了一种启发式算法，该算法具有简单快速等优点，但求解质量有待提高. 近年来，运用智能优化算法求解TALBP成为一个重要趋势.文献[7]提出了一种求解双边装配线平衡问题的遗传算法；文献[8]提出了双边装配线平衡问题的一种基于任务序列的改进遗传算法，采用基于序列、任务及其分配方位组合的编码方法，运用可行的交叉与变异算子，使搜索过程仅在可行解空间内进西南交通大学学报第48卷第4期张则强等：第Ⅰ类双边装配线平衡问题的改进蚁群算法行，提高了效率；文献[9]提出了求解双边装配线平衡问题的禁忌搜索算法，该算法在求解效率与求解质量方面都有较好表现，但求解时间较长，测试问题计算用时最长达到2 100 s；文献[10]提出了一种蜂群算法求解带区域约束的双边装配线平衡问题.
通过模仿蚁群觅食行为发展起来的蚁群算法（ant colony optimization， ACO），在求解诸多组合优化问题时表现出优异的求解能力[1112]，对装配线平衡问题[1314]求解速度快、平衡率高.鉴于ACO求解装配线平衡问题的优越性能，已有应用ACO求解双边装配线平衡问题.文献[15]提出了求解双边装配线平衡问题的一种蚁群优化算法，其特点是两队蚂蚁协同工作，分别在装配线的两边构造平衡解，具有较优的求解性能.
为探索解决问题的新途径，本文提出了一种先构造任务排列序列，后采用改进启发式规则产生具体工作站分配方案的蚁群算法.该方法采用了在任务及其排列序列中可能位置之间释放信息素的方法，并引入带信息素总合规则的混合搜索机制，针对TALBP问题特征，提出了新的启发式规则.最后对多个不同规模的实例进行了验证，表明了算法的有效性.1双边装配线平衡问题1.1 双边装配线双边装配线是在单边装配线的基础上，将原本单一的生产线分成左右两侧.如图1所示，在装配线的两侧并行完成同一产品的不同装配任务，互对的两工位称为成对工位，其中一个为另一个的伴随工位，如工位1和工位2. 在双边装配线中，可供分配的任务按其操作位置偏向性可分为3种：适左型任务（L）、适右型任务（R）、无偏向型任务（E，即两边皆可操作）.故在双边装配线问题中，除需考虑任务之间的先后约束关系外，还需考虑任务的操作方位约束，图2中圈内数字表示任务编号，圈外字母表示任务的操作方位约束，树状图体现了任务之间的先后操作顺序的约束关系.
图1双边装配线示例
Fig.1Typical example of twosided assembly line图2优先顺序图示例
Fig.2Example of a precedence diagram
1.2第Ⅰ类双边装配线平衡问题的数学模型第Ⅰ类双边装配线平衡问题（TALBPⅠ）定义为：在给定生产节拍，并满足任务先后约束关系的条件下，将一组任务尽可能均衡地分配到各个工位的左右两边装配线中，以最小化装配线长度.其TALBPⅠ数学模型如下.
设I为任务集， I={1，2，…，N}； ID为按操作方位分割的任务集， D=L，R，E； Ij、Ij′为工位j和j′上分配的任务集； tT j、tD j为工位j的总操作时间及延迟时间； tT j′为工位j′的总操作时间； tD j′为工位j′的延迟时间； P（i）为任务i的所有前序任务集； S为所有P（i）为空的任务i的集合，即可选任务集合； W为未分配任务集合； n为开启的位置总数； NS为开启的工位总数；
xiuk=1，任务i分配到位置u上，
操作方位为k，k∈{L，R}，
0，否则.
目标函数为
min n，（1）
约束条件为
若xiuk=1， 则xhgk=0，
h∈P（i），g，u=1，2，…，n，且g>u；
∑nu=1xiuk=1，k∈{L， R}，i∈I，（2）
u，j=2u-1，j′=2u，（3）
tT j=∑i∈Ixiukti，k=L，
tT j′=∑i∈Ixiukti，k=R，（4）
tT j+tD j≤C，tT j′+tD j′≤C，u.（5）
式（1）表示最小化装配线长度；式（2）表示任务安排满足优先顺序关系约束；式（3）表示任一任务必须且只能分配到一个位置u上，且分配后操作方位为左边或右边；式（4）中tT j、tT j′分别表示在某位置u时工位j与j′的总操作时间；式（5）表示任意位置u的双边工位作业时间必须满足节拍约束.2TALBPI的改进蚁群算法2.1 蚁群算法蚁群算法[16]在诸多组合优化问题中得到了应用[1112]，并表现出优异的求解性能.在应用此算法解决工程问题时，需先将问题抽象为若干个节点或步骤，在每个节点或步骤需进行构造解元素的多种选择.人工蚂蚁在节点图中搜索前进， 每遍历一次节点，就构成问题的一个完整解.通过信息素的正反馈作用，最后收敛到最优解.本文提出求解TALBP的改进蚁群算法包括4个主要内容：构造任务排列序列、改进的信息素搜索规则、启发式分配规则产生解的具体分配方案、信息素更新规则.2.2 构造任务排列序列先产生一列仅考虑任务先后约束关系的排列，即所有装配任务的一个排列序列. 随后用启发式分配规则调用此排列，并产生一个完整的双边工位分配方案，即一个可行解.为较快形成仅考虑先后约束关系的排列，采用候选任务集方法，仅在可选任务列表中进行任务选择，以减少问题的搜索空间，提高搜索速度.
考虑任务的先后约束关系，若一个未分配任务i的所有前序任务都已分配，则任务i是可选任务. 再考虑优先顺序约束和节拍约束，在任务排列序列中确定当前位置的可选任务集合，即候选任务集合Nj.
蚂蚁在访问每个序列位置时，都将面对一个可选任务集合Nj，蚂蚁需根据每项任务的选择概率选择一项任务，并进入此排列的下一个位置，直至访问整个序列完毕.图3表示图2所示问题的一个任务排列序列，图3中数字表示任务编号，字母代表任务操作偏向性. IE3R2E4L7E5R6L8R9L
图3一个完整的任务排列序列
Fig.3A full task sequence of assignment
2.3 改进的信息素搜索规则在任务序列构造过程中，蚂蚁每周游一次即构造出一个完整任务排列序列.构造出最优解所对应任务序列的蚂蚁在所经路径上释放信息素，以吸引后续蚂蚁跟随.基本蚁群算法在寻优过程中，易受早期发现的较好解的影响而陷入局部最优.
为避免算法搜索停滞现象并保持其搜索范围，即在“利用”信息素的同时保持较大的随机性，本文借鉴了文献[13]的改进信息素规则，即增加一个随机搜索以避免陷入局部最优，综合考虑了利用现有信息和随机搜索两种规则，构造出如下2种方式的混合搜索机制：
Pij=∑jh=1τihαηβi∑s∈Nj∑jh=1τshαηβs，0≤r≤r1，
随机选择i∈Nj， r1
τih为任务i分配到位置h的信息素；
r为（0， 1）之间的随机数；
r1为用户定义的参数，满足0
α、 β为决定信息素强度和启发式信息相对重要性的参数；
ηi为任务i的启发式信息，选取该任务的位置权重wP i作为启发式信息：
ηi=wP i=ti+∑j∈Fitj，i=1，2，…，N，（7）
式中： Fi为任务i的后继任务集合.
启发式规则采用了位置权重，综合考虑了作业时间和后续作业数，是2种规则的结合.在该启发式规则的指引下，对后续任务较多且作业时间较长的任务优先分配的概率更大.
根据式（6），按照概率选择使用2个策略中的某个规则，从候选任务集Nj中选择一项任务：
（1） 利用.若随机数r满足0≤r≤r1，则以概率Pij从候选任务集Nj中选择一项任务.
（2） 随机选择.若随机数r满足r1
（1） 开启新工位，并记录工位数.
（2） 检查任务序列q处任务是否满足左右工位任一边的节拍约束，转步骤（3）.
（3） 任务为L型或R型进入步骤（4），为E型进入步骤（5）.
（4） 查找是否有处于同一工位的紧前任务，是则进入步骤（4.1），否则进入步骤（4.2）.
（4.1） 找出同一工位中所有紧前任务的最晚结束时刻，并与此边结束时刻对比，选择较大者与序列q处任务装配时间相加，判断是否满足节拍约束.若满足令q=q+1，并更新左边工位（当为L型任务时）或右边工位（当为R型任务时）的结束时刻，转步骤（6），否则转步骤（1）.
（4.2） 查看是否满足节拍约束，若满足令q=q+1，并更新左边工位（当为L型任务时）或右边工位（当为R型任务时）的结束时刻，转步骤（6），否则转步骤（1）.
（5） 查找是否有处于同一工位的紧前任务，若有转步骤（5.1），否则转步骤（5.2）.
（5.1） 查找处于同一工位中紧前任务的最晚结束时刻，判断是否满足节拍约束，若满足令q=q+1，并且放入同一边，并更新此边工位结束时刻，转步骤（6），否则返回步骤（1）开启新的工位.
（5.2） 在左右两边中选择能使其最早开始的一边，若左右两边结束时刻相同，则随机选择一边，更新此边结束时刻，转步骤（6）.
（6） 查看任务是否全部分配完毕，若是转步骤（7），否则返回步骤（2）.
（7） 记录此任务排列的工位数量，作为适应度值储存，至此任务序列分配完毕.2.5 信息素更新规则局部信息素更新，当蚂蚁将任务i分配到序列位置j，边ij上的信息素τij按式（8）进行更新，
τij←（1-ρ1）τij+ρ1τ0，（8）
式中： ρ1为局部信息素蒸发系数， 0<ρ1<1；
τ0为初始化信息素的值（一个很小的初始输入），
τ0=1NK*，K*=1C∑Ni=1ti.
当构建了一个完整解后，各任务至序列位置之间的信息素均按如下规则进行信息素全局更新，
τij←（1-ρ2）τij+ρ2Δτij，（9）
式中： ρ2为全局信息素蒸发系数， 0<ρ2<1；
Δτij=1Lgb，当前最优分配方案包含边（i，j），
0，否则，
式中： Lgb为当前最优分配序列（方案）所需的工作站数.3 算法测试与分析本文采用MATLAB7.8对此改进蚁群算法（pACO）与普通蚁群算法（ACO）分别编写了实验程序.在处理器为e5300、主频2.6 GHz、内存2.0 GB的硬件环境下，进行了算法测试.分别对Lee、Kim和Bartholdi双边装配线平衡问题进行求解，问题规模为P9、P12、P24、P65、P148和P205. 普通蚁群算法与改进蚁群算法采用相同参数设置： α=1， β=2， ρ1=0.1， ρ2=0.9， r=0.9.
设蚂蚁数为60、迭代次数为20，对所测试问题能找到大部分最优解.引用文献[9]中的禁忌搜索（tabu search， TS）作为对比算例，表1给出了30个测试问题的测试结果及其对比.表1中， N为问题的任务规模， C为节拍时间， ACO为普通蚁群算法， pACO为本文提出的改进蚁群算法. 表1测试结果及其对比
Tab.1Performance comparison for three algorithms
问题NC
/smmin
/个ACO
/个TS
/个pACO
/个Kim93333394333395222296222212533331263333127222212822222420444424253333243033332435232324402222Lee653818888654357777654906666655445665Bartholdi1483578988148408787714845967661485106666Lee2051 322111111112051 510910992051 69988982051 88888882052 07777772052 26677772052 45466662052 64356652052 8325565
当求解LeeP65问题的节拍时间为490 s时，在蚂蚁数为60条件下，采用普通蚁群算法与改进蚁群算法分别运算10次. 普通蚁群算法平均在第7代找到最优解，而改进蚁群算法在第2代找到最优解，改进蚁群算法平均比普通蚁群算法可更快收敛至最优解.图4为改进蚁群算法与普通蚁群算法迭代收敛的对比.
分析表1中数据，在30个测试算例中，普通蚁群算法共求得23个最优解；禁忌搜索算法共求得26个最优解；本文的改进蚁群算法求得29个最优解，用时最长284.69 s，并在较大规模问题（LeeP205）的求解中有显著优势.从文献[9]知， TSA求得26个最优解.可见，由于采用改进的信息素搜索规则和改进的全局信息素更新规则等改进措施，相对普通蚁群算法、TSA算法，改进蚁群算法能对更大规模问题求得最优解.
图4LeeP65迭代收敛对比
Fig.4The convergent iterative comparison for LeeP65 4算法工程应用对某公司的微型车双边装配线进行规划设计，经实际调研，将该双边装配线操作任务合并为85项.任务优先关系如图5～7所示，为简化图的复杂度拆分成3个图显示.可综合图5～7得到任务之间的优先关系.
图5优先顺序图（Ⅰ）
Fig.5Precedence diagram（Ⅰ）
表2（第1栏为任务编号）为任务的操作时间、操作方位汇总（为节省篇幅，省略了操作名称及说明）.采用本文的改进蚁群算法，对此双边装配线进行优化设计，参数设置为α=1， β=2， ρ1=0.1， ρ2=0.9， r=0.9，蚂蚁数目为40，迭代次数为20. 普通蚁群算法和改进蚁群算法在相同参数设置下各运算10次求解该实例.当节拍时间为620 s时，优化结果（表3）的平衡率为87.07%，平滑系数为92.10，平衡效果较好.
图6优先顺序图（Ⅱ）
Fig.6Precedence diagram（Ⅱ）图7优先顺序图（Ⅲ）
Fig.7Precedence diagram（Ⅲ）
表2任务操作时间及操作方位
Tab.2Operation time and position of taskss
编号t/方位编号t/方位编号t/方位编号t/方位175/R2370/L4573/L67213/R278/E2474/L4675/L6870/L3150/E2573/R47143/R6971/R473/E2673/R4874/L7070/L575/L2773/L4973/L7173/R675/R2875/L5071/R7270/L767/L2973/R5171/R7370/R875/L3073/R52150/L7470/L975/R3175/L5375/R7570/L10150/L32108/R5475/L7673/L1175/E3373/L5571/R7770/L1271/E3470/L5673/L78130/R1369/E3567/R5771/R7975/L1474/R3667/L58146/R80106/R1575/L3770/R5971/L81106/L1675/R3870/L6071/L8269/R1768/E39126/R6167/L8375/R1875/L40126/L62286/R8471/R1973/E4170/L6373/R8567/L2075/E4273/E64146/L2171/E4373/R65210/R2267/L4475/R66286/L注：—/—表示作业时间/操作方位.
表3双边装配线实例优化结果
Tab.3Optimal solution for the realworld example of twosided assembly line
位置工位任务分配情况1左边79（75，150）， 4（150，223）， 75（223，293），74（293，363），48（363，437）， 3（437，587）右边1（0，75）， 2（75，153）， 78（153，383），67（283，496）2左边7（0，67），5（67，142），49（143，216），10（216，366），68（366，436）， 22（436，503）右边47（0，143），9（143，218），65（218，428），11（428，503），73（503，573）3左边52（0，150），41（150，220），54（220，295），18（295，370），64（370，516），70（516，586）右边13（0，69），32（69，177），19（177，250），26（250，323），25（323，396），58（396，542），51（542，613）4左边23（0，70），27（70，143），8（143，218），28（218，293），66（293，579）右边71（0，73）， 6（73，148）， 16（148，223），63（223，296）， 62（296，582）5左边60（75，146），59（146，217），45（217，290），33（290，363），34（363，433），15（433，508），21（508，579）右边55（0，71），14（75，149），29（149，222），17（222，290），30（290，363），43（363，436），44（436，511），84（511，582）6左边56（0，73），24（73，147），72（147，217），76（217，290），46（290，365），61（365，432），77（432，502），36（502，569）右边55（0，71），57（147，218），39（218，344），35（344，411），80（502，608）7左边40（0，126），42（126，199），31（199，274），12（274，345），81（345，451），38（451，521），85（521，588）右边20（0，75），50（75，146），82（199，268），69（268，339），37（339，409），83（409，484）注：—（—，—）表示任务序号（开始作业时间，完成作业时间），作业时间单位： s. 改进蚁群算法平均在迭代次数17.2次时找到的总位置数为7的较优解，而普通蚁群算法针对该实例则仅有1次求得的总位置数为7的解.同时，在算法求解速度上，改进蚁群算法平均耗时21.01 s，而普通蚁群算法则耗时30.15 s，节省了9.14 s，计算效率提高了30.3%.由此可见，本文提出的改进蚁群算法较普通蚁群算法在求解质量和求解速度方面均表现出更优越的性能. 5 结束语针对TALBP问题提出了一种改进蚁群算法，提出一种新的启发式分配规则以产生可行解.采用在任务与任务序列位置之间释放信息素的策略，并引入综合信息素搜索规则与全局信息素更新策略，可有效脱离陷入局部最优解.通过大量不同规模问题算例，对比普通蚁群算法和禁忌搜索算法，改进蚁群算法对不同规模问题的求解质量和速度更优，验证了该算法的有效性.应用改进蚁群算法求解某汽车双边装配线任务分配问题，取得了良好的求解效果.
下一步研究可将ACO算法拓展应用至更接近实际的TALBP，例如，考虑复杂区域约束、不确定环境下存在多种随机因素等情形下的TALBP.参考文献：[1]LEE T O， KIM Y， KIM Y K. Twosided assembly line balancing to maximize work relatedness and slackness[J]. Computers and Industrial Engineering， 2001， 40（3）： 273292.
[2]SCHOLL A， BECKER C. Stateoftheart exact and heuristic solution procedures for simple assembly line balancing[J]. European Journal of Operational Research， 2006， 168（3）： 666693.
[3]OZCAN U， TOKLU B. Multiplecriteria decisionmaking in twosided assembly line balancing： a goal programming and a fuzzy goal programming models[J]. Computers & Operations Research， 2009， 36（6）： 19551965.
[4]OZCAN U， TOKLU B. Balancing twosided assembly lines with sequencedependent setup times[J]. International Journal of Production Research， 2010， 48（18）： 53635383.
[5]ZHANG Zeqiang， MURRAY C C. A corrected formulation for the double row layout problem[J]. International Journal of Production Research， 2012， 50（15）： 42204223.
[6]宋林，张则强，程文明，等. 随机型双边装配线平衡问题的一种启发式算法[J]. 工业工程，2011，14（4）： 129134.
SONG Lin， ZHANG Zeqiang， CHENG Wenming， et al. Heuristic for twosided stochastic assembly line balancing[J]. Industrial Engineering Journal， 2011， 14（4）： 129134
[7]KIM Y K， SONG W S， KIM J H. A mathematical model and a genetic algorithm for twosided assembly line balancing[J]. Computers & Operations Research， 2009， 36（3）： 853865.
[8]吴尔飞，金烨，续爱民，等. 基于改进遗传算法的双边装配线平衡[J]. 计算机集成制造系统，2007，13（2）： 268274.
WU Erfei， JIN Ye， XU Aimin， et al. Twosided assembly line balancing based on modified genetic algorithm[J]. Computer Integrated Manufacturing Systems， 2007， 13（2）： 268274.
[9]ZCAN U， TOKLU B. A tabu search algorithm for twosided assembly line balancing[J]. The International Journal of Advanced Manufacturing Technology， 2009， 43（7/8）： 822829.
[10]ZBAKIR L， TAPKAN P. Bee colony intelligence in zone constrained twosided assembly line balancing problem[J]. Expert Systems with Applications， 2011， 38（9）： 1194711957.
[11]DORIGO M， STTZLE T. Ant colony optimization： overview and recent advances[M]∥GENDREAU M， POTVIN J Y. Handbook of Metaheuristics. [S. l.]： Springer， 2010： 227263. [12]刘洁，刘丹，何彦锋. 带中转设施的垃圾收集VRP的改进蚁群算法[J]. 西南交通大学学报，2011，46（2）： 333339.
LIU Jie， LIU Dan， HE Yanfeng. Improved ant colony system algorithm for waste collection vehicle routing problem[J]. Journal of Southwest Jiaotong University， 2011， 46（2）： 333339.
[13]张则强，程文明，钟斌，等. 求解装配线平衡问题的一种改进蚁群算法[J]. 计算机集成制造系统，2007，13（8）： 16321638.
ZHANG Zeqiang， CHENG Wenming， ZHONG Bin， et al. Improved ant colony optimization for assembly line balancing problem[J]. Computer Integrated Manufacturing Systems， 2007， 13（8）： 16321638.
[14]张则强，程文明，钟斌，等. 混合品种装配线平衡问题的一种混合搜索机制的蚁群算法[J]. 机械工程学报，2009，45（5）： 95101.
ZHANG Zeqiang， CHENG Wenming， ZHONG Bin， et al. Hybrid behavior ant colony optimization for mixedmodel assembly line balancing problem[J]. Journal of Mechanical Engineering， 2009， 45（5）： 95101.
[15]SIMARIA A S， VILARINHO P M. 2ANTBAL： an ant colony optimization algorithm for balancing twosided assembly lines[J]. Computers & Industrial Engineering， 2009， 56（2）： 489506.
[16]DORIGO M， BLUM C. Ant colony optimization theory： a survey[J]. Theoretical Computer Science， 2005， 344（2/3）： 243278.