周炳海，康雪云

(同济大学 机械与能源工程学院，上海 201804)

考虑切换时间的机器人装配线平衡优化方法*

周炳海†，康雪云

(同济大学 机械与能源工程学院，上海 201804)

考虑装配过程中的切换时间，以装配线的工位节拍最小为优化目标，建立了机器人装配线平衡问题的数学模型.在此基础上，将自适应策略引入模拟退火遗传算法框架中，构建了自适应模拟退火遗传算法.以轿车制造车身车间左前门内板总成的焊接装配为例，分别对比了标准遗传算法、模拟退火遗传算法及自适应模拟退火遗传算法在解决该问题方面的性能，结果表明自适应模拟退火遗传算法在解的性能和算法收敛性两个方面表现出了较大的优势.

机器人；装配线平衡；切换时间；模拟退火；自适应

随着国家战略性新兴产业的提出，机器人技术和产业得到了迅速发展.作为实现制造业自动化的关键，机器人被广泛应用于自动化装配线，由其产生的机器人装配线平衡问题(Robotic Assembly Line Balancing Problem, RALBP)得到了学术界和工业界的密切关注.

为了有效地解决RALBP，国内外学者们进行了不少的研究工作.文献[1]和[2]分别采用了带局部优化的遗传算法和粒子群算法来最小化工位节拍；文献[3]构造了一种新的染色体交叉和突变方法，并采用具有局部搜索的遗传算法来求解该类问题；文献[4]在粒子群算法的基础上，融入了布谷鸟搜索机制，表现出了较好的性能；文献[5]和[6]分别研究了该问题的U型装配线和双边装配线的数学模型；文献[7]和[8]分别提出了同时最小化工位节拍和能源消耗的单边、双边RALBP的双目标模型；文献[9]提出了同时最小化工位节拍，机器人Setup时间和机器人成本的多目标模型，并给出了该问题的混合整数规划数学模型；文献[10]采用多目标规划方法来最小化工位节拍、工位数量以及机器人成本.然而，以上研究均集中于装配任务本身，并未考虑装配过程中任务之间的切换对工位节拍的影响.

在现代随机混流柔性装配模式下，共线装配的同类、甚至不同类产品之间的工具、工装夹具等的切换时间占工位节拍比例较大；而且就同一产品的装配而言，不同装配任务之间也会存在切换时间.因此，在解决RALBP时，考虑切换时间显得尤为重要.

1 问题描述

产品的装配过程是在满足给定的任务优先关系的前提下，通过相应的设备，将产品的所有装配任务i(i=1,2,…,I)在一系列的工位s(s=1,2,…,S)上装配出产品的过程.

在RALBP中，首先要合理地将所有装配任务分配到相应工位；其次，由于不同类型的机器人r(r=1,2,…,R)完成同一任务的时间不同，并且切换时间也不尽相同，所以需要为每个工位选择最合适的机器人；最后，在确保任务优先关系的前提下，使工位任务序列内的任务之间的切换次数最少.

为了有效地刻画研究的问题域，做如下基本假设：1)各装配任务不可再分,产品的任务优先图和任务之间的切换关系事先已知；2)每项任务的装配时间取决于该工位的机器人，且机器人执行每项任务的时间确定；3)每个工位分配一台机器人，但不同类型的机器人数量没有限制；4)任务和机器人的分配没有限制；5)物料搬运及其他setup时间忽略或者包含在任务时间中，但切换的时间不能忽略；6)不同任务之间的切换时间相等，且为一个定值；7)装配线是只装配一种产品的直型装配线.为方便描述，现定义符号如下：

i—任务序号i(i=1,2,…,I);j—任务优先图中紧随任务i的任务;k—工位任务环中紧随任务i的任务;s—工位序号s(s=1,2,…,S);r—机器人种类序号r(r=1,2,…,R);tir—机器人r完成任务i的工艺时间;cr—机器人r或夹具单次切换时间;τ*s—工位s在任务环内的切换次数;τs—工位s的最小切换次数;xis—表示任务i分配到工位s为1,反之为0;yrs—表示机器人r分配到工位s为1,反之为0;zij—表示任务i和j之间有切换为1,反之为0;wij—表示任务i和j有优先关系为1,反之为0;pre(i)—任务i的直接前序的任务集合;tcs(i)—任务环内任务i的直接后续任务集合.

