混合遗传算法对混流装配线平衡问题的研究

D0L:10.13374.issn1001-053x.2012.08.018 第34卷第8期 北京科技大学学报 Vol.34 No.8 2012年8月 Journal of University of Science and Technology Beijing Aug.2012 混合遗传算法对混流装配线平衡问题的研究 李险峰☒董绍华 北京科技大学机械工程学院，北京100083 ☒通信作者，E-mail:Tecmia(@126.com 摘要基于面向汽车行业总装生产线平衡问题的研究，提出了一种包含模拟退火因子的改进的遗传算法，设计了加速收敛 因子模型以确保在有限种群空间中的快速收敛：同时考虑了更多工程现场实际约束来修正传统的约束模型.新算法模型应用 在混流装配生产线平衡分析中，取得了算法快速收敛和分析结果与实际工程一致的结果 关键词装配：平衡：遗传算法：模拟退火：问题求解 分类号U468.23 Study on mix-model assembly line balancing with a hybrid genetic algorithm LI Xian-feng,DONG Shao-hua School of Mechanical Engineering,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:Tecmia@126.com ABSTRACT Based on the analysis of balancing in an automotive final assembly line,this paper proposed an enhanced genetic algo- rithm which includes a simulated annealing factor.A specific accelerated-convergence factor was designed for the algorithm to ensure fast convergence within a limited space.In the algorithm more engineering constraints were taken into consideration.The algorithm was applied to a mix-model production line,and the result shows a fast convergence and good agreement with practical engineering. KEY WORDS assembly:balancing:genetic algorithms:simulated annealing:problem solving 混流生产线往往根据不同生产任务的要求在生 分配到不同的装配站点，使得作业量均衡.混流装 产线上同时装配不同类型的产品.这些产品之间存 配线不同产品的装配作业任务和作业时间常存在着 在着装配结构类似、工艺接近等特点.混流装配生 差异，因而给均衡作业任务带来了很大的挑战0 产线可以在不占用大量库存的前提之下，快速响应 本文混合遗传算法设计的目标是在己知确定的 市场对于不同产品品种的需求.装配线平衡分析是 作业时间节拍前提下，优化计算最小的装配工位数 指通过优化分析和计算从而将不同产品的各项不同 目（即第一类装配生产线平衡问题），即首先通过计 装配任务分配到每一个装配站点，使得装配站点的 划产品的需求量计算出平均生产节拍，然后计算最 作业时间小于或者等于预先设定的生产节拍，这在 小装配工位数，通过建立算法模型并用改进的遗传 工程上属于典型的组合优化问题 算法进行问题求解，同时考虑现场待装产品的料箱 目前，对于装配生产线平衡问题的研究，主要围 空间尺寸约束，使得问题的描述更接近生产实际 绕着两个方面进行：(1)给定生产节拍，优化最小工 1问题描述 位数目：(2)给定工位数目，优化最小节拍.前者适 合于计划期产品需求量确定，通过适当的作业分配， 设定M种产品在同一装配生产线上同时装配. 实现作业资源最小化：后者适合于生产资源己经确 每种产品的装配任务顺序都有严格作业的前后逻辑 定，通过适当的作业分配，实现生产时间最小化.无 顺序要求，这种约束可以用作业顺序图加以描述 论是哪种情况，都需要将不同产品的不同作业任务 图1为三种不同产品(A,B,C)装配顺序逻辑 收稿日期：2011-10-27

第 34 卷 第 8 期 2012 年 8 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 34 No． 8 Aug． 2012 混合遗传算法对混流装配线平衡问题的研究 李险峰! 董绍华 北京科技大学机械工程学院，北京 100083 !通信作者，E-mail: Tecmia@ 126． com 摘 要 基于面向汽车行业总装生产线平衡问题的研究，提出了一种包含模拟退火因子的改进的遗传算法，设计了加速收敛 因子模型以确保在有限种群空间中的快速收敛; 同时考虑了更多工程现场实际约束来修正传统的约束模型． 新算法模型应用 在混流装配生产线平衡分析中，取得了算法快速收敛和分析结果与实际工程一致的结果． 关键词 装配; 平衡; 遗传算法; 模拟退火; 问题求解 分类号 U468. 2 + 3 Study on mix-model assembly line balancing with a hybrid genetic algorithm LI Xian-feng! ，DONG Shao-hua School of Mechanical Engineering，University of Science and Technology Beijing，Beijing 100083，China !Corresponding author，E-mail: Tecmia@ 126． com ABSTRACT Based on the analysis of balancing in an automotive final assembly line，this paper proposed an enhanced genetic algo￾rithm which includes a simulated annealing factor． A specific accelerated-convergence factor was designed for the algorithm to ensure fast convergence within a limited space． In the algorithm more engineering constraints were taken into consideration． The algorithm was applied to a mix-model production line，and the result shows a fast convergence and good agreement with practical engineering． KEY WORDS assembly; balancing; genetic algorithms; simulated annealing; problem solving 收稿日期: 2011--10--27 混流生产线往往根据不同生产任务的要求在生 产线上同时装配不同类型的产品． 这些产品之间存 在着装配结构类似、工艺接近等特点． 混流装配生 产线可以在不占用大量库存的前提之下，快速响应 市场对于不同产品品种的需求． 装配线平衡分析是 指通过优化分析和计算从而将不同产品的各项不同 装配任务分配到每一个装配站点，使得装配站点的 作业时间小于或者等于预先设定的生产节拍，这在 工程上属于典型的组合优化问题． 目前，对于装配生产线平衡问题的研究，主要围 绕着两个方面进行: ( 1) 给定生产节拍，优化最小工 位数目; ( 2) 给定工位数目，优化最小节拍． 前者适 合于计划期产品需求量确定，通过适当的作业分配， 实现作业资源最小化; 后者适合于生产资源已经确 定，通过适当的作业分配，实现生产时间最小化． 无 论是哪种情况，都需要将不同产品的不同作业任务 分配到不同的装配站点，使得作业量均衡． 混流装 配线不同产品的装配作业任务和作业时间常存在着 差异，因而给均衡作业任务带来了很大的挑战［1］． 本文混合遗传算法设计的目标是在已知确定的 作业时间节拍前提下，优化计算最小的装配工位数 目( 即第一类装配生产线平衡问题) ，即首先通过计 划产品的需求量计算出平均生产节拍，然后计算最 小装配工位数，通过建立算法模型并用改进的遗传 算法进行问题求解，同时考虑现场待装产品的料箱 空间尺寸约束，使得问题的描述更接近生产实际． 1 问题描述 设定 M 种产品在同一装配生产线上同时装配． 每种产品的装配任务顺序都有严格作业的前后逻辑 顺序要求，这种约束可以用作业顺序图加以描述． 图 1 为三种不同产品 ( A，B，C) 装 配 顺 序 逻 辑 DOI:10.13374/j.issn1001-053x.2012.08.018

第8期 李险峰等：混合遗传算法对混流装配线平衡问题的研究 ·953· 图).每一种产品的装配任务和对应的逻辑顺序 为R(i=1,2,…,m)的最大公约数，则M种产品的 不尽相同.因此在研究多种产品装配顺序问题时， 总需求量r= 把这些不同的产品的装配任务和顺序逻辑图加以综 ,Tm:第m种产品第i个作业任务 合，合并成为一个统一的多产品装配任务、顺序图集 的作业时间为tm;理论最小工位数目则为 (见图2).这个综合任务顺序图包含了M种产品的 M N N个装配操作.由于某个操作的时间对于不同的产 m=1】 (1) 品可能不一样，当一种产品的装配不含其中的某项 C∑rm 装配任务时，则将该任务时间设置为零.在此基础 =】 之上，再根据作业任务的先后顺序约束和一个装配 上式中的最小工位数目为理论上的最小值，但 工艺节拍内M种产品的平均作业时间将作业任务 是实际情况的工位数目往往会大于ST·比如：装 平均分配到各个工位点中.分配方案不一样，各个 配线上有较多的作业任务的平均作业时间接近平均 站点的作业时间也不一样.混流装配线平衡问题是 节拍；或者在任务分配过程之中，即使当前工位的己 求解满足约束条件前提下作业任务的分配，通过一 分配任务的作业时间较短，也有可能容纳不下一个 种优化方案使得各个装配站点的作业时间尽可能均 接近平均节拍时间的操作任务.因此，STm只是一 衡控制到预先设定的节拍限制范围0， 个理论的最小值参考. 在实际平衡装配生产线的分析过程中，装配工 (② *（3 位的负荷平衡是一个很重要的衡量因素，当负荷不 6 均匀时，系统的等待、堵塞较重，效率低下.只有当 4 负荷均匀时，才能使整个装配生产系统的效率最 高刀.因此，在平衡作业任务时，整线的效率K是一 个重要的考察目标.以各个工位负荷均匀为优化目 ) ①②③⑥ 标，可以描述为： (e) 图1装配顺序逻辑图.(a)产品A:(b)产品B:()产品C min:K:= Fig.I Logic diagram of assembly sequence by products:(a)Prod- uct A:(b)Product B:(c)Product C (2) (② (③ xg=1,i=1,2,…,N: (3) (6 g≤∑ui,k=l,…N: (4) 4 taxe:m=12.M j-12.8; ⑤ (5) 图2合并后装配顺序逻辑图 Fig.2 Logic diagram of combined assembly sequence 言9.7eCj=125: (6) xg∈{0,1}，i=1,2,…,N,j=1,2,…,S:(7) 2数学模型 ∑D,≤D (8) 基于上述的问题描述，提出了针对这类问题的 数学模型 式(2)中的目标函数是各个工位点的负荷的均方差 设定在一个计划时期T内，第m种产品的需求 最小，也就是说各个站点的负荷尽可能接近，其中 量为Rm(m=1,2,…,M),则M种产品的总需求量 qm是第m种产品需求量占所有产品需求量的百分 R=立R:平均生产节拍G=了在一个最小 比，三。=1：式3)表示作业任务分配到工位时 R 候的唯一性：式(4)中表示装配约束属性：式(5)为 整个工位作业时间和时间不大于式(6)中预设的节 生产循环中，第m种产品的需求量为dn,dn= 拍C,;式(7)表示作业任务分配的装配（己分配为

第 8 期 李险峰等: 混合遗传算法对混流装配线平衡问题的研究 图［2--3］． 每一种产品的装配任务和对应的逻辑顺序 不尽相同． 因此在研究多种产品装配顺序问题时， 把这些不同的产品的装配任务和顺序逻辑图加以综 合，合并成为一个统一的多产品装配任务、顺序图集 ( 见图 2) ． 这个综合任务顺序图包含了 M 种产品的 N 个装配操作． 由于某个操作的时间对于不同的产 品可能不一样，当一种产品的装配不含其中的某项 装配任务时，则将该任务时间设置为零． 在此基础 之上，再根据作业任务的先后顺序约束和一个装配 工艺节拍内 M 种产品的平均作业时间将作业任务 平均分配到各个工位点中． 分配方案不一样，各个 站点的作业时间也不一样． 混流装配线平衡问题是 求解满足约束条件前提下作业任务的分配，通过一 种优化方案使得各个装配站点的作业时间尽可能均 衡控制到预先设定的节拍限制范围［4］． 图 1 装配顺序逻辑图． ( a) 产品 A; ( b) 产品 B; ( c) 产品 C Fig． 1 Logic diagram of assembly sequence by products: ( a) Prod￾uct A; ( b) Product B; ( c) Product C 图 2 合并后装配顺序逻辑图 Fig． 2 Logic diagram of combined assembly sequence 2 数学模型 基于上述的问题描述，提出了针对这类问题的 数学模型． 设定在一个计划时期 T 内，第 m 种产品的需求 量为 Rm ( m = 1，2，…，M) ，则 M 种产品的总需求量 R = ∑ M m = 1 Rm ; 平均生产节拍 Ct = T ∑ M m = 1 Rm ; 在一个最小 生产循环中，第 m 种产品的需求量为 dm，dm = Rm r ，r 为 Ri ( i = 1，2，…，m) 的最大公约数，则 M 种产品的 总需求量 r = ∑ M m = 1 rm ． 第 m 种产品第 i 个作业任务 的作业时间为 tim ; 理论最小工位数目［5--6］则为 STmin = ∑ M m = 1 ∑ N i = 1 rm tim Ct∑ M m = 1 rm ． ( 1) 上式中的最小工位数目为理论上的最小值，但 是实际情况的工位数目往往会大于STmin ． 比如: 装 配线上有较多的作业任务的平均作业时间接近平均 节拍; 或者在任务分配过程之中，即使当前工位的已 分配任务的作业时间较短，也有可能容纳不下一个 接近平均节拍时间的操作任务． 因此，STmin只是一 个理论的最小值参考． 在实际平衡装配生产线的分析过程中，装配工 位的负荷平衡是一个很重要的衡量因素，当负荷不 均匀时，系统的等待、堵塞较重，效率低下． 只有当 负荷均匀时，才能使整个装配生产系统的效率最 高［7］． 因此，在平衡作业任务时，整线的效率 K 是一 个重要的考察目标． 以各个工位负荷均匀为优化目 标，可以描述为: min: Ki = ∑ S k = ( 1 ∑ M m = 1 qm Tmk － ∑ S j = 1 ∑ M m = 1 qm Tmj S ) 2 槡 S ; ( 2) s． t． ∑ S j = 1 xij = 1，i = 1，2，…，N; ( 3) ∑ S j = 1 jxij≤ ∑ S l = 1 lxkl，i，k = 1，…，N; ( 4) Tmj = ∑ N i = 1 tmixij ，m = 1，2，…，M，j = 1，2，…，S; ( 5) ∑ M m = 1 qm Tmj≤Ct，j = 1，2，…，S; ( 6) xij∈{ 0，1} ，i = 1，2，…，N，j = 1，2，…，S; ( 7) ∑ M i = 1 Di≤Dv ． ( 8) 式( 2) 中的目标函数是各个工位点的负荷的均方差 最小，也就是说各个站点的负荷尽可能接近，其中 qm 是第 m 种产品需求量占所有产品需求量的百分 比，∑ M m = 1 qm = 1; 式( 3) 表示作业任务分配到工位时 候的唯一性; 式( 4) 中表示装配约束属性; 式( 5) 为 整个工位作业时间和时间不大于式( 6) 中预设的节 拍 Ct ; 式( 7) 表示作业任务分配的装配( 已分配为 ·953·

·954· 北京科技大学学报 第34卷 1;未分配为0). 边，要么只能放在右边，要么两边都能放，如果都能 另外，作者查阅到的研究文献未见有在负荷平 放，就随机选一个位置插入.对于一般的情况，即队 衡计算时考虑工程现场物料体积约束影响的.装配 列中已经有k个节点的情况，任选一个待插入节点， 生产线上每一个作业区域（装配工位）有一个固定 将有k+1个可插入位置，对这k+1个位置进行逐 的空间体积D,在装配线旁的零部件物流区中预置 步排查，假设有n个可插入节点，则任选一个可插入 的待装零部件总体的体积不能超过这个预设的体位置将其插入队列.重复以上过程，直到队列满 积.式(8)中约束条件是指每一个装配工位旁的物位置 料存放的总体尺寸不超过预先设定的空间体积（见 3.3交叉算子 图3). 为了更好地保留父辈的信息，本文采用了一种 所谓“次序交叉”(sequence crossover)的方法.该方 法是传统单点交叉圆的扩展，具体步骤如下 步骤1：随机产生交叉点（见图5） 父辈个体11256438107911 父辈个体21324579681011 图5交叉算子设计第一步 Fig.5 Step I of crossover design 每个装配工位的固定尺寸 步骤2：选取父代1交叉点左侧部分染色体进 入子代1（见图6）. 图3体积约束示意图 Fig.3 Illustration of volume restraints 父辈个体1125643 图6交叉算子设计第二步 3算法设计 Fig.6 Step 2 of crossover design 装配生产线作业平衡问题是一个典型NP难 步骤3：根据父代2产生子代1剩余染色体（见 题，本文采用改进的遗传算法对于这个问题进行 图7). 分析. 父辈个体2132457968101日 3.1编码方法 子代个体11256437g81011 基因串的编码采用自然数编码，编码是长度为 图7交叉算子设计第三步 N的数据串.每一个基因的序号对应任务的序号， Fig.7 Step 3 of crossover design 基因座上的基因值标识的是分配到的作业单元的编 号，如图4所示 步骤4：交换父代位置，产生子代2（见图8）. 基因中四 子代个体21324576810911 个 图8交叉算子设计第四步 工作点123456？8 Fig.8 Step 4 of crossover design 作业任务1523746,8129101日2014,1516,1718,19 通过次序交叉之后的子代可能存在产生不可行 图4基因编码方法 解的问题，本文通过采取将染色体中交叉重复的基 Fig.4 Chromosome coding 因剔除的方法来保证后代解的可行性.如两个父代 3.2初始种群的产生方法 染色体f:{63254}和f万：{4365 将V个作业任务分配到M个工位，需要考虑作 2}的交叉点为3，则f中的{54}和6中的{52} 业任务之间的先后顺序和工位时间累积消耗不超过 进行交换，并删除∫和方中相同的基因部分，即生 节拍的限制.为此，本文设计了一种基于任务排序 成子代f:{63452}和：{3625 的种群初始化方法，流程如下. 4},从而避免了交叉过程中产生的不可行解. 首先，任意取出一个任务节点，加入空队列.然 3.4变异算子 后，从剩余节点中任选一个节点，它要么只能放在左 交叉重组之后是个体的变异.子个体变量以很

