求解双边装配线第二类平衡问题的一种蚁群算法*

胡俊逸， 张则强，金初云

(1.浙江交通职业技术学院 机电与航空学院，杭州 311112；2.西南交通大学，机械工程学院，成都 610031)



求解双边装配线第二类平衡问题的一种蚁群算法*

胡俊逸1， 张则强2，金初云1

(1.浙江交通职业技术学院 机电与航空学院，杭州 311112；2.西南交通大学，机械工程学院，成都 610031)

摘要：双边装配线在任务分配过程中，除考虑任务先后关系约束外还需兼顾任务操作方位约束及任务操作的并行性要求。针对双边装配线第二类平衡问题提出了数学模型并构建了一种蚁群算法。此算法采用蚁群综合搜索规则、启发式任务分配规则构造一个可行解，对最优解的搜索过程提出了可行的规划方案。最后，通过为某型装载机的实例提出多组较好的平衡方案，验证了此算法的有效性。

关键词：双边装配线; 平衡; 蚁群算法

0引言

在汽车、工程机械产业，因产品尺寸大、装配复杂，难以采用单边生产线，故双边装配线得以广泛应用。双边装配线平衡问题 (Two-sided Assembly Lines Balancing Problem, TALBP) 因此受到较多关注。双边装配线平衡问题分为两类：第一类平衡问题为在限定节拍时间的前提下，尽量缩减装配线长度；第二类平衡问题为在限定装配线成对工位数目的情况下，尽量缩减工位的节拍。生产实际中为降低产品的生产周期，常以第二类问题为优化目标。

对于双边装配线第一类问题，已有较多学者进行过研究：Bartholdi[1]首次提出双边装配线的概念，并针对第一类问题提出了一种基于First Fit规则的启发式算法；Kim[2]和Lee[3]的团队针对第一类问题提出了遗传算法，并加入成组分派策略以优化任务之间的相关性指标；Simaria[4]和Baykasoglu[5]运用蚁群优化算法求解第一类问题，其中Baykasoglu首次引入区域约束的概念，并提出解决附带此特殊条件的蚁群算法；吴尔飞与胡小锋提出解决第一类问题的精确解法[6]。

目前，较少有学者对第二类平衡问题(TALBP-Ⅱ)进行研究[7-8]：吴而飞[8]首次提出一种基于任务归组的遗传算法，并采用此算法对某装载机生产线进行节拍优化，取得较好效果；Kim[9]采用类似的遗传编码策略，并对目前双边装配线引用较多的算例进行节拍优化，算法适应性较好。可见，目前国内外对此类问题研究中解决方法相似性高。蚁群算法在单边装配线的优化问题中通过采用综合信息素搜索规则[10]或加入自适应搜索策略[11]，都展现较优性能。而目前还未有针对双边装配线第二类平衡问题(TALBP-Ⅱ)的蚁群算法公开文献。

本文针对制造企业中普遍存在的双边装配线第二类平衡问题，提出一种蚁群算法，采用蚁群综合搜索规则选择任务，采取任务分配规则分配任务，对蚁群整体搜索进程提出了可行的规划方案。引用实际算例进行测试，具有较好效果。

1双边装配线简介

如图1所示，在双边装配线中，两侧工位中的不同操作任务可以同时展开。工位1和2由于相互面对，故称为一对成对工位(mated-station)，同时，工位1又可称为工位2的伴随工位(companion)，其余工位关系类似。在双边装配线中，两个相互之间无任何先后约束关系的操作任务可同时进行作业，从而相比于单边装配线更能节约时间。

图1　双边装配线

图2为某双边装配线的操作任务之间先后约束关系的网络图，圆内标示任务序号，圆外标示任务操作时间。图3为此简单问题的所有操作任务在双边工位中的排列方案，并可视为甘特图。黑色部分标示成对工位之间的操作任务由于图2所示的先后约束关系而产生的延迟与空余。可见双边装配线的规划问题比单边装配线更为复杂。

图2　操作任务先后约束关系网络图

图3　双边装配线成对工位中的延迟与等待

2双边装配线第二类平衡问题

2.1双边装配线第二类平衡问题的数学模型

为方便表达，首先列出相关变量：I—任务集，I={1, 2, …,i,N}；ID—将任务按其操作方位分割为三类，D=L(左)、R(右)或E(两边)，IL/IR/IE分别表示必须在左侧、右侧装配的任务集合和可以在任意侧操作的任务集合；Ij、Ij′—工位j和j′上所分配的任务集；Tj、Rj—工位j的操作时间累计值及延迟时间累计值,同理Tj′、Rj′则表示工位j′的操作时间及延迟时间累计值；P(i)—任务i的所有前序任务集；S—所有前序任务集P(i)为空的任务i的集合，即可选任务集合；S′—集合S中满足当前工位节拍约束条件的任务集合，即选择后就可直接分配的任务集，可见任务集S′是对S的进一步筛选；W—未分配任务集合；n—共开启的位置数量；NS—共开启的工位数量；xipk—若任务i分配到位置p上，操作方位为k，k∈{L,R}，则为1，否则为0。

约束条件：

若xipk=1,则xhgk=0