为了进一步分析问题，做以下定义并给出相关定理如下.

(1)

特殊地，单、双任务环分别如图2和图3所示.

图1 任务环Fig.1 The loop of assembly tasks

图2 单任务环 图3 双任务环Fig.2 Single task loop Fig.3 Double tasks loop

定理1 如果zi,j=0，zj,k=0，那么zi,k=0.即任务之间的切换具有传递性.

证 如果任务i和j之间不存在切换，并且任务j和k之间也不存在切换，那么，显然任务i和任务k之间也不存在切换，即有zi,k=0.

证毕.

(2)

证毕.

定理3 工位节拍下界可表达为：

(3)

证毕.

根据定义和定理，对所研究的考虑切换时间的RALBP建模如下：

(4)

约束条件：

(5)

(6)

(7)

xis∈{0,1},i=1,2,…,I;s=1,2,…,S

(8)

yrs∈{0,1},r=1,2,…,R;s=1,2,…,S

(9)

zik∈{0,1},i=1,2,…,I;k=1,2,…,K

(10)

目标函数(4)最小化工位节拍；约束条件参考文献[3],不等式(5)保证各项任务之间的优先关系；等式(6)表示每个工位都必须被分配到工位；等式(7)表示每个工位只能被分配到一台机器人；约束(8)～(10)是0-1变量.

2 算法构建

ALBP是一个典型的NP-hard组合优化问题，问题的复杂度随着任务数的增加呈几何级数增长，不存在精确求得最优解的多项式时间算法[12].而作为ALBP的子问题，RALBP更具复杂性.

为此，本文提出了一种有竞争性的自适应模拟退火遗传算法(ASAGA).该算法以遗传算法为主体，融入模拟退火机制，从而极大地克服了遗传算法局部搜索能力较弱的缺点；为了进一步改善遗传算法早熟收敛以及收敛性能差的缺点，将自适应策略引入算法框架中，有效缓解遗传算法的退化现象，提高收敛速度，并克服遗传算法的早熟收敛和收敛性能差的缺点，大大地提高了遗传算法的运行效率[13-14].

算法的总体流程图如图4所示.

图4 算法总体流程Fig.4 The flow chart of ASAGA

算法的具体步骤如下：

步骤1 设置初始参数，包括种群大小Num_Pop，最大遗传代数Num_Gene，退火初始温度T0，温度冷却系数α，退火迭代次数MaxIter.

步骤1.1 编码

本文采用基于基因序列的编码方式.首先，按作业元素分派至工位的先后顺序，将作业排成一列，每个作业对应一个基因位；其次，对基因序列进行分割，将每个作业按照加工顺序分配给工位；最后，根据节拍最小原则为工位选择最合适的机器人.

步骤1.2 译码

在实际装配中，线体的节拍增量不是一个连续的值，而是以一个作业元素的时间值作为增量.基于此，参考文献[15]的步骤进行译码操作.

步骤1.3 初始种群的产生

本文在满足优先关系的前提下，采用如下的步骤产生初始种群：

步骤1.3.1 首先随机选取一个无前序作业的元素作为染色体的第一个基因.

步骤1.3.2 挑选无前序作业或者前序作业已被分配到的作业元素放入备选集合中.然后在备选集合中随机地选择一个编入染色体基因位.

步骤1.3.3 更新备选集合.如此循环，直到所有作业元素都编入染色体，产生一个染色体.

步骤2 适应度计算

对于RALBP，不仅要求工位节拍最小，而且还应该考虑机器人装配线的负载是否均衡，因此，构造适应度函数如下：

F=ω1F1+ω2F2

(11)

式中：

(12)

(13)

其中F1表示按工位节拍最小的适应度，F2表示按工位分配相对均匀的适应度,STmax为工位最大时间，STs为第s工位的时间.

步骤3 遗传操作

步骤3.1 选择