北 京 科 技 大 学 学 报 第 34 卷 1; 未分配为 0) ． 另外，作者查阅到的研究文献未见有在负荷平 衡计算时考虑工程现场物料体积约束影响的． 装配 生产线上每一个作业区域( 装配工位) 有一个固定 的空间体积 Dv，在装配线旁的零部件物流区中预置 的待装零部件总体的体积不能超过这个预设的体 积． 式( 8) 中约束条件是指每一个装配工位旁的物 料存放的总体尺寸不超过预先设定的空间体积( 见 图 3) ． 图 3 体积约束示意图 Fig． 3 Illustration of volume restraints 3 算法设计 装配生产线作业平衡问题是一个典型 NP 难 题，本文采用改进的遗传算法对于这个问题进行 分析． 3. 1 编码方法 基因串的编码采用自然数编码，编码是长度为 N 的数据串． 每一个基因的序号对应任务的序号， 基因座上的基因值标识的是分配到的作业单元的编 号，如图 4 所示． 图 4 基因编码方法 Fig． 4 Chromosome coding 3. 2 初始种群的产生方法 将 N 个作业任务分配到 M 个工位，需要考虑作 业任务之间的先后顺序和工位时间累积消耗不超过 节拍的限制． 为此，本文设计了一种基于任务排序 的种群初始化方法，流程如下． 首先，任意取出一个任务节点，加入空队列． 然 后，从剩余节点中任选一个节点，它要么只能放在左 边，要么只能放在右边，要么两边都能放，如果都能 放，就随机选一个位置插入． 对于一般的情况，即队 列中已经有 k 个节点的情况，任选一个待插入节点， 将有 k + 1 个可插入位置，对这 k + 1 个位置进行逐 步排查，假设有 n 个可插入节点，则任选一个可插入 位置将其插入队列． 重复以上过程，直到队列满 位置． 3. 3 交叉算子 为了更好地保留父辈的信息，本文采用了一种 所谓“次序交叉”( sequence crossover) 的方法． 该方 法是传统单点交叉［8］的扩展，具体步骤如下． 步骤 1: 随机产生交叉点( 见图 5) ． 图 5 交叉算子设计第一步 Fig． 5 Step 1 of crossover design 步骤 2: 选取父代 1 交叉点左侧部分染色体进 入子代 1 ( 见图 6) ． 图 6 交叉算子设计第二步 Fig． 6 Step 2 of crossover design 步骤 3: 根据父代 2 产生子代 1 剩余染色体( 见 图 7) ． 图 7 交叉算子设计第三步 Fig． 7 Step 3 of crossover design 步骤 4: 交换父代位置，产生子代 2( 见图 8) ． 图 8 交叉算子设计第四步 Fig． 8 Step 4 of crossover design 通过次序交叉之后的子代可能存在产生不可行 解的问题，本文通过采取将染色体中交叉重复的基 因剔除的方法来保证后代解的可行性． 如两个父代 染色体 f1 : { 6 3 2 5 4} 和 f2 : { 4 3 6 5 2} 的交叉点为 3，则 f1 中的{ 5 4} 和 f2 中的{ 5 2} 进行交换，并删除 f1 和 f2 中相同的基因部分，即生 成子代 f1 : { 6 3 4 5 2} 和 f2 : { 3 6 2 5 4} ，从而避免了交叉过程中产生的不可行解． 3. 4 变异算子 交叉重组之后是个体的变异． 子个体变量以很 ·954·

