CN116911515A - 基于遗传模拟退火混合算法的滚动生产紧急调度方法 - Google Patents

Abstract

本发明公开了一种基于遗传模拟退火混合算法的滚动生产紧急调度方法，针对供应市场生产计划、紧急资源调度方案的选取，构建最优选择模型，采用模拟退火算法进行数据的分析训练，利用训练好的模型得到最优的方案。本发明在时间效率为第一准则的情况下，能够考虑到生产中经常发生的市场所需资源的临时插入等突发情况，合理安排临时插入的紧急订单可以使得现有订单延期交货时间最短甚至不会出现延期情况。本发明能够快速响应市场需求和突发扰动事件，按订单组织货源，面向目标优化，合理调度复杂多样的工序排产，实现了滚动预测、滚动计划、滚动生产、滚动应急调度，最终实现高质高效的滚动生产。

Description

基于遗传模拟退火混合算法的滚动生产紧急调度方法

技术领域

本发明属于滚动生产技术领域，具体涉及一种基于遗传模拟退火混合算法的滚动生产紧急调度方法。

背景技术

滚动生产是一个全流程的生产模式，其中包含生产计划和紧急订单等，对过去的生产计划和紧急订单进行单独研究，发现在安排生产计划时，往往假设整个生产系统处于理想化的状态，忽略了生产进度等一些实际情况。生产能力的计算也忽略了设备出现故障的可能，而是将最大化产能作为约束条件安排生产，没有充分考虑生产系统的可靠性；另外，客户在追求个性化和多样化的同时，往往会带来订单的变化。在日常消费中，客户往往会因为某些原因对某些产品有特定的需求，而这些特定的需求最终会以订单的形式表现出来；当需求特别紧急时，就会产生所谓的紧急订单，如何解决好制造企业正面临的复杂环境下的调度问题对于企业的发展与核心竞争力的提升有重大意义。

一个企业的核心竞争力是在多批量的生产模式下，高质高效得满足多变的市场动态需求，并快速制定生产调度方案。目前，许多企业仍依靠人工经验生成调度方案，智能化生产水平低导致调度效率低、灵活性低、科学性不足等现象；还存在交货期准时度差、设备利用率不均衡不充分、订单反馈速度慢等问题；生产过程中出现的突发事件需要人工进行处理，处理不及时会影响产线的稳定性和连续性，进而无法保证生产进度和产品质量，甚至错过交货期。

基于现代化技术的各种调度方法层出不穷，各种人工智能算法的提出极大的拓宽了解决复杂调度问题的思路，大量学者的研究也表明人工智能算法在解决很多实践问题时具有良好的应用效果。例如文献[Chen T L,Cheng C Y,Chou YH.Multi-objectivegenetic algorithm for energy-efficient hybrid flow shop scheduling with lotstreaming[J].Annals of Operations Research,2020,290(1):813-836]以最大程度减少生产周期和电力消耗为目标提出了一种基于遗传算法的多目标解决方案；文献[Chen T L,Cheng C Y,Chou Y H.Multi-objective genetic algorithm for energy-efficienthybrid flow shop scheduling with lot streaming[J].Annals of OperationsResearch,2020,290(4)]以最大程度减少生产周期和电力消耗为目标提出了一种基于遗传算法的多目标解决方案；公开号为CN115438970A的中国专利将鲸鱼优化算法与遗传算法混合，提出一种适用于工件离散制造的大规模生产调度方法。虽然这些智能调度优化方法从理论上能求得最优解，但往往需要构造大量候选解，计算量大，在实际应用中受到限制；而且上述智能调度方法主要用于大规模生产计划的批量调度，而当生产计划产生变更时，往往无法处理或无法优化调度。

发明内容

鉴于上述，本发明提供了一种基于遗传模拟退火混合算法的滚动生产紧急调度方法，根据给定的生产计划周期，将生产计划与紧急订单进行整合研究，以受影响订单的延期最小目标，建立生产计划与紧急订单联合优化模型，借助模拟退火算法和遗传算法对模型进行求解，同时对紧急订单下的复杂调度问题进行优化。

