李六柯 张则强 胡 扬 邹宾森

西南交通大学机械工程学院，成都，610031

基于多目标算法与动态仿真的带调整时间的拆卸线平衡优化方法

李六柯 张则强 胡 扬 邹宾森

西南交通大学机械工程学院，成都，610031

针对拆卸方向改变对作业时间的影响，以最小化拆卸成本、无效作业率和不平滑率为优化目标，构建了考虑调整时间的多目标拆卸线平衡问题模型，并提出了一种Pareto免疫遗传算法与仿真技术相结合的求解方法。算法融合了遗传算子和免疫算子，能有效避免解出现退化和陷入局部最优。通过求解25项拆卸任务算例，并与现有5种算法进行对比，验证了所提算法的有效性。进而将所提模型和算法应用于某打印机拆卸线实例，进一步考虑拆卸时间不确定、存在故障等实际情况，运用仿真技术分析与优化，结果表明所提方法能有效降低等待和堵塞造成的无效作业时间，提高拆卸效率。

拆卸线平衡问题；多目标优化；调整时间；免疫遗传算法；仿真

0 引言

文献[1]针对拆卸线中的任务排序及流水作业控制问题，首次正式提出了拆卸线平衡问题，并设计了一种基于多维优先级值累加筛选策略的启发式算法。在DLBP的早期研究中以启发式算法[2-3]为主，如贪婪算法与2-opt算法结合[3]。启发式算法具有原理直观、操作简单，能快速求得一个可行解等优点，但求解结果完全依赖启发式规则，具有不确定性。为提高求解质量，一些学者尝试采用数学规划方法[4]，但由于DLBP是NP完全问题[5]，求解难度随着问题规模的增大呈几何级增长，因而数学规划方法不适用于求解大规模问题。智能算法因能很好兼顾求解质量和求解效率而被广泛使用，如遗传算法[6]、蚁群算法[7-8]、人工蜂群算法[9]和粒子群算法[10]等。上述文献在建模阶段虽然考虑了多个优化目标，但使用智能算法求解时却将多目标问题转化为带有优先顺序的单目标问题，而多个优化目标间往往是相互冲突的，这种处理方法难以保证所有目标间的均衡性。丁力平等[11]提出了一种多目标蚁群算法，结合Pareto解集筛选策略，为求解多目标DLBP提供了一种新思路。

前述文献中DLBP模型均假设忽略调整时间，或将其归为作业时间，然而，在实际拆卸操作中，当调整时间占比比较大或调整工作由前后任务共同决定时，则不能忽略调整时间的影响。文献[12]将拆卸方向改变次数作为优化目标，但未深入研究拆卸方向改变对拆卸线平衡性的影响，同时也未考虑由拆卸方向改变引起的调整时间。

基于此，本文引入因拆卸方向改变带来的调整时间，构建了考虑调整时间的多目标DLBP模型;在节拍时间已知、拆卸工作站数目和周期时间未知情况下，综合拆卸成本、无效作业率和不平滑率等三个目标，采用一种基于Pareto思想的多目标免疫遗传算法(multi-objective immune genetic algorithm, MIGA)进行求解;进而针对实际生产中由于拆卸时间不确定及零部件或设备故障导致的生产延误等情况，应用仿真技术对理论方案进行建模仿真，并提出改善方案。

1 考虑调整时间的多目标DLBP模型

为建立DLBP模型，现作如下假设：报废产品足够多，不存在缺货情况；在拆卸线上拆除全部零件；拆卸线采用直线型布局；所有零部件齐全、连接可靠、能够正常拆卸；标准化拆卸作业，拆卸时间已知；不考虑零部件在拆卸线上的流转时间；在满足优先关系约束条件下，得到拆卸任务序列，并根据节拍时间开启工作站，分配拆卸任务。该问题为寻求一组满足约束条件的拆卸序列，同时优化多个目标。

1.1符号说明

