生产调度和模具预防性维护集成优化研究*

沈 露, 杨宏兵,2, 高 胜

(1.苏州大学 机电工程学院，江苏 苏州 215006；2.广东工业大学 广东省计算机集成制造重点实验室，广州 510006)

0 引言

传统的生产调度研究通常不考虑机器模具等资源的故障和维护活动引起的不可用时间问题，在实际运行中，故障随时可能中断产品的加工，严重地影响企业生产计划的执行，预防性维护活动可以有效地控制资源不可用因素对企业生产进程的影响，是生产调度领域的研究热点。

文献[1]对考虑预防性维护的单机系统进行研究，应用启发式和分支定界法来最小化总完工时间，该问题已被证明为NP难问题。文献[2]提出在并行机调度问题中，研究基于固定维护时长的周期性维护和集成维护两种策略对模型的影响。文献[3-4]在注塑作业车间集成生产调度和基于线性维护时长的预防性维护活动以期优化最大完工时间。文献[5]针对柔性作业车间，以最小完工时间为目标研究了考虑不等周期的预防性维护活动的调度问题。

此外，不少学者聚焦于同时考虑生产排序和资源维护的多目标优化问题，文献[6]将维护成本，最大完工时间，加权完工时间，提前/拖期惩罚，和机器可得性同时作为目标，利用多目标遗传算法求解。文献[7]研究并行机问题中的生产和维护活动，比较两种遗传算法NSGA-II 和WSGA来同时优化最大完工时间和系统可用性。文献[8]进一步研究文献[7]提出的问题，设计一种多目标蚁群算法来同时优化提前/拖期惩罚和系统不可得性。文献[9]在单机系统调度中集成预防性维护活动，设计改进的多目标遗传算法进而寻求生产和维护活动之间的平衡。文献[10]设计一种有效的DCRO算法来优化带维护约束的多目标柔性作业车间调度问题，之后，文献[11]中进一步提出DABC算法求解该问题。从现有的研究文献不难看出，以NSGA-II算法为代表的多目标遗传算法被广泛应用于调度与预防性维护多目标集成优化研究中，并取得了一定的研究成果。本文提出一种改进的双种群差分进化算法 (ADPDE) 对多目标集成优化模型进行求解，并在算法的优劣性上与NSGA-II算法进行分析和比较。此外，生产调度的相关研究通常假设生产过程中模具持续可用，不考虑实际生产中模具基于使用时间和役龄的堕化。在现有为数不多的调度与模具预防性维护集成优化研究中也没有同时考虑产品交货期和设备利用率，而交货期满意度和设备利用率等是制造企业普遍关注的性能指标，作为注塑、冲压等车间批量生产活动的关键资源，不同产品类型批量之间的模具切换以及维护部门的模具维护计划加大了生产调度活动的复杂性，其对生产时间的占用，也是影响企业交货期的重要因素。本文集成考虑带堕化效应的模具的预防性维护计划以期同时优化企业的交货期和模具利用率，平衡生产和维护部门的冲突。为求解受模具维护约束的集成调度模型，本文提出基于区分可行解和不可行解的双种群差分进化算法对模型进行求解。

1 双目标集成调度模型

本文基于文献[12]的集成调度模型以批量Flow Shop为研究对象，调度期内有N种产品顺序在M台机器上进行加工，每种产品j按固定等批量划分批次，假设模具的维护时间与模具的当前役龄amjk相关，如图1所示，模具必须在役龄到达阈值MA之前执行维护活动。

图1 基于役龄的线性维护时长

从生产实际的角度，同时以企业普遍关注的交货期满意度和设备利用率为目标建立集成优化模型，最小化提前/拖后惩罚和最大化模具利用率，定义如下：

(1)

(2)

其中Dj，Tj，αj，βj，Ij分别为产品j的交货期，完工时间，提前惩罚系数，拖期惩罚系数和模具维护次数。

2 改进双种群差分进化算法

标准差分进化算法[13]操作简单，且具有良好的一致性和优化性能，在约束优化问题中应用较多。

2.1 差分进化算法

