考虑备料计划的柔性作业车间动态调度*

周鑫文,陈 豪,张剑铭,刘 文

(1.福州大学先进制造学院,晋江 362251;2.中国科学院海西研究院泉州装备制造研究中心,泉州 362000)

0 引言

近年来,柔性作业车间调度问题(flexible job-shop scheduling problem,FJSP)已成为制造业企业主要面临的问题之一。在实际的生产过程中,经常发生诸如机器故障[1]、订单加急[2]等动态事件,使生产环境越加复杂,因此延伸出动态柔性作业车间调度问题(dynamic flexible job-shop scheduling problem,DFJSP)。受动态事件影响,未加工工序需要调整加工设备,进一步造成相应的原料需求变更,而过度的备料计划调整会进一步降低生产效率[3]。因此,引起许多研究学者在物料准备方面做研究,CHAKRABORTTY等[4]考虑资源中断的因素,提出了多种的启发式算法来求解建立的混合整数规划模型。刁林倩[5]在机器故障下考虑物料搬运问题,设计改进的文化基因算法解决调度问题。涂海宁等[6]提出一种改进的蚁群算法解决生产车间中物料配送不及时、效率低等问题。

为解决动态柔性作业车间调度问题,国内外的许多研究学者提出了多种解决方法。AHMADI等[7]采用基于NSGA-Ⅱ的右移重调度与完全重调度,但只考虑了对最大完成时间与稳定性的优化。朱传军等[8]建立了基于调度稳健性的动态调度模型,并提出差分变频邻域算法,虽然提高了鲁棒性与稳定性,但实时性差。ZHANG等[9]提出一种基于动态博弈的双层调度方法,采用逆向推导法求解子博弈精炼纳什均衡,能够实时解决多种动态问题,却缺乏考虑鲁棒性与稳定性。卫少鹏等[10]针对质检扰动问题,采用改进的头脑风暴算法求解,却没有考虑调度方案的实时性。因此,HE等[11]采用路线更改与右移重调度方式实现机器故障下的实时动态调度,提高了调度方案的稳定性与鲁棒性。尤一琛等[12]将动态调度问题看作完全信息下的动态博弈,提出一种混合纳什均衡策略有效平衡鲁棒性与稳定性,并具有较好的实时性。

综上所述,为兼顾动态调度方案的实时性、鲁棒性和稳定性,针对备料计划调整问题,以最小化最大完成时间为预调度目标,当机器故障时快速建立带有备料计划关联调整的柔性作业车间动态调度模型,提出改进的受影响工序选择方法,并设计多阶段的合作博弈策略,用于快速寻找最优的动态调度方案。

1 问题描述

考虑备料计划关联调整的DFJSP依然采用同FJSP一致的描述:车间共有m台{M1,M2,…,Mm}机器用于工作,包含n个待加工工件{J1,J2,…,Jn},每个工件有j道工序,每道工序可以在不同机器上加工,加工时间根据机器的性能决定。引入机器故障作为动态扰动因素,在工件生产过程的随机时刻机器发生故障,且恢复时间可预测,此时车间动态调度任务为:在机器故障下进行合理的动态调度,以满足动态调度目标。

针对DFJSP,进行如下规范化约束:

(1)初始零时刻所有工件皆可进行加工;

(2)每台机器同一时刻只能加工一个工件;

(3)每个工件的加工都按照严格的加工工艺次序,不能抢断;

(4)每个工件的工序同一时刻只能在一个机器上加工;

(5)不同工件优先级相同;

(6)不同工件的各工序之间没有先后次序之分;

(7)工件一旦开始在机器上加工,便不能中断;

(8)故障机器上的在生产工件立刻停止加工,且不可转移,等待故障修复成功后继续加工;

(9)除故障机器外,其余机器上正在加工的工件仍在原分配的机器上进行加工,直至完成。

对DFJSP变量及含义设置如表1所示。

表1 DFJSP变量及含义设置表

柔性作业车间的预调度目标为最小化最大完成时间,指所有工件加工完成的时间最小:

(1)

预调度方案采用IPSO算法[13]获得,这里不再复述,仅引入余弦自适应调整因子来提升pf在迭代前期的全局搜索能力,增强后期的收敛能力,pf为IPSO算法中的自适应调整概率,用于优化机器选择部分,其表达式为:

(2)

式中:Iter为总迭代次数,k为当前迭代次数,pfmin与pfmax分别为自适应调整概率的最小值与最大值。

对于动态事件处理,研究机器故障下的DFJSP,考虑到备料计划调整将会大幅度恶化生产计划的进展,故将备料计划调整次数定义为稳定性f3,而鲁棒性作为衡量预调度受影响后的性能指标,这里指最大完成时间偏差f2。

(3)

(4)