第8期 李险峰等：混合遗传算法对混流装配线平衡问题的研究 ·955· 小的概率或者步长进行变异，变量转变的概率或者 P= aP: (10) 步长与维数（变量的个数）成反比，与种群的数量大 小无关.据研究，变异本身是一种局部随机搜索，与 选择、重组算子组合在一起，保证了遗传算法的有效 第三步：对变异得到的新个体mutpop:(k)计算 性：同时保证了种群的多样性，以防止出现非成熟收 其适应度值，并按照Metropolis概率准则选择接受 敛.在本文变异操作中，引入变异率P,它是一个很 或者放弃这个个体，如果接受则更新，否则放弃 关键的参数，控制着种群中参与变异的基因个体位 第四步：按照这个过程循环N次 数，P是一个取值在0~1之间的参数，取值越大表 整个算法的流程框架如图9所示 示参与变异的基因位越多，但当P大于0.5后，算 确定算法参数 法退化变成了随机搜索，遗传算法的意义就不复存 t 在回.与此同时，变异概率P决定了某个个体参与 初始化种群，确定初温 有 变异的概率，它是一个相对种群而言的概念.一旦 评价当前种群中各个个体 决定参与变异的基因位，这些基因就被抽出来，剩余 的队列中的作业元素（任务）保持原来的顺序不变， 算法收敛准则 输出优化结柴 将这些抽取出来的任务节点重新插入到队列中，从 满足杏？ TN 而实现变异.同样地，采用和交叉算子类似的方法 执行GA选择和复制操作 处理变异后产生的不可行解问题，从而保证变异的 执行CA的交叉操作保优) 解满足基础的装配顺序约束. 3.5适应度函数 执行GA的变异操作（保优） 为了构造能够满足装配生产线平衡的适应度函 得到SA初始种群，对种群中的 数，让遗传算法朝着装配作业工位数目最少的方向 个体实施SA搜索 市 进化.本文提出了如下的适应度函数： 山SA状态产生函数产生 新的个体 f=1-K (9) 以概率接受新的个体 3.6加入模拟退火因子和收敛加速因子辅助算法 加速收敛 退温操作、y SA出样是杏稳定？ N 为了克服传统单一的基于轮盘赌思路的遗传算 GA一遗传算法：SA一模拟退火算法 法的局限性)，很多学者分别将其他智能算法的因 图9改进遗传算法流程框架 素引入遗传算法，形成了很多新的智能组合优化算 Fig.9 Workflow of the enhanced genetic algorithm 法.从算法本质而言，这些新的模拟自然界现象的 优化策略加入到遗传算法的选择环节就是为了解决 算法实现与验证 在选择父代和生成子代的过程中子代“新鲜性”问 题.在种群数量相对有限的前提下，跳出局部最优 基于上述算法思路和流程，本文采用通用仿真 解的“陷阱”，达到全局最优或者工程最优回.本文 工具MATLAB进行了算法实现.同时为了验证和分 中解决遗传算法早熟问题的思路是引入“遗传退 析改进的遗传算法在工程应用中的价值和能力，本 火”的策略 文选取了某型号汽车驾驶室仪表台总成（如图10 在基于标准模拟退火思路的基础之上，本文给 所示)的分装线的数据，结合本文算法程序进行了 出了包含“退火算法”思想的改进的选择操作的思 路和算法框架以及程序脚本.算法思路如下 第一步：在第k代种群poP:和当前温度tk条件 下，访问种群中的每一个个体pop,(k). 第二步：对于每一个个体，随机选择变异位，进 行变异（在其邻域中随机选择一个状态）.其中变异 概率与被选路径总数成正比，α为比例常数.经修 图10待分析产品结构示意图 正的变异概率P为 Fig.10 Schematic diagram of to-be assembled products