一种基于遗传模拟退火混合算法的滚动生产紧急调度方法，包括如下步骤：

(1)对包括当前未完工订单及紧急插入订单在内的所有订单进行优先级排序；

(2)根据订单优先级对所有未完成的工序进行排列，并对这些工序进行编码；

(3)采用遗传模拟退火混合算法确定最优的调度方案；

(4)根据上述调度方案为所有未完成的工序分配机器进行加工。

进一步地，所述步骤(1)中采用灰色关联度分析法对所有订单进行优先级排序，即通过比较多个数据列与参考数据列之间的相似性来衡量影响因素之间关系的密切程度。

进一步地，每一个订单对应要求生产一个工件，每个工件的生产完工需要经历多道工序，不同的工件所经历的工序不尽相同，所有工序会被安排在固定数量的机器上进行加工，每道工序至少有一台机器可被选择加工，不同机器加工同一道工序的加工时间不尽相同。

进一步地，所述步骤(2)中根据订单优先级，订单优先级高的工件，其对应的所有工序排列在前；对于同一工件所要经历的工序，则按其生产过程进行排序；依据上述将所有未完成的工序排列完成后采用机器编码与工件编码相结合的编码方式进行编码。

进一步地，所述步骤(3)的具体执行过程如下：

3.1初始化一定规模的种群，计算种群中每个染色体的适应度，取适应度最高的染色体作为最优染色体；所述染色体包含有n个基因，n为当前所有未完成的工序数量，所述基因与未完成工序为对应关系即表示为对应工序所分配到的机器编号，则染色体即对应为关于所有未完成工序的一整套调度方案；

3.2使种群中的染色体进行交叉变异，对于交叉变异过程中生成的任一子染色体，则计算该子染色体的适应度并使其与对应的父染色体进行比较：若子染色体的适应度小于等于父染色体的适应度，则使子染色体按概率η替换父染色体；若子染色体的适应度大于父染色体的适应度，则使子染色体替换父染色体，进而使该子染色体与最优染色体进行适应度比较，若子染色体的适应度大于最优染色体的适应度，则使子染色体替换最优染色体；所述概率η基于模拟退火算法确定；

3.3以设定的冷却速率对模拟退火算法中的当前温度进行降温；

3.4根据步骤3.2～3.3反复进行遗传迭代直至温度降至设定的最低温度阈值，输出种群中的最优染色体并根据其对应的调度方案为所有未完成工序分配机器。

进一步地，所述步骤3.1中对于初始化种群每一染色体的基因，则从可执行对应工序的机器集合中随机选取，并将所选机器的编号赋予对应的基因。

进一步地，所述步骤3.1中计算每个染色体的适应度，即采用染色体所对应的调度方案为每个未完成工序分配对应的机器，进而对这些机器进行分配调度后计算确定所有订单整体的完工时间，该完工时间即为染色体的适应度，完工时间越少则适应度越高。

进一步地，所述步骤3.2中基于模拟退火算法确定概率η的计算表达式如下：

其中：K为给定常数，T为当前温度，I_s和I_f分别为子染色体和父染色体的适应度。

本发明调度方法以使受影响订单交货期延迟最小为目标，将模拟退火算法与遗传算法相融合，能够集合两者的优点、避免各自的缺点，使得该混合算法具有良好的搜索寻优能力。然后在此基础上本发明加入了订单优先级确定模块，决定将灰色关联分析法应用于此，初始解质量对算法的寻优速度与求解质量具有一定影响，进行订单优先级排序便是为了构造较为优秀的初始解。在紧急插单的事件中，本发明算法较退单算法和顺延插单算法相比有着明显的优势，现有两种算法大概率会出现订单交期延迟的现象，而用本发明算法可以让整个生产过程中始终是处于最合理且在交货日期之前能尽可能的完成订单，有更好的求解性能，能够动态的解决紧急插单问题。

