一种基于离散花朵授粉算法的装配车间调度集成优化方法

摘要

本发明公开了一种基于离散花朵授粉算法的装配车间调度集成优化方法，包括以下步骤：S1、针对考虑工人柔性的装配车间调度集成优化问题，建立适应度函数以及约束条件等数学模型；S2、提出一种改进的离散花朵授粉算法，对花粉个体进行离散化处理，采用了适应该问题求解的混合花粉编码，重新定义了异花授粉与自花授粉方式，设计了基于装配序列的变异算子，结合案例进行仿真，并与NSGA‑II算法运行结果进行对比，验证了算法的有效性。本发明提出的基于离散花朵授粉算法的装配车间调度集成优化方法，可以同时优化零件加工序列、产品装配序列和工人分配方案，以最大完工时间、工人成本和零件库存时间作为优化目标，降低产品生产时间，减少生产成本，提升企业竞争力。

说明书

技术领域

本发明属于智能制造领域，具体涉及一种基于离散花朵授粉算法的装配车间调度集成优化方法。

背景技术

现如今由于制造企业竞争的加剧，以前小品种、大批量的生产方式已经渐渐无法满足客户的个性化需求，按订单的定制化生产方式已经逐渐成为制造企业的主要生产方式之一。尤其是对于一些机械产品，如大型汽轮机等，是由小批量多品种的定制化生产方式生产的。定制化的生产方式一般是在离散型生产车间进行。生产方式的改动会造成实际的车间生产过程愈加不可预测，进而出现很多难题，如零部件较多、工艺复杂等。离散制造主要包含两个重要阶段：零件加工和产品装配，一般通过装配车间调度的方法生成最佳的车间调度方案即零件加工装配计划，将机器合理地分配给不同工序，从而减少产品的生产完成时间，提升离散制造企业竞争力。

目前，传统的装配车间调度问题通常是基于给定的产品装配顺序进行研究的，但是在大型机械产品的生产过程中，往往会采用零件加工与产品装配并行的生产方式，不同的产品装配顺序会对零件库存时间等造成影响，另一方面，传统的装配车间调度往往只考虑了工序、机器的约束，而忽略了工人在生产车间的约束。在实际的零件加工或者装配环节，如果工人缺乏所需的操作机器作业能力或者工人离岗，这会导致该项操作无法进行，并且不同工人往往掌握技能种类和熟练度有所不同，这也会导致不同工人在操作同一设备时的时间和经济成本有所不同，从而影响到生产效率。

因此，有必要对考虑工人柔性的装配车间调度集成优化问题进行研究，提出一种基于离散花朵授粉算法的装配车间调度集成优化方法，同时优化车间加工调度、产品装配序列和工人分配方案，从而提升制造企业生产效率，缩短产品制造周期，减少生产成本。

考虑工人柔性的装配车间调度集成优化问题描述如下：一个产品由N个零件组成，在M台机器上加工，零件P

发明内容

本发明的目的是解决上述问题，为了提升制造企业的生产效率、降低制造成本，提出一种基于离散花朵授粉算法的装配车间调度集成优化方法，使零件加工序列、产品装配序列和工人分配方案同时得到优化。

为解决上述问题，本发明的技术方案是：一种基于离散花朵授粉算法的装配车间调度集成优化方法，包含以下步骤：

S1：根据考虑工人柔性的装配车间调度集成优化问题，建立包含适应度函数以及约束条件等数学模型。

S2：在考虑工人柔性的装配车间调度集成优化模型上，提出一种改进的离散花朵授粉算法，对花粉个体进行离散化处理，采用了适应该问题求解的混合花粉编码，重新定义了异花授粉与自花授粉方式，设计了基于装配序列的变异算子。结合案例仿真，通过与NSGA-II算法对比，验证了算法的有效性。

其中，所述步骤S1中，根据考虑工人柔性的装配车间调度集成优化问题建立的适应度函数以及约束条件等数学模型具体为：

S11：针对考虑工人柔性的装配车间调度集成优化问题建立适应度函数

S12：提出该问题的约束条件

S13：针对装配序列的可行性进行评估

所述步骤S2中，提出的一种改进的离散花朵授粉算法，对花粉个体进行离散化处理，采用了适应该问题求解的混合花粉编码，重新定义了异花授粉与自花授粉方式，设计了基于装配序列的变异算子，具体步骤为：

S21：设计混合花粉编码方法

