第13卷第6期工业工程2010年12月December 2010 Industrial Engineering Journal 运用改进蚁群算法求解直线型和U型装配线平衡问题查舰，徐学军，余建军，宋莉波(华南理工大学工商管理学院，广东广州51侃40)摘要:针对直线型和U型装配线第一类平衡问题，提出-种基于最优成分信息素更新规则的改进蚁群算法。算法在任务和工作站之间释放信息素，综合利用多种优先权规则作为启发式信息，在解构造中加入下界检查，在全局信息素更新中仅对本次迭代最优解中的最优成分释放信息素，既保留了最优解信息，又增加了探索更优解可能。仿真对比实验表明了该算法的有效性。关键词:装配线平衡问题;蚁群算法;直线型装配线;U型装配线中图分类号:TH181;TP301. 6 文献标识码:A文章编号:1∞7 -7375 (2010) 06-∞76-06 A Modified Ant Colony Algorithm for Simple and U- Shaped Assembly Line Balancing Zha Jing, Xu Xue-jun, Yu Jian才un，Song Li-bo (School of Business Administration, South China Un iversity of Technology ,Guangzhou 510640 , China) Abstract: Simple (straight line) and U- shaped assembly line balancing problem (ALBP) is discussed. A modified ant colony algorithm is presented for it. By the algorithm, pheromone is defined as the information on the task and assigned workstation to combine task sequencing and task assignment to workstations. Sev›eral priority rules are integrated as heuristic information for ant moving. 1ρwer bound calculation is added so as to quickly obtain a good initial solution. During global pheromone updating, pheromone about one task and assigned workstation is allowed to be deposited if the assignment is contained in the optimal solution and the workstation fully operates. In this w町，itcan search more solutions without losing optimal informa›tion. Comparison is made by simulation and it shows that the solution obtained by using the proposed algo›rithm is better than that obtained by existing algorithms, especially for large-scale ALBPs. Key words: assembly line balancing problem (ALBP); ant colony algorithm; simple assembly line; U -shaped assembly line 装配线平衡问题(AssemblyLine Balancing Prob›最优化生产节拍;3)ALBP-E，工作站数和节拍可变lem，ALBP)是进行装配线设计时需要考虑的核心问情况下，最优化生产线效率[1]。本文研究的是单一题，对于提高生产效率至关重要。装配线平衡问题产品的直线型和U型装配线第一类平衡问题按照不同的标准可划分为不同的类别。按照装配线(SALBP-1 ,UALBP-1 )。的布局不同，可分为直线型和U型。按照装配产品装配线平衡问题与装箱问题类似，是NP-hard问式样的多少，可分为单一产品(singleproduct)、多产题。由于加人了任务优先顺序约束，因此比装箱问品(multi-model)和混流(mixed-model)生产。按照优题更复杂。对于一个有n个作业元素和r个优先关化目标的不同，可分为3类:1)ALBP-1 ，已知装配线系的ALBP来说，存在n!/2'种可能的作业顺序。节拍，最优化工作站数;2)ALBP-11 ，已知工作站数，随着n的增加，计算规模呈几何级数增加，确定性算收稿日期:2010-01-11 基金项目:国家自然科学基金资助项目(70872031);教育部"新世纪优秀人才支持计划"资助项目(NCET . ) ;教育部人文社科青年基金资助项目(07JC63∞38);广州市社会科学规划课题资助项目(08ψ4)作者简介:查舰(1978-)，女，湖北省人，博士研究生，主要研究方向为工业工程、生产运作管理.
第6期查舰，徐学军，余建军，等:运用改进蚁群算法求解直线型和U型装配线平衡问题77 法很难甚至是不可能在合理的时间内计算出精确作站数最少。解，因此各种启发式算法被相继提出。现有的启发问题包含的假设条件为:式算法[2]主要是基于各种优先权规则的贪婪式建构1 )装配线由若干个工作站组成，每个工作站按算法，如最大阶位权重法(RPW)、最大作业时间法照固定的节拍(cycletime)执行1个或多个任务等。这类方法以某种确定的规则进行任务的分(ta配sk，) ，节拍由市场需求所决定;虽然计算简单快捷，但求解精度不高。随着人工智2)装配线上生产同一种产品;能的不断发展，禁忌搜索、模拟退火、遗传算法等元3)工作站串行排列，不存在并行任务或并行工启发式算法被用于求解各类装配线平衡问题。作站而;目前蚁群算法的应用相对4较)少任。务的执行顺序服从由工艺决定的优先顺作为模仿蚂蚁觅食行为发序，展只起存来在的一种蚁确群定算的优知帧序，不存在其它约束条件;法[叫，是一种分布式的带有构造性特征的随机搜索5)任务的执行时间是确定的，不随加工顺序而方法改，变其;用于求解装配线平衡问题时，直接从构造可6)任务是最小不可行分解的出自发然，作方业便单处元理，复只杂能约分束条件，易与各种优先权规则配相到结一合个工，作具站有完良成好;的应用前景。Bautista和Pereira[5]首7)先不应考用虑工蚂作蚁站算之法间求设解备S和AL人BP员-配备的差异，1 ，对267一个任务可以被分配到任何一个工作站个。问题进行测试，182个问题找到最优解。Sima巾符号约定如下:i，j和为任Vil务ari编nh号o[6];利k为用工两作组站蚂编蚁并行计算求解了双边装号;n为任务个数，同时也为工作站数的上界;C为生配线平衡问题。张则强[7-8]提出了一种带信息素总产节拍;t，为任务的作业时间;P表示优先关系集合，合规则的蚁群算法求解单一产品和混流产品装配线例如(1，2)εP表示任务2必须要在任务1完成后平衡问题，AdilBaykasoglu和TurkayDereli[9]集成才能开始。COMSOAL、阶位权重法和蚁群算法求解了直线型和构建整数规划模型如下[10] U型装配线平衡问题。现有研究进行信息素更新时常采用两种方式，Min L Sko (1) 一是对蚂蚁找到的所有解都进行信息素蒸发和释放[叫，二是对找到的最优解的所有成分进行信息素s t Z~=1, 释放[7-9]。由于装配线第一类平衡问题存在非常多t分配方案对应相同工作站数的情况，这两种方式都LX'k，运CS，k(3) 不能很好地保留真正的当前最优解信息，因此很多L k(x-~，k)注0，(i，j)εP (4) 问题找不到最优解。Jk 本文针对装配线第一类平衡问题的特点，提出一种基于最优成分信息素更新规则决策变量的改进蚁群算法进行求解，算法在任务和工作站之S.[I, 表示第k个工作站分配有任务;间释放信息素，综合利用多种优先权规则作为启发klo, 表示第k个工作站没有分配任务。式信息，在解构造中加人下界检查，在全局信息素更r1 , 表示第i个任务分配到第k个工作站;新中仅对本次迭代最优解中的最优成分释放信息吨，表示第i个任务没有分配到如个工作站。素，既保留了最优解信息，又增加了探索更优解可式(1 )为目标函数，表示所需工作站数最少。约能。通过对测试问题的计算并与前人计算结果进行束条件(2)表示每个任务只能分配到一个工作站。对比，表明了算法的优越性。约束条件(3)表示分配有任务的工作站的总作业时间不能超过节拍要求，没有分配任务的工作站的作1 装配线平衡问题的数学模型业时间为0。约束条件(4)表示任务的分派要满足1. 1 SALBP-1的整数规划模型优先顺序的约束。第一类装配线平衡问题(SALBP-1 )是指将一 UALBP-1的整数规划模型系列任务按照工艺决定的优先顺序从前向后分配到U型装配线与传统的直线型布局相比具有更高直线型装配线的各个工作站，使得在每个工作的站柔的性和效率，因此越来越多的企业采用了这种布局方式。M作il业ten时be间rg总和和W不iji超ng过aa一rd定[11]节首拍次的提条出件U下型，需要的工
工业工程第13卷78 装配线第一类平衡问题(UALBP-1 ) 0 U型装配线的特点是人口和出口在相同的位置，U型线内的作业人员在执行完左边的任务后，再执行右边的任务，因此在分配任务时从前向后分配和从后向前分配可同时进行，没有紧前任务的任务分配到U型线的左臂，没有紧后任务的任务分配到U型线的右臂。如图1所示为某U型装配线分配方案。与直线型装配线平衡问题的整数规划模型相比，U型的不同之处在于约束条件(4)用式(5)和(6)替代。L k(X’k -X，k)运M凡，(i ，j)εP; (5) L k(X-X，k)运(1-M)y" (j,l) E Po (6) 1k M为一个大数，增加决策变量Or, 表示从前向后分配任务j;凡=b，表示从后向前分配任务j。圄2算法流程固当任务较少时，利用Lingo、Matlab等工具求解蚁群算法是-种分布式算法，多只蚂蚁搜索解整数规划模型可得最优解。但是当任务较多时，则空间，蚂蚁之间通过信息素进行沟通。现有研究一需要寻求其他算法。般在作业任务和作业分配序列的相对位置或绝对位置之间释放信息素，解的建立过程是对任务的一个2 求解装配线平衡问题的改进蚁群算法排序过程。但是对于装配线平衡问题而言，两个不蚁群算法用于求解装配线平衡问题具有良好的同的排序序列作和臂'对应的可能是同一种分配方应用前景。但是标准的蚁群算法不能直接应用，还案，因此本算法在建立解的过程中同时考虑任务的需要根据研究问题的特点作适当的调整和改进。如排序和分派到工作站，选择在任务和工作站之间释图2所示为改进算法的基本流程。以下进一步对算放信息素。信息素T，k代表了任务i被分配到工作站法实现作详细说明。k的期望。T，k值较高意味着较多的前代蚂蚁选择将2. 1 构建固和信息素任务i分配到工作站KJ受T，k的影响当前蚂蚁会以较对构建图Gc(/，L)和信息素T，k的定义是蚁群算高的概率作出同样的选择。正是采用了这种方式使法设计的第一步。得在进行全局信息素更新时能够辨识出最优成分。在本问题对应的构建图中，定义I为作业任务 启发式信息和优先权规则和所需工作站的集合。其中所需工作站数是决策变除信息素外，启发式信息是影响蚂蚁移动选择量，事先未知，可取上界值，即令工作站数=任务的的另一重要因素。标准蚁群算法存在的问题之一是个数。L为任务与工作站之间的连接所构成的集合。求解时间较长，尤其是初次找到一个较优解的时间人工蚂蚁在构建图上游走的过程代表了任务一一被较长。因此利用问题隐含的启发式信息帮助蚂蚁快分配到工作站的过程。当人工蚂蚁在构建图上完成速构建一个较优解是很有必要的。在求解装配线平-次周游(tour)，代表所有任务被分配到工作站，即衡问题时，现有的改进蚁群算法只使用阶位权重建立了问题的一个解。种优先权规则，即以任务i的阶位权重的大小作为启
第6期查舰，徐学军，余建军，等:运用改进蚁群算法求解直线型和U型装配线平衡问题79 发式信息影响蚂蚁的移动选择。事实上，除了阶位务才能被分配;对于U型装配线没有前序任务和没权重外，还存在多种优先权规则。这些规则各有其有后序任务的任务均可被分配。如果没有前序任最适范围。综合运用多种启发式信息，有助于蚂蚁务，说明此任务可以被分配到装配线的左臂。如果针对不同的问题都能快速构建较优解。没有后序任务，说明此任务可以被分配到装配线的在选择优先权规则时需兼顾算法的有效性和算右臂。只有满足上述3个约束条件的任务i才能被法的复杂性。经过比较，选择最长加工时间、最多紧添加进候选任务集合A。后任务个数、最多后继任务个数、最大阶位权重、最在STEP3中采用如式(7)所示的伪随机比例规则(3)选择任务i。大平均阶位权重这5种计算相对简单且有效的优先权规则。每个任务的优先权值pW，只在,I算J 法=运 ar行g电之aX[(1"'k)α(η，)β] ,q :s; qo; 初计算一次。在每只蚂蚁构建可行解之前，通过轮i{. (1"'k)α(η， )β(7) 盘赌的方式随机抽取一种优先权规则，在解构建过l12 :Pik =三[(1 "jk)α(ηI)ßJ ,q ;> qo。程中读取对应的PW，opW，作为静态启发式信息影响其中ηi代表启发式信息。为了消除量纲的影响，对蚂蚁的移动选择，pW值高的可分派任务以较j高的概pW，作归一化后再赋值给吼。参数α和β决定了信率优先被分派到当前工作站。息素和启发式信息的相对影响力。α=0时只有启对于U型装配线平衡问题而言，与直线型布发式信息起作用，算法退化为基于优先权规则的贪局不同的是存在从前向后和从后向前两种搜索婪算法。β=0时分配任务的选择只依赖历史信息，方向，每个任务对应存在前向和后向两种权值启发式信息将不起作用。q为[0，1]区间上的一个(pW,(f) ，PW，(b))'取最大值作为其优先权重，即pW，= 随机数，参数qo为控制任务选择时使用的策略。当m缸(pWj(f),PWj(b) )。q运qo时完全利用信息素所代表的搜索经验和启发 可行解的构建式信息，选择(η)α(ηI)ß值最大的任务分配到当前针对装配线平衡问题的特点，设计单只蚂蚁构工作站。否则按照P品的大小进行有偏好的搜索。建可行解的步骤如下。为了避免对无效解的构建，提高迭代效率，在STEP1 :创建第1个工作站k= 1，当前工作站kSTEP4中，每当一个工作站分配完成后就进行下界的空闲时间节拍idletime=节拍C，初始化tabu，tabu rem(LB)检查。如式(8)，T是尚未被分配的任务集用于保存当前已分配任务的信息。合，如果当前已分配工作站k与LB之和大于已找到STEP2:建立符合约束条件的候选任务集合A。的最优解工作站数，说明不管后续如何分配都只能STEP3:如果A非空，采用伪随机比例规则从~A找到比当前最优解更差的解，因此终止当前解构造。中选择一个任务i分配到当前工作站k，将任务i添加到tabu，更新未分配任务的前序任务和后序任务(8) B =用信息，更新工作站k的空闲时间idletime=i dletime -t，对~进行局部信息素更新(更新规则见)，转iIX丁代表大于等于z的最小整数。STEP2;如果A为空，需要进行进一步判断，转 信息素更新规则STEP4。信息素更新策略分为全局信息素更新和局部信STEP4:如果还存在没有被分配的任务，说明需息素更新两种。要开新工作站，令k=k+1，重置工作站k的空闲时局部信息素更新体现了算法的负反馈精神。在间idletime=节拍C，进行下界检查;如果构建的解肯蚂蚁构建解的过程中，蚂蚁每移动一步，即分配任务定比已找到的最优解差，停止解构建，子程序结束，i到工作站k时，该路径上的信息素以一定比例挥否则转STEP1;如果所有任务已经分配，说明已经构发，使后面的蚂蚁选中该路径的概率减少，探索其他建一个完整解，子程序结束。路径的可能性增加。局部信息素更新规则(3)如式需要说明的是，在STEP2中建立候选任务集合(9)所示:A的条件包括:1 )未被分配的任务，即没有加入tabuT此(t)=(1-ρ)T昨(t-1)+PJX1"oo(9) 的任务。2)节拍约束，被分配任务的加工时间小于O:S;PJ运1代表局部信息素挥发速率，1"0是信息当前工作站空闲时间，即t:s; idletime3)优先关系素的初始值。io 约束，对于直线型装配线只有不存在前全序局任信务息的素任更新体现了算法的正反馈精神，是
工业工程第l3卷80 对蚂蚁找到的最优解实施额外奖励的一种手段，以问题的标准蚁群算法的建议，结合多种组合实验结鼓励后面的蚂蚁遵循此最优路径。标准蚁群算法在果，最终设置如下:α=1，β=2，ρ1 =，ρ2 = O. l,qo 完成一次迭代后，对最优解上的所有(i，k)边释放信=，信息素初值To=lI(nxm*)，n为任务数，息素。m事为所需工作站下界值，蚂蚁数=20。通过仿真实验发现，装配线第一类平衡问题存Gunther问题的任务数为35，总任务时间为在非常多分配方案对应工作站个数相同的情况，即483，任务优先关系图如图3所示，设定节拍为41。蚂蚁找到的当前最优解存在多个。如果只针对第一算法运行中目标函数的变化情况如图4所示。在多次找到的最优解进行全局信息素更新，会遗漏其它种启发式规则的帮助下，算法在第一代即获得很好最优解信息，算法容易陷入局部最优。如果对找到的初始解:15和14，分别在第9代和第4代跳出局的所有最优解的所有成分均进行全局信息素更新，部最优，找到了问题的最优解:14和12。计算时间信息素会累积过多，多次迭代后很多信息素值趋同，均小于1s。不能保留真正的最优信息。对于一个分配方案而言，如果一个工作站总的作业时间等于生产设定的节拍时间，说明这个工作站没有空闲时间，已达到最优;如果没有空闲时间的工作站数越多，需要的工作站可能越少。因此，本改进算法考虑只对本次迭代最优解上的最优成分释放信息素，如果本次迭代没有找到最优解，则选择至今最优解。更新规则如下。1 )如果边(i，k)为最优解gb的成分，并且工作国3Gunther问题的任务优先圄站为满负荷工作站，则在每次迭代后在边(i，k)释放信息素如式(10)所示:16 ßTTœc(t) =( 1-P2)T’k(t -1) +ρ2沪)(t-l)o(10) ~、器14O运P2运1代表全局信息素释放速率，ATJfb)(t-f总jg …飞1) =1/j协)(t) ，/阱)(t)是最优解gb所需的工作站数。DlI 12 ·直线型2)如果边(i，k)不是最优解gb的成分，或者是.u型最优解的成分但工作站k不是满负荷工作站，在每10 246 8 10 次迭代后保持信息素不变，T以t)=Tik(t-l)。迭代次数这样的改变使得可以在保留最优工作站分配信圄4算法运行情况息的情况下，让后续的蚂蚁探索更多的解，有效避免运算结果见表1。算法的"早熟"。表1Gunther问题直线型装配线和U型装配线任务分配方案 算法的终止工作站序号直线型U型当算法的迭代次数达到预设值或者算法找的解1,2,5,17 1,2,5,17 已经为问题的下界时，算法终止。2 3,6,7,8 3,10,29,34,35 3 10,14 28 3 仿真实验4 4,15 32,33 5 16 12,27,31 为了检验算法的有效性，使用Talbot等问]和6 12,18 23,24 Scholl[叫问题集对算法进行仿真实验。算法采用7 9,19 6,7,11 ,14 编写，在 T2250 CPU ，512M内存8 20,21,25 8,13,18,22 9 11 ,26 4,15 的计算机上运行。10 23,24 16,25,26 3. 1 实例分析11 13,27,30,31,32,34 9,19 首先以问题集中的Gunther问题为例说明改进12 28 20,21,30 算法的运行情况。13 33 算法参数的选择参考了Dorigo等[3]对求解TSP14 29,35
第6期查舰，徐学军，余建军，等:运用改进蚁群算法求解直线型和U型装配线平衡问题81 对比实验查;为了让蚂蚁搜索更多的解，避免"早熟"，采取了接着对问题集中的各种规模的问题进行测试。只对最优解的最优成分释放信息素的信息素更新策测试结果与阶位权重法、文献[7]的改进蚁群算法进略。大量仿真对比实验表明了算法的有效性。行对比，见表2。表中第4、7栏为阶位权重法计算结目前将蚁群算法应用于装配线平衡问题的研究果，第5，8栏为文献[7]所提改进蚁群算法的计算结相对较少。下一步的研究可以考虑将改进蚁群算法果，第6、9栏为本文所提改进蚁群算法的计算结果。拓展到其他类型的装配线平衡问题中去，例如装配表2不同规模问题测试结果对比1)线平衡第二类问题、多目标装配线平衡问题、带有大直线型U型量复杂约束限制的装配线平衡问题、混型装配线的问题n c 酬文献[7JIA'ω丽面7JIACO 平衡和排序的协同优化问题等，将具有非常重要的Mertens 7 10 3 33333 理论意义和实践意义。Bowan 8 20 5 5 5 544 Jaeschke 9 8 6 66666 参考文献:Jackson 11 7 8 8 8 8 7 7 [ 1 J Boysen N, Fliedner M, Scholl A. A classification of assembly Mansoor 11 62 4 3 343 3 line balancing problems [J J . European Joumal of Operational Mitchell 21 21 6 5 5 655 Research，2∞'7，183(2) :674-693. Rosenberg 25 14 10 10 10 10 10 9" [2 J Ponnambalam S G, Aravindan P, Mogileeswar Naidu G. A Heskiaoff 28 216 5 5 5 5 5 5 comp缸ativeevaluation of assembly line balancing heuristics Buxey 8 8929 941 98 事[J J . Intemational Joumal of Advanced Manufacturing Tech›Sa町er30 30 12 12 12 12 12 11 " nology, 1999 ,15(8) :577-586. Lutzl 32 1 572 11 10 10 10 10 10 [ 3 J Dorigo M, Stutzle T. Ant ColonyG uOntphteirm ization [ M J . MA: MIT 35 41 16 14 14 14 14 12 " K&Wester 45 92 7 66766 Press ，2∞4. Hahn 53 2∞4 8 8 8 8 8 8 [ 4 J Dorigo M, Maniezzo V, Colomi A. The ant system: optimiza›句句3，9"&，句l'n31·Ym'A1LI'句o3o'7sI"aA咱TAJ句TMI句mALU1句a，缸a句af鸣，"咱IAU........ Warnecke 58 54 33 33 32" 33 tion by a colony of cooperating agents [ J J . IEEE Transactions Tonge 70 176 22 21 21 21 on systems ,man,and cyberetics-Part B, 1996 ,26(1) : 1-13. Wee-mag 39 38审75 4045 41 [ 5 J Bautista J ,Pereira J. Ant algorithms for assembly line balan›丛TAU--q&句，句300'lArcusl 83 5 853 14 14 14 14 cing//Proceedings of the 3rd International Workshop, ANTS Lutz2 89 11 52 51 49" 51 2∞2 [. C J . Berlin, German: Spinger-Verlag ，2∞2:65扫.4Lu凶8983 21 22 21 21 鸣，&句，旬'IA[6 J Simaria A S, Vilarinho PM. 2-ANTBAL: An ant colony opti›M咏h叫ee94 201 23 23 23 22 mization algorithm for balancing two-sided assernbly lines [ J J . Arcus2 111 5 755 27 27 27 27 Computers & Industrial Engineeri吨，2∞9(56):489-506. B缸tholdi1148 470 13 13 13 13 丛丁TZJBartholdi2 148 93 48 49 47" 48 [7J张则强，程文明，钟斌，等.求解装配线平衡问题的一种改'3Scholl 297 1 422 51 52 50" 50 进蚁群算法[1].计算机集成制造系统，2腑，13 ( 8 ) : 1632-1638. 1) "表示本文算法的计算结果优于前两种算法。[8J张则强，程文明，钟斌，等.7昆合品种装配线平衡问题的一对比实验表明对于中小规模的直线型和U型装种j昆合搜索机制的蚁群算法[J].机械工程学报，2∞9，45配线问题，文献[7]的改进蚁群算法和本文的改进蚁(5) :95-101. 群算法都找到了问题的最优解，优于阶位权重法;对[9 J Adil Baykasoglu, Turkay Dereli. Simple and U- type assernbly 于较大规模的直线型和U型装配线平衡问题，本文line balancing by using an ant colony based algorithm [ J ] . 的改进蚁群算法优于文献[7J的改进蚁群算法和阶Mathematical and Computational Applications, 2∞9，14(1) : 1-12. 位权重法。[10J吴隆，余海明，吴援援.基于Lingo的汽车装配线建模与4 结论与展望平衡研究[JJ.工业工程与管理，2∞8，13(6):74-104. [ 11 J Miltenburg J, Wijngaard J.哑leU-line balancing problem 针对直线型和U型装配线第一类平衡问题的特[JJ. Management Science, 1994 ,40(10) : 1378-1388. 点提出了一种改进蚁群算法。为在解构造中同时考[ 12] Talbot F B, Patterson J H, Gehrlein W V. A comp缸atIvee›虑排序和分配工作站，算法在任务和工作站之间释valuation of heuristic line balancing techniques [ J J. Man›放信息素;为了得到较好的初始解，算法集成了多种agement Science, 1986 (32) :430454. 基于优先权规则的启发式算法;为了提早结束对劣[B J Scholl A. Balancing and sequencing of assembly lines[ M J . 解的构造，提高算法效率，在解构造中引入了下界检、2nded. Heidelberg, Germany: Physica-Verlag, 1999.
