考虑机器故障的柔性作业车间动态调度*

周尔民,马 畅,刘 宁

(华东交通大学a.机电与车辆工程学院;b.交通运输与物流学院,南昌 330013)

0 引言

动态的柔性车间调度问题是在柔性作业车间调度问题的基础上延伸而来,因其考虑到车间实际加工生产过程中会受到紧急件插入、交货期变更、机器故障、等各类不确定扰动的影响,所以是一种更符合实际生产环境的调度问题[1]。而机器故障作为加工车间常见扰动之一,具有随机、离散分布的特点,故障发生前可能无法准确预估其发生时刻点,以及需要的修复时间,因此当机器故障发生时保证生产加工正常运行是关键,这就需要在故障发生时对当前加工任务状态和故障扰动程度进行评估分析,对原有的调度方案进行重新规划。在故障发生后选择合理的重调度方式,生成新的满足既定目标、偏离度小、响应迅速的调度方案逐渐成为研究的重点[2]。

针对动态的柔性作业车间调度问题(dynamic flexible job-shop scheduling problem,DFJSP),学者们从问题的不同角度提出有效的动态调度方法[3-4]。SHAHGHOLI等[5]使用改进的人工蜂群算法通过在启发式算法模型框架双层编码基础上对工序编码优化,对机器编码引入本地搜索进行优化。GAO等[6]针对FJSP中存在的机器故障修复问题引入两种新的局部搜索算子,有效地平衡重调度阶段的稳定性和完工时间。SHAHRABI等[7]提出了一种基于变量邻域搜索的调度方法,在基于Q因子算法的强化学习框架中使用了新方法来计算学习过程中的奖励值,并将该方法的实验结果与常用调度规则进行对比。吴正佳等[8]构建了机器故障发生后剩余工件约束数学模型,提出插入重调度的方式。刘壮等[9]考虑了不同的决策指标,以调度方案间的偏序关系为依据进行选取最优重调度方案。尤一琛等[10]采用事件和周期混合驱动的方式设计组合重调度策略应对机器故障的影响。

综上所述,目前对机器故障动态调度的研究大部分针对算法层面的改进,或者在故障发生后直接采用事件和周期混合驱动的方式进行重调度。很少考虑周期重调度的驱动区间,以及机器故障概率不同对重调度方案的影响。本文采用事件和基于机器故障概率周期的混合驱动方式,通过求解加工机器发生故障的概率确定周期重调度驱动区间,即机器故障概率值越大则周期驱动区间越小。并采用熵值法确定引入评价指标的权重系数,设计了3种邻域结构提高算法局部搜索能力,利用改进的遗传变邻域算法对最优重调度方案进行求解,最后通过案例分析验证了该方法的有效性。

1 问题描述

FJSP可概括为:有i个工件,每个工件有j道工序,工件按照指定加工路线安排在在k个设备上,并使调度方案指标最优[11]。机器故障下的柔性作业车间调度是在初始化调度的基础上,当机器故障发生时,对未完成工件的加工设备、工序加工顺序重新调整。

1.1 符号说明

本文的变量及符号定义如表1所示。

表1 模型参数符号及定义

决策变量:重调度方案中,如果第i个工件的第j道工序在机器k上加工,aijk则为1;否则为0。

原调度方案中,如果第i个工件的第j道工序在机器k上加工,aijko则为1;否则为0。

如果操作aij在重调度方案和原调度方案选择的加工机器不同,aij则为1;否则为0。

1.2 重新调度约束条件

右移重调度约束条件如下:

(1)

式(1)表示右移重调度中受故障影响工件开始时间等于故障时刻加上故障设备修复时间;一个工件的一道工序只能在一台机器上加工;一道工序的开始时间与加工时间之和等于结束时间。

完全重调度约束条件:

(2)

部分重调度约束条件:

(3)

式(2)表示在故障时刻点针对未加工工序实施完全重调度,生成新的加工列表下加工机器和加工工序、加工时间的约束关系。式(3)表示部分重调度条件下故障机器上未加工工件工序重新安排至剩余的加工机器,但不改变剩余机器上原有的工件工序,只改变加工时间和加工顺序。

1.3 目标函数

式(4)表示t时刻机器发生故障时对应的最小化最大完工时间的数学模型:

(4)

式中:r表示发生故障机器数。

2 机器故障下的重调度方法

2.1 机器故障概率

生产加工过程中机器发生故障的概率Mfr由质量参数、机器开动率和已工作时间共同决定。

(5)

