一种面向大型复杂产品生产装配的动态调度方法

摘要

本发明公开了一种面向大型复杂产品生产装配的动态调度方法，针对检测到的动态扰动，以最小化最大完工时间和任务总拖期量作为优化目标，同时考虑产品工序紧前紧后、设备资源占用的约束条件，构建动态调度模型，采用加权法将多优化目标转化为单一评价函数；最后采用改进粒子群算法对动态调度模型进行求解。本发明使用改进粒子群算法求解考虑扰动的装配车间综合动态调度问题，保证在初始化解集和迭代过程中不会产生非法解，对粒子群算法的变异操作进一步改进，并结合改进粒子群算法和动态重调度求解方式，提出了基于事件驱动的动态调度算法，使之较遗传算法和其他启发式算法更具有优越性。

权利要求

1.一种面向大型复杂产品生产装配的动态调度方法，其特征在于，针对检测到的动态扰动，以最小化最大完工时间和任务总拖期量作为优化目标，同时考虑产品工序紧前紧后、设备资源占用的约束条件，构建动态调度模型，采用加权法将多优化目标转化为单一评价函数；最后采用改进粒子群算法对动态调度模型进行求解：步骤A1：初始化拥有K个个体的粒子种群，设置惯性权重，计算这K个个体的适应度，并随机给予每个粒子一个初始速度 ；

步骤A2：比较更新每个粒子的历史最佳适应度值位置 和全体粒子的历史最佳适应度值位置Fmax；

步骤A3：每循环D步后，选取适应度最低的10%的个体进行高斯变异操作，更新为新的粒子种群；若还未循环D步，则进行步骤A4；

步骤A4：更新粒子的移动距离，更新粒子的位置，并对移动距离不足的根据方向进行延长，对超出最大移动距离的粒子进行映射处理；

步骤A5：判断当前移动次数i是否达到最大移动次数I的50%，若达到，则粒子的基本移动距离A乘以衰减系数α，以更新粒子的基本移动距离A，返回步骤A2；若还未达到，则直接返回步骤A2。

2.根据权利要求1所述的一种面向大型复杂产品生产装配的动态调度方法，其特征在于，在步骤A3中，高斯变异操作：（15）

其中：mut为变异操作；

Gs（）为高斯变异函数；

代表第K个粒子第i步的位置；

Lfb为紧后工序和紧前工序之间的距离；

被选择的维度在满足工艺紧前、紧后约束的条件下，进行高斯位置变换，得到高斯变异的结果；粒子 进行高斯变异，则不受速度与空间移动距离的约束；在工艺信息树找到维度z上的工序的紧前工序和紧后工序约束的位置，得到其紧后工序和紧前工序之间的距离Lfb。

3.根据权利要求2所述的一种面向大型复杂产品生产装配的动态调度方法，其特征在于，所述步骤A4中，更新粒子的移动距离，更新粒子的位置：（13）

（14）

其中，

w为粒子的惯性权重，

r1和r2分别为随机变量，

c1为当前适应度最优值权重，c2为历史适应度最优值权重，A为粒子的基本移动距离，

Fmax为全体粒子的历史最佳适应度值的位置；

为第Ｋ个粒子的历史最佳适应度值的位置；

代表第K个粒子第i步的位置；

为第K个粒子第i‑1步的位置；

为粒子第i次移动的移动距离，为粒子第i‑1次移动的移动距离，代表 的模长。

4.根据权利要求1所述的一种面向大型复杂产品生产装配的动态调度方法，其特征在于，在构建动态调度模型中，构建目标函数：最小化最大完工时间，且目标函数为：（1‑1）

最小化总拖期时间，且目标函数为：（1‑2）

鲁棒性的目标函数为：

（1‑3）

因此，最终的目标函数为：

min f=αβ1 1f1+αβ2 2f2+αβ3 3f（3 1‑4）其中，

n为待装配零部件总数，

Cj代表零部件j的完工时间，dj代表零部件j的交付期，

wj代表零部件j的拖期系数，ρ代表偏离系数，

第i个零部件j重调度的开始时间，Sj,i代表第i个零部件j原始调度方案的开始时间；

α1、α2、α3分别为目标函数f1、f2、f3的目标权重，且α1+α2+α3=1；

β1、β2、β3分别为目标函数f1、f2、f3的归一化因子。

5.根据权利要求4所述的一种面向大型复杂产品生产装配的动态调度方法，其特征在于，在构建动态调度模型中，构建约束条件：（2）

（3）

（4）

（5）

（6）

（7）

（8）

（9）

（10）

（11）

（12）

其中：

Mp为设备平台索引，

Mj,i为零部件j的第i道工序的可选平台集合，J为零部件集合，