附图说明

图1为本发明滚动生产紧急调度方法的流程示意图。

图2为初始调度方案示意图。

图3为采用本发明遗传模拟退火混合算法输出的调度方案示意图。

具体实施方式

为了更为具体地描述本发明，下面结合附图及具体实施方式对本发明的技术方案进行详细说明。

本发明基于遗传模拟退火混合算法的滚动生产应急调度方法，通过加入灰度关联分析法确定优先级，用于解决或者至少部分解决现有技术的方法存在的市场生产效果不佳；具体实现过程如图1所示：

首先用灰色关联分析主要通过比较多个数据列与参考数据列之间的相似性来衡量影响因素之间关系的密切程度。

先数据无量纲处理，这里a_i表示第i个订单，a₀表示参考订单，x_ij(j＝1,2,3,4,5,6,7)为订单i对应的第j个影响因子，通过无量纲处理可将原始数据转换为[0,1]区间内的数据，具体表达式如下：

然后进行灰色关联系数计算，对原始数据进行无量纲处理后，接下来计算灰色关联系数，首先令Δ_ij＝|x_0j-x_ij|，Δ_ij代表第j个影响因素下订单a_i与订单a₀的评价差值的绝对值，关联系数ξ_ij用下面公式计算：

式中：ξ_ij表示第j个评价指标下订单a_i和a₀的关联系数，ξ为分辨系数，一般取值0.5。

最后进行订单优先级计算，关联系数ξ_ij数量大，信息相对分散，难以相互比较，并且数据处理过程繁杂。因此本发明采用灰色关联系数的算术平均值来进行比较，这一平均值称为灰色关联度。

式中：r_i为订单灰色关联度，r_i的取值范围为(0,1]；r_i的值越大，表明第i个订单与最高优先级订单关联度越大，该订单的优先级别越高；r_i的值越小，该订单与最高优先级订单关联度越小，该订单的优先级别越低。

得到灰色关联度后，计算求得平均值，将订单优先顺序按照平均关联系数数值的大小进行排列，便得到了订单的优先级顺序，生成初始种群，计算个体适应度值f(G_i)，其中Mt(G_i)为个体G_i对应的最大完工时间，Mt(G_i)_max和Mt(G_i)_min分别表示种群中Mt(G_i)的最大值和最小值，则个体适应度值 得到的适应度值区分度大大提高。

如表1所示为插单时原来订单加工的状态，我们计算各个订单的优先级，依订单优先级实现种群初始化。

表1

订单名称

工件

工序1

工序2

工序3

工序4

工序5

1

J1

已完工

已完工

正在加工

尚未开工

——

2

J2

已完工

正在加工

尚未开工

尚未开工

尚未开工

3

J3

正在加工

尚未开工

尚未开工

尚未开工

尚未开工

4

J4

正在加工

尚未开工

尚未开工

——

——

5

J5

尚未开工

尚未开工

尚未开工

尚未开工

尚未开工

依据订单优先级将未加工的工件工序进行排列，订单优先级大的工序排位在前，优先级小的工序排位在后，并采用机器编码与工件编码相结合的编码方式进行编码，得到初始调度方案如图2所示。

从种群中选择较优秀的两个个体作为亲本，使用保留最佳个体策略复制前10％的优秀染色体作为亲本，其余个体利用锦标赛选择方式获得；从目前的最优解中选择最佳个体直接进行复制，完全保留下来，未经任何交叉操作。锦标赛选择则从当前种群中随机选择两个个体，在0到1之间生成随机k，若k<0.8，则选择适应度大的染色体；否则，选择适应度小的染色体。

本实施方式选择的是一种基于工序编码的IPOX交叉法，其优点在于不用进行冲突检测，IPOX交叉法的具体步骤如下：