式中:g1(g1>1)表示质量参数,值越大表示该类机器质量越好;g2(0

2.2 组合重调度策略

针对何时进行重调度和如何进行重调度,采用异常事件和基于机器故障频率的周期混合驱动策略,根据机器故障频率设置合理的重调度周期区间,在保证加工车间调度稳定性的同时,也能够快速响应突发的设备故障事件,从而更加有效地提高了系统的稳定性。

2.3 重调度方式

重调度方案结合部分重调度、完全重调度[12]、右移重调度[13]3种重调度方式。部分重调度针对故障机器上未开始加工工序,重新安排其加工机器,没发生故障的机器上加工工序保持不变,加工时间和加工顺序均有变化,机器故障恢复时间未知时大多采用此调度方式。

2.4 重调度方案评价指标

机器故障下重调度方案评价模型表达式为:

(6)

把最大完工时间偏差α、工序结束时间累积偏差值β和机器偏离成本γ作为评价指标,μ1、μ2、μ3为权重系数,重调度评价指标越小越好。

2.5 重调度流程

在整个调度过程中,原调度方案以最小化最大完成时间为目标,机器发生故障时,采用事件和基于故障概率的周期混合驱动策略,综合使用右移重调度、完全重调度、部分重调度3种组合方式。在重调度方案优选阶段中,考虑到方案变动必然带来额外成本增加以及加工生产稳定性降低的问题,因而引入最大完工时间差值、工序结束时间差值和机器偏离成本作为评价指标,评价指标权重系数采用熵值法确定,在3者生成方案中选择生成的最优方案。重调度流程如图1所示。

图1 重调度流程图

3 遗传变邻域算法

在遗传(genetic algorithm,GA)算法[14]的基础上综合使用变邻域搜索(variable neighborhood search,VNS)算法,并设计了自适应交叉算子和变异算子,以及基于VNS关键路径的3种邻域结构。

3.1 染色体编码与解码

针对FJSP2个子问题工序排列和机器选择,采用双层编码结构对染色体完成编码[15]。解码时采用文献[16]给出的插入式贪婪解码。

3.2 交叉、变异操作

遗传算子包括交叉算子和变异算子。染色体有机器字符串和操作字符串两个字符串,为了避免在遗传重组后产生不可行的解,对交叉算子和变异算子设计不同的方法。

3.2.1 交叉算子

针对编码方式采用OS层染色体的IPOX交叉[17]。交叉概率随迭代次数在(pcmin,pcmax)之间变化。

(7)

式中:pc表示交叉概率,pcmax表示最大概率,pcmin表示最小概率,genNum、iterNum分别表示生成次数和算法当前迭代次数。

3.2.2 变异算子

变异算子用于保持种群的多样性。变异概率也是自适应的从pmmax更改为pmmin。开始时大的突变概率可以增强搜索空间以提高搜索能力,随着变异概率的降低开发能力逐渐提高。

(8)

式中:pm表示突变概率,pmmax表示最大概率,pmmin表示最小概率,genNum、iterNum表示与式(7)相同。

3.3 邻域结构

在局部搜索中改变初始解周围的有效邻域结构非常重要。图2虚线部分展示了为4个工件在3个机器加工的关键路径。

图2 关键路径图

设计了3种基于关键路径的邻域结构,一是更换关键操作的加工机器;另外两个是更改关键操作以生成相邻的解决方案。

邻域结构1将操作分配给替代机器集合的机器生成解决方案,所选操作必须是关键操作。在这种邻域结构中,机器上的操作顺序不会改变。步骤如下:首先随机选择关键操作;然后选择备选机器集中的最短机器来分配以处理操作。

邻域结构2通过插入改变操作顺序,任务分配不会更改。这些步骤可以描述如下:随机获得两个数字,一个用于确定要插入的基因,另一个用于确定基因插入位置。如果关键块只有一个或两个操作则插入取消。如果关键块包含两个以上的操作,则在每个关键块中第一个(最后一个)操作被插入到关键块内的内部操作中,并且内部操作被移动到关键块的开始或结束。

邻域结构3通过交换操作顺序。基于关键块的任意两个随机选择的操作顺序都会被交换。交换关键路径上的两个操作顺序规则如下:如果关键块只有一个操作则不进行交换,如果关键块有两个操作直接交换顺序,如果关键块包含两个以上的操作则随机选择两个操作进行交换。

3.4 外部精英库保留策略

对于柔性车间调度问题可能存在相同目标值,但不同的机器加工甘特图。为了让调度人员有更多选项,对这些解决方案要进行保存。因此在本研究中,采用外部精英库来保存解决方案,在外部库中根据目标值有序地保存解决方案。在更新过程中首先比较目标值,如果值相等则比较机器字符串,如果两个机器字符串不相同则保存解决方案。

3.5 GAVNS算法流程图

步骤1:输入调度任务参数,使用文献[17]GLR初始化方法;

步骤2:判断当前迭代次数N是否达到终止条件。是则输出最优解;否则继续执行步骤3;

步骤3:计算个体适应度同时执行轮盘赌算子选择优化操作,生成子代种群;

步骤4:根据自适应变异率选取交叉变异个体;

步骤5:对全部个体执行3种邻域结构搜索,对劣势解集进行一定数量替换;

步骤6:选取当代种群中的一定比例较优个体储存,保留精英个体;

步骤7:每代以随机选择的方式生成一定比例的新个体,对当前种群最差的一部分个体进行替代,基本流程如图3所示。

图3 GAVNS算法流程图

4 算例分析

实验算例来自某汽车变速器零部件加工车间,简化为6×6×8的柔性作业调度问题,表2、表3分别为工件工序的可选操作设备以及对应的加工时间。

表2 操作设备表

表3 加工时间表

4.1 参数设置及生成预调度方案

算法具体参数设置如下:整体种群规模100;初始调度迭代次数200;重调度迭代次数50;优解储存库容量20;GLR的比例分别为0.6,0.3,0.1;交叉概率pcmax=0.7;pcmin=0.5;变异概率pmmin=0.05;pmmax=0.1;通过遗传变邻域算法求得初始调度方案。

图4可以得到各道工序对应的机器设备,以及对应的开始、结束时间。在未发生机器故障扰动的情况下,车间生产依照图中调度方案执行,图5为初始调度方案适应度值变化曲线。

图4 预调度方案

图5 加工总耗时寻优曲线

采用熵值法确定3个子评价指标的权重系数。使用熵值判断子目标的离散程度,依据离散程度判断该子目标对总目标的影响程度。确定3个参数分别为μ1=0.21,μ2=0.32,μ3=0.47。针对变速器零部件加工车间故障频率较高的设备7,设置故障参数:故障发生时间(15,30 (h)),故障修复时间分别为(3,6 (h))。在4种故障状态下分别进行10次仿真实验,重调度评价指标数值取平均值。

4.2 试验结果分析

根据图6中预调度方案,加工到30 h时机器7出现故障,工序P63中断,故障修复时间为6 h。对受影响工序执行重调度策略得到如图6所示的最优重调度方案以及图7所示的重调度评价指标收敛曲线。

图6 最优重调度方案

图7 重调度评价指标

重调度方案中部分工序操作机器发生变化,且故障机器恢复后部分工序仍在已修复的故障机器加工。由此可以判断,该故障条件下最优重调度方式为完全重调度。为了验证该结果,对右移重调度和部分重调度得到对应的图8、图9调度方案,图8中右移重调度只针对部分受影响的工序进行右移,右移量不光取决于故障修复所需要的时间,而且还需要参考剩余机器和对应工序间隙时间。

图8 右移重调度方案

图9 部分重调度方案

对图8和图9方案进行相应的重调度评价指标计算。右移重调度和部分重调度的评价指标值分别为4.74和4.46,高于完全重调度对应的评价指标值4.37,验证了选择完全重调度方式的合理性。不同故障状态下几种重调度方式评价值如表4所示。

表4 仿真结果对比

从仿真结果中可以看出在不同生产时期、机器故障修复时间不同的情况下,最优重调度方式也在发生改变,且同一种重调度方式不同时期效果差距很大。而在生产初期15 h、机器故障时间长3 h的情况下,右移重调度表现的更为优越,但随着机器故障修复时间的延长,同样的故障时刻机器故障时间长6 h的情况下,完全重调度最优,评价指标提升16.9%。在故障时间节点30 h,修复时间3 h时修复时右移重调度表现远远超过完全重调度;从表4可以看出完全重调度适合前期故障时间较长的情况;右移重调度适合后期故障时间较短的情况;部分重调度更适合处理特定时间点故障发生时间以及故障持续时间未知的情况。因此机器故障下加工车间依靠单一右移重调度方式无法满足车间加工需求。只有结合多种重调度方式建立综合的评价指标在不同时期选择最优的重调度方式,才能降低任意时刻机器故障对生产车间带来的负面影响。

5 结论

本文针对机器故障下的柔性作业车间动态调度问题提出了一种考虑机器故障概率的重调度方法。综合使用3种重调度方式并建立了相应约束条件下的数学模型,设计了重调度方案评价模型用于最优重调度方式的选择。利用机器故障概率明确了混合驱动中周期驱动的区间,设计了3种邻域结构对遗传变邻域算法进行改进,用于调度方案的求解,提高了整体搜索效率。

通过对不同故障情况下的组合仿真实验,对3种重调度方式的评价指标进行对比分析,得到如下结论:不同生产时期机器故障下不同重调度方式表现存在差异,同一种重调度方式在不同时期的表现差距也较大;右移重调度方式在机器故障时间短、加工末期具有优越性,完全重调度在早期,故障修复时间较长表现更好。