(1)

其中h∈P(i),g、p=1, 2, 3, …,n, 且g>p；

(2)

(3)

(4)

对位置p，Tj+Rj≤C，且Tj′+Rj′≤C；

(5)

目标函数： MinimizeC

(6)

(7)

(8)

式(1)代表任务的分配需符合先后约束关系；式(2)表示任务必须且只能出现在双边装配线的某侧一个工位中；式(3)、(4)表示工位j与j′的操作时间累计值；式(5)表示构成任意位置p的双边工位中，其累计操作时间与累计延迟时间和必须小于节拍时间；式(6)表示双边装配线第二类问题(TALBP-Ⅱ) 的主要优化目标，即在整体双边装配线开启位置数量确定条件下尽可能缩减节拍时间；式(7)和式(8)为次要优化目标，LE为平衡率，SI为平滑系数，当LE=1、SI=0时为各工位负荷完全一致的理想平衡状态。

2.2生产节拍的理论下限

借鉴文献[8]的节拍下限公式，并参考单边装配线平衡问题中节拍时间下限的确定方式，本文提出的节拍下限值为：

Cmin=max{|TSUM/2n|,|TSUML/n|,|TSUMR/n|,tmax}

(9)

其中，TSUM为任务集I中所有任务的操作时间累计总和；TSUML、TSUMR、TSUME分别为任务集IL、IR、IE中所有任务的操作时间累计总和；tmax为所有操作任务中操作时间最长值。

3蚁群算法的构建

3.1蚁群综合搜索规则

从可供直接分配的任务集合S′中进行筛选：在当前双边工位任务安排情况之下可最早被操作的任务具有优先权，并汇集为优选集合FT(FT中包含的任务可在相同的最早时刻被操作)。若集合FT仅含一个元素，则可直接按3.2节的启发式任务分配规则进行分配；否则，在借鉴了文献[10]的改进信息素规则基础上，按以下混合搜索机制进行下一步筛选：

(10)

式中r——由程序随机产生的(0,1)之间随机数，

r1——规则选择参数阀，0≤r1≤1

FT——当前位置j的最早可开始任务集合

α,β——调节信息素强度和启发式信息在规则I1中相对比例的参数值

ηi——以任务i的位置权重pwi作为其启发式信息：

(11)

在公式(11)中，Fi表示在优先顺序网络图中，任务i的后继任务集合。此启发式规则综合衡量了本任务的作业时间以及其后续所有任务数量及作业时间。在该规则之下，后续任务数量多且累计作业时间较长的任务具有更高的被选择概率。

公式(10)中的两项概率选择规则：

(1)利用信息素和启发式信息的规则：若产生的随机数r符合0≤r≤r1，以概率pij从集合FT中选择任务。

(2)随机搜索的规则：若随机数r符合r1

3.2启发式任务分配规则

规则1：首先判断任务的操作方位，若为L(或R)，则按其操作方位特性放入左侧(或右侧)工位；规则2：若此任务的操作方位为两边均可的E型，则放入能使其最早进行操作的一侧工位；若放入两侧工位能使之同时开始操作，随机选择一侧工位。

3.3蚁群算法可行解的构造

图4　蚁群算法构造可行解流程

可行解的构造流程如图4所示。针对第二类平衡问题，为限定开启的位置数量n，且在此条件下优化节拍时间。为保证所有任务都能分配完毕，在前n-1个位置处，采用当前迭代时刻最优节拍时间进行节拍时间约束；当处于第n个位置时，在忽略节拍约束条件下选择剩余未分配任务并形成可行解。最后统计此可行解所有工位中的最长操作时间，作为此节的节拍时间。

3.4信息素更新规则

局部信息素更新：由于蚂蚁会在沿途释放信息素从而吸引其余蚂蚁，为减弱这种作用从而减少已选的方案对后来的蚂蚁对未知方案探索的干扰，增强蚁群对未知方案的探索能力。当蚂蚁将任务i分配到排列序列位置j处，则信息素矩阵τij上的值按下式更新：

τij←(1-ρ1)+ρ1τ0

(12)

ρ1—蒸发控制系数，0<ρ1<1；

τ0—信息素初始值；

全局信息素更新：每代蚂蚁的最优解搜索结果将建立最优解集合，集合中每个解都对路径释放信息素。为降低算法搜索陷入局部最优的概率，在每代最优搜索结果释放信息素时，限定各最优解的同一任务只在同一位置之间释放一次信息素：

τij←(1-ρ1)τij+ρ1Δτij

(13)

Δτij=

ρ2为信息素蒸发控制系数，0<ρ2<1。

3.5蚁群整体搜索规划

最优解的搜索从理论最小节拍Cmin开始，首代蚂蚁从理论最小节拍Ct=Cmin处搜索，若未找到满足此条件的可行解，则进行下一代蚂蚁群搜索，并将搜索的节拍值更新为Ct=Ct+1；若某代蚁群所得最优解的节拍时间恰好等于当前的节拍时间限定值Ct，则在下一代搜索时缩小节拍时间标准，令Ct=Ct-1；整体搜索按此规则进行，直到达到最大搜索代数或找到理论最优停止。