Oj为零部件j的所有工序的集合，Qj,i为零部件j的第i道工序前置工序集合{1,2,3…,i' }，为零部件j的第i道工序的占用平台数；

为零部件j的第i道工序在平台p上加工的开始时间，为零部件j'的第i'道工序在平台p上加工的开始时间，为零部件j的第i道工序在平台p上的完工时间，为零部件j'的第i'道工序在平台p上的完工时间，Inf为极大值，

tj,i为零部件j的第i道工序所需加工时间，tj',i'为零部件j'的第i'道工序所需加工时间，j'为零部件索引，

i'为工序索引，

Sj,i为零部件j的第i道工序的开始时间，Sj',i'为零部件j'的第i'道工序的开始时间，Fj为零部件j的前序零部件集，Cj,i为零部件j的第i道工序的结束时间，Cj,i'为零部件j'的第i'道工序的结束时间，、 分别为决策变量，

为零部件j的第i道工序在第a时刻所占用第k种工人的数量，为第k类工人在时间a的可用数量，k为工人种类，

K为工人种类集合，

a为时间索引，

Amax为最大时间索引集合；

公式(2)表示零部件每道工序只能占用一个设备/平台；

公式(3)和公式(4)表示工序占用设备/平台的开工时间早于或等于该工序在设备/平台上完工时间；

公式(5)表示零部件的开工时间需晚于或等于其所有前序零部件所有工序的完工时间；

公式(6)表示同一零部件所有前道工序的完工时间均早于或等于后一道工序的开工时间；

公式(7)和公式(8)表示不同零部件的工序可占用同一个设备/平台时，不可同时进行加工，即在任何时候同一设备/平台正在加工零部件不能超过一个；

公式(9)表示在任何时刻对每种工人的调用数量不能超过当前时间其实际车间该种工人数量上限；

公式(10)～公式(12)表示决策变量为0‑1变量。

6.根据权利要求1‑5任一项所述的一种面向大型复杂产品生产装配的动态调度方法，其特征在于，包括以下步骤：步骤S1：输入车间的订单信息；

步骤S2：根据任务信息和车间资源，采用改进粒子群算法生成车间初始调度方案，并执行生产任务；

步骤S3：若执行过程中检测到动态扰动，则判断是否出现扰动事件，若检测到扰动事件，则更新调度任务，使用改进粒子群算法进行完全重调度，生成重调度方案，否则继续执行步骤S2中的生产任务。

7.根据权利要求6所述的一种面向大型复杂产品生产装配的动态调度方法，其特征在于，在步骤S3中，当触发重调度时，需先获取已完工零部件集、正在加工零部件集、未加工零部件集的信息，对车间剩余任务进行重新初始化，同时更新所有任务中零部件、平台的最早可加工时间，以及最新工人资源占用情况，然后通过改进粒子群算法进行重调度，并下发到车间执行。

8.根据权利要求1所述的一种面向大型复杂产品生产装配的动态调度方法，其特征在于，所述动态扰动包括质检工序检测质量问题、装配过程异常导致中断、紧急插单三种类型的扰动：针对质检工序检测质量问题，上报到质量部门，安排零部件的返工返修，由于质检不合格导致该零部件的工序加工时间延后，并增加返工工序，确定好返修工序时间后进行重调度；

针对装配过程异常导致中断，上报到质量部门，安排零部件的返工返修，一旦确定返工返修则需要进行重调度；

u u

针对紧急插单问题，将收到插单任务的时刻t 作为分界线，在原先的调度计划中从t 时刻开始之后未开始的调度计划失效，在扰动之后进行全局重调度。

说明书

一种面向大型复杂产品生产装配的动态调度方法

技术领域

[0001] 本发明属于装配动态调度的技术领域，具体涉及一种面向大型复杂产品生产装配的动态调度方法。

背景技术

[0002] 考虑动态扰动的装配调度问题（Dynamic Assemble Shop Scheduling Problem，DASSP）广泛存在于能源装备、航空航天装备、船舶结构件制造等领域，在现代制造业当中作为关键的加工制造技术之一。

[0003] 目前，对于装配车间综合调度问题的研究较少，而且集中于车间的静态调度，对于动态调度中扰动分类和重调度鲜有研究，而实际装配车间通常会伴随着各种扰动，会使车间生产状态发生变动，导致最初由静态调度生成的任务计划变得不可行。在传统的调度方案中，鲜有考虑动态调度，针对动态调度的重调度方案通常是对紧急插单扰动使用右移重调度进行的。而装配车间与传统车间扰动问题不同，除了常见的插单扰动之外，还存在不同类型的质量问题扰动，其中包括在装配过程中凭经验判断间隙等装配质量不合格，以及在装配结束后由质检工序检测到质量不合格等问题。若仍采用传统方式解决问题，会导致最大完工时间增长、任务拖期延长和鲁棒性差等多种问题。由于问题的复杂度较高，目前鲜有其研究成果的报道，因此，针对复杂产品的综合动态调度问题的研究存在较大的意义。

发明内容

[0004] 本发明的目的在于提供一种面向大型复杂产品生产装配的动态调度方法，旨在解决上述的问题。本发明针对具有扰动的装配产品工序加工与装配工艺约束，建立装配车间综合调度的数学模型，并采用加权法将多个优化目标转化为单一评价函数，同时设计多目标粒子群算法进行优化求解，实现装配产品调度的多目标求解。最终优化求解得到一个使最大完工时间最小，总拖期时间最小，鲁棒性最强的调度方案，为企业获得更大的利益。

[0005] 本发明主要通过以下技术方案实现：

[0006] 一种面向大型复杂产品生产装配的动态调度方法，针对检测到的动态扰动，以最小化最大完工时间和任务总拖期量作为优化目标，同时考虑产品工序紧前紧后、设备资源占用的约束条件，构建动态调度模型，采用加权法将多优化目标转化为单一评价函数；最后采用改进粒子群算法对动态调度模型进行求解：

[0007] 步骤A1：初始化拥有K个个体的粒子种群，设置惯性权重，计算这K个个体的适应度，并随机给予每个粒子一个初始速度 ；

[0008] 步骤A2：比较更新每个粒子的历史最佳适应度值位置 和全体粒子的历史最佳适应度值位置Fmax；

[0009] 步骤A3：每循环D步后，选取适应度最低的10%的个体进行高斯变异操作，更新为新的粒子种群；若还未循环D步，则进行步骤A4；

[0010] 步骤A4：更新粒子的移动距离，更新粒子的位置，并对移动距离不足的根据方向进行延长，对超出最大移动距离的粒子进行映射处理；

[0011] 步骤A5：判断当前移动次数i是否达到最大移动次数I的50%，若达到，则粒子的基本移动距离A乘以衰减系数α，以更新粒子的基本移动距离A，返回步骤A2；若还未达到，则直接返回步骤A2。

[0012] 为了更好地实现本发明，进一步地，在步骤A3中，高斯变异操作：

[0013] （15）

[0014] 其中：

[0015] mut为变异操作；

[0016] Gs（）为高斯变异函数；

[0017] 代表第K个粒子第i步的位置；

[0018] Lfb为紧后工序和紧前工序之间的距离；

[0019] 被选择的维度在满足工艺紧前、紧后约束的条件下，进行高斯位置变换，得到高斯变异的结果；粒子 进行高斯变异，则不受速度与空间移动距离的约束；在工艺信息树找到维度z上的工序的紧前工序和紧后工序约束的位置，得到其紧后工序和紧前工序之间的距离Lfb。

[0020] 为了更好地实现本发明，进一步地，所述步骤A4中，更新粒子的移动距离，更新粒子的位置：

[0021] （13）

[0022] （14）

[0023] 其中，

[0024] w为粒子的惯性权重，

[0025] r1和r2分别为随机变量，

[0026] c1为当前适应度最优值权重，

[0027] c2为历史适应度最优值权重，

[0028] A为粒子的基本移动距离，

[0029] Fmax为全体粒子的历史最佳适应度值的位置；

[0030] 为第Ｋ个粒子的历史最佳适应度值的位置；

[0031] 代表第K个粒子第i步的位置；

[0032] 为第K个粒子第i－１步的位置；

[0033] 为粒子第i次移动的移动距离，

[0034] 为粒子第i－１次移动的移动距离，

[0035] 代表 的模长。

[0036] 为了更好地实现本发明，进一步地，在构建动态调度模型中，构建目标函数：

[0037] （1）最小化最大完工时间，且目标函数为：

[0038] （1‑1）

[0039] （2）最小化总拖期时间，且目标函数为：

[0040] （1‑2）

[0041] （3）鲁棒性的目标函数为：

[0042] （1‑3）

[0043] 因此，最终的目标函数为：

[0044] min f=αβ1 1f1+αβ2 2f2+αβ3 3f（3 1‑4）

[0045] 其中，

[0046] n为待装配零部件总数，

[0047] Cj代表零部件j的完工时间，

[0048] dj代表零部件j的交付期，

[0049] wj代表零部件j的拖期系数，

[0050] ρ代表偏离系数，

[0051] 第i个零部件j重调度的开始时间，

[0052] Sj,i代表第i个零部件j原始调度方案的开始时间；

[0053] α1、α2、α3分别为目标函数f1、f2、f3的目标权重，且α1+α2+α3=1；

[0054] β1、β2、β3分别为目标函数f1、f2、f3的归一化因子。

[0055] 为了更好地实现本发明，进一步地，在构建动态调度模型中，构建约束条件：

[0056] （2）

[0057] （3）

[0058] （4）

[0059] （5）

[0060] （6）

[0061] （7）

[0062] （8）

[0063] （9）

[0064] （10）

[0065] （11）

[0066] （12）

[0067] 其中：

[0068] Mp为设备平台索引，

[0069] Mj,i为零部件j的第i道工序的可选平台集合，

[0070] J为零部件集合，

[0071] Oj为零部件j的所有工序的集合，

[0072] Qj,i为零部件j的第i道工序前置工序集合{1,2,3…,i'}，

[0073] 为零部件j的第i道工序的占用平台数；

[0074] 为零部件j的第i道工序在平台p上加工的开始时间，

[0075] 为零部件j'的第i'道工序在平台p上加工的开始时间，

[0076] 为零部件j的第i道工序在平台p上的完工时间，

[0077] 为零部件j'的第i'道工序在平台p上的完工时间，

[0078] Inf为极大值，

[0079] tj,i为零部件j的第i道工序所需加工时间，

[0080] tj',i'为零部件j'的第i'道工序所需加工时间，

[0081] j'为零部件索引，

[0082] i'为工序索引，

[0083] Sj,i为零部件j的第i道工序的开始时间，

[0084] Sj',i'为零部件j'的第i'道工序的开始时间，

[0085] Fj为零部件j的前序零部件集，

[0086] Cj,i为零部件j的第i道工序的结束时间，

[0087] Cj,i'为零部件j'的第i'道工序的结束时间，

[0088] 、 分别为决策变量，

[0089] 为零部件j的第i道工序在第a时刻（天）所占用第k种工人的数量，

[0090] 为第k类工人在时间a的可用数量，

[0091] k为工人种类，

[0092] K为工人种类集合，

[0093] a为时间索引，

[0094] Amax为最大时间索引集合；

[0095] 公式(2)表示零部件每道工序只能占用一个设备/平台；

[0096] 公式(3)和公式(4)表示工序占用设备/平台的开工时间早于或等于该工序在设备/平台上完工时间；

[0097] 公式(5)表示零部件的开工时间需晚于或等于其所有前序零部件所有工序的完工时间；

[0098] 公式(6)表示同一零部件所有前道工序的完工时间均早于或等于后一道工序的开工时间；

[0099] 公式(7)和公式(8)表示不同零部件的工序可占用同一个设备/平台时，不可同时进行加工，即在任何时候同一设备/平台正在加工零部件不能超过一个；

[0100] 公式(9)表示在任何时刻对每种工人的调用数量不能超过当前时间其实际车间该种工人数量上限；

[0101] 公式(10)～公式(12)表示决策变量为0‑1变量。

[0102] 为了更好地实现本发明，进一步地，包括以下步骤：

[0103] 步骤S1：输入车间的订单信息；

[0104] 步骤S2：根据任务信息和车间资源，采用改进粒子群算法生成车间初始调度方案，并执行生产任务；

[0105] 步骤S3：若执行过程中检测到动态扰动，则判断是否出现扰动事件，若检测到扰动事件，则更新调度任务，使用改进粒子群算法进行完全重调度，生成重调度方案，否则继续执行步骤S2中的生产任务。

[0106] 为了更好地实现本发明，进一步地，在步骤S3中，当触发重调度时，需先获取已完工零部件集、正在加工零部件集、未加工零部件集的信息，对车间剩余任务进行重新初始化，同时更新所有任务中零部件、平台的最早可加工时间，以及最新工人资源占用情况，然后通过改进粒子群算法进行重调度，并下发到车间执行。

[0107] 为了更好地实现本发明，进一步地，所述动态扰动包括质检工序检测质量问题、装配过程异常导致中断、紧急插单三种类型的扰动：

[0108] 针对质检工序检测质量问题，上报到质量部门，安排零部件的返工返修，由于质检不合格导致该零部件的工序加工时间延后，并增加返工工序，确定好返修工序时间后进行重调度；

[0109] 针对装配过程异常导致中断，上报到质量部门，安排零部件的返工返修，一旦确定返工返修则需要进行重调度；

[0110] 针对紧急插单问题，将收到插单任务的时刻tu作为分界线，在原先的调度计划中u从t 时刻开始之后未开始的调度计划失效，在扰动之后进行全局重调度。

[0111] 本发明的有益效果如下：

[0112] （1）本发明首先将车间生产过程中遇到的扰动分为检测工序检测出装配质量问题、装配过程异常导致中断、紧急插单三种类型的扰动，其次以最小化最大完工时间、任务总拖期量、鲁棒性作为优化目标，同时考虑产品工序紧前紧后、设备资源占用等约束条件，构建车间综合动态调度模型，采用加权法将多优化目标转化为单一评价函数；最后采用改进粒子群算法（Improved Particle Swarm Optimization, IPSO）进行求解。在求解过程中，本发明提出了动态车间事件驱动重调度机制和算法，保证在求解过程中不会产生非法解。通过本发明所求得的车间重调度方案可有效解决复杂产品的动态调度问题。

[0113] （2）本发明使用基于事件驱动的重调度机制对生产过程中存在的扰动进行重调度，在重调度中使用基于改进粒子群算法的完全重调度策略，考虑工序之间的紧前紧后关系以及在重调度时刻工序是否已经开始加工。同时在实际生产装配过程中的扰动类型可分为紧急插单扰动、装配过程自检质量问题引起中断、质检工序检测质量问题，在实际调度过程中不同扰动类型常常被混淆，造成调度结果与实际现场之间存在差距。本发明充分考虑现场实际生产过程中出现的扰动类型，针对不同的扰动求解，使得动态调度求解方案更合理。

[0114] （3）本发明使用改进粒子群算法求解考虑扰动的装配车间综合动态调度问题，保证在初始化解集和迭代过程中不会产生非法解，同时针对传统粒子群算法局部搜索能力差的问题，在粒子群算法中引入高斯变异操作以提高其局部搜索能力，并结合改进粒子群算法和动态重调度求解方式，提出了基于事件驱动的动态调度算法，使之较遗传算法和其他启发式算法更具有优越性。

附图说明

[0115] 图1为高斯变异的原理图；

[0116] 图2为本发明动态调度方法的流程图；

[0117] 图3为实施例3中生产任务产品工艺树信息结构示意图；

[0118] 图4为实施例3中生产任务产品零部件代号示意图；

[0119] 图5为实施例3中静态实例求解结果甘特图；

[0120] 图6为实施例3中质检异常插入式右移重调度甘特图；

[0121] 图7为实施例3中质检异常改进粒子群算法完全重调度甘特图；

[0122] 图8为实施例3中装配中断右移重调度甘特图；

[0123] 图9为实施例3中装配中断改进粒子群算法完全重调度甘特图；

[0124] 图10为实施例3中紧急插单右移重调度甘特图；

[0125] 图11为实施例3中紧急插单改进粒子群算法完全重调度甘特图。

具体实施方式

[0126] 实施例1：

[0127] 一种面向大型复杂产品生产装配的动态调度方法，针对检测到的动态扰动，以最小化最大完工时间和任务总拖期量作为优化目标，同时考虑产品工序紧前紧后、设备资源占用的约束条件，构建动态调度模型，采用加权法将多优化目标转化为单一评价函数；最后采用改进粒子群算法对动态调度模型进行求解：

[0128] 步骤A1：初始化拥有K个个体的粒子种群，设置惯性权重，计算这K个个体的适应度，并随机给予每个粒子一个初始速度 ；

[0129] 步骤A2：比较更新每个粒子的历史最佳适应度值位置 和全体粒子的历史最佳适应度值位置Fmax；

[0130] 步骤A3：每循环D步后，选取适应度最低的10%的个体进行高斯变异操作，更新为新的粒子种群；若还未循环D步，则进行步骤A4；

[0131] 步骤A4：更新粒子的移动距离，更新粒子的位置，并对移动距离不足的根据方向进行延长，对超出最大移动距离的粒子进行映射处理；

[0132] 步骤A5：判断当前移动次数i是否达到最大移动次数I的50%，若达到，则粒子的基本移动距离A乘以衰减系数α，以更新粒子的基本移动距离A，返回步骤A2；若还未达到，则直接返回步骤A2。

[0133] 优选地，如图1所示，在步骤A3中，高斯变异操作：

[0134] （15）

[0135] 其中： 代表第K个粒子第i步的位置；

[0136] Lfb为紧后工序和紧前工序之间的距离；

[0137] 被选择的维度在满足工艺紧前、紧后约束的条件下，进行高斯位置变换，得到高斯变异的结果；粒子 进行高斯变异，则不受速度与空间移动距离的约束；在工艺信息树找到维度z上的工序的紧前工序和紧后工序约束的位置，得到其紧后工序和紧前工序之间的距离Lfb。

[0138] 优选地，所述步骤A4中，更新粒子的移动距离，更新粒子的位置：

[0139] （13）

[0140] （14）

[0141] 其中，

[0142] w为粒子的惯性权重，

[0143] r1和r2分别为随机变量，

[0144] c1为当前适应度最优值权重，

[0145] c2为历史适应度最优值权重，

[0146] A为粒子的基本移动距离，

[0147] Fmax为全体粒子的历史最佳适应度值的位置；

[0148] 为第Ｋ个粒子的历史最佳适应度值的位置；

[0149] 代表第K个粒子第i步的位置；

[0150] 为第K个粒子第i－１步的位置；

[0151] 为粒子第i次移动的移动距离，

[0152] 为粒子第i－１次移动的移动距离，

[0153] 代表 的模长。

[0154] 优选地，如图2所示，在实际生产过程中，包括以下步骤：

[0155] 步骤S1：输入车间的订单信息；

[0156] 步骤S2：根据任务信息和车间资源，采用改进粒子群算法生成车间初始调度方案，并执行生产任务；

[0157] 步骤S3：若执行过程中检测到动态扰动，则判断是否出现扰动事件，若检测到扰动事件，则更新调度任务，使用改进粒子群算法进行完全重调度，生成重调度方案，否则继续执行步骤S2中的生产任务。

[0158] 优选地，在步骤S3中，当触发重调度时，需先获取已完工零部件集、正在加工零部件集、未加工零部件集的信息，对车间剩余任务进行重新初始化，同时更新所有任务中零部件、平台的最早可加工时间，以及最新工人资源占用情况，然后通过改进粒子群算法进行重调度，并下发到车间执行。

[0159] 本发明使用基于事件驱动的重调度机制对生产过程中存在的扰动进行重调度，在重调度中使用基于改进粒子群算法的完全重调度策略，考虑工序之间的紧前紧后关系以及在重调度时刻工序是否已经开始加工。本发明使用改进粒子群算法求解考虑扰动的装配车间综合动态调度问题，保证在初始化解集和迭代过程中不会产生非法解，对粒子群算法的变异操作进一步改进，并结合改进粒子群算法和动态重调度求解方式，提出了基于事件驱动的动态调度算法，使之较遗传算法和其他启发式算法更具有优越性。

[0160] 实施例2：

[0161] 一种面向大型复杂产品生产装配的动态调度方法，首先将车间生产过程中遇到的扰动分为检测工序检测出装配质量问题、装配过程异常导致中断、紧急插单三种类型的扰动，其次以最小化最大完工时间、任务总拖期量、鲁棒性作为优化目标，同时考虑产品工序紧前紧后、设备资源占用等约束条件，构建车间综合动态调度模型，采用加权法将多优化目标转化为单一评价函数；最后采用改进粒子群算法（Improved  Particle Swarm Optimization, IPSO）进行求解。在求解过程中，本发明提出了动态车间事件驱动重调度机制和算法，保证在求解过程中不会产生非法解。通过本发明所求得的车间重调度方案可有效解决复杂产品的动态调度问题。

[0162] 优选地，确定车间综合动态调度的描述和相关假设：

[0163] 考虑动态扰动的装配综合调度问题DASSP（Dynamic Assemble Shop Scheduling Problem，DASSP）是初始静态调度方案形成并下派后，在车间执行过程中遇到扰动因素后对装配过程进行动态调度的调度问题。车间动态调度过程首先需要确定车间的初始调度方案，之后检测车间状态变化，接收在生产过程中产生的动态扰动信息，在出现扰动信息后确定扰动事件类型，启动动态调度算法，生成对车间扰动的动态调度结果。

[0164] DASSP问题的建立的前提假设包括：

[0165] （1）在装配工程中，除非出现质量问题，否则被加工工序不会中断；

[0166] （2）车间内每种工人资源的数量是有限的，在满足工序占用设备/平台资源时，还需要考虑当日工人是否充足，未达到开工条件则不能开工；

[0167] （3）已调度到某一工序上的工人，在该工序没有完成时，不可被调度到其他工序上加工，避免该工序的中断；

[0168] （4）当实际车间运输能力充足的情况下，运输时间相对于复杂产品生产时间而言通常较小，所以忽略运输时间；

[0169] （5）零部件之间的优先级根据工艺树确定，即紧后零部件所有工序必须等其紧前零部件所有工序全部完工后才能开始加工；

[0170] （6）所有空闲设备/平台和在岗工人在零时刻都可被占用和调度；

[0171] （7）重调度不影响已完工或已开工的工序；

[0172] （8）在加工中，如在过程中发现装配间隙等质量问题，需立即停止当前工序，并安排返工返修对初始计划进行重调度。

[0173] DASSP问题可以描述为：在某车间内有m种类型的设备/平台、k类不同技能的工人和n个待装配的零部件，m为设备/平台的类型数，k为所需要的技能数，n为待装配零件数。零部件之间具有有紧前紧后关系和优先级，每个零部件需要进行一道或多道工序，其工序信息已知，且每道工序可选用设备/平台至少一个。车间首先已经完成初始任务中n个零部件的调度，在各种扰动因素作用下，例如紧急插单，质检工序检测出质量问题，装配过程中出现质量问题导致中断等，对初始调度方案造成影响后，在满足产品工序优先级和不影响已开工和已完工零部件工序的前提下，为所有需要重调度的工序确定一个合理的制造顺序，选择合适设备/平台，配置合理数量工人，使得所有产品的最大完工时间最小，总拖期量最小，鲁棒性最强。

[0174] 优选地，DASSP问题中不同的扰动可以描述为：

[0175] (1) 紧急插单扰动：当在初始订单的零部件集进行调度结束后，在tu时刻车间接u u u收到一批紧急任务J ，需要尽快安排生产，t 为紧急任务到达时刻，J 为紧急任务集合。由于车间的设备/平台以及人员是有限的，因此紧急插单对初始调度生产计划产生了扰动，由于u u
紧急插单尚不能预测性，需要以t 时刻为分界线，在原先的调度计划中从t 时刻开始之后未开始的调度计划失效，在扰动之后进行全局重调度。

[0176] (2) 装配过程自检质量问题引起中断：在装配过程中，零部件的表面由于操作等问题直接发生了肉眼可辨别的质量问题，这种情况下需要立即停止该道装配工序的加工，由于复杂产品的质量问题比较棘手，在出现装配质量或成品质量问题后，往往需要上报到质量部门，由质量部门和工艺部门协商安排零部件的返工返修，一旦返工返修则需要进行重调度。

[0177] (3) 质检工序检测质量问题：与第二种质量问题不同，本类质量问题在装配过程中并未发现，当车间按照初始计划对零部件进行装配时，某道零部件的装配工序已经按照调度计划进行完毕后，需要进行装配质量检验工序，如果质检合格则可直接进行后道工序，质量不合格，需要上报到质量部门，由质量部门和工艺部门协商安排零部件的返工返修，确定好返修工序时间后重新进行处理后，再进入到后面的工序。由于质检不合格导致该零部件的工序加工时间延后，并增加了返工工序。

[0178] 优选地，建立装配焊接车间调度优化的数学模型：

[0179] 目标函数：最小化最大完工时间和任务总拖期量。

[0180] （1）最小化最大完工时间：

[0181] 完工时间（makespan）在本模型中指所有生产订单中的零部件全部完成生产所需要的时间，makespan直接反映了加工所有零部件所用的总时间，可以直接体现生产的时间效益，因此最小化最大完工时间是考虑扰动的焊接综合调度中的一个重要指标。目标函数为式（1‑1）：

[0182] （1‑1）

[0183] （2）总拖期时间最小：

[0184] 生产制造过程中的拖期是指被加工零部件的实际的完工时间晚于订单计划的交货期，即待交货零部件在期望交货的时间节点前未完成。合理的控制订单总拖期量是一个重要的性能指标。目标函数为：

[0185] （1‑2）

[0186] （3）鲁棒性：

[0187] 动态调度需要考虑调度计划的稳定性和鲁棒性，而调度计划的稳定性和鲁棒性是指在处理扰动事件后，重调度方案与初始方案的动态调整应尽可能维持初始调度方案。由于运输时间相对于零部件加工时间而言较小，且实际车间通常运输能力充足，所以零部件在各个平台之间的物流时间和运输成本忽略不计。因此在鲁棒性指标中不涉及平台设备选择的变更。零部件开工时间偏离度是指重调度计划与初始计划相比每个零部件对应的开始加工时间的偏离，零部件开工时间的变更会造成工人排班计划以及开工前准备工作的浪费。综上所述，重调度的鲁棒性指标为考虑任务中待加工零部件的开工时间偏离度，目标函数为式（1‑3）：

[0188] （1‑3）

[0189] 其中ρ代表偏离系数。

[0190] 综上所述，考虑动态扰动的焊接综合调度数学问题的加权目标函数为：

[0191] min f=αβ1 1f1+αβ2 2f2+αβ3 3f（3 1‑4）

[0192] 式（1‑4）中，α1、α2、α3为多目标权重，并且α1+α2+α3=1，β1、β2、β3为各目标函数的归一化因子。

[0193] 式（1‑1）中：n为待装配零部件总数，Cj代表零部件j的完工时间。

[0194] 式（1‑2）中，dj代表零部件j的交付期，wj代表零部件j的拖期系数。

[0195] 式（1‑3）中ρ代表偏离系数， 第i个零部件j重调度的开始时间，Sj,i代表第i个零部件j原始调度方案的开始时间。

[0196] 约束条件：

[0197] （2）

[0198] （3）

[0199] （4）

[0200] （5）

[0201] （6）

[0202] （7）

[0203] （8）

[0204] （9）

[0205] （10）

[0206] （11）

[0207] （12）

[0208] 其中，

[0209] Mp为设备平台索引，

[0210] Mj,i为零部件j的第i道工序的可选平台集合，

[0211] J为零部件集合，

[0212] Oj为零部件j的所有工序的集合，

[0213] Qj,i为零部件j的第i道工序前置工序集合{1,2,3…,i'}，

[0214] 为零部件j的第i道工序的占用平台数；

[0215] 为零部件j的第i道工序在平台p上加工的开始时间，

[0216] 为零部件j'的第i'道工序在平台p上加工的开始时间，

[0217] 为零部件j的第i道工序在平台p上的完工时间，

[0218] 为零部件j'的第i'道工序在平台p上的完工时间，

[0219] Inf为极大值，

[0220] tj,i为零部件j的第i道工序所需加工时间，

[0221] tj',i'为零部件j'的第i'道工序所需加工时间，

[0222] j'为零部件索引，

[0223] i'为工序索引，

[0224] Sj,i为零部件j的第i道工序的开始时间，

[0225] Sj',i'为零部件j'的第i'道工序的开始时间，

[0226] Fj为零部件j的前序零部件集，

[0227] Cj,i为零部件j的第i道工序的结束时间，

[0228] Cj,i'为零部件j'的第i'道工序的结束时间，

[0229] 、 分别为决策变量，

[0230] 为零部件j的第i道工序在第a时刻（天）所占用第k种工人的数量，

[0231] 为第k类工人在时间a的可用数量，

[0232] k为工人种类，

[0233] K为工人种类集合，

[0234] a为时间索引，

[0235] Amax为最大时间索引集合。

[0236] 其中：式(2)表示零部件每道工序只能占用一个设备/平台；约束(3)和约束(4)表示工序占用设备/平台的开工时间早于或等于该工序在设备/平台上完工时间；约束(5)表示零部件的开工时间需晚于或等于其所有前序零部件所有工序的完工时间；约束(6)表示同一零部件所有前道工序的完工时间均早于或等于后一道工序的开工时间；约束(7)和约束(8)表示不同零部件的工序可占用同一个设备/平台时，不可同时进行加工，即在任何时候同一设备/平台正在加工零部件不能超过一个；约束(9)表示在任何时刻对每种工人的调用数量不能超过当前时间其实际车间该种工人数量上限；约束(10)～约束(12)表示决策变量为0‑1变量。

[0237] 优选地，改进粒子群算法优化求解

[0238] 粒子群位置为 ，其中的K为粒子群的粒子数目，i为粒子的移动步数， 代表第K个粒子第i步的位置，式（13）（14）中I为最大移动次数，A为粒子的基本移动距离，M为粒子的最大移动距离， 为粒子第i次移动的移动距离， 为第 个粒子适
应度的最优值的位置，Fmax为历史中粒子适应度的最优值的位置，粒子K根据适应度以距离进行移动，r1和r2为随机变量，w为粒子的惯性权重，c1为当前适应度最优值权重，c2为历史适应度最优值权重, 代表 的模长。

[0239] （13）

[0240] （14）

[0241] Step1：初始化拥有K个个体的粒子种群，设置惯性权重，计算这K个个体的适应度，并随机给予每个粒子一个初始速度 ；

[0242] Step2：比较更新每个粒子的历史最佳适应度值位置 和全体粒子的历史最佳适应度值位置Fmax；

[0243] Step3：每循环D步后，选取适应度最低的10%的个体进行高斯变异操作，更新为新的粒子种群；若还未循环D步，则进行Step4；

[0244] 如图1所示，高斯变异：粒子 进行高斯变异则不受速度与空间移动距离的约束，工艺信息树找到维度z上的工序的紧前工序和紧后约束的位置，其紧后工序和紧前工序之间的距离为Lfb，这样通过高斯变异得到的变异粒子都是满足约束的合法解，不需要对其进行修复操作：

[0245] (15

[0246] 其中：zf为紧前工序所在位置，zb为紧后工序所在位置，被选择的维度在满足工艺紧前、紧后约束的条件下，进行高斯位置变换，得到高斯变异的结果；

[0247] Step4：根据公式得到粒子的新位置 ，更新粒子惯性速度 ，并对移动距离不足的根据方向进行延长，对超出最大移动距离的粒子进行映射处理。

[0248] Step5：判断当前移动次数i是否达到最大移动次数I的50%，若达到，则A乘以衰减系数α，返回Step2；若还未达到，则直接返回Step2。

[0249] 优选地，基于事件的完全重调度：

[0250] 如图2所示，在初始时刻输入的焊接车间的订单信息，根据任务信息和车间资源，通过使用IPSO算法形成车间初始调度方案，根据调度方案执行生产任务，如果执行过程中检测到动态扰动，比如出现紧急插单和焊接零部件质量问题等，则需要触发重调度机制，根据相应的扰动事件来对更新任务信息，执行重调度策略对扰动事件进行处理。

[0251] 触发重调度时，需先获取已完工零部件集、正在加工零部件集、未加工零部件集的信息，对车间剩余任务进行重新初始化，同时更新所有任务中零部件、平台的最早可加工时间，以及最新工人资源占用情况，然后通过本专利提出的IPSO算法进行重调度，得到重调度方案并下发到车间执行。

[0252] 实施例3：

[0253] 一种面向大型复杂产品生产装配的动态调度方法，以某生产复杂产品的大型装备制造企业分厂车间为例，该车间主要工具/设备信息组成：线束敷设工具L1={M1,M2}，数量为2；线束安装工具L2={M3,M4,M5,M6,M7,M8}；管路安装工具L3={M9,M10,M11,M12,M13,M14}，数量为
6；导通检测设备L4={M15}，数量为1；气密检测设备L5={M16}，数量为1；打磨工具L6={M17,M18,M19,M20}，数量为4；紧固工具L7={M21,M22,M23,M24}，数量为4；涂胶工具L8={M25}，数量为1；搭铁电阻检测工具L9={M26,M27,M28,M29}，数量为4。各个工具/设备类型下的详细信息以及对应可加工工序如表1所示。

[0254] 表1工具/设备详细信息

[0255]

[0256] 如表2所示，车间包含的工人班组有调试班组、装配班组、打磨班组、导通班组，其中装配班组有6人，焊接班组有26人，打磨班组有4人，导通班组为2人。每种工人可加工与技能对应的工序。

[0257] 表2工人信息

[0258]

[0259] 1、生产任务分析

[0260] （1）现有产品工艺信息

[0261] 每道工序生产实际和生产周期如表3所示。据调研，车间原排程调度计划是由排程调度人员按照以往生产经验根据产品的生产周期与交付期来确定生产计划，对车间设备工具资源以及工人资源的全局把控不足，为了满足产品交付，经常导致车间加班以及对设备工具和工人的调度不均衡。与此同时在生产过程中存在急件插单、装配调试过程中质量问题导致中断、检测出质量问题导致返工等干扰因素，这些车间中常见的动态扰动给车间计划生产决策增添了很大的难度，频繁的扰动会导致任务中大量任务完工时间滞后于约定交付期，从而造成效益上的损失。

[0262] 表3产品零部件工序装配时间（单位：小时）

[0263]

[0264] 每道工序需要占用相应的设备工具，其中每种设备工具的数量至少为1个，如表4所示，产品类别为1的工序1需要的设备工具类型为L9，从表4中读取到该类型的可选设备工具为{M26, M27, M28, M29}。

[0265] 表4产品零部件工序工具类型需求

[0266]

[0267] 车间的各类工人资源是有限的，在一些工序的加工中需要对这些工人在当日可调度的余量进行考虑，一般在装配工序需要的工人类型为H1，在焊接工序需要的工人类型为H2，在打磨工序需要的工人类型为H3，在油漆工序需要的工人类型为H4，对于每种类型产品对于工人的具体需求数量如表5所示。

[0268] 表 5产品零部件工序工人需求

[0269]

[0270] 基于以上不同类型的产品零部件装配需求，在实际生产中，某次任务计划采用工艺树表示，零部件之间的工艺顺序约束如图3所示。图中对多批量同种类型的产品进行了简化，例如工艺树第一行从左往右第一个矩形框中“线束2×4”代表该类型产品的需求量为4。该任务原计划装配总周期为160小时。对图3所示的工艺树进行零部件编号，编号后的结果如图4所示，其中第一行从左往右第一个方框中J39‑J42代表零部件类型为线束2的零部件装配工序包括{J39, J40, J41,J42}，最末行从左往右第一个方框J1代表零部件类型为氧气管路1的零部件装配工序包括{J1}。所有任务对应安装完成期限如表6所示， J1对应安装完成期限为生产进行的第50小时。

[0271] 表6交付期信息

[0272]

[0273] 2、问题求解及分析

[0274] 对以上车间实例进行分析可以发现，在实际生产调度过程中需要在排程计划阶段考虑设备/平台资源与工人资源上限和复杂工艺约束影响，即本发明所提出装配调度建模和求解。因此将综合调度问题模型应用到此问题上，可解决车间的初始排程调度问题。本节采用基于python 3.7的Pycharm软件工具进行仿真优化求解，多目标改进粒子群算法参数设置如下：

[0275] 根据相关经验设置初始化种群参数：粒子种群数量K为50，移动更新次数IT为100，高斯概率Pm为0.25；三种初始化分配方案为随机初始化40%，按交付期初始化30%，按交付期与生产周期之间的差值优先级初始化30%。车间初始静态求解结果如图5所示。

[0276] 3、工程实例调度求解

[0277] 3.1 质检检测工序检测出装配质量问题

[0278] 零部件J28在30时刻在探伤检测平台上经过探伤质检工序时被检测出在第二道焊接工序过程中存在质量问题时，此时需要停止零部件J28后续的热处理、打磨、油漆等一系列工序，通常车间在遇到此类动态扰动后，质量和技术部门给出返修工序的时间，对该零部件进行装配、焊接等工序的返工，然后再次经过质检工序并合格后，才能进行后续工序的加工。

[0279] 经由直接插入式右移重调度算法得到甘特图结果如图6所示，图中可以看出重调度后最大完工时间为142小时，订单总拖期量为10，鲁棒性指标为180。

[0280] 基于改进粒子群算法的完全重调度算法求得结果如图7所示，最优重调度方案的最大完工时间为139小时，订单总拖期量为11，鲁棒性指标为82，对比插入式右移重调度算法，最大完工时间缩短3小时，与初始调度计划保持一致，订单总拖期量差别不大，鲁棒性指标优化54%，结果表明改进粒子群算法完全重调度算法具有更好的重调度优化效果，能够有效地规避探伤质量问题扰动带来的影响。

[0281] 3.2装配过程中质量异常导致中断

[0282] 零部件J28在进行初始计划中从17到27时刻的焊接工序时，由于突发质量问题导致该道焊接工序的焊缝出现了凭借焊接工人经验可识别出的焊缝质量问题，即还未进行探伤检测工序时已经发现了质量问题，这时需要立即停止该道焊接工序，对其进行返工，此时对后续生产计划造成了扰动，因此触发了重调度，经由直接插入式右移重调度算法得到的结果如图8所示，最大完工时间为143小时，订单总拖期量为7，鲁棒性为119。基于改进粒子群算法的完全重调度算法求得结果如图9所示，最优重调度方案的最大完工时间为139小
时，订单总拖期量为7，鲁棒性为45，说明该完全重调度算法能够有效地规避由焊接质量引起生产中断带来的影响。

[0283] 3.3紧急插单

[0284] 车间于50时刻到达了一批交付期为第100小时（指从最初调度时刻开始的第100小时对应的时间）的紧急任务，紧急任务中包含的零部件加工信息如表7所示在不影响已完工任务和正在加工任务的前提下，需要对紧急任务优先进行调度并加工，因此需要重调度算法对其进行处理。

[0285] 表7紧急插单件信息

[0286]

[0287] 通过插入式右移重调度算法求解获得的调度方案甘特图如图10所示，最大时间为146小时，订单总拖期量为12，鲁棒性为159。基于改进粒子群算法的完全重调度方法求得调度结果甘特图如图11所示，最大完工时间为140小时，订单总拖期量为10，鲁棒性为92。

[0288] 对比插入式右移重调度算法，本发明的最大完工时间缩短了6小时，订单总拖期量优化16%，鲁棒性指标优化42%，说明基于改进粒子群算法的完全重调度方法具有更好的重调度优化效果，能够有效地规避紧急插单扰动带来的影响。

[0289] 以上所述，仅是本发明的较佳实施例，并非对本发明做任何形式上的限制，凡是依据本发明的技术实质对以上实施例所作的任何简单修改、等同变化，均落入本发明的保护范围之内。