差分进化算法和其他进化算法相似有变异，交叉和选择三个操作，交叉变异产生新的试验个体，选择算子决定进入下一代的个体选择。差分进化算法[14]对包含Np个个体Xi(t),i=1,2,…,Np的种群进行随机搜索求解，其中Np表示种群规模，t表示种群的迭代次数。

标准差分进化算法是在父代个体之间差分矢量的基础上进行变异操作的，由父代两个不同随机个体相减得到的差分矢量加到随机选择的第三个个体上, 生成一变异个体。该过程即为变异，如公式(3)所示：

Vi(t)=Xi1(t)+F(Xi2(t)-Xi3(t))

(3)

其中，i=1,2,…,Np，i1,i2,i3为从{1,2,…,Np}随机选择的整数，且i≠i1≠i2≠i3，F表示缩放因子。

执行差分变异操作后，对父代个体，和得到的变异个体进行交叉操作以生成试验个体，如公式(4)所示：

(4)

其中，CR控制交叉率，rand(0,1)是(0,1)间的随机值。

2.2 改进双种群差分进化算法

为了提高标准差分进化算法的求解性能，本文基于双种群差分进化算法[15]中区分可行解和不可行解并分别存储的双种群处理机制，设计了一种改进的双种群差分进化算法，在新的算法中进一步改进了变异交叉机制，同时利用全局最优解参与种群进化加快算法收敛速度，以期提高算法的求解性能。

2.2.1 编码

染色体包括两个部分：第一部分为基于子批量排序的实数编码，第二部分为二进制维护决策变量，0表示当前工序后不进行模具维护，1则表示执行维护。2种工件分别拥有2和3个子批量在3台设备上依次加工，如{2 1 4 5 3 0 0 1 0 0 1 0 1 0 0 1 1 1 1 0}，染色体前部分是总计5个子批量的随机排序{2 1 4 5 3}，每个子批量对应3个模具的维护决策变量因而染色体第二部分{0 0 1 0 0 1 0 2 0 0 1 1 1 1 0}包括5×3个基因序列，表示对第一个子批量只在最后一道工序之后进行模具维护(二进制编码第3位为1前两位为0)，以此类推。

2.2.2 改进的变异操作

在种群进化过程中引入不可行解和全局最优解的参与，以可行解作为目标个体提出改进的双种群差分进化算法，将整个算法过程分为三个阶段，每个阶段均采用差别的变异交叉策略，提高算法的寻优能力。

(1)种群初始化，区分可行解和不可行解后，如果当前可行解集Pf规模小于Nf，应用公式(3)中的标准差分进化算法的变异方法。

(2)可行解集规模到达Nf，且迭代次数t<0.5×T时在可行解集Pf和全局最优解集gbest的并集中随机选择两个可行解，不可行解集Pc中随机选择一个不可行解，应用公式(5)，通过保留部分不可行解参与种群进化来避免算法早熟。

Vi(t)=Xi1(t)+F(gi1(t)-Xi2(t))

(5)

其中，Xi1(t),Xi2(t)∈[Pf;gbest],gi1(t)∈Pc，T为最大迭代次数。

(3)在算法的最后阶段，在Pf和gbest的并集中随机选择两个可行解，gbest中随机选择一个不可行解，应用公式(6)，全局最优解直接参与进化加快算法收敛速度。

Vi(t)=Xi1(t)+F(gi1(t)-Xi2(t))

(6)

其中:Xi1(t),Xi2(t)∈[Pf;gbest],gi1∈gbest。

上述方法均针对生产排序问题，此外，在维护决策中随机选择一点进行单点变异，如果选中的基因值为1，转换为0，反之亦然。

2.2.3 改进的交叉操作

不同于第一阶段采用公式(4)中的标准差分交叉方法，算法的后两阶段，改进双种群差分进化算法在变异个体和不可行解或全局最优解之间直接进行交叉操作，试验个体直接继承变异个体或不可行解与全局最优解的基因，以充分保留不可行解和全局最优解的优良性能如公式(7)：

(7)

染色体第一部分的实数编码在上述变异交叉操作后难以保持整数形式，根据相对位置排序法将对应基因位置的值转换为整数排序。

2.2.4 选择

与采用贪婪策略进行选择的标准差分进化算法相比, 选择操作由于采用了双群体搜索机制而变得更为复杂。通过前述交叉、 变异产生新的个体后, 将采用不同策略来进行选择操作, 以产生新一代的可行种群与不可行种群。方法如下:

(1)可行解集规模与当前生成的可行解个数之和不足Nf时，直接将可行解插入可行解集Pf；否则基于优化目标对两者的并集进行非支配排序，选择前Nf个个体更新可行解集。

(2)不可行解集规模与当前生成的不可行解个数之和不足Nc时，直接将不可行解插入不可行解集Pc；否则基于约束违反程度[16]对两者的并集进行非支配排序，选择前Nc个个体更新可行解集。

2.3 算法流程

改进双种群差分进化算法的步骤如下：

步骤1： 设置初始种群规模Np，可行解集Pf规模Nf，不可行解集Pc规模Nc，变异因子F，交叉因子CR，最大迭代次数T等参数，种群初始化。

步骤2： 计算个体的目标值及约束违反程度，将可行解与不可行解插入相应种群，初始化全局最优解gbest。

步骤3：进行标准差分进化变异交叉如公式(3)、公式(4)，更新Pf，Pc，gbest。

步骤4：如果t<0.5×T，执行公式(5)、公式(7)的变异交叉操作，更新Pf，Pc，gbest。

步骤5：如果0.5×T≤t

步骤6：终止条件t=T满足时，输出最优解gbest。

算法流程如图2所示。

图2 ADPDE算法流程图

3 算例分析

在工程约束优化问题中，通常构造罚函数应用遗传算法进行求解，改进双种群差分进化算法通过分别保存可行解集和不可行解集利用不可行解参与进化来避免罚函数的构造。为证明算法的有效性，现将改进的双种群差分进化算法与NSGA-II算法在内存2G，主频2.4GHz的Intel Core i3的Win7系统中通过MATLAB 7.8.0 (R2009a)平台进行比较，在6个假设性的问题中，可归类为三类问题(3×5, 4×5, 5×5)，每类问题包含2种子批量规模，种群规模设定为100，NAGA-II 的变异因子为0.9，交叉因子为0.1，ADPDE的变异交叉因子分别为0.7和0.9，终止条件设定为种群进化代数满1000，每种算法在每个问题中运行20次。

Zitzler[17]等提出的C矩阵是多目标优化问题中评价Pareto曲线优劣的著名指标，C(A,B)的值表示前沿B中被前沿A的至少一个个体支配的个体占总体的比例。

(8)

C(A,B)=1表示中所有解都至少被中的一个解支配；相反地，C(A,B)=0表示B中没有解被A中的任一解支配。因此，C(A,B)越接近0，表示Pareto前沿B相对于A来说越好。

对每个问题两种算法均运行20次对比结果，表1总结了两种算法20次运行所得最优解集的最大，最小和平均解个数，从表格中可以发现最大，最小，平均值方面ADPDE均优于NSGA-II；表格2总结了两种算法20次运行所得C值的最大，最小和平均值，从表格中可以发现最大，最小，平均值方面ADPDE均优于NSGA-II，ADPDE求解的Pareto前沿明显优于NSGA-II。上述分析结果表明ADPDE求解本文提出的约束优化问题时，在不同的问题规模下求得的最优解的个数和质量均优于NSGA-II算法。

表1 两种算法运行20次所求非支配解个数的最大值，平均值和最小值

表2 两种算法运行20次所求非支配解集覆盖率的最大值，平均值和最小值

(a) 问题 1

(b) 问题 2

(c) 问题3

(d) 问题4

(e) 问题5

(f) 问题6图3 ADPDE和NSGA-II运行20次后返回的非支配解集

在表格3中，比较两种算法的运行时间，鉴于差分进化算法操作简单，改进的交叉策略的进一步优化，ADPDE的运行速度明显优于NSGA-II，问题的规模越大，变量越多，ADPDE的优越性越凸显。

表3 比较ADPDE和NSGA-II的运行时间(s)

4 结束语