采用轮盘选择策略进行个体选择，同时采用最优保留策略.每个染色体的选择概率正比于适应度，对于适应度为Fs的染色体，其选择概率为：

(14)

步骤3.2 交叉

在遗传操作中，交叉概率Pc的选取是影响算法行为和性能的关键因素.Pc过大或过小都会影响收敛速度和过程.因此，对交叉概率Pc做如下设置：

(15)

式中:fmax和favg分别为群体中的最大和平均适应度值，fc为要交叉的两个个体中较大的适应度值,Pc1和fc2为交叉相关系数，分别取值为Pc1=0.90，Pc2=0.20.从选择操作产生的交配库中随机选取两条染色体，依据自适应概率Pc采用两点交叉进行交叉操作(见图5)，相同地可得到第二条后代染色体.

图5 染色体交叉示意Fig.5 Illustration of crossover

步骤3.3 变异

同样地，采用该策略对Pm进行自适应调整：

(16)

式中:Pm1和Pm2为变异相关系数，分别取值为Pm1=0.15，Pm2=0.05.任意选择一个个体，依据概率Pm进行突变，得到突变后个体.

步骤4 模拟退火操作

步骤4.1 令内循环次数gene=0，计算遗传操作后种群的适应度值，并分别采用Metropolis判别准则进行模拟退火操作.Metropolis判别准则：状态F变为状态F′的接受概率：

(17)

式中:Ti为当前控制温度;F和F′分别为遗传操作前、后的适应度值.

步骤4.2 计算退火后种群的适应度，并将群体中适应度最小的个体替换为遗传操作前适应度最大的个体，以保证算法的收敛性.

步骤4.3 如果当前退火代数Iter

Ti+1=α*Ti

(18)

式中:Ti+1为当前控制温度;Ti为上一代温度，取T1=100;α为冷却系数，取α=0.90.

3 实例分析

某轿车车身车间中左前门内板任务优先关系如图6所示，焊接工艺程序如图7所示，机器人对各作业的装配时间见表1，各任务间的切换关系及机器人的切换时间见表2和表3.机器人焊接装配线的工位数S=6,共有R=4种类型的机器人可供选择.

图6 任务优先图Fig.6 Precedence diagram of the tasks

图7 左前门内板总成工艺程序图Fig.7 Process flow chart of the inner assembly of left front door

本文采用Matlab R2014a编程，运用ASAGA算法来平衡车身车间中左前门内板总成焊接装配的RALBP，在主频为2.13 GHz，内存为2 GB的PC机上运行，并做了如下几种分析.

3.1 评价指标

为有效评价算法的性能，提出以解的相对偏差Q作为算法的评价指标：

(19)

其中V(H,T,Y)表示用算法H在迭代次数为T时对实例Y的求解结果，CLB表示定理3提到的工位节拍下界.Q能够真实地反映算法的收敛性能，其值越小，表明算法的收敛性能越好.

表1 机器人装配时间表Tab.1 Table of assembly time by robots

表2 任务切换关系表Tab.2 Table of the changeover relationships of tasks

表3 不同类型机器人切换时间表Tab.3 Table of changeover time by the different robots

本例中，首先，根据优先图和切换关系找到序列1→3→8→4→12→2→5→9→13→6→7→10→11→14→15→16，得到最小切换次数τ0=6，根据Cat=72.5,然后进行序列分割，得到如图8所示的切换结果，即最少切换次数τs=4.即工位下界CLB=81.8.

图8 最少切换次数分析Fig.8 Analysis of the minimum changeover times

3.2 参数分析

为了确定较佳的内层迭代次数，先设置外层循环次数为1，再根据作业分配的约束条件，产生20个初始种群进行试验，并将自适应模拟退火遗传算法(ASAGA)与标准遗传算法(SGA)、模拟退火遗传算法(SAGA)进行对比，得到内层迭代次数对最大适应度和求解时间的影响分别如图9和10所示.

图9 迭代次数对最大适应度值的影响Fig.9 The effect of number of iterations to maximum fitness

图10 迭代次数对计算时间的影响Fig.10 The effect of number of iterations to computation time