第 8 期 李险峰等: 混合遗传算法对混流装配线平衡问题的研究 小的概率或者步长进行变异，变量转变的概率或者 步长与维数( 变量的个数) 成反比，与种群的数量大 小无关． 据研究，变异本身是一种局部随机搜索，与 选择、重组算子组合在一起，保证了遗传算法的有效 性; 同时保证了种群的多样性，以防止出现非成熟收 敛． 在本文变异操作中，引入变异率 Pd，它是一个很 关键的参数，控制着种群中参与变异的基因个体位 数，Pd 是一个取值在 0 ～ 1 之间的参数，取值越大表 示参与变异的基因位越多，但当 Pd 大于 0. 5 后，算 法退化变成了随机搜索，遗传算法的意义就不复存 在［9］． 与此同时，变异概率 Pm 决定了某个个体参与 变异的概率，它是一个相对种群而言的概念． 一旦 决定参与变异的基因位，这些基因就被抽出来，剩余 的队列中的作业元素( 任务) 保持原来的顺序不变， 将这些抽取出来的任务节点重新插入到队列中，从 而实现变异． 同样地，采用和交叉算子类似的方法 处理变异后产生的不可行解问题，从而保证变异的 解满足基础的装配顺序约束． 3. 5 适应度函数 为了构造能够满足装配生产线平衡的适应度函 数，让遗传算法朝着装配作业工位数目最少的方向 进化． 本文提出了如下的适应度函数: f = 1 － K． ( 9) 3. 6 加入模拟退火因子和收敛加速因子辅助算法 加速收敛 为了克服传统单一的基于轮盘赌思路的遗传算 法的局限性［7］，很多学者分别将其他智能算法的因 素引入遗传算法，形成了很多新的智能组合优化算 法． 从算法本质而言，这些新的模拟自然界现象的 优化策略加入到遗传算法的选择环节就是为了解决 在选择父代和生成子代的过程中子代“新鲜性”问 题． 在种群数量相对有限的前提下，跳出局部最优 解的“陷阱”，达到全局最优或者工程最优［9］． 本文 中解决遗传算法早熟问题的思路是引入“遗传退 火”的策略． 在基于标准模拟退火思路的基础之上，本文给 出了包含“退火算法”思想的改进的选择操作的思 路和算法框架以及程序脚本． 算法思路如下． 第一步: 在第 k 代种群 popk 和当前温度 tk 条件 下，访问种群中的每一个个体 popi ( k) ． 第二步: 对于每一个个体，随机选择变异位，进 行变异( 在其邻域中随机选择一个状态) ． 其中变异 概率与被选路径总数成正比，α 为比例常数． 经修 正的变异概率 P 槇i 为 P 槇i = αPi ∑ m j = 1 Pj ． ( 10) 第三步: 对变异得到的新个体 mutpopi ( k) 计算 其适应度值，并按照 Metropolis 概率准则选择接受 或者放弃这个个体，如果接受则更新，否则放弃． 第四步: 按照这个过程循环 N 次． 整个算法的流程框架如图 9 所示． GA—遗传算法; SA—模拟退火算法 图 9 改进遗传算法流程框架 Fig． 9 Workflow of the enhanced genetic algorithm 图 10 待分析产品结构示意图 Fig． 10 Schematic diagram of to-be assembled products 4 算法实现与验证 基于上述算法思路和流程，本文采用通用仿真 工具 MATLAB 进行了算法实现． 同时为了验证和分 析改进的遗传算法在工程应用中的价值和能力，本 文选取了某型号汽车驾驶室仪表台总成( 如图 10 所示) 的分装线的数据，结合本文算法程序进行了 ·955·