(5)

根据动态调度特性,通过采用加权和的方式可以兼顾鲁棒性与稳定性,生成式(6)评价指标Y:

Y=r1f2+r2f3

(6)

式中:r1、r2分别为鲁棒性与稳定性的惩罚因子,r1+r2=1,且0

2 柔性作业车间动态调度方法

2.1 改进的受影响工序选择方法

当机器发生故障时,传统的路线更改方式挑选的受影响工序为在故障时间范围内覆盖的工序,虽然避免了本机器后续工序的调整,保证了一定的稳定性,但往往不能很好的兼顾鲁棒性。因此为兼顾鲁棒性与稳定性,提出一种改进的受影响工序选择方法(an improved method of selection of the affected process,IMSAP),对影响弱的工序,可将其直接影响转移到该机器上的后续的工序中,该方法的步骤如下:

步骤1:工序后移。故障机器上的后续工序后移:

(7)

(8)

(9)

式中:tcko、tck(o+1)分别为预调度中在机器k上正在加工的与后一个工序的结束时间,tsk(o+1)为预调度中机器k上安排的下一个工序的开始时间,PTko为对应工序在机器k上的加工时长,Tbk为机器故障预计恢复时间,t′为故障发生后工序后移的状态。

步骤2:工序分类。步骤1结束后,将故障后续工序分为3类:受影响弱、受影响强、可调节,分别对应等级1、2、3。

①受影响弱的工序指,工序后移并不直接造成下一道工序的开始时间延后:

(10)

②受影响强的工序指,工序后移直接造成下一道工序的开始时间延后:

(11)

③可调节的工序指,工序为最后一道工序或右移重调度后的关键路径上的工序:

O={Oij|j=hi∪Oij⊆Ocpfr}

(12)

步骤3:工序挑选。采用窗户位置更新的方式挑选工序。只有受影响弱的工序才能逃脱挑选,否则表示消除故障影响的有效工序。预调度工件工序的STijk在窗户位置thk内,如果至少存在一个受影响弱的工序则不可选中该类工序,选择其它类别的工序,然后将窗户位置更新再进行下一个工序判断,否则可选中。当thk内不再含有受影响弱的工序,则结束窗户位置更新,仅需要判断后续工序是否属于可调节工序,如果是则选中,否则不选中,直至后续工序遍历结束。具体窗户位置更新方式如下:

①故障发生出现在这两种情况:空转机器与在生产工序机器,那么初始的窗户位置t0k:

(13)

②第h次的窗户经过更新后的位置thk:

(14)

(15)

式中:「thk⎤表示thk的上界,υ表示窗户包含的最后一个工序的序号。

例如1个3×3算例,假设工序O21在tbk为8 min时机器M1出现故障,故障修复时间预计为7 min,采用上述提出的影响转移方法,最终选中的工序为O32、O13。具体的演示如图1～图3和表2、表3所示。

图1 预调度 图2 工序后移

图3 右移重调度关键路径

表2 采用窗户位置更新方式选中工序

表3 待窗户位置更新结束后选中工序

2.2 基于多阶段的合作博弈策略

机器故障会直接导致后续工序的开始时间延迟,由于工序加工与机器分配存在一定的约束关系,因此可以将重调度问题看成在完全信息下的动态博弈问题[12]。将动态博弈问题分为多阶段的静态合作博弈问题,并在此基础上设计基于多阶段的合作博弈策略(multi-stage cooperative game strategy,MCGS)。

在生产过程中,当机器发生故障时,通过采用IMSAP可以获得被挑选的工序集Ou。在动态调度中进行分阶段的调度,在每一个阶段,从Ou中随机选取g(g≥2)道工序作为待加工工序,并放入待调度任务池(task pool,TP)中,再对TP中的工序进行重调度,见图4。每一个阶段中至少存在一个待加工的工序需要进行排序,将TP中的工序作为博弈玩家集Pt,可用机器集作为决策池St,玩家进行策略选择后的所有效用集记为Ut,因此构建基于多阶段的柔性作业车间动态调度模型:

图4 分阶段选取工序

Gt={Pt;St;Ut}t=1,2,…,L

(16)

式中:L为博弈阶段次数。

在每一阶段的合作博弈中,各个博弈玩家之间相互协调以达到全体效果的最优值:

(17)

引入条件筛选转移工序的可用机器集,获取St:

(18)

式中:k为预调度中工序Oij的机器,k*为该阶段选取的机器。对每个阶段的工序只有满足式(18)的情况下才有可转移的机器集St。

在t阶段,从TP中取出待加工的工序,然后从St选取可转移机器,对所有可能组合选择最优min(Y),当出现多个最优组合时,选择最小σ2的组合,σ2的计算方式如下:

(19)

(20)