由图9,图10可知，当迭代次数达到300到1 500时，3种算法的最大适应度值都趋于稳定，同时可以看出ASAGA的收敛速度更快，当迭代次数达到80次时已经找到了较稳定的最大适应度值.综合考虑时间成本和最大适应度值，本文认为在该试验中，ASAGA的内层迭代次数定为80，SAGA的迭代次数定为120，SGA的内层迭代次数定为300是合理的.

确定内层迭代次数后，按照上述方式再次进行试验，得到外层迭代次数对Q和时间的影响如表4所示.当迭代次数在30到50时，两种算法都趋于稳定，融入自适应机制的ASAGA算法在外循环系数为10次时，解达到了近优值，此时Q=16.14%，而SAGA在外循环系数为30次时才达到近优解.因此，ASAGA相比于SAGA表现出了较好的收敛性.

表4 外层迭代次数对解的相对偏差Q和 求解时间T的影响Tab.4 The effect on therelative deviation Q & time T by number of outer iterations

3.3 结果分析

根据以上分析，在运用ASAGA,SAGA以及SGA算法求解决该问题时，就解的性能而言，ASAGA和SAGA的最/近优值均为95 s，解的相对偏差为16.14%，总切换次数为7次，而SGA的最/近优值为104 s，解的相对偏差为27.12%，总切换次数为12次，即增加模拟退火机制可以减少装配任务间的切换次数，减少解的相对偏差，提高解的性能；就算法的收敛速度而言，ASAGA在内、外循环次数分别为80，10次时取得最/近优值，耗时71.127 s，均小于SAGA在内、外循环次数分别为120，30时取得最/近优值时所耗时的288.455 s以及SGA循环次数为300次解趋于平衡时所耗时的174.905 s，显然，ASAGA的收敛速度均大于SAGA和SGA.可见，融入模拟退火机制和自适应策略不仅可以减少切换次数，增强解的性能，而且还极大地提高算法的收敛速度.

由表5和图11可知，工位1中，由于任务1,2，5之间存在优先关系，所以机器人先上件到夹具后，再切换焊枪焊接，完成后需要换回抓手，等待进行下一个节拍，因此有两次切换时间；而在工位2中，由于产品结构和焊点位置的不同，使得任务9和任务4之间需要换枪，且它们之间没有优先关系，因此，可以在前一个节拍先执行任务9，再执行任务4，而在下一个节拍先执行任务4，再执行任务9，从而节省一次换枪时间；同理，工位5中，任务11和13之间没有优先关系，可节省一次机器人的换枪时间；工位6中，由于任务14,15和16之间有优先关系，机器人在固定焊枪焊接完成后，换抓手进行检查和下件，结束后需换回执行固定焊枪焊接时所用的抓手，因此，该过程中有两次切换时间.

表5 实例求解结果Tab.5 The result of the example by ASAGA

图11 装配任务切换示意Fig.11 Illustration of changeover of assembly tasks

4 结 论

1)考虑了装配过程中任务间的切换关系，以最小化装配线的工位节拍为目标，提出了相关的定义、定理，建立了该类问题的数学模型.

2)将模拟退火机制和自适应策略引入遗传算法的框架中，构造了自适应模拟退火遗传算法，该算法能够在解的质量和算法的收敛速度两方面取得令人满意的结果，丰富了解决RALBP的理论方法.

3)在平衡机器人装配线过程中，考虑装配任务间的切换关系，可以减小装配线的工位节拍，提高不同装配任务间设备的共用性，充分节省资源，降低生产成本，为企业带来更大的经济效益.

[1] LEVITIN G,RUBINOVITZ J,SHNITS B. A genetic algor-ithm for robotic assembly balancing[J]. European Journal of Operational Research, 2006,168:811-825.

[2] NILAKANTAN J Mukund,PONNAMBALAM S G. An efficient PSO for type-II robotic assembly line balancing problem[C]/Automation Science and Engineering(CASE),2012 IEEE International Conference on.IEEE,2012:600-605.

[3] GAO Jie,SUN Linyan,WANG Lihua,etal. An efficient approach for type-II robotic assembly line balancing problems[J]. Computers & Industrial Engineering,2009,56(3):1065-1080.