n为待拆卸产品包含的总任务数目；M为拆卸过程开启的工作站数目；ti为任务i的作业时间；A为优先关系矩阵，A=(aij)n×n，若任务i为任务j的紧前工作，则aij=1，否则aij=0；xim表示当任务i分配到第m个拆卸工作站，则xim=1，否则xim=0；Tc为周期时间；Tt为由产量和工作时间估计的节拍时间；hm为第m个工作站的作业时间；TSm为第m个工作站的调整时间。ci为任务i的单位时间拆卸成本；ri为任务i的拆卸方向；qi为任务i在拆卸序列的位置；di为任务i的需求量。

1.2数学模型

在实际生产中，当某工作站完成了所分配的拆卸任务，且下游工作站处于空闲状态时，作业对象不必等到周期时间结束即可直接输送到下游工作站；若下游工作站仍在工作状态，则该工作站处于堵塞状态，因此，对实际拆卸线进行平衡优化时，目标值的计算应以实际周期时间Tc为准。周期时间由工作站作业时间和调整时间共同决定，其计算公式如下：

Tc=max(hm+TSm)
m∈{1,2,…,M}

(1)

出于节约成本、提高效率的考虑，选取拆卸成本f1、无效作业率f2和不平滑率f3为优化目标，则有

(2)

(3)

(4)

考虑调整时间的多目标拆卸线平衡问题模型如下：

目标函数

F=min(f1,f2,f3)

(5)

约束条件

(6)

(7)

Tc≤Tt

(8)

其中，式(6)保证所有拆卸任务分配完毕且任务不可再分；式(7)保证拆卸序列满足优先关系约束；式(8)保证周期时间不超过节拍时间。

2 Pareto免疫遗传算法设计

免疫遗传算法是一种基于迭代搜索机制的混合智能优化算法，通过将免疫操作融入遗传算法，为个体及种群更新提供指导，从而有效避免解出现退化和早熟。该混合算法能够在解的质量和多样性方面取得很好平衡，全局搜索能力强，已在诸多组合优化问题中得到了成功应用，如调度问题[13]、旅行商问题[14]和设施布局问题[15]等，并表现出优异的求解性能。本文结合多目标拆卸线平衡问题的特点，引入Pareto思想，提出了一种求解DLBP的Pareto多目标免疫遗传算法。

2.1Pareto解集

DLBP的目标函数F(X)是最小化多目标优化函数，决策变量X表示可行拆卸序列。多目标优化问题中各目标间量纲不同，互相冲突，难以进行比较。借鉴Pareto思想评价多目标问题解的优劣，决策空间中的任意两个解X1、X2满足：

(9)

则称X1支配X2，记为X1X2，X2称为被支配解。若X1不被任意可行解支配，则称X1为非劣解，互不占优的非劣解构成Pareto最优解集。Pareto最优解集映射在目标空间的集合称为Pareto最优前沿。其中，Z为子目标函数个数；fi(X)、fj(X)为第i、j个子目标函数。

2.2编码和解码方法

DLBP属于典型的组合优化问题，带有复杂的约束条件，需避免非法解和不可行解。其解的形式为满足约束条件的最优排列，合理的编码方式是智能算法求解问题的关键。本文采用基于零件编号的编码方式，即长度为n的整数编码表示拆卸序列。

解码是指将拆卸序列还原为任务分配方案，结合式(1)中拆卸任务的作业时间和调整时间，在保证周期时间不超过节拍时间的前提下，依次将拆卸序列中的任务分配到工作站，直至所有的任务分配完毕。具体的解码操作见表1。

2.3种群初始化

在满足优先关系约束条件下随机生成一个长度为n的一维数组，其元素与拆卸任务编号一一对应，该数组表示可行拆卸序列，重复执行N次得到初始种群。生成可行拆卸序列的步骤如下。

(1)根据优先关系约束搜索无紧前工作的拆卸任务，构成待分配任务集V，随机在V中选择一个任务，分配到拆卸序列。

(2)约束已分配任务，解除已分配任务对未分配任务的约束。

(3)重复执行步骤(1)、步骤(2)，直至所有任务分配完毕。

表1 解码操作过程Tab.1 The decode operation

2.4构建疫苗库