对每一阶段选择最优决策后,将决策结果作为下一阶段的初始基础,并指导下一次博弈。在最后一次合作博弈中,不考虑σ2,直接选取最优值即可。

2.3 IMSAP-MCGS重调度流程

IMSAP-MCGS重调度流程如图5所示,步骤如下:

图5 重调度流程图

步骤1:读取故障机器信息;

步骤2:通过故障机器信息,采用IMSAP获得待调整工序集Ou;

步骤3:将Ou分阶段从中随机选取g个工序给TP;

步骤4:判断第t阶段TP中是否仅剩一个工序,如果是则跳跃到步骤7,否则进入下一个步骤;

步骤5:将每个工序作为玩家,在决策池中选取机器,采用MCGS求解最优组合;

步骤6:判断所有工序是否都被选择,是则跳跃到步骤8,否则t=t+1,回到步骤4;

步骤7:采用枚举法选择最优机器;

步骤8:输出最终多阶段合作博弈最优解。

3 实验结果与分析

本文仿真实验的硬件环境处理器为Intel(R) Core(TM) i7-11700 CPU @ 2.50 GHz,RAM 32 GB;使用Windows 11操作系统,运行平台为PyCharm。

3.1 实验设置与内容

在整个调度策略中设置参数如下:IPSO算法[13]群体规模为100,迭代次数为100,ω为0.15,C1、C2分别为0.5与0.7,最小调整阈值因子pfmin为0.2,最大调整阈值因子pfmax为0.8,惩罚因子r1、r2分别设置为0.6、0.4。

本文首先使用Brandimarte的标准算例MK1,10×6实例进行仿真测试,该算例中含有10个工件,每个工件含有5～6个工序,共有6台机器可供使用。然后对MK1～MK10经典调度案例集进行仿真验证,将IMSAP-MCGS重调度与右移重调度、完全重调度和传统路线更改-MCGS重调度的仿真结果进行了对比分析。

3.2 实验仿真分析

本文采用引入余弦自适应调整因子的IPSO算法[13]得到预调度方案如图6所示,其最大完成时间为42 min。当机器3在时刻为15 min时发生故障,预测机器恢复时间为20 min,分别采用IMSAP-MCGS重调度、右移重调度和完全重调度进行调度,仿真实验得到如图7～图9所示的调度方案及表4对比结果。从中可以看出当机器发生故障时,采用IMSAP-MCGS重调度得到的评价指标Y优于右移重调度与完全重调度,其鲁棒性指标小于完全重调度和右移重调度,降低了机器故障对生产目标的影响,而且运行时间也更快于完全重调度,保证了柔性车间遇到机器故障时能够进行及时有效的反应。在稳定性方面,虽然右移重调度稳定性指标最好,但是鲁棒性差,而IMSAP-MCGS重调度对两者的平衡更好。因此,IMSAP-MCGS重调度能够有效平衡鲁棒性与稳定性,能够及时有效地解决柔性作业车间下因机器故障造成备料计划调整的问题。

图6 预调度甘特图

图7 IMSAP-MCGS重调度甘特图

图8 右移重调度甘特图

图9 完全重调度甘特图

表4 仿真结果对比

表5记录MK1～MK10采用多种重调度方式后的最终结果。从表中可以看出右移重调度的稳定性最好,运行时间也最短,但是鲁棒性却很差。完全重调度的鲁棒性最好,但是稳定性很差、运行时间很长。在案例中,IMSAP-MCGS重调度的评价指标相比于右移重调度、完全重调度和传统路线更改-MCGS重调度会更有优势,而且IMSAP-MCGS重调度的稳定性指标2[14]也同样更有优势,同时运行时间远远小于完全重调度。综上所述,本文提出的IMSAP-MCGS重调度在针对备料计划调整问题下拥有更好的性能,在机器故障发生时不仅能够及时有效地处理动态事件,还能合理减轻备料计划调整压力,具有较好的鲁棒性与稳定性。

表5 仿真结果对比

4 结论

本文研究在机器故障下,针对生产车间备料计划调整问题,提出一种改进的受影响工序选择方法,并设计多阶段的合作博弈调度策略。首先,采用引入余弦自适应调整因子的IPSO算法产生预调度方案;其次,利用机器故障信息采用改进的受影响工序选择方法获得工序集;然后,设计多阶段的合作博弈策略,在每一个阶段通过合作博弈的方式选取阶段性的最优策略,最终得到动态调度方案;最后,通过实验结果对比分析,验证了针对机器故障下的备料计划调整问题,IMSAP-MCGS重调度不仅具有较好的鲁棒性和稳定性,而且对机器故障的处理具有实时性。

本文仅考虑了机器故障动态事件,对于其他动态事件下的备料计划调整问题还需进一步研究。