(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111367235.0 (22)申请日 2021.11.18 (71)申请人 东北大学 地址 110819 辽宁省沈阳市和平区文化路3 号巷11号 (72)发明人 高鸿瑞　薛冯　张颖伟　冯琳　 张升阳　李祖边　 (74)专利代理 机构 沈阳东大知识产权代理有限 公司 21109 代理人 梁焱 (51)Int.Cl. G06F 30/27(2020.01) G06N 3/12(2006.01) G06F 111/04(2020.01) (54)发明名称 基于迁移遗传算法的电脑第二类装配线平 衡优化方法 (57)摘要 本发明公开了一种基于迁移遗传算法的电 脑第二类装配线平衡优化方法， 涉及装配线平衡 技术领域。 该方法利用相似装配线的装配经验， 将已知装配线的可行解集合迁移到待优化装配 线平衡问题的初始解集中， 由于迁移优质可行解 的缘故， 该方法能够有效降低算法性能与初始值 及参数有关的敏感性， 提高启发 式算法求解装配 线平衡问题局部最优可行解的下限。 同时相比于 现有解决装配线平衡问题的方法， 该方法能够加 快收敛速度， 减少执行时间， 更加快速地求出优 质的可行解。 从而优化电脑装配线平衡问题、 降 低电脑生产成本、 改善电脑装配质量、 缩短电脑 生产周期， 助力离 散制造业装配技 术的发展。 权利要求书4页 说明书13页 附图4页 CN 113901728 A 2022.01.07 CN 113901728 A 1.一种基于迁移遗传算法的电脑第二类装配线平衡优化方法， 其特征在于， 该方法包 括如下步骤： 步骤1： 采集A、 B两种型号电脑的生产线装配过程数据， 并将其中的作业先后顺序、 作 业 标时和作业区间数据以矩阵形式进行表示； 步骤2： 根据表示A型号电脑装配过程作业先后顺序的矩阵branch， 建立A型号电脑装配 过程的优先关系矩阵Mat rix； 步骤3： 根据A型号电脑装配过程的优先关系矩阵Matrix和以矩阵形式表示的作业区 间， 对遗传算法的种群进 行初始化， 并对遗传算法的相关参数初始 化， 初始化获得的初始种 群中每条染色体对应A型号电脑装配线平衡 问题的一个可行解； 所述遗传算法的相关参数 包括初始种群 个数、 种群大小、 交换基因个数、 种群交叉概 率、 种群变异概率； 步骤4： 对初始种群进行繁衍， 在种群繁衍的过程中搜索并存储种群中的优质可行解， 由所有优质可 行解形成A型号电脑装配线平衡问题的外 部解集； 步骤5： 对B型号电脑装配作业单元进行拆分或者合并， 做与A型号电脑装配作业单元相 对应处理， 获得B型号电脑装配过程新的作业先后顺序以及作业区间， 该处理后对A型号电 脑装配线平衡问题的外部解集进行调整， 使调整后的所述外部解集满足B型号电脑装配线 的工艺要求， 包括B型号电脑装配线的作业先后顺序、 作业区间； 步骤6： 综合考虑作业标时、 作业先后顺序以及作业区间三个因素计算A、 B两种型号电 脑装配过程的相似度； 步骤7： 计算步骤5得到的所述外部解集中每个染色体的适应度函数值， 在所述外部解 集中选出W个适应度函数值最大的染色体， 形成B型号电脑装配线平衡问题的优质可行解集 合， 其中W 根据步骤6计算出的A、 B两种型号电脑装配过程的相似度确定； 步骤8： 以B型号电脑装配过程新的作业先后顺序以及作业区间初始化U个染色体， 并将 B型号电脑装配线平衡 问题的优质可行解集合与U个染色体组合在一起， 形成B型号电脑装 配线平衡问题的初始种群， 初始种群中每条染色体对应B型号电脑装配线平衡问题的一个 可行解； 步骤9： 对B型号电脑装配线平衡问题的初始种群执行预设次数的繁衍操作， 并在每次 种群繁衍过程中选取预设的Q个适应度函数值最大 的可行解， 替代下一次繁衍种群中适应 度函数值最小的Q个可行解对B型号电脑装配线平衡 问题的可行解进行优化， 获得B型号电 脑装配线平衡问题的最优解 集。 2.根据权利要求1所述的基于迁移遗传算法的 电脑第二类装配线平衡优化方法， 其特 征在于， 所述步骤1中所述的生产线装配过程数据包括装配线工作站数、 作业先后顺序、 作 业单元序号、 作业标时、 作业区间。 3.根据权利要求1所述的基于迁移遗传算法的 电脑第二类装配线平衡优化方法， 其特 征在于， 在所述步骤1中， 将所述作业先后顺序以矩阵形式进行表示时， 是以每一作业单元 与其紧前作业成对排列在矩阵中， 获得矩阵branc h。 4.根据权利要求1所述的基于迁移遗传算法的 电脑第二类装配线平衡优化方法， 其特 征在于， 所述建立A型号电脑装配过程的优 先关系矩阵Matr ix的方法为： 根据在矩阵branch 中若作业单元i是作业单元j的紧前作业， 则将矩阵Matrix中的第i行、 第j列取值为1， 否则 取值为0。权　利　要　求　书 1/4 页 2 CN 113901728 A 25.根据权利要求1所述的基于迁移遗传算法的 电脑第二类装配线平衡优化方法， 其特 征在于， 所述步骤3中所述的根据 A型号电脑装配过程的优 先关系矩阵Matr ix和以矩阵形式 表示的作业区间对遗传算法的种群进行初始化的方法包括如下步骤： 步骤3‑2： 以作业先后顺序和作业区间作为约束条件对遗传算法的种群进行初始化保 证其中的每条染色体对应A型号电脑装配线平衡问题的一个可 行解； 步骤3‑2‑1： 以A型号电脑装配过程的作 业单元总数作为染色体的长度 N， 从染色体计数 t＝1开始， 执 行步骤3‑2‑2； 步骤3‑2‑2： 寻找没有紧前作 业或者其 紧前作业已被分配到相应染色体中的作业单元， 将这些作业单 元添加到可分配作业单 元集S中； 步骤3‑2‑3： 计算可分配作业单元集S中各作业单元各自对应的作业区间上限high ‑ level分别与当前 未分配作业单 元的第一个 基因位置n的差值， 获得差值 集合； 步骤3‑2‑4： 对差值集合中的各个差值进行升序排序， 从中选择排在第一位的差值对应 的作业单元i分配到染色体的第n个基因位置， 并从作业单元集S中将该作业单元i删除， 同 时将该作业单元i的所有紧后作业在 优先关系矩阵中所对应列的第i行元素更新为0， 并令n ＝n+1； 步骤3‑2‑5： 判断是否n≤N， 若是， 则转至步骤3 ‑2‑2； 若否， 执 行步骤3‑2‑6； 步骤3‑2‑6： 令t＝t+1， 判断是否t≤Z， Z为种群大小， 若是， 则令n＝1并转至步骤3 ‑2‑2； 若否， 则执 行步骤3‑3； 步骤3‑3： 搜索出每一条染色体 中作业单元分配顺序下的最小瓶颈时间， 并根据最小瓶 颈时间将每条染色体中分配的所有作业单元按照其各自所处的染色体基因位置分配至给 定的m个工作站， 这样获得每条染色体对应A型号电脑装配线平衡问题的可 行解。 6.根据权利要求5所述的基于迁移遗传算法的 电脑第二类装配线平衡优化方法， 其特 征在于， 所述搜索出每一条染色体中作业单元分配顺序下的最小瓶颈时间的方法包括如下 步骤： 步骤3‑3‑1： 计算每条染色体对应的可 行解的理论 最小瓶颈时间CT； 步骤3‑3‑2： 根据当前最小瓶颈时间CT， 将每条染色体中分配的所有作 业单元按照其各 自所处的染色体基因位置 分配至给定的m个工作站， 计算并获得m个工作 站的生产 节拍集合 {TTi}(i＝1,2,3 ……,m)； 且判断是否满足max{TTi}≤CT， 如果是， 则当前最小瓶颈时间CT为 该染色体中所有作业单 元排序下的实际最小瓶颈时间； 如果否， 则转到步骤3 ‑3‑3； 步骤3‑3‑3： 计算各工作站生产节拍潜在增量ΔTi， ΔTi表示第i+1工作站 上的第一个作 业单元作业标时， 故而ΔTm＝0； 步骤3‑3‑4： 令CT＝max{TTi+ΔTi}， C＝max{TTi}， 判断是否满足C≤CT， 如果是， 则当前 最小瓶颈时间CT为该染色体中所有作业单元排序下的实际最小瓶颈时间； 如果否， 则转到 步骤3‑3‑2。 7.根据权利要求1所述的基于迁移遗传算法的 电脑第二类装配线平衡优化方法， 其特 征在于， 所述 步骤4进一 步包括如下步骤： 步骤4‑1： 设置繁衍代数M与保存次数r＝0， 并计算初始种群 的平衡率percent； 所述种 群的平衡率为种群中所有染色体适应度函数值的均值； 所述适应度函数采用现有的装配线 平衡率求解公式；权　利　要　求　书 2/4 页 3 CN 113901728 A 3