疫苗库是某一问题特征信息的集合，反映了拆卸任务分配的一种优先顺序。针对问题特点，以加权值和拆卸时间为疫苗产生规则：拆卸任务按加权值降序排列，若加权值相等，则优先分配作业时间长的拆卸任务，其中某任务的加权值等于该任务与前序任务的作业时间之和。确定某拆卸任务在该排列中的位置，则排序位置在其前的任务即为该任务的疫苗。

2.5遗传算子

遗传算子包括交叉、变异两个操作，以实现个体间的信息交换和局部搜索。

(1)交叉操作。采用两点交叉方式，种群中个体随机两两配对且不重复，根据交叉概率Pc判断配对个体是否执行交叉操作，随机选择两个不同的交叉点，交换两父代在交叉点间的元素。由于父代均为可行序列，交叉操作未改变拆卸任务的相对位置，交叉子代仍满足优先关系约束，保证了拆卸序列的可行性。

(2)变异操作。采用多点变异方式，根据变异概率Pm选择执行变异操作的任务。为保证变异操作后的个体仍为可行序列，变异位置必须满足以下两个条件：①其所有紧前工作的最后一项任务后的位置；②其所有紧后工作的最前一项任务前的位置。其余任务的相对位置保持不变，变异子代继承了父代的局部信息，同时保证了拆卸序列的可行性。

2.6免疫算子

免疫算子包括接种疫苗、免疫检测、更新外部档案、免疫平衡和免疫选择等操作，为个体进化提供方向，维持种群多样性。

(2)免疫检测操作。计算接种疫苗前后抗体的适应度，根据Pareto思想，判断抗体是否得到优化。若X2X1，则保留子代；否则，若接种疫苗次数在最大尝试次数L=n/2⎤范围内，则需重新接种疫苗；若超出最大尝试次数，则保留父代。该操作有效地避免了遗传算法因交叉、变异操作后子代不如父代的退化现象，为个体更新提供优化方向，只有进化的个体才有可能参与下一次迭代。

(3)更新外部档案。交叉、变异、接种疫苗和免疫检测等操作实现了个体更新，其中接种疫苗操作为个体更新提供了进化方向，并通过免疫检测操作筛选了进化个体。在算法搜索过程中使用外部档案保留精英解：计算初始种群的目标值，根据式(9)筛选出非劣解，并将其作为初始化的外部档案，在迭代过程中，判断新解与外部档案中非劣解的支配关系，在外部档案中剔除受支配解，同时保留非劣解以更新外部档案。

(4)免疫平衡操作。随着迭代次数的增加，外部档案中高适应度抗体浓度不断提高，为了平衡抗体的质量与多样性，当抗体浓度达到设定阈值时，抑制高适应度抗体，而促进低适应度抗体。

抗体i、j的相似度Jij定义为

(10)

式中，R为相似度半径。

第i个抗体浓度Ci定义为种群中的抗体与第i个抗体相似的抗体数目占种群规模N的比例，即

(11)

(12)

(13)

描述抗体适应度在种群总适应度的占比，第i个抗体的适应度概率

(14)

(15)

(16)

2.7算法流程

Pareto免疫遗传算法求解DLBP的步骤如下。

(1)输入待求解问题的参数：拆卸时间、单位时间拆卸成本和拆卸方向等相关信息、优先关系矩阵A、节拍时间Tc、任务数目n。

(2)设定算法参数：种群规模N、最大迭代次数Gmax、交叉概率Pc、变异概率Pm、疫苗接种比例β、最大尝试次数L、相似度半径R和免疫选择参数α，种群初始化，令外部档案Q=∅。

(3)构建疫苗库，开始循环计数，令循环次数g=1。

(4)执行交叉、变异等遗传操作。

(5)判断抗体是否需要接种疫苗，若需要则执行接种疫苗操作，令接种疫苗次数l=1，否则转至步骤(7)。

(6)执行免疫检测操作。计算接种疫苗操作前后抗体X1、X2的适应度，若X2X1，则保留子代，否则判断尝试次数是否满足要求l

(7)更新外部档案Q。

(8)执行免疫平衡操作，计算外部档案Q浓度概率Pd和适应度概率Pf。

