生产批量约束下的串并联系统选择性维修方法研究

1、生产批量约束下的串并联系统选择性维修方法研究基金项目：国家自然科学基金资助项目(50705036)；国家科技人员服务企业行动项目资助(2009GJE00016)。朱海平, 郭磊, 刘繁茂（华中科技大学，数字制造装备与技术国家重点实验室，湖北 武汉 430074）摘要：针对由多台设备组成的串并联加工生产线系统，在满足生产批量的前提下，使总的维修费用最小。在加工生产线的维修决策过程中，设备有小修、预防性维修和大修三种维修方式，并且有维修时长限制，通过计算每个设备在不同维修策略下的期望生产件数，建立了维修决策模型，并采用文化基因算法理论，实现了遗传算法和禁忌搜索相结合的求解算法，应用实例表明，采用该

2、方法，能快速获得近似最优解。关键词：选择性维修；文化基因算法；遗传算法；禁忌搜索A Selective Maintenance Decision-making Method for the Series-parallel System under the Constraint of Production LotZhu Haiping, Guo Lei, Liu Fanmao(State Key Laboratory of Digital Manufacturing Equipment & Technology, Huazhong University of Science &

3、Technology, Wuhan 430074)Abstract: For the series-parallel machining line consisting of several equipments, it is necessary to minimize the overall maintenance cost under the constraint of production lot. During the maintenance decision-making process, three types of maintenance actions: minimal rep

4、air, preventive maintenance and overhaul are taken into account, and the maintenance time length is limited. By calculating the expected production size in different maintenance actions for each equipment, the maintenance decision-making model is set up. Based on the memetic algorithm theory, the al

5、gorithm integrating the genetic algorithm and tabu search is realized. The case study proves that the approximate optimal solution can be fast obtained by means of this approach.Key words: selective maintenance; memetic algorithm; genetic algorithm; tabu search1引言在复杂制造系统中，各设备的最优维修间隔按照单设备的维修策略来确定，它们的

6、维修间隔不尽相同，甚至差距很大，如果直接依照这些维修间隔来执行维修操作，系统就需要不断地停机，因此必须将很多维修任务集中起来做，这就是成组维修策略。选择性维修是成组维修的一种，其目的是针对多台设备构成的制造系统，在有维修时长限制的情况下，通过优化决策，选择最关键的部分设备进行维修，确定它们合理的维修方式，从而最小化制造系统在下一工作时段内因设备故障造成的生产损失和维修成本等费用之和。选择性维修在实际生产中，拥有很大的现实意义。设备通常有三种维修方式：小修、预防性维修和大修。小修属于恢复性维修，是在设备工作时间内，对于突发性故障进行维修，使其快速恢复到正常状态，小修不改变设备的故障率。大修是一种

7、全面维修，包括更换关键性部件，大修可以使设备恢复如新。预防性维修是一种主动维修策略，关于预防性维修策略的文献有很多，这里综合役龄递减因子和故障率递增因子的优点1，建立了基于设备可靠性的预防性维护修复非新模型，预防性维修前后部件的故障率函数之间的关系定义为。其中，其中称为役龄递减因子，在此规则之下，预防性维护后设备的初始故障率变成了，而不是0；称为故障率递增因子，也就是说，每次预防性维护都增加了故障率函数的变化率。Cassady等2以串并联系统的最大化可靠性为目标，建立了设备服从威布尔分布的选择性维修优化模型。Lust等3改进了模型，并实现了启发式方法和禁忌搜索相结合的模型求解算法。本文研究的是

8、串并联系统的加工生产线，在一定维修的时间内，选择合理的维修方式，在满足下一个周期生产任务的前提下，使维修费用最低，并以此建立数学模型，通过文化基因算法4理论，实现了遗传算法和禁忌搜索算法相结合的模型求解算法。2选择性维修决策图1 加工生产线系统图1是一个发动机缸体的加工生产线，该系统由m道工序(工序用OP表示)组成，工序k(1km)由台设备并联组成，设机器总数为M台，则有。生产线的节拍为1分钟，工作周期为80小时，维修时间为16小时。机器分为故障和正常两种状态，在维修时段内，对于正常的设备，可以采取不修、预防性维修和大修（更换）三种处理方式；对于故障的设备，可以采取不修、小修和大修三种处理方式

