考虑设备退化与预防维护的柔性作业车间调度
2018-07-04杜阳宇
杜阳宇，张 枫
(武汉理工大学 机电工程学院，武汉 430070)
传统的柔性作业车间调度,往往根据经验对设备进行周期性维护。然而，在实际的调度过程中,每个设备具体工作时间不等、损坏状况不一，这种维护策略不仅会造成人力物力的浪费，并且还可能导致维护活动与调度计划的冲突，影响整个调度方案的执行。因此，需要将二者进行集成优化。很多国内外学者对这一问题进行了研究：马慧民等[1]采用预防性维护和小修结合的维护策略，建立了调度和维护的联合决策模型；崔维伟等[2]以单机系统为研究对象，考虑设备和工件的堕化效应,建立以完工时间最小和维修成本最低的多目标联合优化模型；刘永等[3]提出的作业车间调度和维护的集成调度模型，维护周期和维护时间都是基于机器役龄约束的；张思源等[4]提出了基于NEH(nawaz enscore ham)思想的快速启发式算法来解决考虑设备维护的流水车间调度问题；金锋赫等[5]等提出了基于设备可用时间的装配作业车间调度规则；Khatami等[6]提出了维护活动的次数和时间间隔不固定的协调模型；Al-Hinai等[7]则是在使用重调度方法时,定义并比较了预测调度的鲁棒性和稳定性,提出了一种两阶段的混合遗传算法(hybrid genetic algorithm,HGA)；Jabbarizadeh等[8]考虑混合车间作业和基于设备可用性约束的预防性维护,使用了3种启发式算法求解。
上述文献在研究调度和预防性维护的集成问题时，主要引入可靠模型作为控制因子，设备可靠度低于临界值进行维护，维护之后可靠度恢复如初。在实际调度作业中，任何一道工序的加工都不允许中断，设备可靠度达到临界值可能发生在连续作业的不同时期，因此作业完工之后设备的实际情况往往是不一致的，部分设备可能因为可靠度远低于临界值而发生严重故障。因此，笔者以柔性作业车间为研究目标，假设设备发生故障的时间服从威布尔分布，建立以可靠度区间为决策变量，以最小化完工时间为目标的集成模型。
1 问题描述
1.1 柔性作业车间问题描述
柔性作业车间调度问题描述如下：车间有m台加工设备，n个待加工工件，每个工件有一道或多道加工工序，每道工序都有一个或者多个设备可以加工，不同工件之间没有加工顺序约束，同一工件的不同工序之间存在加工顺序约束，同一设备同一时刻只能加工一道工序。本文所研究的问题基于如下假设：
(1)零时刻，所有设备均可用；
(2)加工过程不允许被中断；
(3)维护活动过程设备停工；
(4)维护活动在工序完工之后进行；
(5)维护后设备恢复到开始加工时的状态。
1.2 设备维护描述
随着设备的运转，役龄不断增大，设备可靠度就会逐渐下降，因此要对设备进行维护活动。假设生产设备的故障服从威布尔分布λ(t)，如式(1)所示：
(1)
式中：β(β>1)为形状参数，不同的取值决定不同的分布曲线形状；η为尺度参数，不同取值影响分布曲线的缩放比例[9]。t为设备役龄。
可靠度函数R(t)如式(2)所示：
(2)
笔者引入可靠度阈值区间[D[s]，D[l]]作为设备维护的控制因子。D[s]为设备可靠度的起始值，D[l]为设备可靠度的临界值。设备可靠度和役龄的关系如图1所示，[T[s],T[l]]为可靠度区间对应的设备役龄区间。
图1 可靠度区间维护策略示意图
设备维护的条件分为以下两种情况：
(1)工序Oij完工之后，设备k的役龄t∈[T[s],T[l]]，设备状态处于图1中的区域A；
(2)假设Oqh和Oij是设备k上将要加工的相邻的两道工序(Oqh在前)，工序Oqh完工之后，设备k的役龄t
在区域A，B中，设备的可靠度不同，损坏程度也不一致，因此维护时间符合不同的函数关系如式(3)，a为基础时间，b为系数。
(3)
在式(3)中，设备役龄处于区域A时，维护时间长于基础时间，且时间函数是关于役龄差值的二次函数；设备役龄处于区域B时，维护时间短于基础时间，且时间函数是关于役龄差值的一次函数。当设备可靠度低于可靠度界限时，设备需要更多的时间维护，才能恢复役龄为0时刻的可靠度。
D[l]为可靠度临界值，不允许可靠度低于D[l]，否则会导致设备出现严重故障。
1.3 设备退化描述
设备在不断的加工过程中会产生退化。工序Oij在设备k上的退化函数如式(4)所示，实际加工时间如式(5)所示。
×∂
(4)
uijk=pijk+αkpijk
(5)
式中：Tijk为工序Oij加工完成时设备的役龄；pijk为工序Oij在设备k上的标准加工时间；αk为退化因子；∂为退化权值。
2 模型建立
根据最大完工时间最小的要求及相应的约束条件建立如下数学模型：
(6)
s.t.ei(j-1)≤sij
(7)
(8)
(9)
(10)
式(6)为目标函数，最大完工时间最小；式(7)表示两道工序之间的约束；式(8)表示加工时间的约束；式(9)表示设备的役龄约束；式(10)表示加工约束。
3 算法设计
笔者采用改进的遗传算法，在传统遗传算法的基础上结合了基于工件顺序的邻域搜索算法，同时优化初始解，加快了收敛的速度。
遗传算法全局搜索能力较强，不仅可以快速地将解空间中的全体解搜索出，而且不会出现局部最优解快速下降的情况。但是遗传算法的局部搜索能力较差，因此单纯的遗传算法比较费时，在算法后期搜索效率较低。为了提高遗传算法的局部搜索能力，笔者将邻域搜索算法引入遗传算法中，构建出改进的遗传算法，可以有效提高收敛速度。算法流程如图2所示。
图2 算法流程图
3.1 编码和解码
笔者采用基于工序、设备和维护的3层基因编码方式，每层基因长度均为工序总数。
第一层基因确定工序顺序。每个工件的工序均由该工件号表示，第几次出现表示第几道工序。如基因段[1 3 5 2 3 5 2]表示工序O11,O31,O51,O21,O32,O52,O22。
第二层基因确定加工设备。将所有工件的工序依次排列，每道工序对应一个加工设备。如工件1有四道工序，工件2有3道工序，则[1 2 1 3 5 3 2]表示O11,O12,O13,O14的加工设备为1,2,1,3；O21,O22,O23的加工设备为5,3,2。
第三层基因确定工序完成之后是否需要维护以及维护的时间。若维护，则是对应的维护时间，否则为0。
解码时根据前两层编码确定调度顺序和使用设备，根据第三层基因插入维护活动及维护时间。
3.2 初始化
遗传算法的初始解优劣直接影响收敛的速度和最终解的质量，采用基于设备时间最短的方法[10-11]提高初始解的质量。
(1)将所有工件工序依次排列生成一个序列，把生成的序列随机乱序排列，生成第一层基因的初始编码,即工序顺序编码，如[1 2 1 3 5 3 …]。
(2)依据已经确认的工序顺序编码，安排第一道工序的加工设备。首先在可以加工该工序的所有设备中选取时间最短的设备分配给该工序，假设加工时间为t。然后所有工序在各自可加工设备上的加工时间全部增加t。
(3)每分配一道工序，后续工序对应的设备就要增加该工序的加工时间，再选择加工时间最短的设备。依次为每道工序选择加工设备，生成第二层基因的初始解。假设工序[1 2 1 3 5 3]在3个设备上的加工时间如图3所示，则这6道工序选择的设备依次是1,3,2,2,2,3。
图3 设备时间最短法选择设备流程
(4)第三层基因的初始解全部设置为0。至此，3部分的基因初始化完成。
3.3 遗传算子
3.3.1 选择算子
选择操作是把父代中的一部分染色体选中并产生子代染色体,适应度越大的个体越有可能被选中。笔者采用锦标赛法来进行子代的选择[12],目标值即为适应值。
3.3.2 交叉算子
第一层基因编码,为避免出现非法子串的产生,随机选择两个交叉点a,b,两个父代P1,P2,在交叉点之内的基因进行互换交叉,生成两个新的子代C1,C2。
第二层基因编码采用POX的交叉方法,生成子代染色体C1,C2，具体步骤如下：
(1)随机生成两个父代交叉点如图4所示。
图4 POX交叉(一)
(2)交叉父代染色体中a,b之间的基因,分别复制给两个子代染色体C2,C1,结果如图5所示。
图5 POX交叉(二)
(3)将P1中与C2ab段基因相同的编码删除；将P2中与C1ab段基因相同的编码删除,结果如图6所示。
图6 POX交叉(三)
(4)将P1中剩余的基因编码依次填入C2的空余部分；P2,C1执行相同的操作,结果如图7所示。
图7 POX交叉(四)
第三层基因编码记录机器的维护情况,不参与交叉和变异。
3.3.3 变异算子
遗传算法解决柔性作业车间调度问题时常使用的变异算子有插入变异、逆转变异和交换变异等。
为防止出现违法的染色体,第一部分基因编码,随机选择一个变异点,再重新选择一个不同的机器子集；第二部分则从染色体中随机选取两个变异点,互换两个位置的基因。
3.4 邻域搜索算法
笔者对染色体中第一层基因和第二层基因采用不同的搜索策略。
(1)针对第一层基因，采用基于工件交换的搜索策略。随机选择两个不同的工件，将一条染色体中两个工件的所有工序交换位置。如果工序数量不一致，则工序数量少的工件从左往右依次与工序多的工件交换位置。
(2)针对第二层基因，采用基于最小时间的搜索策略。随机选择一段编码基因，在每道工序的可选设备中选择加工时间最小的设备代替当前设备。
3.5 终止准则
整个算法在迭代的过程中呈现收敛的趋势,迭代终止条件为：目标值达到预期的设定值,或者迭代次数达到预期设定值。最小目标值对应的染色体即为最佳调度方案。本文的终止条件为迭代500次。
4 计算实例
目前调度车间常采用固定周期维护策略和可靠度单值控制维护策略对设备进行周期性维护。为验证本文模型的有效性，将笔者提出的可靠度区间控制维护策略(策略一)与可靠度单值控制维护策略(策略二)和固定周期维护策略(策略三)进行了对比。
策略一的维护时间与役龄的函数关系见式(3)。为了使3种维护策略的对比更加符合实际情况，策略二的可靠度单值取策略一的可靠度区间中值，策略三的维护周期为20个时间单位,策略二、三的维护时间求取方法如式(12)所示：
(12)
3种策略的维护参数如表1所示。
表1 维护参数表
实例采用文献[13]中的MK01算例，策略三直接使用该算例的最优调度方案。该方案对应的标准算例工时和本文模型的工时如表2所示。
表2 MK01算例完成时间对比表
参数设置如下：种群规模为50，最大迭代次数为500，交叉概率为0.85，变异概率为0.15，威布尔分布中β=3，η=60，退化权值为0.2。3种维护策略的计算结果如表3所示。
表3 计算结果对比
从表3可以看出，策略一的最优调度方案完成时间为45.75个时间单位,维护次数为4次，相较于策略二完工时间减少了1.27个时间单位；相较于维护策略三，完工时间减少3.75个时间单位,并且维护次数减少两次。3种维护策略的甘特图如图8～图10所示。
对比图8～图10可看出，相较于策略三，策略一和策略二中的维护是基于设备实际加工时间的维护，更有针对性。对比图8和图9，策略一不仅完工时间更短，并且对于不同役龄的设备采用时间不等的维护，维护时间更加灵活。综上所述，对比3种维护策略，本文的维护策略优于其他两种维护策略。
5 结论
针对设备退化和预防性维护的柔性作业车间调度问题，采用基于可靠度区间的维护策略，考虑设备退化和役龄之间的关系，以最大完工时间最小为目标，建立了生产调度和预防性维护相结合的优化模型。在遗传算法基础上，改进编码方式和初始化方法，并且加入邻域搜索的过程，提高了局部搜索的能力。使用MK01基准测试实例，通过对比传统的固定周期维护策略和可靠度单值维护策略，验证了本文模型和算法的有效性，充分说明了使用本文的集成模型可以有效提高设备的加工效率，减少资源浪费。
图8 可靠度区间调度甘特图
参考文献：
[1] 马慧民,叶健飞.柔性车间调度与设备维护的联合优化研究[J].机械设计与制造,2015(7):248-250.
[2] 崔维伟,陆志强,潘尔顺.基于多目标优化的生产调度与设备维护集成研究[J].计算机集成制造系统，2014(6):1398-1404.
[3] 刘永,杨明顺,高新勤,等.基于机器役龄约束的车间作业与预防维修的集成调度[J].制造业自动化,2016(11):70-74.
[4] 张思源,陆志强,崔维伟.考虑设备周期性维护的流水车间生产调度优化算法[J].计算机集成制造系统,2014,20(6):1379-1387.
[5] 金锋赫,孔繁森,金东园.基于设备可用时间约束的装配作业车间调度规则[J].计算机集成制造系统,2008(9):1727-1732.
[6] Khatami M，Zegordi Sh. Coordinative Production and Maintence Scheduling Problem with Flexible Maintenance Time Intervals[J].Journal of Intelligent Manufacturing,2017,28(4):857-867.
[7] Al-Hinai N, ElMekkawy T Y. Robust and Stable Flexible Job Shop Scheduling with Random Machine Breakdowns Using a Hybrid Genetic Algorithm[J].International Journal of Production Economics,2011,132(2):279-291.
[8] Jabbarizadeh F, Zandieh M, Talebi D. Hybrid Flexible Flowshops with Sequence-dependent Setup Times and Machine Availability Constraints[J].Computer & Industrial Engineering,2009,57(3):949-957.
[9] Moubray J. Reliability-centred Maintenance [M]. Amsterdam:Elsevier，1997.
[10] 朱传军,邱文,张超勇,等.多目标柔性作业车间稳健性动态调度研究[J].中国机械工程,2017(2):173-182.
[11] 祁文博，郭顺生，赵国，等.改进初始化方法求解柔性作业车间调度问题[J].数字制造科学，2017，15(4)：192-196.
[12] 李素粉,朱云龙,尹朝万.具有随机加工时间和机器故障的流水车间调度[J].计算机集成制造系统,2005(10):1425-1429.
[13] Brandimarte P. Routing and Scheduling in a Flexible Job Shop by Tabu Search[J]. Annals of Operations Research,1993,41(3):157-183.
