预防性维修计划和生产调度的多目标优化

金玉兰，蒋祖华

(1.上海工程技术大学 管理学院，上海200260;2.上海交通大学 机械与动力工程学院，上海200240)

预防性维修计划和生产调度是生产企业所面临的最常见和最重要的问题之一.预防性维修占据了本来用来进行生产活动的时间，同时，如果不进行预防性维修，又有可能在生产过程中发生突发故障，更大程度地影响生产进程.

为合理解决生产调度和预防性维修间的矛盾冲突，许多学者对预防性维修计划和生产调度的联合优化问题进行了研究［1-4］，主要集中在最小化加权总完工时间［1，3］、最小化加权总延迟时间［2］、最小化生产任务的最大完成时间［4］等时间目标的优化上，而对于维修的成本问题没有涉及.有效的预防性维修计划和生产调度计划必须同时考虑到降低维修成本，提高生产效率.

本文对单设备预防性维修和生产调度的多目标优化问题进行了研究，并分别与单目标联合优化的方法［1-3］和独立优化的方法进行了对比.

1 预防性维修计划和生产调度的多目标联合优化模型

1.1 生产调度

假设一个生产系统中的一台设备需要顺序完成n个作业，pj为作业j的加工时间，dj为作业j的预定完成时间，wj为作业 j的重要性，j=1，2，…，n.生产调度计划的目的是对n个作业进行合理的作业排序.令［1-2］

设 p［i］为作业序列中第 i个作业所用时间，d［i］为作业序列中第i个作业的预定完成，w［i］为作业序列中第i个作业的重要性，C［i］为作业序列中第i个作业的实际完成时间，T［i］为作业序列中第i个作业的延迟时间，i=1，2，…，n.若忽略设备的失效状况，则［1-3］

对生产调度计划的制定，经常考虑到以下一些面向时间的目标，如:全部生产任务的最大完成时间(makespan)，加权总完工时间(total weighted completion times，TWC)，加权总延迟时间(total weighted tardiness，TWT)等.其中［3］:

1.2 维修计划

设备可靠性状况、预防性维修策略、预防性维修处理时间、突发故障处理时间、突发故障次数等因素都会影响到生产任务中各个作业的最终完成时间［1］.因此，在生产调度时要同时考虑维修策略.同文献［1-3］，将预防性维修计划安排在作业序列中每个作业开始之前.假设预防性维修使设备的状态修复到全新.生产过程中的突发故障用小修处理.设R0为加工整个作业序列前的设备初始可靠度，tp为预防性维修平均所需时间，tr为突发故障平均处理时间，cp为进行一次预防性维修的平均成本，cr为处理一次突发故障的平均成本.

设y［i］为作业序列中第 个作业加工前的预防性维修决策，则［1］

当生产设备的故障服从威布尔分布，形状参数为β(β＞1)，尺寸参数为 η，则设备的可靠度R(t)和故障率λ(t)分别为

设从全新状态始，设备运行时间τ内发生的故障次数为 N(τ)，则

设as［i］为作业序列中进行第i个作业加工前的设备役龄，ae［i］为作业序列中完成第i个作业完成后的设备役龄，则［1］

根据式(10)，当加工整个作业序列前的设备初始可靠度为R0时有

作业序列中第i个作业的完成时间C［i］为

设MC为完成整个作业序列所需的维修成本(maintenance cost)，则

1.3 多目标联合优化模型

为更好地节约维修成本和完成生产任务，设fk(k=1，2，3，4)为需要考虑的目标，则

设 fopt为目标向量函数，fopt=(f1，f2，f3，f4)，则多目标优化模型为

2 多目标遗传算法

多目标优化问题常会存在一个Pareto最优集，集中的每个解都是多目标优化问题的一个非劣解，可为决策者作最终选择所用.与大多数优化算法不同，遗传算法可以提供一个种群的相似解，同时寻找到多个 Pareto优解［5］.

多目标遗传算法是根据支配的概念来运作的［5］.如果说解x1支配x2，则必须满足以下2个条件［5］:1)对于所有的目标x1非劣于x2;2)至少有一个目标x1优于x2.如果以上2个条件不满足，则x1不支配x2.

2.1 编码和初始种群

个体(染色体)采用实值编码法.对于种群中的每个个体先随机产生一个预防性维修序列，再产生一个随机的作业序列.如个体{01104321}表示预防性维修序列为0-1-1-0，作业序列为4-3-2-1.随机产生多目标遗传算法的初始种群，种群的大小为Npop，Npop设定要适中，太小会使收敛速度变慢，太大则会增加搜索的难点，降低搜索效率.

2.2 精英策略

