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

1、第 32 卷第 9 期哈尔滨工程大学学报Vol 32 92011 年 9 月Journal of Harbin Engineering UniversitySep 2011doi： 10 3969/j issn 1006-7043 2011 09 019预防性维修计划和生产调度的多目标优化金玉兰1， 蒋祖华2（ 1 上海工程技术大学管理学院 ， 上海 200260；2 上海交通大学机械与动力工程学院， 上海 200240）摘要： 为了降低设备故障对生产成本和生产时间的影响， 建立了单台设备预防性维修计划和生产调度的多目标联合优化模型 将维修成本 、 生产任务的最大完成时间、 加权总完工时间及加

2、权总延迟时间作为优化目标 采用了多目标遗传算法， 同时对预防性维修计划和生产调度进行优化 通过实例 ， 将预防性维修计划、 生产调度的多目标联合优化方法分别与单目标联合优化方法、 独立优化方法进行了对比， 结果表明 ， 文中的方法更节约成本和生产时间关键词 ： 预防性维修计划； 生产调度 ； 多目标优化 ； 遗传算法中图分类号 ： TH165 3文献标识码 ： A文章编号 ： 1006-7043（ 2011） 09-1205-05Multi- objective optimizationresearch onpreventive maintenance planning and product

3、ion schedulingJIN Yulan1，JIANG Zuhua2（ 1Schoolof Management ，ShanghaiUniversity of Engineering Science ，Shanghai200260，China；2Schoolof Mechanical Engineer-ing，ShanghaiJiaoTongUniversity，Shanghai200240，China）Abstract ： In order to reduce the effects of machine failures on the manufacturing cost and t

4、ime，a multi- objectiveoptimization model wasproposedto jointly determine preventive maintenanceplanning and production scheduling fora single machine The maintenancecost，makespan ，total weighted completion times，and total weighted tardinesswere simultaneouslyconsidered as objectivesMulti- objective

5、genetic algorithms were developedto solvea joint op-timization model for PM planning and production schedulingComparedwith the method of optimization integratingPM planning and production scheduling and the methodsseparatelyoptimizing PM planning and production schedu-ling in an example，the proposed

6、multi-objective joint optimization method can savemore time at a lower cost Keywords ： preventive maintenance planning；production scheduling；multi- objective optimization；genetic algo-rithms收稿日期 ： 2011-01-19作者简介 ： 金玉 兰 （ 1980-） ， 女，讲 师， 博 士，E-mail：jinyulan12 ya-hoo cn ；蒋祖华 （ 1966-） ， 男， 教授 ， 博士生导师，

7、E-mail：zhjiang sj-tu edu cn通信作者 ： 金玉兰 预防性维修计划和生产调度是生产企业所面临的最常见和最重要的问题之一 预防性维修占据了本来用来进行生产活动的时间， 同时 ， 如果不进行预防性维修 ， 又有可能在生产过程中发生突发故障， 更大程度地影响生产进程为合理解决生产调度和预防性维修间的矛盾冲突， 许多学者对预防性维修计划和生产调度的联合优化问题进行了研究1-4 ， 主要集中在最小化加权总完工时间1， 3 、 最小化加权总延迟时间2 、 最小化生产任务的最大完成时间4等时间目标的优化上，而对于维修的成本问题没有涉及 有效的预防性维修计划和生产调度计划必须同时考虑到

8、降低维修成本 ， 提高生产效率 本文对单设备预防性维修和生产调度的多目标优化问题进行了研究， 并分别与单目标联合优化的方法1-3和独立优化的方法进行了对比1预防性维修计划和生产调度的多目标联合优化模型1 1生产调度假设一个生产系统中的一台设备需要顺序完成n 个作业 ， pj为作业 j 的加工时间， dj为作业j 的预定完成时间 ， wj为作业 j 的重要性 ， j = 1， 2， ， n 生产调度计划的目的是对n 个作业进行合理的作业排序 令1-2xi j=1， 作业 j 是第 i 个加工的 ；0， 其他i = 1， 2， ， n， j = 1， 2， ， n（ 1）设 pi 为作业序列中第i