(9)执行免疫选择算子，根据式(15)、式(16)分别计算高低浓度抗体的选择概率Ps，执行免疫选择操作，更新种群。

(10)判断循环次数g

Pareto免疫遗传算法的流程如图1所示。

图1 Pareto免疫遗传算法流程图Fig.1 The flow chart of Pareto MIGA

3 算法验证与应用

3.1算法验证

文献[2]研究了包含25项拆卸任务的某手机拆卸实例(P25问题)，考虑工作站数目M，空闲时间均衡指数I和需求指数D等多目标，具体为

(17)

(18)

现有求解P25问题的方法包括H-K算法[7]、单目标蚁群算法[7]、单目标粒子群算法[10]和多目标蚁群算法[11]，上述算法的结果见表2。

表2 现有算法求解P25问题的结果Tab.2 Solution of P25 of the existing algorithms

为便于比较算法性能，引用文献[2]所提的3个目标函数。算法参数设置如下：N=200，Gmax=20，Pc=0.7，Pm=0.1，β=0.9，L=13，R=0.1，α=0.7。在计算机硬件配置为Intel(R) Pentium(R) CPU，主频为2.90 GHz双核，内存为2 GB，MATLAB R2010b环境下运行算法程序，可以求得10个非劣解的Pareto最优解集，见表3。

对比上述5种算法，启发式算法和H-K算法依据某一规则分配拆卸任务，所得结果与启发式规则直接相关，无法同时优化多个目标；单目标蚁群算法和单目标粒子群算法将多目标问题转化为具有优先顺序的单目标问题，求解结果较为单一；多目标蚁群算法能求得多个互不占优的分配方案。分析表2可知，单目标粒子群算法在求解P25问题时表现优异：M=9，I= 9，D= 853，所得结果能支配上述4种方法的解；多目标蚁群算法能求解出包含两个非劣解的Pareto解集。

对比表2与表3，MIGA算法可求出包含10个非劣解的Pareto解集，其中解1的工作站数目和空闲时间均衡指标与单目标粒子群算法的结果相同，但需求指标较优，因此解1能支配上述5种算法的解；余下9个解中空闲时间均衡指标最小为11，需求指标最大为849，与单目标粒子群算法所求结果比较互不占优。综上所述，本文MIGA算法能够求得多样的、高质量的解，表明了所提MIGA算法的有效性。

表3 MIGA求解P25问题的结果Tab.3 The solution results of MIGA for P25

3.2实例应用

针对某型号打印机的拆卸回收工作，拟规划一条专门的拆卸线。经实地调研得到打印机拆卸作业信息见表4，包括零件的拆卸时间t(s)、单位时间拆卸成本c(元/s)和拆卸方向r，各作业单元的拆卸优先关系如图2所示。

表4 打印机拆卸实例信息表Tab.4 Data information of the printer disassembly instance

图2 打印机拆卸实例的优先关系图Fig.2 The precedence relationships graph of the printer disassembly instance

该打印机拆卸线的规划产量是4500台/月，每月工作30天，每天有效作业时间为6.5 h，总有效作业时间与规划产量的商即为节拍时间Tt，经计算节拍时间Tt=156 s，假设每次方向改变所需的调整时间为2 s。

权衡搜索能力和收敛性能，经多次测算，将算法参数设置为：N=200，Gmax=40，Pc=0.7，Pm=0.1，β=0.9，L=28，R=0.1，α=0.7。运行MIGA求得3个非劣解，根据打印机拆卸线的平衡方案，可以计算出调整次数Ns、工作站数目M、周期时间Tc和产量，各平衡方案的指标见表5。

表5 打印机拆卸线三种平衡方案的指标Tab.5 The indicators for three balancing schemes ofprinter disassembly line

实际生产中，作业人员针对同一拆卸任务的作业时间不为定值，并且存在设备或零部件故障以致无法正常拆卸，需要花费额外的时间，采用特殊手段处理后才能继续拆卸作业。为了确定上述情况是否会对平衡方案的生产能力产生较大影响，采用仿真的方法对方案进行模拟分析。