在多目标优化中，存在一组非被支配个体的集合 Eg(g=1，2，…，Gen，Gen 为算法的代数).在进行遗传算法时，从Eg找出不同于Ei(i=1，2，…，g-1)中的非被支配个体，组成新集合Eg'.将Eg'中的个体保存在精英集中.从这个精英集中随机选择Nelite组个体作为遗传算法中的精英［5］.

2.2.1 评价

对种群中的每个个体，按照1.1节和1.2节分别计算出各个目标函数.将种群中的个体按照是否支配其他个体进行分类，并将非被支配的个体保存在集合 Eg(g=1，2，…，Gen)中.

2.2.2 分类

下列过程可以找出种群中的非被支配个体［5］.

1)从i=1开始.

2)从 j=1，2，…，Npop，如果 i≠j，则根据支配的概念来判断个体xi和个体xj之间的支配关系.

3)如果对于任意的j(i≠j)，xj都支配，xi则表示xi是被支配的.

4)如果种群中的所有个体都考虑了，转步骤4);否则，转步骤2).

5)除被支配的个体外，种群中的其他个体都是非被支配个体.

2.3 选择

本文采用随机加权法［5］将多目标转化成单目标，从而计算个体的适应度.对目标 fk(k=1，2，3，4)线性正规化处理，设fmaxk和fmink分别为种群中目标fk的最大值和最小值，线性正规化后目标值vk(fk)为［6］

在选择一组个体作为父代产生新个体时，用以下方法为各目标产生一个随机权重:

式中:randomk(·)为任意非负随机数，且randomk(·)∈［0，1］.由式(24)、(25)得随机加权适应度函数为

2.4 交叉

本文采用单点交叉，交叉点范围为［1，2n-1］，n为作业序列中作业的个数，在交叉点之后的父个体的变量相互交换.当交叉点为［1，n］时，即交叉点在预防性维修序列中，则直接进行交换.当交叉点为［n+1，2n-1］时，即交叉点在作业序列中，则从交叉点之后父个体Parent1的作业序列为父个体Parent2中除去Parent1交叉点前作业后的作业序列［3］.

2.5 变异

本文采用单点变异，变异点的范围为［1，2n］，n为作业序列中作业的个数.当变异点为［1，n］时，即变异点处于预防性维修序列中，将变异点值进行0和1之间的转换.当变异点为［n+1，2n］时，即变异点处于作业序列中，将变异点处的作业转移到作业序列的最后一个进行加工［3］.

2.6 多目标遗传算法流程

1)根据2.1节产生初始种群Npop.

2)根据2.2节找出种群中的非支配个体集Eg和Eg'，并将Eg'保存在精英集中.判断是否满足优化准则，如果满足，转步骤7)，否则，转步骤3).

3)从精英集中随机选择Nelite组个体作为父个体.其余(Npop-Nelite)组父个体从种群中选出.根据2.3节计算种群中各个体的随机加权适应度函数，然后用轮盘赌的方法选出(Npop-Nelite)组父个体.

4)将Npop组父个体重新随机组对.根据交叉概率pc和2.4节的交叉方法，生成一组新个体.

5)根据变异概率pm和2.5节的变异方法对新的个体进行变异操作.

6)对每组新个体根据2.2.1 节和2.2.2 节进行评价分类，并找出一个较优的个体作为新个体.如果没有较优的个体，则随机选择一个作为新个体.Npop个新个体组成新的种群.转步骤2).

7)根据2.2节的方法，从精英集中找出非被支配的个体作为Pareto最优集.

8)决策者根据偏好从Pareto最优集中选出满意解.

3 算例分析

3.1 算例及结果

假设设备的初始可靠度R0=0.8;故障服从威布尔分布，形状参数β=1.8，尺寸参数η=100;预防性维修处理时间tp=5，小修处理时间tr=15;预防性维修成本cp=500，小修的成本cr=300.有4个作业需要进行加工，其参数见表1.

表1 生产调度参数示例Table 1 Factors of production scheduling in the example

将以上参数代入优化模型，在Visual Basic 6.0中编程实现多目标遗传算法.当遗传代数Gen=30，种群大小 Npop=30，交叉概率 pc=0.8，变异概率pm=0.7，Nelite=3 时，所得优化结果见表2.

一般情况下预防性维修次数越多，则突发故障的产生次数越少.由表2可知，对于特定的生产要求(如表1所示)由于cp＞cr所以维修成本(MC)还是随维修次数的增多而升高.由表2可知，加权总完工时间(TWC)和加权总延迟时间(TWT)则同时受作业序列和预防性维修序列的影响.当预防性维修次数相同时，对于相同的作业序列，TWC和TWT随预防性维修序列的变化而小幅变化;对于相同的预防性维修序列，TWC和TWT随作业序列的变化而发生较大幅度的变化.makespan主要受预防性维修序列的影响，作业序列对makespan的相对较小.