步骤1：随机选择2条父代染色体P1和P2，其中P1＝[3,1,3,2,2,1,3,2,1]，P2＝[2,3,1,3,1,2,3,1,2]。

步骤2：将工件集J＝{1,2,…,n}(n＝3)随机划分为2个非空子集合J₁和J₂，其中J₁＝{1}，J₂＝{2,3}。

步骤3：复制父代染色体P1中包含J₁的元素(基因)到子代染色体Z1中，并保留其原来的顺序；复制父代染色体P2中包含J₁的元素到子代染色体Z2中，并保留其原来的顺序。

步骤4：复制父代染色体P1中包含J₂的元素到子代染色体Z2中，在保留其原来顺序的基础上再对这些元素采用倒序排列，得到子代染色体Z2＝[2,3,1,2,1,2,3,1,3]；复制父代染色体P2中包含J₂的元素到Z1中，在保留其原来顺序的基础上再对这些元素采用倒序排列，得到子代染色体Z1＝[2,1,3,2,3,1,3,2,1]，如表2所示：

表2

P1	3	1	3	2	2	1	3	2	1
										Z1	2	1	3	2	3	1	3	2	1
P2	2	3	1	3	1	2	3	1	2
										Z2	2	3	1	2	1	2	3	1	3

本实施方式对其进行了局部改进，交叉概率Pc采用自适应调整，引入当前迭代次数。

式中：f(G_i)_max为种群中最大的个体适应度值，f(1)为被选择的2条父代染色体中较小的个体适应度值，f(G_i)_avg为种群的平均适应度值，G为当前迭代次数，K₁为交叉操作调整参数，取值范围为(0,1)。

本实施方式采用基于工序的变异与基于机器的变异两种变异方法：基于工序的变异即随机选择一个工序并插入到另一个工序前，此时工序对应的机器也相应提前；基于机器的变异则保持工序编码不变，选择其中一台机器，确定占用所选机器的加工工序，判断该工序是否可选用其它机器，若允许，则选择其它机器将此设备代替，否则重新选择一台机器；并得到新种群G_i′计算适应度值f(G_i′)。

基于工序的变异步骤如下：

步骤1：随机选定一个工序。

步骤2：将选定的工序任意插入到一个位置，原来位置的工序向后顺延排序；基于工序的变异影响的为一段基因，表3基于工序的变异中将位置9的工序4插入到位置5，原来的基因片段2,3,1,4,4变为了4,2,3,1,4，完成了交叉变异。

表3

基于机器的变异步骤如下：

步骤1：随机选定一台机器。

步骤2：确定占用所选机器的加工工序，判断该工序是否可选用其它机器，若允许，则选择其它机器将此设备代替，否则返回步骤1；基于机器的变异影响的为单个基因，表4中基因2变为了基因1。

表4

P	2	4	1	3	2	3	1	4	4	3	1	2
													NP	2	4	1	3	1	3	1	4	4	3	1	2

判断平均适应度值与平均适应度值/>的大小，若前者大于后者，则接受新种群作为下一代种群，进行退温操作；否则以概率/>L]，L为每个温度下生成解的个数，接受G_i′为下一代种群；若G_i′被拒绝，则返回重新计算适应度值f(G_i′)。

退温操作：使T_i+1＝λT_i，G_i+1＝G_i，i＝i+1，λ为降温系数，接近于1。

经过上一步骤得到了新种群，判断是否满足终止条件，满足则算法结束，输出结果，不满足返回重新计算适应度值f(G_i)，终止条件包括终止温度、迭代次数，输出结果为图3所示的调度方案。

由此可见，订单间的生产工艺往往不同，所需要的生产系统相关机器也不同，就会产生多条生产线，所以在多条生产线多个工艺多个设备生产的间隙，我们在产生新的生产计划过程中有效的利用这些间隙进行生产最优最佳。