表6 方案1的拆卸任务分配情况(Tc=148 s)Tab.6 The disassembly task assignment of scheme 1(Tc=148 s)

4 仿真优化

拆卸线规划设计阶段，由于尚未搭建拆卸线实体，难以验证给定的平衡方案。若生产线投产后再对方案进行检查，则会产生时间成本，同时耽误生产进度，因此对平衡方案的预先评估显得尤为重要。对于生产中可能出现的作业时间波动、设备或零部件故障等情况，采用Plant Simulation仿真软件对拆卸线平衡方案进行仿真分析，动态掌握生产线的实际运行状况，完善拆卸线的平衡设计。

4.1仿真建模

根据表6中的拆卸任务分配方案， 建立打印机拆卸线Plant Simulation仿真模型，如图3所示。假设工作站Mm的作业时间服从均值为hm、方差为0.05hm的正态分布，结合“作业信息表Time”中工作站作业时间和调整时间，用封装程序“时间设置Set_time”生成工作站的时间参数。此外，考虑到零部件损坏、设备故障等无法正常拆卸的故障情况，设置工作站出现故障的概率为4%，平均故障处理时间为2 min。

图3 打印机拆卸线仿真模型Fig.3 The simulation model of the printer disassembly line

4.2仿真结果分析及改善

为便于数据统计，设定每天为连续作业，忽略产品在各工作站间的流转时间，只有在上游工作站完成拆卸作业且下游工作站空闲时才能进行产品流转，仿真时间设定为一个月(30天)。设置缓冲区前后工作站各状态时间占比如图4所示，工作站状态包括工作、等待、堵塞和失效状态。无缓存仿真模型的工作站各状态时间占比如图4a所示，具体数据见表7中无缓存值一栏，无缓存仿真模型的月拆卸产量为3855台。

由图4a和表7可知，作业时间的波动性及存在故障等实际情况，使得生产过程中出现了大量的堵塞与等待现象，且靠前的工作站堵塞现象较严重，靠后的工作站等待时间较长。为提高工作站的利用率，通过将图3仿真模型的缓存区Bm连接到工作站Mm前来设置缓存区，其中工作站1紧挨供货源，待拆卸产品持续供货，不存在缺货情况，故工作站1前未设置缓存区，而工作站2～5受相邻工作站作业状态的干扰，出现等待或堵塞情况，因此需要设置缓存区。

由于设置缓存区会导致拆卸线的在制品增多，增加企业的成本，因此必须在尽可能高的利用率和尽可能低的缓存区容量间作出权衡，在此采用仿真软件内置的ExperimentManager控件进行多水平因子试验设计，以确定每个缓存区的最佳容量。设置第i个缓存区的容量Ci从2变化到10且每次递增2，共计625组试验，由于作业时间不为定值，采取多次重复试验取平均值的方法统计数据，重复次数设为10，置信水平设为95%，试验结果如图5所示，横坐标表示试验编号，纵坐标表示10次重复试验的月平均拆卸产量。

(a)无缓存

(b)有缓存图4 设置缓存区前后工作站各状态时间百分比Fig.4 Percentage of each state of the workstation before and after setting cache

由图5可知，纵坐标在水平线4500以上的点表示满足产量要求的缓存区配比。E1最小配比2/2/2/2对应的月平均产出最小为4388台，未达到产量规划要求，但与未设置缓存区时相比多拆卸533台，产量提高了13.8%，表明在工作站前增加缓存区可提高工作站利用率，从而增加产量。最大平均产量4515台对应E370配比为6/10/8/10，产量极差为127台。E625最大配比10/10/10/10对应的平均产量为4512台，并不为所有结果中的最大值，由此说明将各缓存区全部设为最大容量的做法过于粗糙从而造成浪费。以规划产量4500台作为可接受的产出指标，总共有85组平均产量达标，其中有13组较低容量的缓存区容量配比见表8。

表7 理论作业状态与有无缓存区仿真作业状态时间占比Tab.7 The time proportion of the workstations in three different status %

图5 多水平因子试验结果Fig.5 Multilevel factor test results