S22：自花授粉

S23：异花授粉

S24：基于装配序列的变异算子

本发明的有益效果是：对于考虑工人柔性的装配车间生产过程，为了使产品的最大完工时间最小、工人成本最小和零件库存时间最小，提出一种基于离散花粉授粉算法的装配车间调度集成优化方法，使零件加工序列、产品装配序列和工人分配方案能够被同时优化。该发明研究了在产品的生产过程中，不同的工人分配方案对产品生产完成时间和零件库存时间的影响，基于考虑工人柔性的装配车间调度集成优化问题，提出该问题的数学模型，设定了该模型下的约束条件及目标函数。为了求解该问题，提出一种改进的离散花朵授粉算法，采用了适应该问题求解的混合花粉编码，重新定义了异花授粉与自花授粉方式，设计了基于装配序列的变异算子。

附图说明

图1为混合花粉编码结构

图2为工序编码的异花授粉

图3为工人编码的异花授粉

图4为自花授粉的逆序操作

图5为自花授粉的插入操作

图6为基于装配序列的变异算子

图7为决策得到的调度甘特图

图8为摘要附图

具体实施方式：

S1：建立了考虑工人柔性的装配车间调度集成优化数学模型，提出了该模型的适应度函数以及约束条件。

S11：若装配序列未发生装配干涉，那么该序列是可行的，提出三个目标函数MinF

目标函数F

F

目标函数F

目标函数F

Fn

若装配序列发生装配干涉，则三个目标函数Min F

F

k是装配序列中的干涉次数，在装配过程中，若装配序列发生干涉，将通过增大适应度值来对该公式进行惩罚。

在考虑工人柔性的零件加工与产品装配并行方式中，当装配序列为：{X1,X2,...,Xi,...,Xn}，零件P

零件P

Fn

在对零件进行装配时，当装配方向、操作类型和装配工具改变时。装配时间会增加，零件P

Ca

S12：为了求解考虑工人柔性的装配车间调度集成优化问题，除了建立目标函数，在考虑工人柔性的零件加工和产品装配并行方式中，以下约束条件也必须满足：

产品的加工需要保证零件的工艺约束，可得：

同一时刻，一台机器只能处理一道工序，可得：

同一时刻，一道工序仅在一台机器上进行操作，可得：

在对零件P

当装配顺序为{X1,X2,...,Xi,...,Xn}时，零件P

对于加工零件工序的一台机器只能由一个工人操作，可得：

在同一时间一个工人只能操作一个加工或者装配工序，可得：

一道装配工序只能由一名工人来操作，可得：

S13：在提出的考虑工人柔性的装配车间调度集成优化数学模型中，为了得到三个评价函数值，还需要得到装配干涉次数以及装配序列的可行性评价指标如装配方向变动次数、装配方式变动次数和装配工具变动次数。干涉矩阵可以通过三维CAD系统得到。在空间直角坐标系中，六个基本方向(+x,-x,+y,-y,+z,-z)是可行的装配方向。

若一个产品由n个零件装配完成，干涉矩阵

其中，元素a

在装配环节，零件无法与自身发生干涉，因此a

通过干涉矩阵，也可以推算出给定可行的装配序列的装配方向变化次数。若产品由n个零件装配完成，令装配方向D

步骤一：设i＝1，q＝1，md

步骤二：若D

步骤三：设i＝i+q+1，q＝1，若i＜m，继续进行步骤二；若不是，进行步骤四。

步骤四：结束。

对于一组装配序列，计算零件P

S2：针对考虑工人柔性的装配车间调度集成优化问题，提出一种改进的离散花朵授粉算法，对花粉个体进行离散化处理，采用了适应该问题求解的混合花粉编码，重新定义了异花授粉与自花授粉方式，设计了基于装配序列的变异算子，结合案例进行求解。

S21：混合花粉编码机制

为了解决考虑工人柔性的装配车间调度集成优化问题，采用了基于工序和工人的双层编码，针对工序序列，设计了一种混合花粉编码机制，包含加工序列和装配序列两部分，在花粉的加工序列部分，每次零件的加工工序都被编码为工序层的一个整数，其出现的次数表示该零件的工序号，在装配序列部分，零件的装配工序同样被编码为工序层的一个整数，以工序层不同整数最后一次出现时的对应工序代表装配工序，花粉个体中装配工序依次出现的顺序代表了产品的装配顺序。若一个产品由n个零件组成，同时零件P

