衰退流水车间生产与预防性维护调度研究

陈阳 谭园园

摘要：针对实际生产中调度与维修计划相互影响的问题。以衰退流水车间为研究对象，考虑设备的退化和预防性维护限制，决策工件调度计划和设备的预防性维护计划。建立了不确定环境下以最小化最大工件完工时间和最小化平均设备空闲时间为目标的数学模型。基于非支配排序遗传算法（Non-dominated Sorting Genetic Algorithm，NSGA-Ⅱ），为避免算法陷入局部最优前沿，提出了混合多样性解的多目标优化算法。不同规模的算例应用改进算法与原NSGA-Ⅱ算法进行求解，对比结果表明所设计算法在收敛性、多样性方面上表现更好。

关键词：流水车间;设备衰退;预防性维护;多目标优化;NSGA-Ⅱ算法

中图分类号：TP302 文献标识码：A

文章编号：1009-3044（2020）03-0237-03

1 概述

生产与维护调度因其问题的复杂性和目标的冲突性，受到了国内外学者的广泛关注。针对维护不可用期固定的调度问题，Kubzin[1]研究了双机的开放车间调度和流水车间调度，考虑了设备在生产期内存在不可用期的限制，证明了流水车间调度下该问题的NP难性。Wang[2]研究了并行机在确定的周期维护策略下，以最大化按时完工数量为目标，设计了具有向后调整和两阶段前瞻性策略的启发式算法。Hugo[3]将预防性维护作为M台设备无等待流水车间调度的约束，以最小化最大完工时间为优化目标，设计了具有最大维护水平间隔的预防性维护操作以保证调度期内最少维护次数。Ma[4]对单机、并行机、流水车间及作业车间环境下确定不可用期的问题做出了综述。 针对问题实际特点及现有方法的不足，本文考虑设备退化对加工时间的影响，建立了加T时间与工件开.工时间，以最小化最大完工时间和最小化平均设备空闲时间为优化目标，考虑设备的不定期灵活维护，决策工件加工顺序和设备预防性维护计划。

2 问题描述

2.1 流水车间调度问题

调度期内有n个工件，m台设备，每一道生产工序仅有一台设备，每个工件依次在m台设备上加工，工件在每台设备上的加工顺序相同，每个工件在每台设备上只能被加工一次。

2.2 设备故障

设备的失效函数服从威布尔分布，设备的故障率函数λ（t）是关于时间t的增函数，如式（1）所示：式（5）～（6）分别表示最小化完工时间和最小化平均设备空闲时间两个目标约束式（7）～（8）表示设备生产约束;约束式（9）表示机器役龄的累积，在预防性维护之后役龄归零;约束式（10）表示预防性维护策略，式（11） -（13）表示工序与位置一一对应。

4 算法设计

本文基于Deb等[s]提出的NSGA-Ⅱ算法，根据问题模型特点，提出了混合多样性解的保留策略，计算种群中个体与高质量解的最小欧几里得距离，将种群按照最小欧几里得距离由大到小排序，选择排序占前的个体作为多样性解填人筛选集扩大种群搜索范围，避免算法过早地陷入局部最优。本文算法标记为I-NSGA-II。

4.1 编码与解码

本文研究问题涉及工件生产顺序和设备维护两部分，生产部分采用1-n整数编码。维护部分采用矩阵表示预防性维护的位置，n个工件m台设备的流水车间的维护矩阵Dpm表示为：

4.2 交叉、变异算子

对于流水车间问题，顺序交叉（Order Crossover，OX）可以保留工件位置关系，保证生成可行性解，故本文采用顺序交叉方式。以11个工件的交叉为例，如图1。变异算子采用交换变异（Exchange Mutation，EM）在一条染色体上随机选择两个基因位，交换这两个基因位，构成新的染色体。

5 仿真实验

5.1 实验设置

本文采用C++编程实现算法，参照文献[6]，[7]设置参数如下：最大迭代次数为100，交叉概率Pc= 0.9，变异概率Pn=0.1，tr=5，tp0= 15，RL= 0.8，p=2，η=150，pok，i=U（15，29），tp0=15，a0= 0.01。问题规模分别是lOx6、15x8、20xl0、30x15。

为清楚展示本文研究问题，在此给出lOx6算例下本文算法求解的甘特图。图2为lOx6算例调度甘特图。

5.2 实验结果分析

为更直观展示两算法结果的差别，在此做出Pareto前沿图像，图3所示：

观察图3，相同完工时间目标下本文算法所得Pareto解的设备空闲时间更小，相同设备空闲时间目标下本文算法所得Pareto解的完工时间更小。本文算法所得解在两个目标维度上均优于且绝大多数都支配原NSGA-II所得解。改进后算法有效地逼近了Pareto前沿，搜索能力更好，求解效率更高。

6 总结

本文针对流水车间联合生产与维护双目标优化问题，建立了考虑设备退化影响下的预防性维护与生产调度模型，并改进了传统NSGA-II算法，设计了混合多样性解的保留算子，通过实验对比分析，本文所获得的Pareto解在空间散布范围、间距及解的个数上均有改善，同时本文提出的算法可以很好地逼近Pareto前沿，保持解的多样性，是一种有效求解多目标优化问题的方法。

参考文献;

[1] Kubzin M A，Strusevich V A.Planning machine maintenancein two-machine shop scheduling[J]. Operations Research.2006， 54（4）：789-800.

[2] Wang X，Cheng T C E.A heuristic for scheduling jobs on twoidentical parallel machines with a machine availability con-straint[J]. Intemational Journal of Production Economics.2015， 161（3）：74-82.

[3] Hugo H M， Marcelo S N，et al.Integrating preventive mainte-nance activities to the no-wait flow shop scheduling problemwith dependent-sequence setup times and makespanminimization[J]. Computers&Industrial Engineering， 2019， 135（9）：79-104.

[4] Ma Y，Chu C，Zuo C.A survey of scheduling with determinis-tic machine availability constraints[J]. Computers&IndustrialEngineering， 2010， 58（2）：199-211.

[5] Deb K，PratapA，Agarwal S，et al.A fast and elitist multi-ob-jective genetic algorithm： NSGA-II[J]. IEEE Transactions onEvolutionary Computation. 2002， 6（2）：0-197.

[6]周炳海，蔣舒宇，王世进，等.集成生产与预防性维护的流水线车间调度算法[J]大连海事大学学报，2007，33（3）：32-35.

[7]金玉兰，蒋祖华.预防性维修计划和生产调度的多目标优化[J].哈尔滨工程大学学报，2011，32（09）：1205-1209.