本文提出Flow Shop生产调度与模具预防性维护的集成优化问题，同时考虑提前/拖后完工时间和模具利用率双目标来平衡两者间的矛盾，基于不可行解的优良特性设计改进的双种群差分进化算法求解该约束优化问题。比较ADPDE与NSGA-II的实验数据结果，不仅ADPDE所获得的C值最大，最小，平均值均优于NSGA-II算法，ADPDE算法的Pareto前沿相比较NSGA-II算法也更靠近Pareto最优前沿，ADPDE算法所得到的解明显优于NSGA-II算法，在保证解的优越性的同时有效提高了算法的运行速度。验证了本文提出的改进的双种群差分进化算法求解所建模型的有效性。

完善集成优化模型的实际生产因素如其他资源的维护活动，同时考虑批量分割问题将是下一步的研究方向，以进一步提高生产效率和最大程度满足交期的要求。

[1] X Qi, T Chen, F Tu. Scheduling the maintenance on single machine[J]. Journal of the Operational Research Society, 1999, 50(10):1071-1078.

[2] K Sun, H Li. Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines[J]. International Journal of Production Economics, 2010, 124 (1):151-158.

[3] C S Wong, F T S Chan, S H Chung. A genetic algorithm approach for production scheduling with mould maintenance consideration[J]. International Journal of Production Research, 2012, 2011(20):5683-5697.

[4] C S Wong, F T S Chan, S H Chung. A joint production scheduling approach considering multiple resources and preventive maintenance tasks[J]. International Journal of Production Research, 2013, 51(3):1-14.

[5] 查靓, 金花, 潘志成, 等.基于顺序相关调整时间的FJSP与设备维护计划集成优化[J]. 组合机床与自动化加工技术, 2016(5):155-160.

[6] Y Jin, Z Jiang, W Hou. Multi-objective integrated optimization research on preventive maintenance planning and production scheduling for a single machine[J]. International Journal of Advanced Manufacturing Technology, 2008, 39(9):954-964.

[7] Berrichi A, Amodeo L, Yalaoui F, et al. Bi-objective optimization algorithms for joint production and maintenance scheduling: application to the parallel machine problem[J]. Journal of Intelligent Manufacturing, 2009, 20(4): 389.

[8] Berrichi A, Yalaoui F. Efficient bi-objective ant colony approach to minimize total tardiness and system unavailability for a parallel machine scheduling problem[J]. International Journal of Advanced Manufacturing Technology, 2013, 68(9): 2295-2310.

[9] 崔维伟, 陆志强, 潘尔顺. 基于多目标优化的生产调度与设备维护集成研究[J].计算机集成制造系统, 2014, 20(6):1398-1404.

[10] JQ Li, QK Pan. Chemical-reaction optimization for flexible job-shop scheduling problems with maintenance activity[J]. Applied Soft Computing, 2012, 12(9): 2896-2912.

[11] JQ Li, QK Pan, MF Tasgetiren. A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities[J]. Applied Mathematical Modelling, 2014, 38(3):1111-1132.

[12] Lu Shen, Hongbing Yang, Sheng Gao, et al. Production Scheduling with Mould Maintenance in Flow Shop [C]. Proceedings of the 2016 4thInternational Conference on Sensors, Mechatronics and Automation, 2016, (136):730-733.

[13] E Mezura-Montes, CAC Coello. Constraint handling in nature-inspired numerical optimization: past, present and future[J]. Swarm and Evolutionary Computation, 2011, 1(4): 173-194.

[14] S Das, PN Suganthan. Differential evolution: A survey of the state-of-the-art[J]. IEEE Trans on Evolutionary Computation 2011,15(1): 4-31.

[15] 孟红云, 张小华, 刘三阳. 用于约束多目标优化问题的双种群差分进化算法[J].计算机学报, 2008, 31(2):228-235.

[16] K Deb. An efficient constraint handling method for genetic algorithms[J]. Computer Methods in Applied Mechanics & Engineering, 2000, 186(2-4): 311-338.

[17] E Zitzler, L Thiele. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4): 257-271.

[18] C GarcíaMartínez, O Cordón, F Herrera. An Empirical Analysis of Multiple Objective Ant Colony Optimization Algorithms for the Bi-criteria TSP[J]. European Journal of Operational Research, 2007, 180(1): 116-148.

[19] E Zitzler, K Deb, L Thiele. Comparison of multiobjective evolutionary algorithms: empirical results[J]. Evolutionary Computation, 2000, 8(2): 173.