[4] NILAKANTAN J Mukund,PONNAMBALAM S G,JAWAHAR N,etal. Bioinspired search algorithms to solve robotic assembly line balancing problems[J].Neural Computer & Application, 2015,26:1379-1393.

[5] NILAKANTAN J Mukund,PONNAMBALAM S G.Robotic U-shaped assembly line balancing using particle swarm optimization[J].Engineering Optimization,2016,48(2):231-252.

[6] AGHAJANI M, GHODSI R, JAVADI B. Balancing of robotic mixed-model two-sided assembly line with robot setup times[J]. The International Journal of Advanced Manufacturing Technology, 2014,74:1005-1016.

[7] NILAKANTAN J Mukund,HUANG George Q, PONNAMBALAM S G. An investigation on minimizing cycle time and total energy consumption in robotic assembly line systems[J].Journal of Cleaner Production,2015,90:311-325.

[8] LI Zixiang,TANG Qiuhua,ZHANG Liping. Minimizing ene-rgy consumption and cycle time in two-sided robotic assemble line systems using restarted simulated annealing algorithm[J].Journal of Cleaner Production,2016,135:508-522.

[9] YOOSEFELAHI A, AMINNAYERI M, MOSADEGH H,etal.Type II robotic assembly line balancing problem: An evolution strategies algorithm for a multi-objective model[J].Journal of Manufacturing Systems,2012,31:139-151.

[11]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:666-693.

[12]KILINCCI O. A petri net-based heuristic for simple assembly line balancing problem of type 2[J].International Journal of Advanced Manufacturing Technology,2010,46:329-338.

[13]黄英杰,姚锡凡,古耀达.基于熵的混合粒子群算法在柔性调度中的应用[J].湖南大学学报：自然科学版, 2012,39(3):48-52.

HUANG Yingjie, YAO Xifan, GU Yaoda. Hybrid particle swarm optimization baesd on entropy for fleible job shop scheduling problems[J].Journal of Hunan University:Natural Sciences, 2012,39(3):48-52.(In Chinese)

[14]曹一家,曹丽华,李勇,等.改进的自适应多目标粒子群算法[J].湖南大学学报：自然科学版,2014,41(10):84-90.

CAO Yijia, CAO Lihua, LI Yong,etal.Improved adaptive multiobjective particle swarm algorithm[J].Journal of Hunan University:Natural Sciences,2014,41(10):84-90.(In Chinese)

[15]陈星宇.基于改进遗传算法的装配生产线平衡技术研究[D].上海:上海交通大学机械与动力工程学院，2011:40-41.

CHEN Xingyu. Study on assembly line production balance technique base on the improved genetic algorithm[D]. Shanghai:School of Mechanical Engineering,Shanghai Jiaotong University, 2011:40-41.(In Chinese)

Optimal Method of Robotic Assemble Line Balancing Considering Changeover Time

ZHOU Binghai†, KANG Xueyun

(School of Mechanical Engineering，Tongji University，Shanghai 201804，China)

Considering the changeover time in the process of assembly production，a mathematical model with an objective function to minimize the cycle time of robotic assembly line was developed.On the basis of the model，an adaptive strategy was combined into the frame of simulated annealing genetic algorithm，and an Adaptive Simulated Annealing Genetic Algorithm (ASAGA) was then proposed.Finally，an example of the welding assembly for the inner assembly of the left front door in the Body Shop was provided to illustrate greater advantages in the quality of the solution and the algorithm convergence，compared with the SGA (Standard Genetic Algorithm) and SAGA (Simulated Annealing Genetic Algorithm) in solving this problem.

robot；assembly line balancing；changeover time；simulated annealing；adapt

1674-2474(2017)08-0035-08

10.16339/j.cnki.hdxbzkb.2017.08.006

2016-07-06

国家自然科学基金资助项目(71471135，61273035),National Natural Science Foundation of China(71471135，61273035)

周炳海(1965—)，男，浙江浦江人，同济大学教授，博士

†通讯联系人，E-mail：bhzhou@tongji.edu.cn

TP29

A