9、 个作业所用时间， di 为作业序列中第i个作业的预定完成， wi为作业序列中第 i 个作业的重要性， Ci 为作业序列中第i 个作业的实际完成时间， Ti 为作业序列中第i 个作业的延迟时间 ， i = 1， 2， ， n 若忽略设备的失效状况，则1-3pi =nj = 1pjxi j，（ 2）di =nj = 1djxi j，（ 3）wi =nj = 1wjxi j，（ 4）Ti = max（ 0， Cidi） （ 5）对生产调度计划的制定， 经常考虑到以下一些面向时间的目标， 如： 全部生产任务的最大完成时间（ makespan ） ， 加权总完工时间（ total weighted c

10、om-pletion times， TWC） ，加权总延迟时间（ total weightedtardiness，TWT） 等 其中3：makespan = max（ C1 ， ， Cn ） ，（ 6）TWC =ni = 1wi Ci ，（ 7）TWT =ni = 1wi Ti （ 8）1 2维修计划设备可靠性状况、 预防性维修策略、 预防性维修处理时间、突发故障处理时间、突发故障次数等因素都会影 响 到 生 产 任 务 中 各 个 作 业 的 最 终 完 成 时间1 因此 ， 在生产调度时要同时考虑维修策略 同文献1-3， 将预防性维修计划安排在作业序列中每个作业开始之前 假设预防性维修使设

11、备的状态修复到全新 生产过程中的突发故障用小修处理 设R0为加工整个作业序列前的设备初始可靠度， tp为预防性维修平均所需时间， tr为突发故障平均处理时间 ， cp为进行一次预防性维修的平均成本， cr为处理一次突发故障的平均成本设 yi为作业序列中第个作业加工前的预防性维修决策，则1 yi =1，0，作业序列中第 i 个作业加工前进行预防性维修 ；其他（ 9）当生产设备的故障服从威布尔分布， 形状参数为 （ 1） ， 尺寸参数为 ， 则设备的可靠度R（ t）和故障率 （ t） 分别为R（ t） = exp（t） ，（ 10） （ t） =t( ) 1（ 11）设从全新状态始， 设备运行时间

12、内发生的故障次数为N（ ） ， 则N（ ） =0 （ t） dt =0t( ) 1dt =( )（ 12）设 as i为作业序列中进行第i 个作业加工前的设备役龄 ， ae i为作业序列中完成第i 个作业完成后的设备役龄 ， 则1 as i= ae i 1（ 1 yi） ， i = 1， 2， ， n，（ 13）ae i = as i + pi ， i = 1， 2， ， n（ 14）根据式 （ 10） ， 当加工整个作业序列前的设备初始可靠度为R0时有ae 0= expln（ lnR0）（ 15）作业序列中第i 个作业的完成时间Ci 为Ci =ik =1 pk+ tpyk + tr N（ a

13、e k ）N（ as k ） （ 16）设 MC 为完成整个作业序列所需的维修成本（ main-tenance cost） ， 则MC =ik = 1 cpyi + cr N（ ae i ）N（ as i ） （ 17）1 3多目标联合优化模型为更好地节约维修成本和完成生产任务， 设 fk（ k = 1， 2， 3， 4） 为需要考虑的目标， 则f1= makespan = max（ C1 ， ， Cn） ，（ 18）f2= TWC =ni = 1wi Ci ，（ 19）f3= TWT =ni = 1wi max（ 0， Ci di ，（ 20）f4= MC =ni = 1 cpyi + cr