第二部分是分配工人的编码，整数代表工人编号，这一部分同样由∑O

如图1所示，花粉有4个零件组成，每个零件包含2道加工工序，在工序层编码中，花粉编码工序层中出现的第一个整数“2”代表零件2的第一道工序，第二个“2”代表零件2的第二道工序，第三个“2”则代表零件2的装配工序，其他零件同理。在工人编码中，依次出现“2-3-3-1-4-2-1-4-2-1-1-3”。第一个整数“2”代表零件1的第一道工序O

S22：异花授粉

花朵授粉算法中的异花授粉对应算法中的全局搜索，对于装配车间调度这类离散型问题，花朵授粉算法中的异花授粉策略无法直接用于处理花粉编码的迭代更新，重新设计了花朵授粉算法的异花授粉方式。在算法运行过程中，第i次迭代时，选择出种群中具有最优解的花粉个体gbest，将花粉X

在花粉种群中选取最优解的花粉个体gbest与花粉X

步骤一：处理工序层编码，随机生成零件集，如零件集为{2，3}，确定gbest中工件为{2，3}对应的工序序列，并移除X

步骤二：将步骤一选取的gbest对应序列复制到X

步骤三：选择X

工人分配编码的交叉如图3所示，操作步骤如下：

步骤一：随机生成一组二进制数字，长度为混合花粉编码长度∑O

步骤二：确定二进制数字为1时所对应的工人编码位置号，将gbest对应位置的编码值复制到X

步骤三：确定二进制数字为0时所对应的工人编码位置号，将X

步骤四：检查工人分配的可行性，在工人分配编码交叉更新后，由于工人掌握的技能不同，若某道工序分配的工人缺乏操作该工作的技能，无法对该工序进行作业，则需要在该工序的可选工人集中重新分配一位工人进行作业。

S22：自花授粉

自花授粉对应算法中的局部搜索过程，在自花授粉环节，引入了二种邻域结构的搜索方式，以实现种群对种群中的较优花粉个体实现局部搜索，二种邻域结构的过程如下：

(1)逆序：随机选择两道工序，将工序编码层两道工序之间的工序逆序重新排列，并将逆序的工序在可选的工人集里随机分配工人进行作业，如图4所示。

(2)插入：选择一道工序，将该工序插入到花粉个体中某一个任意位置，将工序分配给操作时间最小的工人，其余工序则从相应的工人集合中随机选择一个工人进行操作，如图5所示。

S23：基于装配序列的变异算子

