考虑订单加急生产的柔性车间作业动态调度*

2022-12-26朱旭东

机电工程 2022年12期

关键词：加急遗传算法机床

朱旭东

(无锡工艺职业技术学院,江苏宜兴 214200)

0 引言

随着车间生产的智能化程度和柔性程度不断提高,目前的车间机床可以加工多工件的多种工序,且工序在不同机床上的生产加工效率也可以不一致[1]。

合理的柔性车间调度方案可以有效提升车间的生产效率,体现企业的核心竞争力[2]。因此,研究柔性车间的生产调度问题具有重要的经济意义和实用价值。

柔性车间动态调度是在静态调度基础上,考虑生产扰动的一类调度问题。生产干扰主要由加工的中断因素和不确定事件所引起,包括机床故障、紧急插单、加急生产、任务随机到达等因素[3]。

根据优化目标分类,柔性车间动态调度问题可以分为完工时间优化、能耗优化和负载均衡优化等[4]。根据优化目标数量分类,柔性车间动态调度问题可以分为单目标调度问题和多目标调度问题[5]。从动态调度算法的角度出发,柔性车间动态调度问题又可以分为精确求解算法和启发类求解算法。

其中,精确求解算法是基于梯度的一类求解方法,该方法的优点是可以获得算法的精确最优解,且收敛速度较快;其缺点是只适用于小规模调度问题,且计算量较大。

启发类求解方法是基于元启发算法的一类求解方法。常见启发类求解算法包括遗传算法、粒子群算法等[6,7]。该类方法的优点是适用于大规模调度问题、计算量适中,缺点是调度方案的优劣与算法性能优劣直接相关,不能保证一定获得最优解。

尤一琛等人[8]研究了机器发生随机故障时的车间动态调度问题,设计了组合重调度策略,并使用精英选择遗传算法对其进行了求解,实现了机械故障条件下重调度的目的。张国辉等人[9]基于改进帝国竞争算法,研究了机械故障发生时的车间重调度问题,并在3种机器故障情景下,验证了该方法的可行性与有效性。模糊加工时间和新订单插入两种扰动下,RAKOVITIS N等人[10]研究了车间的重调度问题,提出了采用两阶段人工蜂群算法求解重调度的方法,经测试,该方法调度结果优于另外7种现有的算法调度结果。

上述针对中断因素和不确定事件的车间动态重调度问题中,研究人员主要研究了由机械故障、新订单插入、订单加工事件模糊等因素导致的重调度问题,而针对现有订单的加急生产扰动的相关研究较少。但是当前市场需求瞬息万变,因此,客户依据市场而具有时变的生产需求是常见情况。

笔者针对上述问题进行研究。首先,根据预先设定的生产需求,提出基于强制进化遗传算法的静态调度方法;然后,当发生订单加急生产扰动时,设计具有记忆功能的优先生产通道,该生产通道能够根据订单紧急程度,自适应地调整相应生产机床;最后,在生产车间中,对该研究的重调度方法进行验证。

1 问题描述与建模

1.1 订单加急的动态重调度问题描述

订单扰动可以分为订单插入和订单加急两类,订单插入是指原本不在计划中的订单插入到当前生产节奏中;订单加急是指本来就在计划中的订单,要求加急生产[11]。

此处,笔者研究的是订单加急扰动下的柔性车间动态重调度问题。

假设具有N个工件生产任务,记为{T1,T2,…,TN},工件i的第j道生产工序记为Oij,工件i的工序数量记为Ji;车间中具有K个加工机床,记为{M1,M2,…,MK}。每个机床具有加工不同工序的能力,每个工序允许选择不同的机床。由于机床性能的差异性,同一工序在不同机床上的加工时间是不一致的。

柔性车间生产调度是指:通过合理地安排工序的加工顺序和对应机床,实现时间最短、能耗最低、负载均衡等目标[12]。

而订单加急扰动下的柔性车间动态重调度问题是指:按照预定调度方案生产过程中,忽然接到某一订单加急生产的通知,而对车间内剩余生产任务进行重新调度的问题。

1.2 动态重调度问题建模

为了建立规范实用的柔性车间动态重调度问题模型,笔者对该问题做出以下假设和规范:

(1)初始时刻,所有机床均处于健康可用状态;

(2)所有工件必须按照设定的工序顺序加工;

(3)任一工序不能在多个机床上同时加工,但是必须加工一次;

(4)在任意时刻,同一机床无法同时加工多个工序;

(5)同一工件的下一工序开始时刻必须处于上一工序加工完成时刻之后;

(6)任一工序在可选机床上的加工概率是一致的。

为了建立柔性车间动态重调度模型,笔者设置一个标识参数xijk,并将其定义为:

(1)

基于上述假设和规范,根据订单加急扰动柔性车间动态重调度问题特点,笔者在保证加急订单优先生产的前提下,以全部订单的完工时间最短为优化目标,进行动态重调度问题建模。

则订单加急生产扰动下的车间重调度问题优化模型为:

(2)

式中:T—最大完工时间;tSij—工序Oij的开始时间;tEij—工序Oij的结束时间;Pijk1—工序Oij在机器k1上的加工概率。

2 基于强制进化遗传的静态调度

当发生订单加急生产扰动时,在预先设定生产方案的基础上进行重调度,因此,笔者首先要进行静态生产调度,而后考虑订单加急生产扰动下的动态重调度。

2.1 染色体编码与解码

对于多工件、多工序、多柔性机床的生产调度问题,此处笔者使用双基因链十进制编码方式,其基因长度与总工序数量一致。一条基因链为工序基因链,规定了工序的加工顺序;另一条基因链为机器基因链,规定了各工序加工对应的机器。

此处以3个工件共10道工序、4个生产机床为例,某染色体编码如图1所示。

图1 双基因链编码

图1所示的染色体的工序链中,数字3出现了4次,表明工件3具有4道加工工序,数字3第1次出现代表工序O31,第2次出现代表工序O32,依此类推。

工序链解码得到工序的加工顺序为:O31→O11→O21→O32→O22→O12→O13→O33→O23→O34;机器链解码得到对应的生产机床为:M2→M4→M3→M1→M1→M3→M4→M2→M3→M1。

2.2 强制进化遗传实现方法

强制进化遗传操作的核心思想是:适应度强的染色体具有较多的优秀基因片段,因此,适应度强的染色体应该大概率进行交叉,实现优秀基因片段重组的目的;同时进行小概率、小范围的基因变异,防止优秀基因片段的破坏;相应的,适应度弱的染色体具有较少的优秀基因片段[13]。

因此,适应度弱的染色体应该小概率进行交叉,同时进行大概率、大范围的基因变异使染色体强制进化。

将交叉概率范围设置为[pc1,pc2],变异概率范围设置为[pm1,pm2]。某一染色体i的适应度值记为fi,则其交叉概率和变异概率分别为:

(3)

式中:pci—染色体i的交叉概率;pmi—染色体i的变异概率;fmax，fmin—适应度最大值和最小值。

前文中提到,交叉操作时,适应度强的染色体进行小范围变异,适应度弱的染色体进行大范围变异(所谓的“大小范围”是指参与变异的基因片段长度)。

(4)

2.3 遗传操作方式与自然选择

为了满足柔性机床加工的约束条件,遗传操作前后工序链中每个工序必须出现且仅出现1次,笔者提出了改进POX交叉策略,该策略在交叉前后能够满足工序约束,无需进行人为检查和验证。改进POX交叉策略如图2所示。

图2 改进POX交叉策略

改进POX交叉策略具体方法为:

(1)将工件按照数量大致相等的原则分为两组,图2中工件2和3为一组,工件1和4为一组;

(2)父代1的工件1、4基因位不变,遗传给子代2,父代2的工件2、3基因位不变,遗传给子代1;

(3)父代1的工件1、4基因位左移一位,嵌入到子代1,父代2的工件2、3基因位左移一位,嵌入到子代2。

变异包括工序变异和机床变异,染色体按照随机方式选择变异方式。当进行工序变异时,按照式(4)确定变异基因长度,然后按照逆序方式进行变异;当进行机床变异时,以负载均衡为目的进行变异,实现方法为:统计机床链中出现频次最多的机床,将频次最多的机床变异为满足该工序生产要求的另一机床。