14、N（ ae i）N（ as i） （ 21）设 fopt为目标向量函数， fopt= （ f1， f2， f3， f4） ， 则多目标优化模型为min（ fopt） ；（ 22）s t ni =1xi j= 1，j = 1， 2， ， n，6021哈尔滨工程大学学报第 32 卷nj = 1xij= 1，j = 1， 2， ， n，xi j= 0 或 1，i = 1， 2， ， n，j = 1， 2， ， n，yi= 0 或 1，i = 1， 2， ， n（ 23）2多目标遗传算法多目标优化问题常会存在一个Pareto最优集 ，集中的每个解都是多目标优化问题的一个非劣解，可为决策者作最终选择所用

15、与大多数优化算法不同， 遗传算法可以提供一个种群的相似解， 同时寻找到多个 Pareto优解5 多目标 遗 传 算 法 是 根 据 支 配 的 概 念 来 运 作的5 如果说解x1支配 x2， 则必须满足以下2 个条件5： 1） 对于所有的目标x1非劣于 x2； 2） 至少有一个目标 x1优于 x2 如果以上2 个条件不满足， 则 x1不支配 x22 1编码和初始种群个体 （ 染色体 ） 采用实值编码法 对于种群中的每个个体先随机产生一个预防性维修序列， 再产生一个随机的作业序列 如个体 01104321 表示预防性维修序列为0 1 1 0， 作业序列为4 3 2 1 随机产生多目标遗传算法的

16、初始种群，种群的大小为Npop， Npop设定要适中 ， 太小会使收敛速度变慢 ， 太大则会增加搜索的难点， 降低搜索效率2 2精英策略在多目标优化中， 存在一组非被支配个体的集合 Eg（ g = 1， 2， ， Gen， Gen 为算法的代数 ） 在进行遗传算法时 ， 从 Eg找出不同于Ei（ i = 1， 2， ， g 1） 中的非被支配个体， 组成新集合Eg 将 Eg 中的个体保存在精英集中 从这个精英集中随机选择Nelite组个体作为遗传算法中的精英52 2 1评价对种群中的每个个体， 按照 1 1 节和 1 2 节分别计算出各个目标函数 将种群中的个体按照是否支配其他个体进行分类，

17、并将非被支配的个体保存在集合 Eg（ g =1， 2， ， Gen） 中2 2 2分类下列过程可以找出种群中的非被支配个体51） 从 i =1 开始 2） 从 j = 1， 2， ， Npop， 如果 ij， 则根据支配的概念来判断个体xi和个体 xj之间的支配关系3） 如果对于任意的j（ i j） ，xj都支配 ， xi则表示 xi是被支配的 4） 如果种群中的所有个体都考虑了， 转步骤4） ； 否则 ， 转步骤 2） 5） 除被支配的个体外， 种群中的其他个体都是非被支配个体2 3选择本文采用随机加权法5 将多目标转化成单目标 ， 从而计算个体的适应度 对目标 fk（ k = 1， 2，

18、3， 4）线性正规化处理， 设 fmaxk和 fmink分别为种群中目标fk的最大值和最小值， 线性正规化后目标值vk（ fk）为6vk（ fk） =fkfmaxkfminkfmaxk，k = 1， 2， 3， 4（ 24）在选择一组个体作为父代产生新个体时， 用以下方法为各目标产生一个随机权重：wGAk=randomk（ ）4k = 1randomk（ ），k = 1， 2， 3， 4 （ 25）式 中：randomk（ ）为 任 意 非 负 随 机 数，且randomk（ ） 0， 1 由式 （ 24） 、 （ 25） 得随机加权适应度函数为f（ x） =4k = 1wGAkvk（ fk）

19、 （ 26）2 4交叉本文采用单点交叉， 交叉点范围为 1， 2n 1 ，n 为作业序列中作业的个数， 在交叉点之后的父个体的变量相互交换 当交叉点为 1， n时， 即交叉点在预防性维修序列中， 则直接进行交换 当交叉点为n + 1， 2n 1时， 即交叉点在作业序列中， 则从交叉点之后父个体Parent1的作业序列为父个体Par-ent2中除去Parent1交叉点前作业后的作业序列3 2 5变异本文采用单点变异， 变异点的范围为 1， 2n ， n为作业序列中作业的个数 当变异点为 1， n时， 即变异点处于预防性维修序列中， 将变异点值进行0和 1 之间的转换 当变异点为 n + 1， 2