9、。在工作周期内，若设备遇到故障，则对设备进行小修，小修的时间可以忽略不计。假设设备故障间隔时间服从两参数的威布尔分布，维修时间服从对数正态分布5。在维修中，维修时间我们采用对数正态分布的平均修复时间。2.1工序并联设备的节拍已知生产线的节拍为，工序k由台设备并联组成，其中设备i(1i)生产一件产品的时间为，则有：在该工序内，设备i的生产能力比重为，满足：，带入上式即得。对于大于1的情况，表示该工序的设备有待机时间。2.2设备期望故障次数一台设备经过大修，则恢复如新；经过小修，恢复到故障前状态，故障率不发生改变；对于预防性维修，则会改变设备的故障率曲线和可靠性。设是设备i第j(j1)次预防维修后

10、的故障率函数(是初始故障率)，是第j-1次主动维修后到第j次主动维修前的设备实际工作时间，则有： (1)设为设备的第j次主动维修前的役龄(从上次大修结束后计算出的实际工作时间的总和)，则有： (2)设备的初始故障率服从两参数的威布尔分布，则，可靠度为，其中和分别为形状参数和尺度参数。由公式(2)可得第j次维修后的故障率函数为，由故障率和可靠性公式可得： (3)根据可靠性理论，由公式(3)，如果设备在t时刻的故障率函数为，则在其后的工作周期内(假定故障修复时间和相比可忽略不计)，该设备期望故障次数为： (4)如前所述，设备正常和故障状态都对应3种维修策略，它们对应4种期望故障次数。设在某个维修决

11、策时刻，设备i自上次大修以来已进行了j次主动维修，第j次主动维修前的役龄为，并在之后工作了时间，则设备的实时役龄为，此时的故障率为1) 对于正常设备不修和故障设备小修，其故障率函数不变，在下一个工作周期内，仍为。 (5)2) 对于故障设备采取不维修策略，在工作周期内故障时间忽略不计的情况下，其期望故障次数比第一种情况多一次。 (6)3) 对于正常设备的预防性维修策略，则维修后设备故障率函数为，其中，为设备的实时役龄。 (7)4) 对于正常设备和故障设备，如果采用大修策略，则设备恢复如新，设备役龄为0，故障率为。 (8)2.3生产计划约束设在工作周期内，要完成P件产品，对于串并联系统而言，在不考

12、虑内故障维修时间的前提下，就需要使每一道工序的并联设备都拥有在工作周期内完成P件产品的能力。已知各设备的期望故障次数为，工序k内有台并联的机器，设备i的加工时间为(分钟)，在工作周期内小修时间为，须满足： (9)3数学优化模型加工生产线中共有M台设备，对于设备i而言，用代表设备在本次维修时的状态，对设备i采取的维修措施有三种，分别用、和三个变量来表示：系统的维修费用有3部分组成：维修时段的固定费用，维修时段的可变费用，工作时段的维修费用。维修时段的固定费用，设单位时间的固定费用为cs，实际维修时间为TA，则维修时段的固定费用为。维修时段的可变费用，即对各设备采取维修策略的费用。假定对设备i进行

13、一次小修、预防性维修和大修的可变费用的期望值分别为、和 (单位：元)，维修所需期望时间分别为、和 (单位：小时)，则总小修可变费用为：，总预防性维修可变费用为：，总大修可变费用为，总小修时间为：，总预防性维修时间为：，总大修时间为，因此，总维修时间合计为：，总维修可变费用合计为：。工作时段的维修费用，即设备发生故障后，小修的费用。对于设备i，有，对于所有的设备，为。综上，维修总费用。选择性维修模型如下： (10) 约束1表明设备集的维修时间之和应不大于给定的时间约束；约束2表明每个工序的期望生产数量都要大于批量；约束3表明最小维修方式仅适用于已发生的故障的设备；约束4表明预防性维修方式仅适用于

14、正常状态的设备；约束5表明对于正常状态的设备，预防性维修和大修只能两者选一；约束6表明对于故障状态的设备，最小维修和大修只能两者选一；约束7表明所有决策变量的取值均为0或1。4文化基因算法求解算法优化模型(11)是一个NP-hard类型的背包问题。在图1的系统中，有M=22台机器，每台机器都有不修、预防性维修/小修、大修三种维修策略。为解决这个问题，我们采用文化基因算法(memetic algorithm)4，其中，全局搜索策略采用遗传算法，局部搜索策略采用禁忌搜索算法。首先对染色体进行编码，染色体长度为机器数目M，0代表不修，1代表预防性维修/小修，2代表大修，具体算法步骤如下：Step1