·956 北京科技大学学报 第34卷 试算. OPTO 分装线上分别有两种不同类型的仪表台装配总 成：A型号仪表台装配流程如图11所示：B型号仪 表台装配流程如图12所示.混装两种仪表台的作 业时间和对应零部件的体积数据见表1. OP0-OF03 -()-OP11 OPTO (m9 OP1-OP13 图12B产品装配工艺顺序图 -() Fig.12 Assembly sequence of Product B OP0S-OPOO-OP11 T 需求量为28000件.装配线时间节拍C,=- M OP1OP13 图11A产品装配工艺顺序图 250×16×3600/48000s=300s(假定一年250个 Fig.11 Assembly sequence of Product A 工作日，一天两班共16h)0:产线布局设计中，装 配线旁物流区零件体积最大值D,=450,算法求解 设定A产品的年需求量为20000件：B产品的 过程中的基本控制参数如下表2所示. 表1装配时间和产品体积信息 Table 1 Assembly time and part size information 产品A 产品B 装配流程 作业代号 作业时间/s 装配产品的体积 作业代号 作业时间/s 装配产品的体积 主定位支架安装 OPO1 33 100 0P01 33 125 转同柱安装 0P02 38 20 OP02 38 20 仪表台内面板安装 OP03 49 35 OP03 49 35 气囊安装 0P04 50 0P04 30 空调风道安装 OP05 15 35 0P05 15 35 空调出风口格栅安装 OP06 3 25 0P06 子 25 仪表（速度、转速）安装 0P07 69 15 0P07 69 15 内部线缆安装 OP08 30 150 0P08 30 150 低位外部面板安装 OP09 吃 0P09 % 手套箱安装 OP1O 15 10 0P10 10 通风控制系统安装 OP11 防 0P11 25 副驾驶储存箱安装 OP12 23 6 OP12 2 67 中央控制面板 OP13 55 35 OP13 38 音响系统安装 0P14 35 66 0P14 35 70 涂腔 OP15 9 15 0P15 9 20 装配控制调整 OP16 27 10 0P16 27 125 注：此处的体积是量纲为1的量 表2算法算例中的控制参数取值 经仿真分析，计算结果如下 Table 2 Description and values of parameters in the algorithm 需要的最小装配工位数为4，见图13，工位1中 算法 参数 取值 算例 收敛 的装配任务为 参数 说明 范围 取值 相关性 M 进化迭代次数 100~200 200 相对高 {oP2(a),0P3(a),0P4(a),0P5(a),oP6(a), 种群规模，必须取偶数 偶数 吃 相对高 OP2(b),0P3(b),OP4(b),OP5(b)}; Po 变异概率 0~1 0.6 令 工位2中的装配任务为 Pa 变异程度控制参数 01 0.1 高 {0P7(a),0P9(a),0P11(b),0P13(a),0P15(a)}: Z 状态转移次数 >1 3 相对高 初始温度 1 1 相对高 工位3中的装配任务为 B 降温系数 01 0.9 高 OP8(a),OP10(a),OP12(a),OP14(a),0P6(b)

北 京 科 技 大 学 学 报 第 34 卷 试算． 分装线上分别有两种不同类型的仪表台装配总 成: A 型号仪表台装配流程如图 11 所示; B 型号仪 表台装配流程如图 12 所示． 混装两种仪表台的作 业时间和对应零部件的体积数据见表 1． 图 11 A 产品装配工艺顺序图 Fig． 11 Assembly sequence of Product A 设定 A 产品的年需求量为 20 000 件; B 产品的 图 12 B 产品装配工艺顺序图 Fig． 12 Assembly sequence of Product B 需求量为28000 件． 装配线时间节拍 Ct = T ∑ M m = 1 Dm = 250 × 16 × 3 600 /48 000 s = 300 s ( 假定一年 250 个 工作日，一天两班共 16 h) ［10］; 产线布局设计中，装 配线旁物流区零件体积最大值 Dv = 450，算法求解 过程中的基本控制参数如下表 2 所示． 表 1 装配时间和产品体积信息 Table 1 Assembly time and part size information 装配流程 产品 A 产品 B 作业代号 作业时间/s 装配产品的体积 作业代号 作业时间/s 装配产品的体积 主定位支架安装 OP01 33 100 OP01 33 125 转同柱安装 OP02 38 20 OP02 38 20 仪表台内面板安装 OP03 49 35 OP03 49 35 气囊安装 OP04 35 50 OP04 35 30 空调风道安装 OP05 15 35 OP05 15 35 空调出风口格栅安装 OP06 25 25 OP06 25 25 仪表( 速度、转速) 安装 OP07 69 15 OP07 69 15 内部线缆安装 OP08 30 150 OP08 30 150 低位外部面板安装 OP09 60 60 OP09 60 60 手套箱安装 OP10 15 10 OP10 15 10 通风控制系统安装 OP11 45 25 OP11 45 25 副驾驶储存箱安装 OP12 23 67 OP12 23 67 中央控制面板 OP13 55 35 OP13 55 38 音响系统安装 OP14 35 66 OP14 35 70 涂腔 OP15 20 15 OP15 20 20 装配控制调整 OP16 27 10 OP16 27 125 注: 此处的体积是量纲为 1 的量． 表 2 算法算例中的控制参数取值 Table 2 Description and values of parameters in the algorithm 算法 参数 参数 说明 取值 范围 算例 取值 收敛 相关性 M 进化迭代次数 100 ～ 200 200 相对高 N 种群规模，必须取偶数 偶数 30 相对高 Pm 变异概率 0 ～ 1 0. 6 高 Pd 变异程度控制参数 0 ～ 1 0. 1 高 Z 状态转移次数 ＞ 1 3 相对高 t0 初始温度 1 1 相对高 β 降温系数 0 ～ 1 0. 9 高 经仿真分析，计算结果如下． 需要的最小装配工位数为 4，见图 13，工位 1 中 的装配任务为 { OP2( a) ，OP3( a) ，OP4( a) ，OP5( a) ，OP6( a) ， OP2( b) ，OP3( b) ，OP4( b) ，OP5( b) } ; 工位 2 中的装配任务为 { OP7( a) ，OP9( a) ，OP11( b) ，OP13( a) ，OP15( a) } ; 工位 3 中的装配任务为 { OP8( a) ，OP10( a) ，OP12( a) ，OP14( a) ，OP6( b) ， ·956·

第8期 李险峰等：混合遗传算法对混流装配线平衡问题的研究 ·957· OP7(b),OP9(b),OP12(b),OP15(b)}; 同时，整线的工位负荷率参见图15.在当前的 工位4中的装配任务为 任务平衡分配方案中，S1工位到S4工位的平衡效 {OP1(a),0P16(a),OP1(b),OP1(b), 率K在97.85%左右（绿色柱状条比例），平衡效率 0P8(b),0P10(b),0P11(b),0P13(b), 指标良好 OP14(b),0P16(b)}. 100 四个工位的总时间消耗均小于C,满足节拍要求： 90 各个工位内部的作业顺序甘特图和累计时间消耗见 图13和14所示，作业时间满足节拍要求，作业顺序 满足装配顺序约束条件 60 50 350 300 00 6 21 250 14 - 2 1- 10 15 215 0 S2 S4 150 -3 S3 2-7 21 工位编号 100 1-7 14 -16 图15装配工位的平衡效率图 2-13 Fig.15 Efficiency of each station 22 19 2-9 2-8 各工位零件体积消耗分布（见图16).根据上 装配线上.工位数目 图的任务分配组合情况，同时得出考虑零件体积约 图13 最小的装配工位数目与作业分配方案 束工况下的每个工位零件体积消耗如下（见表3）， Fig.13 Minimized station numbers and allocated operation 可以看到每个工位下分配任务消耗的零件的体积均 未超过预设D,满足设计要求；相比之下，如果忽略 产品体积的约束条件进行分析计算，得到的工位的 分配任务对应的零件体积消耗与对应作业任务分配 方案见图16(b)、图17和表3第三列，此时虽然工 位下任务时间总和小于预设时间值，但是！和料工 位下的零件体积消耗超过预设的D,这种分配方案 在工程实际中是不允许发生的.很明显，不考虑体 积约束的分配方案在实际场景中是不可行的 优化算法收敛过程如图18所示.本算例的硬 图14 工位任务作业甘特图 件运行环境为CPU2.1GHz主频、4GB内存、250GB Fig.14 Gantt chart in each station 硬盘的DELL笔记本，算例算法预设的最大迭代次 600 500a 500 1-6 400 25 1-10 1-0 400 2-13 300 1-4 1-15 2-15 300 01 -13 200 1-2 1-14 2-6 2-10 200 2-14 -5 l-5 100 22 9 29 100 213 2-9 1-6 2- 2 2 工位数目 工位数目 图16工位零件体积消耗.(a)考虑约束；(b)不考虑约束 Fig.16 Consumed volumes of parts under stations:(a) with considering constraints:(b)without considering constraints

