面向家电产品装配线的Ⅱ型双边装配线平衡方法及系统

摘要

本发明公开了一种面向家电产品装配线的Ⅱ型双边装配线平衡方法及系统，包括以下步骤：(1)收集家电产品双边装配线平衡问题相关数据；(2)种群初始化，随机产生M个对应于3倍任务数长度3N的染色体；(3)将染色体进行解码，将它还原为具体的装配线平衡分配方案，计算染色体适应度值；(4)根据染色体适应度值进行排序，选取S个适应度最大的染色体作为精英解，运用轮盘赌选择法从种群中选出M‑S个染色体用于遗传操作；(5)重复步骤3至4直至达到设定的迭代次数，输出适应度值最小的染色体，得到相应的排布方案。本发明结合生产实际家电产品线的复杂约束场景，以给定工位数求解最小节拍为目标，设计新的编解码方法，应用在实际问题中，具有很强的实际应用价值。

说明书

技术领域

本发明属于家电产品双边装配线领域，更具体地，涉及一种面向家电产品装配线的Ⅱ型双边装配线平衡方法及系统。

背景技术

双边装配线作为家电产品的主要生产形式，在企业生产中占据重要地位。企业在建立装配线后，在一段时间内装配线的工位数量是恒定的，但生产不同型号产品时生产节拍一般会不同。双边装配线平衡是指将有限的任务集分配到装配线两侧有限的工位上，同时满足作业任务之间的约束关系，并优化某些指标。其中，装配线平衡第Ⅱ类问题是指给定装配线的工位数，最小化装配线生产节拍。双边装配线平衡方案的好坏直接影响企业生产效率，降低生产节拍，对提高装配线平衡率、提升生产效率有重要意义。家电产品双边装配线工艺约束场景复杂多样，除了节拍/工位数量约束、操作方位约束、任务优先关系约束外，还包括工人高中低站位约束、工件角度约束、工具约束、紧邻作业约束、成对约束及线体约束等额外约束，且约束间还很可能相互耦合，构成了复杂的多约束双边装配线平衡问题。比起普通的装配线平衡问题，面向家电产品装配线的多约束双边装配平衡问题更符合生产实践的真实状况，但也是更复杂的组合优化难题，解决此类问题的复杂度随着任务数的增长呈指数级增长。目前企业解决这类问题停留在人工经验、“感觉”、试错等方法，往往寻找一个合适的可行解需要耗费很长的时间。

发明内容

针对现有技术的缺陷，本发明的目的在于提供了一种面向家电产品装配线的Ⅱ型双边装配线平衡方法及系统，旨在解决复杂多样的家电产品双边装配线工艺约束场景带来的优化难题。

为了实现上述目的，本发明一方面提供了一种面向家电产品装配线的Ⅱ型双边装配线平衡方法，该方法包含以下步骤：

步骤1、收集家电产品双边装配线平衡问题相关数据，包括任务数N、任务时间t

步骤2、种群初始化：根据任务优先顺序约束P(i)通过随机规则产生M个对应于3倍任务数长度3N的序列，即染色体，其基因值包括任务序号、操作方位和线体选择三部分；

步骤3、对种群中的染色体逐一进行解码，将其还原为具体的装配线平衡分配方案，其中，考虑任务时间t

步骤4、根据染色体适应度值进行排序，选取S个适应度最大的染色体作为精英解，运用轮盘赌选择法从种群中选出M-S个染色体用于遗传操作；

步骤5、重复步骤3至4直至达到设定的迭代次数I

进一步地，一条染色体的基因值由任务序号、操作方位和线体选择三部分构成，根据任务优先顺序约束P(i)，构建任务优先顺序关系图，根据其拓扑排序，不断地从剩余任务优先顺序图中分离出紧前序为空的任务，若有多个任务，则随机选择一个，将该任务序号写入染色体，同时根据操作方位约束K(i)和线体约束L(i)补充操作方位和线体选择基因值，重复上述过程直至所有任务被分配完毕，完成一条染色体序列组合编码操作；重复单条染色体编码操作M次，即完成种群初始化。

进一步地，将染色体进行解码具体包括：

首先考虑紧邻约束L(i)，对不满足紧邻约束的任务进行调整；

考虑成对约束J(i)，对不满足成对约束的任务进行调整；

最后在初始节拍时间下进行解码，对调整完毕的染色体进行解码；

考虑成对约束J(i)、操作方位约束K(i)、操作角度约束A(i)、线体约束L(i)和工具约束G(i)，将其还原为具体的装配线平衡分配方案，计算工位数量，利用预设的Ⅱ型问题节拍更新操作判断是否已达到终止条件，若没有达到，则更新节拍，重新解码。

进一步地，所述遗传操作具体流程如下：

(1)交叉操作：根据交叉率R

(2)变异操作：根据染色体变异率p