上述对实施例的描述是为便于本技术领域的普通技术人员能理解和应用本发明，熟悉本领域技术的人员显然可以容易地对上述实施例做出各种修改，并把在此说明的一般原理应用到其他实施例中而不必经过创造性的劳动。因此，本发明不限于上述实施例，本领域技术人员根据本发明的揭示，对于本发明做出的改进和修改都应该在本发明的保护范围之内。

Claims (8)

1.一种基于遗传模拟退火混合算法的滚动生产紧急调度方法，包括如下步骤：

(1)对包括当前未完工订单及紧急插入订单在内的所有订单进行优先级排序；

(2)根据订单优先级对所有未完成的工序进行排列，并对这些工序进行编码；

(3)采用遗传模拟退火混合算法确定最优的调度方案；

(4)根据上述调度方案为所有未完成的工序分配机器进行加工。

2.根据权利要求1所述的滚动生产紧急调度方法，其特征在于：所述步骤(1)中采用灰色关联度分析法对所有订单进行优先级排序，即通过比较多个数据列与参考数据列之间的相似性来衡量影响因素之间关系的密切程度。

3.根据权利要求1所述的滚动生产紧急调度方法，其特征在于：每一个订单对应要求生产一个工件，每个工件的生产完工需要经历多道工序，不同的工件所经历的工序不尽相同，所有工序会被安排在固定数量的机器上进行加工，每道工序至少有一台机器可被选择加工，不同机器加工同一道工序的加工时间不尽相同。

4.根据权利要求1所述的滚动生产紧急调度方法，其特征在于：所述步骤(2)中根据订单优先级，订单优先级高的工件，其对应的所有工序排列在前；对于同一工件所要经历的工序，则按其生产过程进行排序；依据上述将所有未完成的工序排列完成后采用机器编码与工件编码相结合的编码方式进行编码。

5.根据权利要求1所述的滚动生产紧急调度方法，其特征在于：所述步骤(3)的具体执行过程如下：

3.1初始化一定规模的种群，计算种群中每个染色体的适应度，取适应度最高的染色体作为最优染色体；所述染色体包含有n个基因，n为当前所有未完成的工序数量，所述基因与未完成工序为对应关系即表示为对应工序所分配到的机器编号，则染色体即对应为关于所有未完成工序的一整套调度方案；

3.2使种群中的染色体进行交叉变异，对于交叉变异过程中生成的任一子染色体，则计算该子染色体的适应度并使其与对应的父染色体进行比较：若子染色体的适应度小于等于父染色体的适应度，则使子染色体按概率η替换父染色体；若子染色体的适应度大于父染色体的适应度，则使子染色体替换父染色体，进而使该子染色体与最优染色体进行适应度比较，若子染色体的适应度大于最优染色体的适应度，则使子染色体替换最优染色体；所述概率η基于模拟退火算法确定；

3.3以设定的冷却速率对模拟退火算法中的当前温度进行降温；

3.4根据步骤3.2～3.3反复进行遗传迭代直至温度降至设定的最低温度阈值，输出种群中的最优染色体并根据其对应的调度方案为所有未完成工序分配机器。

6.根据权利要求5所述的滚动生产紧急调度方法，其特征在于：所述步骤3.1中对于初始化种群每一染色体的基因，则从可执行对应工序的机器集合中随机选取，并将所选机器的编号赋予对应的基因。

7.根据权利要求5所述的滚动生产紧急调度方法，其特征在于：所述步骤3.1中计算每个染色体的适应度，即采用染色体所对应的调度方案为每个未完成工序分配对应的机器，进而对这些机器进行分配调度后计算确定所有订单整体的完工时间，该完工时间即为染色体的适应度，完工时间越少则适应度越高。

8.根据权利要求5所述的滚动生产紧急调度方法，其特征在于：所述步骤3.2中基于模拟退火算法确定概率η的计算表达式如下：

其中：K为给定常数，T为当前温度，I_s和I_f分别为子染色体和父染色体的适应度。