EC2C3C4C5产量(台)总容量(台)标准差1904661045002614.641994610845012813.37223481064501289.772394106845012813.433006410104503309.81314666845022613.963236610645022812.6234368864502289.693596104845032815.064208481045043015.86459884845002813.00488810664504309.84568106864505309.51

使用总容量、标准差为评价目标，试验E314、E343和E568为Pareto最优解，综合两目标选择E343的配比6/8/8/6为缓存区容量。设置仿真模型中的缓存区容量6/8/8/6，运行仿真模型可得工作站各状态时间占比如图4b所示，具体数据见表7中有缓存值一栏，月拆卸量为4512台。

对比图4和表7可知，设立缓存区后，工作站的平均利用率提高了17.17%，工作站内的堵塞与等待现象得到了显著改善，堵塞率平均下降了33.36%，等待率平均下降了73.34%，产量提高了14.56%。仿真模型考虑了拆卸时间不确定及存在故障等因素，故该打印机拆卸线的月产量在一定范围内波动。设置工作站的故障率为4%、故障处理时间为2 min、缓存区容量配比为6/8/8/6，置信水平为95%，运行10次，置信区间为[4495,4509]，仿真结果中月拆卸产量的波动范围为[4483,4519]，标准差为9.69。

5 结论

(1)考虑调整时间，建立了以最小化拆卸成本、无效作业率和不平滑率为优化目标的多目标带调整时间拆卸线平衡问题模型，更加符合实际生产。

(2)针对拆卸线平衡问题的特点，提出了一种基于Pareto思想的免疫遗传算法，引入接种疫苗操作、免疫检测操作、免疫平衡操作和免疫选择操作等免疫机制，提高了算法的搜索能力。经测试，所提算法在求解DLBP时表现优异。

(3)考虑了服从正态分布的随机拆卸时间及存在故障率的拆卸过程，采用Plant Simulation软件建模仿真，针对该条件下产量不达标问题，通过增加缓存区来改善生产过程，运用多因子水平试验方法确定缓存区最优配比，最后仿真结果表明了所设计拆卸线方案的有效性。

[1] GUNGOR A, GUPTA S M. Disassembly Line in Product Recovery[J]. International Journal of Production Research,2002,40(11):2569-2589.

[2] GUPTA S M, MCGOVERN S M. Disassembly Sequencing Problem: a Case Study of a Cell Phone[C]// Proceedings of the 2004 SPIE International Conference on Environmentally Conscious Manufacturing. Bellingham, USA: SPIE,2004:43-52.

[3] MCGOVERN S M, GUPTA S M. 2-opt Heuristic for the Disassembly Line Balancing Problem[C]//Proceedings of the SPIE International Conference on Environmentally Conscious Manufacturing III. Bellingham, USA: SPIE,2004:71-84.

[4] KOC A, SABUNCUOGLU I, EREL E. Two Exact Formulations for Disassembly Line Balancing Problems with Task Precedence Diagram Construction Using an AND/OR Graph[J]. IIE Transactions,2009,41(10):866-881.

[5] MCGOVERN S M, GUPTA S M. A Balancing Method and Genetic Algorithm for Disassembly Line Balancing[J]. European Journal of Operational Research,2007,179(3):692-708.

[6] ZHANG Z F, FENG Y X, TAN J R, et al. A Novel Approach for Parallel Disassembly Design Based on a Hybrid Fuzzy-time Model[J]. Journal of Zhejiang Universityence A,2015,16(9):724-736.

[7] MCGOVERN S M, GUPTA S M. Uninformed and Probabilistic Distributed Agent Combinatorial Searches for the Unary NP-complete Disassembly Line Balancing Problem[C]//Proceedings of SPIE-The International Society for Optical Engineering. Bellingham, USA: SPIE,2005:81-92.

[8] 朱兴涛, 张则强, 朱勋梦, 等. 求解多目标拆卸线平衡问题的一种蚁群算法[J]. 中国机械工程,2014,25(8):1075-1079. ZHU Xingtao, ZHANG Zeqiang, ZHU Xunmeng, et al. An Ant Colony Optimization Algorithm for Multi-objective Disassembly Line Balancing Problem[J]. China Mechanical Engineering,2014,25(8):1075-1079.