重分配策略：从RS找出无前序或前序均已被分配的任务i，写入到RC中；选出一个任务，如果RC中有多个任务，找出阶位权值值RPW最大的任务，其中任务i的阶位权值RPW等于其所有后序任务作业时间的总和；计算所选任务i在染色体序列中的可分配区间[SE

为了给家电产品的装配线平衡问题提供更便捷有效的解决方案，发明以给定工位数量，求解最小生产节拍为目标，基于遗传算法基本思想与流程，改进染色体编码方式，提出面向复杂多约束场景的解码操作，在合理的时间内求解大规模问题并验证求解结果的有效性。

本发明另一方面提供了一种面向家电产品装配线的Ⅱ型双边装配线平衡系统，包括：计算机可读存储介质和处理器；

所述计算机可读存储介质用于存储可执行指令；

所述处理器用于读取所述计算机可读存储介质中存储的可执行指令，执行上述的面向家电产品装配线的Ⅱ型双边装配线平衡系统。

与现有技术项目，本发明具有以下有益效果：

(1)在双边装配线平衡问题基础约束的基础上，本发明考虑生产实际家电产品装配线的复杂约束场景，设计的面向家电产品装配线的Ⅱ型双边装配线平衡方法，具有很强的实际应用价值；

(2)本发明设计了新颖的解码方法，先检查调整紧邻约束和成对约束，再检查操作方位约束、操作角度约束、线体约束和工具约束进行任务分配，高效准确还原为具体的装配线平衡分配方案；

(3)本发明提出全新的Ⅱ型问题节拍更新操作，先在初始节拍下按解码任务分配过程求解工位数，再根据工位数与节拍更新操作调整节拍，保证给定工位数能求得准确的节拍，提高算法精确度。

附图说明

图1为本发明提供的面向家电产品装配线的Ⅱ型双边装配线平衡方法的总体流程图；

图2为本发明提供的面向家电产品装配线的Ⅱ型双边装配线的结构图；

图3为本发明提供的面向家电产品装配线的Ⅱ型双边装配线平衡方法中的染色体示意图；

图4为本发明提供的面向家电产品装配线的Ⅱ型双边装配线平衡方法中的任务优先顺序关系图；

图5为本发明提供的面向家电产品装配线的Ⅱ型双边装配线平衡方法中的节拍迭代更新操作；

图6为本发明提供的面向家电产品装配线的Ⅱ型双边装配线平衡方法中的遗传操作举例；

图7为本发明提供的面向家电产品装配线的Ⅱ型双边装配线平衡方法中的采用重分配策略得到完整染色体示意图；

图8为本发明提供的面向家电产品装配线的Ⅱ型双边装配线平衡方法中的改进遗传算法流程图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及示例性实施例，对本发明进一步详细说明。应当理解，此处所描述的示例性实施例仅用以解释本发明，并不用于限定本发明的适用范围。

如图1所示，一种面向家电产品装配线的Ⅱ型双边装配线平衡方法的总体流程如下：

步骤1、收集家电产品双边装配线平衡问题相关数据，包括任务数N、任务时间t

步骤2、种群初始化：根据任务优先顺序约束P(i)通过随机规则产生M个对应于3倍任务数长度3N的序列，即染色体，其基因值包括任务序号、操作方位和线体选择三部分；

步骤3、对种群中的染色体逐一进行解码，将其还原为具体的装配线平衡分配方案，其中，考虑任务时间t

步骤4、根据染色体适应度值进行排序，选取S个适应度最大的染色体作为精英解，运用轮盘赌选择法从种群中选出M-S个染色体用于遗传操作；

步骤5、重复步骤3至4直至达到设定的迭代次数I

具体地，步骤1收集的数据解释如下：任务是本发明最小研究单位，每一个任务只能在一个工位进行装配，本发明实施例任务数N为150；任务时间t

步骤2中，对于E型任务而言，它可以分配到装配线的任意一边，这需要加以明确指定。家用产品装配线通常是多条装配线并行或串行作业，本发明考虑了三条线体，分别是箱体线、桶装线和总装线三条线体。对于多线体可选的任务，它可以分配到多条装配线的任意一条，这需要加以明确指定。

为此，本发明提出了一种基于“序列组合”的编码方法。在该编码方法中，染色体的长度为所求问题的规模的3倍，染色体的基因值由三部分组成：该次序所要装配的任务号码(g

表1

初始化染色体的方法具体是：根据任务优先顺序约束P(i)，构建任务优先顺序关系图，任务优先顺序图如图4所示，根据任务优先顺序图的其拓扑排序，不断地从剩余装配任务优先顺序图中分离出紧前序为空的任务，若有多个任务，则随机选择一个，将该任务序号写入染色体，同时根据操作方位约束K(i)和线体约束L(i)补充满足操作方位约束和线体约束的操作方位和线体选择基因值，重复上述过程直至所有任务被分配完毕，完成一条染色体序列组合编码操作。重复单条染色体编码操作M次，即完成种群初始化。

步骤3中，将染色体进行解码主要分为三大步，首先考虑紧邻约束，对不满足紧邻约束的任务进行调整；详情见步骤(1)-(2)；其次考虑成对约束，对不满足成对约束的任务进行调整，详情见步骤(3)-(9)；最后开始在初始节拍时间下进行解码，对调整完毕的染色体进行解码，考虑成对约束、操作方位约束、操作角度约束、线体约束和工具约束，将它还原为具体的装配线平衡分配方案，计算工位数量。利用设计的Ⅱ型问题节拍更新操作判断是否已达到终止条件，若没有达到，则更新节拍，重新解码。详情见步骤(10)-(20)，节拍迭代更新操作如图5所示。记待解码染色体为R

(1)检查紧邻约束。按照染色体R

(2)检查所有紧邻约束集的任务是否调整完毕，若调整完毕，则执行(3)，否则执行步骤(1)；

(3)检查成对约束。新建一条3倍任务数N长度的染色体R

(4)更新候选集，按照染色体R

(5)判断任务i的成对任务是否还在染色体R

(6)若任务i的紧邻任务无成对任务，则执行(9)，若任务i的紧邻任务有成对任务，判断成对任务是否在候选集中，若在，则执行(9)，否则从候选集中选择另一个任务，执行(9)；

(7)将成对任务的SN前移至该任务的线体选择基因值后面，执行(9)；

(8)将该任务的成对任务及所有前序任务的SN前移至染色体R

(9)在染色体R

(10)给定工位数量为Zm，基于调整完毕的染色体R

(11)按照染色体R

(12)检查任务i与其成对任务分配到该成对工位中能否满足节拍时间约束，且该任务与该工位的操作方位、工人高中低站、操作角度及工具均相同，如果是，则执行(14)，否则开始一个新的成对工位，执行(14)；

(13)检查任务i满足节拍时间约束，且任务i与该工位的操作方位、工人高中低站、操作角度及工具均相同，如果是，则执行(15)，否则开始一个新的成对工位，执行(15)；

(14)根据任务i和其成对任务的优先操作方位将两个任务分配到相对应的工位上，在未解码染色体R

(15)根据任务i优先操作方位将其分配到相对应的工位上，未解码染色体R

(16)判断染色体R

(17)判断是否达到最大迭代次数E

(18)若工位数量Z大于Zm，则执行步骤(19)，若工位数量Z小于Zm，则执行步骤(20)，若工位数量Z等于Zm，停止迭代，输出当前染色体最优节拍；

(19)取当前任务分配方案左右两边最大工位时间Cm，更新节拍值Ct＝Ct+(Ct–Cm)*rand()，其中rand()表示随机产生一个大于0小于1的数。E＝E+1，重新解码R

(20)取当前任务分配方案左右两边最大工位时间Cm，更新节拍值Ct＝Ct-(Ct–Cm)*rand()，E＝E+1，重新解码R

运用如下公式计算各条染色体的工位数量：

其中，Z表示启用的工位数量总和，J表示成对工位集，K(i)表示任务i可以分配的操作方位集，y

步骤4中，根据种群适应度值进行排序，选取M个适应度最大的染色体作为精英解，运用轮盘赌选择法从种群中选出S个染色体作为父代种群，执行遗传操作。所设计的遗传操作具体流程如下：

(1)交叉操作：根据交叉率R

(2)变异操作：根据染色体变异率p

(3)重分配策略：从RS找出无前序(或前序均已被分配)的任务，写入到RC中；选出一个任务，如果RC中有多个任务，找出RPW值最大的任务；计算所选任务(i)在染色体序列中的可分配区间[SE

步骤5，算法终止条件。如图8的改进遗传算法流程图中，若已达到设定的迭代次数，则输出适应度值最小的染色体，得到满足各个约束条件的任务排布方案，否则返回步骤3反复迭代，直到满足终止条件。

采用C++编程实现本发明所设计的面向家电产品装配线的Ⅱ型双边装配线平衡算法，程序运行环境为：2.40GHz Intel(R)Core(TM)i7-4710HQ CPU、8G RAM、win8.1，对某洗衣机企业的双边装配线问题进行了验证。该问题共有150个任务，这些任务之间的复杂约束关系与数据如表2所示。

表2

其中，工人高中低站位一列空值代表高中低站位均可，角度一列空值代表0/90/180/270度均可，工具型号一列空值代表不需要使用工具，紧邻任务、成对任务两列空值分别代表没有紧邻任务、成对任务。算法设定参数为：染色体交叉率R

表3

由实验结果与现场实施来看，本发明所设计的面向家电产品装配线的Ⅱ型双边装配线平衡算法能在较短的时间内，寻找到较优的任务分配方案，极大的减少了生产节拍，提升产能。综上所述，本发明在双边装配线基础约束的基础上，结合家电产品双边装配线的复杂约束场景，研究给定工位数求解最小节拍问题，设计的面向家电产品装配线的Ⅱ型双边装配线平衡算法，取代传统停留在人工经验、“感觉”、试错等解决方法，具有很强的实际应用价值。