4实例验证

采用MATLAB7.8编制算法程序，程序运行时从记事本中读取任务先后约束条件、任务操作适应方位条件、任务操作时间条件，并设置搜索代数、开启位置数目n便可得到节拍时间优化结果，同时可得到任务分配甘特图。

图5　某装载机任务先后约束关系图

图5为适合采用双边装配线规划的某型装载机的任务先后约束关系网络图[12]。经设置4种开启位置数目n；得到表1所示4种优化方案。图6和表2为方案2工位任务安排甘特图和分配情况统计，均由MATLAB生成。

图6　MATLAB输出的方案2工位安排甘特图

方案(位置数目)C(s)LE(%)SI(s)方案1(5)102194.079.73方案2(6)86093.070.22方案3(7)77189.0152.47方案4(8)66091.081.01

表2　方案2任务分配

表1中算法计算所得的4种优化方案的平衡率均达到89%以上。而分配方案的双边工位任务分配甘特图显示模块更增加了算法的实用性与优化结果的直观性。在图6的任务甘特图中，操作时间长度体现于进度条长短，任务的操作开始和结束时间在进度条上方标示；横轴和纵轴分别表示时间和工位，左右工位分别以奇偶数表示。在伴随工位之间，由于任务之间的先后约束关系所形成的等待与延迟均可直观显示，较为实用。

5结束语

本文针对双边装配线第二类平衡问题进行了研究，构建了数学模型并设计了一种蚁群算法求解。以蚁群综合搜索规则、启发式任务分配规则构建出算法的关键模块，用于可行解的构造，采用蚁群整体搜索规划探索最优解。针对某大型装载机进行规划计算，所得分配方案均具有较高的平衡率，说明算法求解有效性。更通过设计了甘特图的显示模块从而增加了算法的实用性。

[参考文献]

[1] BARTHODI J J.Balancing two-sided assembly lines:a case study[J].International Journal of Production Research,1993,31(10):2447-2461.

[2] KIM Y K, KIM Y H, KIM Y J. Two-sided assembly line balancing: a genetic algorithm approach[J]. Production Planning & Control, 2000, 11(1): 44-53.

[3] LEE T O, Kim Y, & Kim Y K. Two-sided assembly line balancing to maximize work relatedness and slackness[J]. Computers & Industrial Engineering, 2001, 40(3):273-292.

[4] SIMARIA A S, VILARINHO P M. 2-ANTBAL: An ant colony optimisation algorithm for balancing two-sided assembly lines[J]. Computers & Industrial Engineering, 2009, 56(2): 489-506.

[5] BAYKASOGLU A, DERELI T. Two-sided assembly line balancing using an ant-colony-based heuristic[J]. The International Journal of Advanced Manufacturing Technology, 2008, 36(5-6): 582-588.

[6] WU E F, JIN Y, BAO J S, et al. A branch-and-bound algorithm for two-sided assembly line balancing[J]. The International Journal of Advanced Manufacturing Technology, 2008, 39(9): 1009-1015.

[7] 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.

[8] 吴尔飞, 金烨, 汪峥.双边装配线第二类平衡问题研究 [J].计算机集成制造系统, 2005, 11(11): 1604-1608.

[9] 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.

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

[11] 邓福平, 张超勇, 连坤雷, 等. 基于自适应蚁群算法的装配线平衡问题研究[J]. 中国机械工程, 2011,22(16): 1949-1953.

[12] 吴尔飞. 双边装配线平衡技术的研究[D]. 上海:上海交通大学, 2009.

(编辑赵蓉)

Ant Algorithm for Two-sided Assembly Line Balancing of Type-2

HU Jun-yi1, ZHANG Ze-qiang2, JIN Chu-yun1

(1. School of Mechanics and Electronics, Zhejiang Institute of Communications, Hangzhou 311112,China;2.School of Mechanical Engineering,Southwest Jiaotong University, Chengdu 610031,China)

Abstract：Two-sided assembly line problem is more difficult than one-sided assembly line problem as the task distribution procedure. In this problem, besides the precedence constraints among tasks, the operation directions constraints of tasks and the requirement of parallel work should also be taken into consideration. The mathematical model and an ant colony algorithm were constructed to solve the Two-sided Assembly Line Balancing Problem of type-2(TALBP-Ⅱ). A hybrid ant-based search rule and a heuristic task distribution rule were used in order to establish a feasible solution, global pheromone trail update and the optimum solution search strategy were considered. The feasibility of this algorithm was indicated by a case of a loader final assembly line.

Key words：two-sided assembly lines; balancing; ant colony algorithm

中图分类号：TH165; TG506

文献标识码：A

作者简介：胡俊逸(1986—)，男，浙江金华人，研究方向为制造系统优化仿真，(E-mail)hujunyi_jt@zjvtit.edu.cn。

*基金项目：国家自然科学基金项目(51205328)；中央高校基本科研业务费专项资金资助项目(SWJTU09CX022; 2010ZT03)

收稿日期：2015-04-13

文章编号：1001-2265(2016)02-0149-04

DOI:10.13462/j.cnki.mmtamt.2016.02.042