工序变异和机床变异方式如图3所示。

图3 变异策略

图3(a)中,父代选择了基因2和基因3之间的片段,将其逆序变异后得到子代工序链;图3(b)中,父代机床链机床2出现的频次最多,随机选择一个机床2,将其变异为满足生产要求的机床3。

自然选择过程即为优胜劣汰过程[14],遗传操作后比较子代和父代的适应度值,保留其中适应度高的个体,维持物种的规模稳定。

3 基于记忆优先通道的动态重调度

接下来,笔者设计记忆优先通道,解决订单加急生产扰动下的柔性车间动态重调度问题。首先,对优先通道的记忆功能进行说明;而后,对优先通道的重调度原理进行设计;最后,给出车间重调度的流程图。

3.1 记忆功能与记忆矩阵

在出现订单紧急加工扰动时,扰动时刻Te之间的加工方案无法改变,扰动时刻Te之后的生产方案进行重新调度。因此,具有记忆功能的记忆矩阵是重调度方法必需的,记忆矩阵包括机器记忆矩阵M和时间记忆矩阵T两个。

其中,机器记忆矩阵M用于记忆已完成工序使用的机床,以及未完成工序的可选机床集合,为:

(5)

式中:mij=[m1,…,mk]—满足工序Oij生产要求的机床集合。

在订单加急生产时刻Te之前,已完成工序只保留选择的机床、淘汰未选机床,未完成工序保留可选机床集合。

同样地,时间记忆矩阵用于记忆已完成工序的耗时,以及未完成工序的可能耗时,为:

(6)

式中:tij=[t1,…,tk]—可选机床集合mij中各机床的加工时间。

在订单加急生产时刻Te之前,已完成工序只保留选择机床对应的加工时间、淘汰未选机床的加工时间,未完成工序保留可选机床集合的加工时间集合。

3.2 优先加工通道设置

优先加工通道是为了应对订单加急等扰动而设置的,当订单加急生产时刻Te到来时,已进行而未完成的工序继续生产,未上机床生产线的工序进行重新调度。

由于订单的紧急程度不同,在安排生产机床时的优先程度也必然不同,笔者通过设置一个优先系数e∈[0,1],使机床安排的优先程度随订单紧急程度自适应变化。

优先加工通道根据订单生产的紧急程度,为其安排耗时相对较小的加工机床,具体方法为:

mij=rand[Mij((1-e)+1)·lij]

(7)

式中:mij—优先通道为工序Oij安排的机床,rand()—随机函数;Mij—工序Oij的可使用机床按照加工时间升序排列得到的集合; —向上取整函数;lij—工序Oij可使用机床的数量。

式(7)可解释为:假设e=70%,那么从加工时间最短的前30%机床集合中随机选择一个机床,执行工序Oij的加工任务。式(7)中,这种按照排序和随机方式产生的机床,既保证了工序Oij的优先生产,也使用随机方式提高了染色体多样性,是一种兼顾优先和多样性的调度方式。

3.3 动态重调度流程

基于记忆优先通道和强制进化遗传算法的柔性车间动态重调度算法流程,如图4所示。

图4 柔性车间动态重调度流程

对柔性车间的动态重调度流程进行如下说明:

(1)车间在接到订单加急生产通知之前,按照静态调度方案进行生产;

(2)车间接到订单加急生产通知之后,使用记忆优先通道对加急订单进行调度,而后使用强制进化遗传算法,将剩余生产任务插入到订单加急调度方案中。

4 实验与结果分析

笔者从两个方面对柔性车间动态重调度方法进行实验验证:(1)验证基于强制进化遗传算法的静态调度性能;(2)验证基于记忆优先通道的动态重调度性能。

4.1 车间静态调度性能验证

根据江苏亨鑫科技有限公司某车间的生产需求,该车间共承担6个工件的生产任务,每个工件具有6道生产工序,车间中具有10台制造机床,各工序的可选机床及对应加工时间如表1所示。

表1 工件加工任务