20、n 时 ， 即变异点处于作业序列中， 将变异点处的作业转移到作业序列的最后一个进行加工32 6多目标遗传算法流程1） 根据 2 1 节产生初始种群Npop2） 根据 2 2 节找出种群中的非支配个体集Eg和Eg，并将Eg保存在精英集中判断是否满足优化准则 ， 如果满足 ， 转步骤 7） ， 否则 ， 转步骤 3） 3） 从精英集中随机选择Nelite组个体作为父个体 其余 （ NpopNelite） 组父个体从种群中选出 根据2 3 节计算种群中各个体的随机加权适应度函数，然后用轮盘赌的方法选出（ NpopNelite） 组父个体 4） 将 Npop组父个体重新随机组对 根据交叉概率 pc和

21、2 4 节的交叉方法 ， 生成一组新个体5） 根据变异概率pm和 2 5 节的变异方法对新7021第 9 期金玉兰 ， 等： 预防性维修计划和生产调度的多目标优化的个体进行变异操作6） 对每组新个体根据2 2 1 节和 2 2 2 节进行评价分类 ， 并找出一个较优的个体作为新个体 如果没有较优的个体， 则随机选择一个作为新个体 Npop个新个体组成新的种群 转步骤 2） 7） 根据 2 2 节的方法 ， 从精英集中找出非被支配的个体作为Pareto最优集 8） 决策者根据偏好从Pareto最优集中选出满意解 3算例分析3 1算例及结果假设设备的初始可靠度R0=0 8 ； 故障服从威布尔分布

22、， 形状参数 = 1 8， 尺寸参数 = 100； 预防性维修处理时间tp= 5， 小修处理时间tr= 15； 预防性维修成本cp= 500， 小修的成本cr= 300 有 4 个作业需要进行加工， 其参数见表1表 1生产调度参数示例Table 1Factors of production scheduling in the example作业编号加工时间预定完成时间权重1231100 252451050 3328850 14651600 35将以上参数代入优化模型， 在 Visual Basic 6 0中编程实现多目标遗传算法 当遗传代数Gen = 30，种群大小Npop= 30， 交叉概率

23、pc= 0 8， 变异概率pm= 0 7， Nelite= 3 时， 所得优化结果见表2一般情况下预防性维修次数越多， 则突发故障的产生次数越少 由表 2 可知 ， 对于特定的生产要求（ 如表 1 所示 ） 由于 cpcr所以维修成本（ MC） 还是随维修次数的增多而升高 由表 2 可知 ， 加权总完工时间 （ TWC） 和加权总延迟时间（ TWT） 则同时受作业序列和预防性维修序列的影响 当预防性维修次数相同时 ， 对于相同的作业序列， TWC 和 TWT 随预防性维修序列的变化而小幅变化； 对于相同的预防性维修序列 ， TWC 和 TWT 随作业序列的变化而发生较大幅度的变化 makesp

24、an主要受预防性维修序列的影响 ， 作业序列对makespan的相对较小 由表 2 可知 ， 多目标联合预防性维修计划和生产调度计划所得的makespan的最小值为190 2，TWC 的最小值为105 1， TWT 的最小值为10 7， MC的最小值为1 020 0 但没有一组预防性维修计划和生产调度计划使得4 个目标同时最优， 因此决策者可根据偏好信息决策出的满意解表 2多目标遗传算法的优化结果Table 2Multi- objective genetic algorithmssimulationresults编号预防性维修序列作业序列makespan TWCTWTMC10 0 0 01 2