第 8 期 李险峰等: 混合遗传算法对混流装配线平衡问题的研究 OP7( b) ，OP9( b) ，OP12( b) ，OP15( b) } ; 工位 4 中的装配任务为 { OP1( a) ，OP16( a) ，OP1( b) ，OP1( b) ， OP8( b) ，OP10( b) ，OP11( b) ，OP13( b) ， OP14( b) ，OP16( b) } ． 图 16 工位零件体积消耗． ( a) 考虑约束; ( b) 不考虑约束 Fig． 16 Consumed volumes of parts under stations: ( a) with considering constraints; ( b) without considering constraints 四个工位的总时间消耗均小于 Ct，满足节拍要求; 各个工位内部的作业顺序甘特图和累计时间消耗见 图 13 和 14 所示，作业时间满足节拍要求，作业顺序 满足装配顺序约束条件． 图 13 最小的装配工位数目与作业分配方案 Fig． 13 Minimized station numbers and allocated operation 图 14 工位任务作业甘特图 Fig． 14 Gantt chart in each station 同时，整线的工位负荷率参见图 15． 在当前的 任务平衡分配方案中，S1 工位到 S4 工位的平衡效 率 K 在 97. 85% 左右( 绿色柱状条比例) ，平衡效率 指标良好． 图 15 装配工位的平衡效率图 Fig． 15 Efficiency of each station 各工位零件体积消耗分布( 见图 16) ． 根据上 图的任务分配组合情况，同时得出考虑零件体积约 束工况下的每个工位零件体积消耗如下( 见表 3) ， 可以看到每个工位下分配任务消耗的零件的体积均 未超过预设 Dv，满足设计要求; 相比之下，如果忽略 产品体积的约束条件进行分析计算，得到的工位的 分配任务对应的零件体积消耗与对应作业任务分配 方案见图 16( b) 、图 17 和表 3 第三列，此时虽然工 位下任务时间总和小于预设时间值，但是#1 和#4 工 位下的零件体积消耗超过预设的 Dv，这种分配方案 在工程实际中是不允许发生的． 很明显，不考虑体 积约束的分配方案在实际场景中是不可行的． 优化算法收敛过程如图 18 所示． 本算例的硬 件运行环境为 CPU 2. 1 GHz 主频、4 GB 内存、250 GB 硬盘的 DELL 笔记本，算例算法预设的最大迭代次 ·957·