为了进行比较,笔者分别使用标准遗传算法、强制进化遗传算法、文献[15]改进遗传算法对表1给出的案例进行调度。文献[15]改进遗传算法的参数按照原文设置,标准遗传算法和强制进化遗传算法的共同参数设置一致:染色体规模为100,算法最大迭代次数为200。另外,在标准遗传算法中,交叉概率Pc=0.3,变异概率Pm=0.2;在强制进化遗传算法中,交叉概率范围[pc1,pc2]=[0.2,0.4],变异概率[pm1,pm2]=[0.1,0.3]。

笔者利用上述3种算法分别进行10次柔性车间静态调度,统计10次最优调度方案的最大生产时间、最小生产时间、平均生产时间,其结果如图5所示。

图5 任务完工时间统计

由图5可知:针对表1给出的加工案例,上述3种算法规划的10次调度方案中,强制进化遗传算法静态调度方案的平均加工时间为39.4 min,比改进遗传算法减少了4.57%,比标准遗传算法减少了6.85%;强制进化遗传算法给定调度案例的最大完成时间、最小完成时间均小于标准遗传算法和文献[15]改进遗传算法所用时间,说明强制进化遗传算法具有最佳的静态调度性能。这是因为:

(1)强制进化遗传算法根据染色体适应度自适应调整个体的交叉概率,使优秀个体的交叉概率较大,实现了优秀基因片段重组;

(2)强制进化遗传算法根据染色体适应度自适应调整个体的变异概率,使较差个体的变异概率和范围较大,实现了较差染色体的强制进化;

(3)改进POX交叉策略在满足工序约束条件下,使染色体变化较大,增强了算法的全局搜索能力。

强制进化遗传算法规划的最优生产调度方案的甘特图,如图6所示。

图6 任务调度的甘特图

分析图6可知:所有工件的工序加工均满足时序要求,且均由满足加工要求的机床完成。

4.2 车间动态重调度性能验证

为了对动态重调度方法进行验证,笔者将记忆优先通道重调度方法与贪婪自适应方法[16]进行比较;并设计不同加急时刻、不同任务加急的情况进行比较。

笔者将加急时刻Te=10min，加急任务T1称为任务1;加急时刻Te=20min，加急任务T1称为任务2;加急时刻Te=20min，加急任务T3称为任务3,重调度结果如表2所示。

表2 动态重调度任务完成时间/min

分析表2中数据可知:

(1)在3个订单加急生产任务中,实现了订单加急生产。以任务1为例,记忆优先通道重调度方法的加急调度方案使任务1的生产时间减少了2 min,贪婪自适应方法的加急调度方案使任务1的生产时间减少了1 min;

(2)在订单加急生产的条件下,相比于预先的静态方案,记忆优先通道重调度方法和贪婪自适应方法在所有任务耗时上均有一定提高,但是记忆优先通道重调度方法的增加时间少于贪婪自适应方法调度方案增加的时间。以任务1为例,记忆优先通道重调度方法的加急调度方案在整体生产时间上增加了5.0 min,贪婪自适应方法加急调度方案在整体生产时间上增加了8.0 min;

(3)记忆优先通道重调度方案在任务1、任务2、任务3的整体完工时间分别为42.0 min、43.0 min、42.5 min,比贪婪自适应方法分别减少了3.0 min、2.0 min、3.5 min,说明记忆优先通道重调度方案在加急工况下的重调度性能好于贪婪自适应方法;

(4)在不同加急时刻、不同工件加急的工况下,记忆优先加工通道的加急订单生产时间、整体加工时间均小于贪婪自适应方法;

(5)对于同一任务,在不同时刻进行加急,任务的可加急空间是不同的;对于同一时刻,不同任务的加急空间也是不同的。

综合上述实验数据可以得出结论:

在上述3种任务加急生产扰动中,记忆优先通道重调度方案的整体生产耗时少于贪婪自适应方法重调度方案,同时记忆优先通道重调度方案的加急订单生产耗时少于贪婪自适应方法。这是因为当发生订单加急扰动时,加急生产通道能够根据生产任务的紧急程度自适应为其分配合适的生产机床,在满足加急生产的同时保证了任务整体的加工效率[17-19]。

以加急时刻为Te=20 min,加急任务为T3为例,对2种方法动态重调度方案进行展示,结果如图7所示。