15、随机产生R个可行解，并通过禁忌搜索算法寻求可行的局部最优解，用局部最优解代替当前可行解，将最优解保存到。Step2 定义交叉操作的概率，对染色体进行交叉操作。这里采用一点交叉方式，即在父染色体上人选一个点，该点前或后的两个个体的部分结构进行互换，产生2个新的个体。如果后代有可行解，对可行个体进行局部搜索后，代替其父代。若无可行解，则重新选择交叉点，直到得到可行的后代或循环了给定次数为止。Step3 定义变异操作的概率，对染色体进行变异操作。即在父染色体中任意选择数点进行变异(由0变1、2或由1变2、0或由2变0、1)，如果变异后的解可行且优于原来的染色体，则对其进行局部搜索后，代替其父代。直到

16、得到可行的后代或循环了给定次数为止。Setp4 根据染色体的目标函数值，计算每个染色体的适应度。Step5 旋转赌轮选择染色体。染色体i被选中的概率。染色体的累积概率，随机产生1个大于0小于1的实数r，若，则选择第i个染色体。Step6 如果染色体的最优解优于，则将最优解保存到；否则，将代替任意一个染色体。循环第2到5步直到迭代次数为止。其中的局部策略禁忌搜索算法如下：Step1将计算的染色体的解作为禁忌搜索的起始当前解和起始最优解，置初始禁忌列表为空，设定该表的最大长度。Step2 改变当前解的每一位的值(由0变1、2或由1变2、0或由2变0、1)，从而得到2*M个领域解。剔除其中不符合约束

17、条件的解，再剔除其中与禁忌列表中操作相同的解，在剩下的解中选出目标函数值最小的解作为当前解。将该解对应的禁忌对象加入禁忌列表，如果禁忌列表超过最大长度则同时移去最早进入禁忌列表的禁忌对象Step3 如果当前解的目标函数值小于最优解的目标函数值，则当前解代替最优解。Step4 重复2到3歩，直到达到迭代次数为止。Step5 用最优解代替原染色体的解。5应用实例如图1所示，该生产线的节拍为1分钟，工作周期为80个小时，维修时间为16个小时，单位时间的固定维修费用为=580元/小时。一共有10个工序，生产批量是4700件。由于设备数较多，表1列出部分设备的维修参数。表1 加工生产线部分设备的维修参数

18、设备jAijSiM1-10.051.11002110035010000.4511.52250881M2-10.051.11201.50251.7533300601M2-20.081.1951.50.158018045011.52.75060721.M4-10.151.1922.50.11202508800.751.2222361551设备有不修，小修/预防性维修，大修。因此可得，各并联工序最小生产能力即设备都不修的生产能力，设备的最大的生产能力即各设备都更换时的生产能力，如表2。表2 各工序的最大和最小生产能力工序工序1工序2工序7工序4工序5工序6工序7工序8工序9

19、工序10最小4726464047164712472146504764460947674769最大4782475747844789478547724793477747954794由表2可得，为实现生产批量的约束，要对最小维修下生产数量小于批量的工序设备进行维修以满足生产批量的约束。对于最小维修下生产数量大于批量的工序，为使维修费用最小，有的设备需要维修以减少维修费用，如工序4（设备M4-1不修的期望故障次数为10.5次，更换后为0.7次）。计算得到的最优维修费用为30892元，此时M2-3，M4-1，M6-2，M8-2应进行大修，M2-6，M8-1应进行小修，M2-4，M2-5应进行预防性维修，

20、总维修时间为15.5小时，生产件数如表3。表3最优维修策略下各工序生产件数工序工序1工序2工序7工序4工序5工序6工序7工序8工序9工序10优化4726470447164755472147034764473047674769计算结果大多出现在第8-12代，如果单用遗传算法，结果大多出现在70-95代，可见，遗传算法加禁忌搜索相结合的算法可以提高获得解的速度。6小结针对串并联系统在满足下一周期的生产批量的基础上的选择性维修问题，本文开展了如下工作：(1) 引进了生产批量计划的概念，通过计算各设备的期望故障次数，根据加工线节拍以及各设备的加工时间，建立了以维修费用最小为目标的选择性维修优化模型；(

21、2) 采用文化基因算法，通过遗传算法进行全局搜索，通过禁忌搜索算法进行局部寻优，可以大大提高运算的速度。本文还存在一些不足，目前只考虑了一个生产周期内的维修费用，没有考虑设备的故障率对以后生产周期的影响。此外，在工作周期内，最小维修时间的忽略将掩盖设备同时故障以及设备实际工作时间改变等问题，这都是在今后研究中需解决的问题。参考文献1 Zhou, X. J., Xi L. F. and Lee, J. Reliability-centered predictive maintenance scheduling for a continuously monitored system subject to degradation. Reliability Engineering and Syst