25、 432120 11281671 020020 0 101 32 41940 1152148 1 060030 0 101 2 431941 1069 1091 061040 10 01 2 431966 1064 1121 112550 10 04 12 31940 1219 2731 059060 1101 2 431916 1051 1071 411470 10 1 1 2 3 41902 10881341 385380 10 1 1 32 41902 1135 1311 385390 10 1 2 3141911 1203 1231 4011100 10 1 3 12 41902 11

26、94 1311 3849110 10 1 3 2 141902 1241 1141 3849121 10 1 2 3141909 12021211 79873 2方法对比将本文所提的预防性维修计划和生产调度多目标联合优化方法分别跟单目标联合优化方法和独立优化方法进行比较1） 单目标联合优化方法若应用文献 1-2的方法 ， 将本文所示范例进行预防性维修计划和生产调度计划的单目标联合优化 当优化目标分别为makespan和 MC 时， 经枚举所得的优化计划结果不唯一 ， makespan和 MC 的 最 小 值 分 别 为 190 2 和1 020 0 当优化目标分别为TWC 和 TWT， 所得最

27、优结果相同且唯一， 预防性维修序列为0 1 1 0 而生产作业序列为1 2 4 3， TWC 和 TWT 分别为最小值 105 1 和 10 7， 此时 makespan和 MC 分别为191 6 和 1 411 4对比表 2 可知 ， 本文的多目标联合优化的Pare-to 最优集中包含了预防性维修计划和生产调度计划的单目标联合优化的优化结果 当决策者要考虑多个优化目标时， 单目标联合优化的效率显然较差2） 独立优化方法 将预防性维修计划和生产调度计划分别进行独立优化 预防性维修计划采用使设备可用度达到最优的基于寿命的维修策略1， 而生产调度计划采用多目标（ makespan ， TWC， T

28、WT）优化 由文献 1可知 ， 当 = 1 8， = 100， tp= 5，tr=15时， 设备从全新状态开始， 经过 61 5 单位时间后进行预防性维修， R（ 61 5）= 0 66， 即当设备可靠度降到 0 66 时， 进行预防性维修 对生产调度计划单独进行多目标优化的结果为： 1 2 3 4、 1 2 8021哈尔滨工程大学学报第 32 卷4 3、 1 3 2 4 将 2 种优化计划组合起来， 计算makespan 、 TWC、 TWT 和 MC 见表 3 由表 3 可见 ， 最优结果为预防性维修开始时间序列为18 79 5 141 且作业序列为1 2 4 3表 3预防性维修计划和生产

29、调度计划的独立优化结果Table 3Calculated results of separately optimizingPM planning and production scheduling in the example编号预防性维修开始时间序列作业序列makespanTWCTWTMC1187951411 2 3 419221107144182472187951411 2 4319221060107182473187951411 32 41922115814518247对比表 2 可知 ， 本文的多目标联合优化的Pareto最优集包含了预防性维修计划和生产调度计划独立优化的结果 对于表

30、3 中的任意计划， 都能从本文的多目标联合优化的Pareto最优集中找出比其更优的计划 因 此，本 文 的 联 合 方 法 要 优 于 独 立 优 化方法 4结束语本文提出了单设备预防性维修计划和生产调度的多目标优化模型 通过实例可知 ， 一般情况下预防性维修次数越多， 则突发故障的产生次数越少 在预防性维修成本高于小修成本的情况下， MC 主要随预防性维修次数的增多而升高 TWC 和 TWT 则同时受作业序列和预防性维修序列的影响 Makespan主要受预防性维修序列的影响本文未 对 决 策 者 如 何 从 多 目 标 联 合 优 化 的Pareto最优集中选出满意解作阐述， 当最优集规模较大时 ， 这一问题值得探讨 对于多台设备、 多种预防性维修方式或flowshop 生产计划问题等， 还需要对预防性维修计划和生产调度的多目标优化方法进行更深入的研究 参考文献 ： 1CASSADY C R，KUTANOGLU E Integrating preventivemaintenanceplanning andproduction schedulingfor a singlemachine J IEEE Transactions on Reliabilit