设计的自花授粉与异花授粉策略用于处理基于工序和工人的双层编码。在工序层，由于装配序列需要在计算出每个装配工序在工序层的位置后才能获得，例如一个产品由4个零部件组成，每个零件在装配前需经过两道加工工序，其工序编码为[1 3 2 2 1 4

基于装配序列的变异算子操作步骤如下：

步骤一：在混合花粉编码中找出各个装配工序的位置及先后顺序，确定该花粉个体的装配序列。

步骤二：在所有零件的装配工序中随机选择两道装配工序，将两道装配工序根据其在工序编码中的位置互相交换。

步骤三：在生成的工序编码中更新每个零件装配工序的位置及先后顺序，得到迭代后的装配序列。

步骤四：将步骤二选择的两道装配工序及两道之间的工序在相应的工人集合里随机分配一位工人进行操作。

如图6所示，初始工序的装配顺序为2-4-1-3，选择装配工序‘2’和‘3’，将两道装配工序按照其在工序编码中的位置互相交换，加工工序保持不变，在生成的工序编码中重新确定每个装配工序的位置及出现的先后顺序，可知迭代后的装配顺序为4-3-1-2，在迭代过程中，装配工序之间的加工工序位置也可能会出现变动，如工序O

以下结合具体案例对本发明提出的优化方法进行说明，验证所提出优化方法的可行性：以模锻压机部件为例，使用MATLAB R2014B进行仿真运算，具体步骤如下：

S1：确定该部件的零件组成，零件的加工与工人分配信息见表1，零件的装配与工人分配信息见表2，每个工人的工资率见表3。

表1

表2

表3

S2：部件的装配干涉矩阵见表4～9，结合干涉矩阵，对装配序列的可行性进行判定。

表4 X轴正方向的零件干涉矩阵

表5 X轴负方向的零件干涉矩阵

表6 Y轴正方向的零件干涉矩阵

表7 Y轴负方向的零件干涉矩阵

表6 Z轴正方向的零件干涉矩阵

表6 Z轴负方向的零件干涉矩阵

S3：在产品的装配过程中，当装配操作类型变化时，设置时间增加为3h，装配工具发生变化时，设置时间增加为2h，装配方向发生变化时，设置时间增加为5h。在所提出的基于离散花朵授粉算法的装配车间调度集成优化方法中，经过参数分析，将种群规模设为150，切换概率设为0.6，变异概率设为0.15，最大迭代次数设为200。

调度甘特结果如图7所示，生产方案的甘特图中包含两个部分，加工调度甘特图和装配调度甘特图。加工调度甘特图表达的是工人操作机器对各个零件的加工顺序。可以看出，机器4的加工顺序依次为：1301-401-1402-1201-1002-902-503-1102，同时由调度甘特图可知参与工序操作的工人信息，如工序1301是零件13的第一道工序，1301上方的W5表示由工人5操作机器4对该工序进行加工，同理，由甘特图可知，401是零件4的第一道工序，由工人1操作机器4对该工序进行加工。1402是零件14的第二道工序，由工人1操作机器4对该工序进行加工。根据图7的甘特图的加工序列，可以知道不同工人操作机器对工件的不同加工工序进行作业的开始时间及结束时间。本发明研究案例为由15个零件组成的模锻压机部件，每个零件包含3个加工工序，每个零件在加工完成后可以进行装配工序，以每个零件的第4道工序代表该零件的装配工序，参与装配工序的工人信息见甘特图可知，如104是零件1的第4个工序即装配工序，由工人3操作完成。804表示零件8的装配工序，由工人1操作完成，204表示零件2的装配工序，工人1操作完成。通过装配调度甘特图，同样能够获得产品的装配顺序以及在装配过程中所有工件的装配开始时间及结束时间。

计算求得的得到的调度方案对三个优化目标进行了优化，分别是产品的最大完工时间、工人成本及零件的库存时间，在得到的最优解中，三个优化目标的值分别为产品的完工时间731h、工人成本37982元、零件的库存时间458h。在该生产方案中，零件加工开始109h后，零件1的装配工序由工人3开始操作进行，之后零件的加工工序和装配工序也会同时进行，同一个工人在同一时间内只能操作一个加工工序或者装配工序。由甘特图的装配序列可知该生产方案的装配顺序为：1-8-2-14-13-12-3-6-7-4-9-5-11-10-15，根据装配干涉矩阵计算，在生产过程中，装配方向变化4次，装配工具变化7次，装配方式变化8次。

为了验证离散花朵授粉算法在计算考虑工人柔性的装配车间调度集成优化问题时的性能，采用了两种性能指标：非支配解数量W

一、非支配解数量

非支配解数量是求解得到的Pareto解集中不被参考集M

二、非支配解的比例

非支配解比例指的是在Pareto解集中，非支配解数量W

上述两种指标越大，说明算法的性能越好。分别使用离散花朵授粉算法与NSGA-II算法对该案例进行计算求解，其中，NSGA-II算法的种群规模为150，交叉率为0.6，变异率为0.15，两种算法各迭代200次，算法的两个性能指标结果如表7所示。

表7

且由表8可以得到最终迭代得到的非支配解集。其中，最大完工时间、零件总库存时间和工人成本三个优化目标的最优值分别为596、169h、37982元。使用NSGA-II算法在求解该案例求得的非支配解集中，最大完工时间、零件总库存时间和工人成本三个优化目标的最优值分别为658h、245h、38127元，根据以上分析，提出的离散花朵授粉算法在求解考虑工人柔性的装配车间调度集成优化问题上性能较优。

表8

为了解决考虑工人柔性的装配车间调度集成优化问题，提出了一种基于离散花朵授粉算法的装配车间调度集成优化方法，使零件加工序列、工人分配方案和产品装配序列同时进行优化，以缩短生产过程中的总生产完成时间、工人成本和零件总库存时间。本发明研究了工人分配方案对产品的生产完成时间和零件库存时间的影响，建立了该问题下的适应度函数和约束条件等数学模型。在此基础上，提出了一种基于离散花朵授粉算法的装配车间调度集成优化方法来进行求解。该发明提出的方法，可以有效缩短装配车间产品的生产时间，降低生产成本，提升企业竞争力。