由表2可知，多目标联合预防性维修计划和生产调度计划所得的 makespan的最小值为190.2，TWC 的最小值为105.1，TWT 的最小值为 10.7，MC的最小值为1 020.0.但没有一组预防性维修计划和生产调度计划使得4个目标同时最优，因此决策者可根据偏好信息决策出的满意解.

表2 多目标遗传算法的优化结果Table 2 Multi-objective genetic algorithms simulation results

3.2 方法对比

将本文所提的预防性维修计划和生产调度多目标联合优化方法分别跟单目标联合优化方法和独立优化方法进行比较.

1)单目标联合优化方法.若应用文献［1-2］的方法，将本文所示范例进行预防性维修计划和生产调度计划的单目标联合优化.当优化目标分别为makespan和MC时，经枚举所得的优化计划结果不唯一，makespan和 MC的最小值分别为190.2和1 020.0.当优化目标分别为TWC和TWT，所得最优结果相同且唯一，预防性维修序列为0-1-1-0而生产作业序列为1-2-4-3，TWC和TWT分别为最小值105.1和10.7，此时makespan和MC分别为191.6 和 1 411.4.

对比表2可知，本文的多目标联合优化的Pareto最优集中包含了预防性维修计划和生产调度计划的单目标联合优化的优化结果.当决策者要考虑多个优化目标时，单目标联合优化的效率显然较差.

2)独立优化方法.将预防性维修计划和生产调度计划分别进行独立优化.预防性维修计划采用使设备可用度达到最优的基于寿命的维修策略［1］，而生产调度计划采用多目标(makespan，TWC，TWT)优化.由文献［1］可知，当 β =1.8，η =100，tp=5，tr=15时，设备从全新状态开始，经过61.5单位时间后进行预防性维修，R(61.5)=0.66，即当设备可靠度降到0.66时，进行预防性维修.对生产调度计划单独进行多目标优化的结果为:1-2-3-4、1-2-4-3、1-3-2-4.将2种优化计划组合起来，计算makespan、TWC、TWT和 MC 见表3.由表 3 可见，最优结果为预防性维修开始时间序列为18-79.5-141且作业序列为1-2-4-3.

表3 预防性维修计划和生产调度计划的独立优化结果Table 3 Calculated results of separately optimizing PM planning and production scheduling in the example

对比表2可知，本文的多目标联合优化的Pareto最优集包含了预防性维修计划和生产调度计划独立优化的结果.对于表3中的任意计划，都能从本文的多目标联合优化的Pareto最优集中找出比其更优的计划.因此，本文的联合方法要优于独立优化方法.

4 结束语

本文提出了单设备预防性维修计划和生产调度的多目标优化模型.通过实例可知，一般情况下预防性维修次数越多，则突发故障的产生次数越少.在预防性维修成本高于小修成本的情况下，MC主要随预防性维修次数的增多而升高.TWC和TWT则同时受作业序列和预防性维修序列的影响.Makespan主要受预防性维修序列的影响.

本文未对决策者如何从多目标联合优化的Pareto最优集中选出满意解作阐述，当最优集规模较大时，这一问题值得探讨.对于多台设备、多种预防性维修方式或flowshop生产计划问题等，还需要对预防性维修计划和生产调度的多目标优化方法进行更深入的研究.

［1］CASSADY C R，KUTANOGLU E.Integrating preventive maintenance planning and production scheduling for a single machine［J］.IEEE Transactions on Reliability，2005，54(2):304-309.

［2］应保胜，但斌斌，张华.生产计划和预防性维修计划的统筹优化模型［J］.机械工程学报，2005，41(3):226-228.YING Baosheng，DAN Binbin，ZHANG Hua.Optimization model by integrating preventive maintenance planning and production scheduling［J］.Chinese Journal of Mechanical Engineering，2005，41(3):226-228.

［3］SORTRAKUL N，NACHTMANN H L，CASSADY C R.Genetic algorithms for integrated preventive maintenance planning and production scheduling for a single machine［J］.Computers in Industry，2005，56(2):161-168.

［4］RUIZ R，CARLOS G J，MAROTO C.Considering scheduling and preventive maintenance in the flowshop sequencing problem［J］.Computers＆ Operations Research，2007，34(11):3314-3330.

［5］OSMAN M S，ABO-SINNA M A，MOUSA A A.An effective genetic algorithm approach to multiobjective routing problems(MORPs) ［J］.Applied Mathematics and Computation，2005，163(2):769-781.

［6］王小平，曹立明.遗传算法——理论、应用与软件实现［M］.西安:西安交通大学出版社，2002:115-122.WANG Xiaoping，CAO Liming.GA—theory，application and software［M］.Xi＇an:Xi＇An Jiao Tong University Press，2002:115-122.