[9] KALAYCI C B, GUPTA S M. Artificial Bee Colony Algorithm for Solving Sequence-dependent Disassembly Line Balancing Problem[J]. Expert Systems with Applications,2013,40(18):7231-7241.

[10] KALAYCI C B, GUPTA S M. A Particle Swarm Optimization Algorithm with Neighborhood-based Mutation for Sequence-dependent Disassembly Line Balancing Problem[J]. Proceedings for the Northeast Region Decision Sciences Institute,2013,69(1/4):197-209.

[11] 丁力平, 谭建荣, 冯毅雄, 等. 基于Pareto蚁群算法的拆卸线平衡多目标优化[J]. 计算机集成制造系统,2009,15(7):1406-1413. DING Liping, TAN Jianrong, FENG Yixiong, et al. Multiobjective Optimization for Disassembly Line Balancing Based on Pareto Ant Colony Algorithm[J]. Computer Integrated Manufacturing Systems,2009,15(7):1406-1413.

[12] MCGOVERN S M, GUPTA S M. Ant Colony Optimization for Disassembly Sequencing with Multiple Objectives[J]. International Journal of Advanced Manufacturing Technology,2006,30(5/6):481-496.

[13] 汤洪涛, 丁彬楚, 李修琳,等. 基于改进免疫遗传算法的混合车间调度研究[J]. 中国机械工程,2014,25(9):1189-1194. TANG Hongtao, DING Binchu, LI Xiulin. Improved Immune Genetic Algorithm for Mixed-model Scheduling Problem[J]. China Mechanical Engineering,2014,25(9):1189-1194.

[14] PAN G, LI K, OUYANG A, et al. Hybrid Immune Algorithm Based on Greedy Algorithm and Delete-cross Operator for Solving TSP[J]. Soft Computing,2016,20(2):1-12.

[15] GHOSH T, DOLOI B, DAN P K. An Immune Genetic Algorithm for Inter-cell Layout Problem in Cellular Manufacturing System[J]. Production Engineering,2015,10(2):1-18.

(编辑王艳丽)

OptimizationofDisassemblyLineBalancingProblemswithSetupTimesBasedon
Multi-objectiveAlgorithmandDynamicSimulation

LI Liuke ZHANG Zeqiang HU Yang ZOU Binsen

School of Mechanical Engineering, SouthwestJiaotong University, Chengdu, 610031

In view of the influences of disassembly direction changes on operation times, a multi-objective model of disassembly line balancing problem considering the setup times was established involving three optimization objectives, i.e. minimizing the disassembly costs, minimizing the invalid work rates and minimizing the non-smooth rates. And a Pareto immune genetic algorithm integrated with the simulation technology was proposed. The proposed algorithm introduced the genetic operator and the immune operator which might avoid the local optimum and ensure the global convergence. The proposed algorithm was applied to a 25-task disassembly case, the results of which indicate the effectiveness of the proposed algorithm by comparing with the other 5 algorithms. Further, the proposed model and the algorithm were applied to design a printer disassembly line. Finally, considering the uncertainty of the disassembly times and failures in the actual disassembly productions, simulation technology was used to analyze and optimize the disassembly line. And the simulation results show that the proposed method may effectively reduce the invalid times caused by waiting and blocking and improve the disassembly efficiency.

disassembly line balancing problem; multi-objective optimization; setup time; immune genetic algorithm; simulation

2016-10-17

国家自然科学基金资助项目(51205328，51405403)；教育部人文社会科学研究青年基金资助项目(12YJCZH296)；四川省应用基础研究计划资助项目(2014JY0232)

TH165

10.3969/j.issn.1004-132X.2017.17.016

李六柯，男，1993年生。西南交通大学机械工程学院硕士研究生。主要研究方向为生产线平衡与智能优化。张则强(通信作者)，男，1978年生。西南交通大学机械工程学院教授、博士研究生导师。E-mail：zzq_22@163.com。胡扬，男，1990年生。西南交通大学机械工程学院硕士。邹宾森，男，1990年生。西南交通大学机械工程学院硕士研究生。