·958 北京科技大学学报 第34卷 数是200.可以看出算法在迭代步数为40步之前己 束条件加入仿真算法模型，使得分析的结果更具可 经收敛，该算例的平均计算时间为10s,算法的收敛 行性. 速度是很快的. 参考文献 表3工位下的零件体积消耗 Table 3 Consumed volumes of parts under stations [Yang BQ,Tong M S.Mathematical modeling of automobile as- sembly line balancing.Electr Drive Autom,2004,26 (1):60 工位号 体积消耗（考虑约束） 体积消耗（不考虑约束） (杨本强，童明似.汽车总成装配作业均衡编排问题的数学建 No.I 450 465 模.电气传动自动化，2004,26(1)：60) No.2 318 276 2]Cao Z X,Zhu Y L,Zhao M Y,et al.Optimal research on balan- No.3 440 502 cing and sequencing of mixed model assembly lines.Inf Control, No.4 450 415 2004,33(6):660 (曹振新，朱云龙，赵明扬，等.混流装配线负荷平衡与投产顺 序的优化研究.信息与控制，2004,33(6)：660) 350 B]Zhou X L.Cao Z X.Planning and simulation of the mix model as- 300 1-8 1-16 2-1 sembly lines.Mach Tool Hydraul,2008,36(4):344 L-0 250- 2.16 (周小丽，曹振新.混流装配线的规划设计与仿真研究.机床 1-9 1-14 2-13 2-0 与液压，2008,36(4)：344) 2-11 [4]Liu J H,Hou D L.The methods for solving the problem of balan- 13 212 150 1-7 -13 cing an assembly line.For Eng,2006,22(4):21 100 (刘晋浩，侯东亮。装配线平衡问题的求解方法浅析.森林工 2-15 2-14 2-3 5 28 程，2006,22(4)：21) 50 1-6 26 22 5]Yu Z Q,Su P.Combining genetic algorithm and simulation analy- 2-4 2-9 sis for mix-model assembly line balancing problem.Comput Integr 4 工位数目 Manuf Syst,2008,14(6):1120 图17工位数与作业平衡分配方案（不考虑约束） (于兆勤，苏平.基于遗传算法和仿真分析的混合装配线平衡 Fig.17 Station number and allocated operation chart (without con- 问题研究.计算机集成制造系统，2008,14(6)：1120) [6]Li B,Chen L P,Huang Z D.et al.Research on assembly line sidering constraint) optimal scheduling for mass customization production.China Mech 1.9 Eng,2005,16(24):2198 1.8 (李斌，陈立平，黄正东，等.面向大规模定制的装配线优化调 1.7 度研究.中国机械工程，2005,16(24)：2198) Ling W S.Research on balancing of mix-model assembly line 三1.6 +最住适应度 平均适应度 workstations based on genetic algorithm.Hefei Unir Technol 1.5 2008,31(8):1287 (凌文曙.基于遗传算法的混流装配线工作站平衡研究.合肥 工业大学学报：自然科学版，2008,31(8)：1287) 1.3 8] Wu J H,Xia J K,Cao S H.Modeling of ALB Problem and its op- 80120 160200 timization.J Syst Simul,1999,11 (5):358 迭代次数 (吴君华，夏巨谌，曹山河.ALB问题的数学模型及其优化算 图18算法收敛曲线图 法的研究.系统仿真学报，1999,11(5)：358) Fig.18 Convergence curves of the algorithm Wang L.Intelligent Optimization Algorithm and its Application Beijing:Tsinghua University Press,2001 5结论 (王凌.智能优化算法与应用.北京：清华大学出版社，2001) [10]Cai M,Wang F N,Yang S X.Material supply on car assembly 在混流生产线平衡问题的研究中，本文的创新 line with JIT manufacturing style.Manuf Autom,2006,28 (Sup- 之处在于数学建模中对于加速迭代收敛、避免遗传 pl):233 算法中的种群退化进行了算法混合优化处理，同时 (蔡苗，王峰年，杨少霞.T生产模式下混流轿车总装配线 将之前很少考虑的现场物料摆放空间的限制作为约 上的物料配送.制造业自动化，2006,28（增刊）：233)

北 京 科 技 大 学 学 报 第 34 卷 数是 200． 可以看出算法在迭代步数为 40 步之前已 经收敛，该算例的平均计算时间为 10 s，算法的收敛 速度是很快的． 表 3 工位下的零件体积消耗 Table 3 Consumed volumes of parts under stations 工位号 体积消耗( 考虑约束) 体积消耗( 不考虑约束) No． 1 450 465 No． 2 318 276 No． 3 440 502 No． 4 450 415 图 17 工位数与作业平衡分配方案( 不考虑约束) Fig． 17 Station number and allocated operation chart ( without con￾sidering constraint) 图 18 算法收敛曲线图 Fig． 18 Convergence curves of the algorithm 5 结论 在混流生产线平衡问题的研究中，本文的创新 之处在于数学建模中对于加速迭代收敛、避免遗传 算法中的种群退化进行了算法混合优化处理，同时 将之前很少考虑的现场物料摆放空间的限制作为约 束条件加入仿真算法模型，使得分析的结果更具可 行性． 参 考 文 献 ［1］ Yang B Q，Tong M S． Mathematical modeling of automobile as￾sembly line balancing． Electr Drive Autom，2004，26 ( 1) : 60 ( 杨本强，童明俶． 汽车总成装配作业均衡编排问题的数学建 模． 电气传动自动化，2004，26( 1) : 60) ［2］ Cao Z X，Zhu Y L，Zhao M Y，et al． Optimal research on balan￾cing and sequencing of mixed model assembly lines． Inf Control， 2004，33( 6) : 660 ( 曹振新，朱云龙，赵明扬，等． 混流装配线负荷平衡与投产顺 序的优化研究． 信息与控制，2004，33( 6) : 660) ［3］ Zhou X L，Cao Z X． Planning and simulation of the mix model as￾sembly lines． Mach Tool Hydraul，2008，36( 4) : 344 ( 周小丽，曹振新． 混流装配线的规划设计与仿真研究． 机床 与液压，2008，36( 4) : 344) ［4］ Liu J H，Hou D L． The methods for solving the problem of balan￾cing an assembly line． For Eng，2006，22( 4) : 21 ( 刘晋浩，侯东亮． 装配线平衡问题的求解方法浅析． 森林工 程，2006，22( 4) : 21) ［5］ Yu Z Q，Su P． Combining genetic algorithm and simulation analy￾sis for mix-model assembly line balancing problem． Comput Integr Manuf Syst，2008，14 ( 6) : 1120 ( 于兆勤，苏平． 基于遗传算法和仿真分析的混合装配线平衡 问题研究． 计算机集成制造系统，2008，14( 6) : 1120) ［6］ Li B，Chen L P，Huang Z D，et al． Research on assembly line optimal scheduling for mass customization production． China Mech Eng，2005，16( 24) : 2198 ( 李斌，陈立平，黄正东，等． 面向大规模定制的装配线优化调 度研究． 中国机械工程，2005，16( 24) : 2198) ［7］ Ling W S． Research on balancing of mix-model assembly line workstations based on genetic algorithm． J Hefei Univ Technol， 2008，31( 8) : 1287 ( 凌文曙． 基于遗传算法的混流装配线工作站平衡研究． 合肥 工业大学学报: 自然科学版，2008，31( 8) : 1287) ［8］ Wu J H，Xia J K，Cao S H． Modeling of ALB Problem and its op￾timization． J Syst Simul，1999，11( 5) : 358 ( 吴君华，夏巨谌，曹山河． ALB 问题的数学模型及其优化算 法的研究． 系统仿真学报，1999，11( 5) : 358) ［9］ Wang L． Intelligent Optimization Algorithm and its Application． Beijing: Tsinghua University Press，2001 ( 王凌． 智能优化算法与应用． 北京: 清华大学出版社，2001) ［10］ Cai M，Wang F N，Yang S X． Material supply on car assembly line with JIT manufacturing style． Manuf Autom，2006，28( Sup￾pl) : 233 ( 蔡苗，王峰年，杨少霞． JIT 生产模式下混流轿车总装配线 上的物料配送． 制造业自动化，2006，28( 增刊) : 233) ·958·