考虑结构相关性的多寿命件更换策略搜索算法

摘要

本发明涉及航空发动机维修技术领域，具体地说是一种考虑结构相关性的多寿命件更换策略搜索算法，在综合考虑航空发动机寿命件之间经济相关性和结构相关性的基础上，以全生命周期内寿命件更换总成本最低为优化目标，建立了多寿命件机会更换问题优化模型；针对优化模型的特点，提出了四种模型解空间约简规则，基于提出的规则提出一种基于约简规则的搜索算法，该算法可以获取模型的最优解。最后采用数值实验和应用案例对提出算法进行了评估和验证。结果表明，提出算法能够实现小规模多寿命件机会更换问题的精确求解。

说明书

技术领域：

本发明涉及航空发动机维修技术领域，具体地说是一种考虑结构相关性的多寿命件更换策略搜索算法。

背景技术：

航空发动机是对安全性要求很高的复杂装备，维修成本十分高昂。其中，寿命件的更换成本是发动机维修成本的重要组成部分。以CFM56-5B发动机为例，更换全套寿命件的成本约为260万美元。寿命件是发动机中有强制寿命限制的部件。在发动机运行过程中，寿命件使用时间不允许超出其寿命限制，在到达寿命限制前必须进行更换。由于各寿命件的材料、结构、工作条件等存在差异，各寿命件的寿命限制相差很大。如CFM56-5B发动机的增压机转子寿命限制为30000飞行循环，高压涡轮转子盘寿命限制为20000飞行循环。如果每次维修仅更换达到其寿命限制的寿命件，则会造成维修次数太多，大大增加发动机的维修成本；如果每次维修均更换全部寿命件，则会造成寿命件的大量浪费，同样会给航空公司造成经济损失。由此可见，确定多寿命件的最优更换策略对降低发动机的维修成本具有重要意义。

目前还没有一种有效的求解算法能够适应于发动机多寿命件机会更换问题的求解，而且目前的研究主要是围绕部件之间的经济相关性展开，对部件之间存在的结构相关性研究比较少。发动机普遍采用了单元体结构设计。当更换某个寿命件时，首先需要将发动机分解为单元体状态，相应会发生一定的装拆成本；然后需要将该寿命件所在单元体进一步分解，相应会发生该单元体的装拆成本，各单元体的装拆成本往往是不同的。目前的研究认为不论更换哪个寿命件，发生的固定维修成本都是相同的，并没有考虑寿命件所在单元体对维修成本的影响。

发明内容：

本发明针对现有技术中存在的缺点和不足，提出了一种考虑结构相关性的多寿命件更换策略搜索算法。

本发明通过以下措施达到：

一种考虑结构相关性的多寿命件更换策略搜索算法，其特征在于包括以下步骤：

步骤1：建立多寿命件机会更换问题优化模型，具体包括：

步骤1-1：定义各参数：考虑发动机总寿命为T_lim，包含p(p≥1)个单元体和n(n≥p)个寿命件的机会更换问题，记发动机固定维修成本为c_b,0，其独立于更换的寿命件数量；记发动机的第k个单元体为M_k(k＝1,2···,p)，其包含n_k个寿命件，则其装拆成本为c_b,k；记为M_k的第i_k(i_k＝1,2···n_k)个寿命件，其寿命限制为成本为发动机当前使用时间记为T，使用时间记为剩余寿命记为显然记所有寿命件的最低剩余寿命为t_res,min(T)，即随着T的增加，相应增加，相应减少，当时，必须进行更换，更换时需将该寿命件所在的单元体M_k分解，产生单元体装拆成本c_b,k，因此更换寿命件产生的成本为更换后，归零，重新开始累积，为了减少全生命周期内的发动机维修次数，也可以在更换其他寿命件时提前进行更换，这样能够节约发动机固定维修成本和单元体装拆成本，但会造成一定的寿命件浪费，发动机在T_lim内的维修次数记为m，历次维修时机记为T_j(j＝1,2,···,m)，m不同，T_j不同，每次维修时更换的寿命件不同，那么发动机全生命周期内的寿命件总成本C就不同；求解多寿命件机会更换问题就是确定多寿命件更换策略，即确定m、T_j(j＝1,2,···,m)、每次维修时更换的寿命件，使得C最小，其可以形式化表示为式(1)：

式中，为决策变量构成的解向量；N表示自然数；表示所有解向量构成的解空间，表示第j次维修时是否更换，更换取值为1，否则为0；的计算如式(2)所示：

式中，T₀＝0，表示的初始使用时间；

步骤1-2：多寿命件机会更换问题属于组合优化问题，该问题的解空间规模如式(3)所示：

问题解空间表达为树，树的根节点表示初始状态(T＝T₀＝0)，记为N₀；N₀的任一子节点表示第1次维修(T＝T₁)，记为N₁；以此类推；问题解空间树除N₀之外的每个节点均表示一次维修，第j次维修对应的任一节点N_j包含的决策变量为维修时机T_j以及所有寿命件更换情况m对应于从N₀到叶节点的路径的长度，从N₀到任一叶节点的路径对应于该问题的一个解；

步骤2：执行基于约简规则的搜索算法，具体包括以下内容：

步骤2-1：优化模型约简化规则，其中包括可行性约简规则、寿命件更换约简规则、维修时机确定约简规则、成本约简规则；

步骤2-2：执行基于约简规则的搜索算法，其中可行性约简规则、寿命件更换约简规则和维修时机确定约简规则作为解空间树中子节点的生成规则，成本约简规则作为在解空间树求解过程中子节点搜寻中止规则；

假设在某次维修中，寿命件和(k≠k^*)均需要更换，则单元体M_k和都需要进行分解，那么求解时，将这两个单元体合并为一个单元体进行处理可有效减小问题的解空间，提高求解效率，上述四类约简规则对该合并单元体也成立，下面给出解空间树的子节点生成方法，为了更清楚的说明子节点生成方法，作如下规定：在维修时机T_j时刻，到寿寿命件的集合为到寿寿命件所在单元体的集合为中未到寿寿命件的集合为全部寿命件均未到寿的单元体集合为临时更换方案寿命件集合为R_must和R_chioce，子节点集合为R。确定任意节点N_j的子节点N_j+1集合的步骤如下：

Step1令将S_RES的元素按照从小到大顺序排成一列，由维修时机确定约简规则可分别确定如下集合：

则

Step2将集合中的寿命件的剩余寿命按照从小到大的顺序进行排序，分别记为r₀,r₂,···,r_q，则初始化l＝0(0≤l≤q)，记为中剩余寿命小于等于r_l的寿命件的集合，即

Step3确定单元体集合中更换寿命件的集合为：

Step4确定不包含到寿寿命件的单元体的集合，按单元体编号将中的单元体排成一列，则单元体个数为初始化b＝1，记b为从中选出的单元体的个数，

Step5从中选择b个单元体作为拆发对象，令则共有种方案，将这些方案排成一列，分别记为初始化c＝1，P_c为第c种方案，记方案P_c对应的单元体集合为

Step6记为中全部寿命件的集合，为中单元体中剩余寿命最短的寿命件集合，将中的寿命件的剩余寿命按照从小到大的顺序进行排序，分别记为r₁,r₂,···,r_M，则初始化m＝0，记为中剩余寿命小于等于r_m的寿命件的集合，即

Step7确定不包含寿命件的单元体的寿命件更换方案：即可确定寿命件更换方案子节点N_S：更换R_chioce和R_must中的寿命件，

Step8判断是否满足，则继续；否则，将更换方案节点N_S加入更换方案子节点集合R中，令

Step9令m＝m+1，判断是否满足m＞M，若成立，则继续，否则跳转至Step7，

Step10令c＝c+1，判断是否如果成立，则继续，否则跳转至Step6，

Step11令b＝b+1，判断是否b＞B；如果成立，继续；否则跳转至Step5，

Step12令l＝l+1，判断是否l＞q；如果成立，算法结束，返回更换方案子节点集合R；否则，跳转至Step3；

根据子节点生成方法，提出多寿命件机会更换问题的求解算法，具体步骤如下。

Step1初始化最优值C_min、最优叶节点集合S_min、活节点列表S_L、根节点N₀，C_min设为一个较大的数，S_min为空，S_L为空；

Step2判断是否t_res,min(T₀)≥T_lim。如果是，C_min＝0，S_min＝{N₀}，算法结束；如果否，将N₀加入S_L；

Step3判断S_L是否为空。如果是，算法结束；如果否，指定S_L中最后一个加入的节点为当前节点N_c；

Step4采用子节点生成方法生成当前节点N_c的子节点，子节点构成集合R；

Step5依次判断R中各子节点是否满足如果满足将该节点从R中去掉，否则继续；

Step6依次判断R中各节点中的全部寿命件是否能够使用到T_lim，如果是，根据式(2-1)计算该元素对应的目标函数值，将目标函数值与C_min进行比较，更新C_min和S_min，并从R中去掉该元素；否则将剩余的节点到活结点集合S_L中，返回步骤3；

由算法的求解步骤可以看出，该算法对问题解空间树进行了大量约简，且一定能够获取到发动机多寿命件机会更换问题的最优解。

本发明步骤2-1中所述可行性约简规则为：对式(1)所示的多寿命件机会更换问题，设N_j-1为解空间树中任意节点，如果该节点有子节点N_j，那么有同时，如果那么

通过式(1)的约束条件可以很容易的得出下面两个引理：

引理1：和(i≠j)是单元体M_k中的两个同类型寿命件，若在T＝T_a时，满足条件则当T＞T_a时，所有适合的更换策略均适用于

引理2：对式(1)所示的多寿命件机会更换问题，假设存在两个可行解路径和若存在时间点T_a使得(k＝1,2,···,p；i_k＝1,2,···,n_k)，则路径也是该问题的可行解。

本发明步骤2-1中所述寿命件更换约简规则中包括寿命件更换约简规则1和寿命件更换约简规则2，其中寿命件更换约简规则1为：对式(1)所示的多寿命件机会更换问题，设N_j为解空间树中任意节点，在同一单元体M_k中，如果有寿命件满足那么一定存在不包含节点N_j的可行解，且该可行解要不劣于包含节点N_j的可行解；该规则说明，当对发动机进行寿命件更换时，对某一单元体中，寿命件的更换应该依照剩余寿命从小到大的顺序。

本发明步骤2-1中所述寿命件更换约简规则中包括寿命件更换约简规则1和寿命件更换约简规则2，其中寿命件更换约简规则2为：对式(1)所示的多寿命件机会更换问题，设N_j为解空间树中任意节点，在同一单元体M_k中，如果存在那么一定存在不包含节点N_j的可行解，且该可行解不劣于包含节点N_j的可行解；由寿命件更换约简规则2可知，当对发动机进行维修时，在同一单元体M_k(k＝1,2,···,p)中，到寿的寿命件必须进行更换；同时，单元体中被更换的寿命件需要满足条件：

维修时机确定约简规则

本发明步骤2-1中所述维修时机确定约简规则为：对式(1)所示的多寿命件机会更换问题，设N_j为解空间树中任意节点，如果存在那么一定存在不包含节点N_j的可行解，且该可行解要不劣于包含节点N_j的可行解，由维修时机确定约简规则可知，当N_j是多寿命件机会更换问题解空间树的任一节点，对应的维修时机为T_j。如果N_j存在子节点N_j+1，则N_j+1的维修时机可以确定为T_j+1＝T_j+t_res，min(T_j)。

本发明步骤2-1中所述成本约简规则为：N_a是解空间树中的一个节点(非叶节点)，所有包含节点N_a的目标函数解的成本评估下限值C_l(N_a)可以通过式(4)进行计算：

式中——圆整为整数；成本约简规则：对式(1)所示的多寿命件机会更换问题，设C_min为目标函数全局最优值，N_a为解空间中一个节点(非叶节点)，如果C_l(N_a)＞C_min，那么包含节点N_a的解不是最优解；通过该规则可知，如果包含当前节点的解的成本评估下界值C_l(N_a)超过了目标函数全局最优解C_min，那么包含当前节点的搜索路径应该被终止。

本发明在综合考虑航空发动机寿命件之间经济相关性和结构相关性的基础上，以全生命周期内寿命件更换总成本最低为优化目标，建立了多寿命件机会更换问题优化模型；针对优化模型的特点，提出了四种模型解空间约简规则，基于提出的规则提出一种基于约简规则的搜索算法，该算法可以获取模型的最优解，能够实现小规模多寿命件机会更换问题的精确求解。

附图说明：

附图1是本发明中问题解空间树示意图。

附图2是本发明中寿命件更换约简规则1示例图。

附图3是本发明中寿命件更换约简规则2示例图。

附图4是本发明中维修时机确定约简规则示例图。

具体实施方式：

下面结合附图对本发明作进一步的说明。

本发明综合考虑多寿命件之间的结构相关性和经济相关性，提出了一种考虑结构相关性的多寿命件更换策略搜索算法，具体包括以下内容：

首先，建立多寿命件机会更换问题优化模型，考虑发动机总寿命为T_lim，包含p(p≥1)个单元体和n(n≥p)个寿命件的机会更换问题。记发动机固定维修成本为c_b,0，其独立于更换的寿命件数量。记发动机的第k个单元体为M_k(k＝1,2···,p)，其包含n_k个寿命件，则其装拆成本为c_b,k。记为M_k的第i_k(i_k＝1,2···n_k)个寿命件，其寿命限制为成本为发动机当前使用时间记为T，使用时间记为剩余寿命记为显然记所有寿命件的最低剩余寿命为t_res,min(T)，即随着T的增加，相应增加，相应减少。当时，必须进行更换。更换时需将该寿命件所在的单元体M_k分解，产生单元体装拆成本c_b,k，因此更换寿命件产生的成本为更换后，归零，重新开始累积。为了减少全生命周期内的发动机维修次数，也可以在更换其他寿命件时提前进行更换，这样能够节约发动机固定维修成本和单元体装拆成本，但会造成一定的寿命件浪费。发动机在T_lim内的维修次数记为m，历次维修时机记为T_j(j＝1,2,···,m)。m不同，T_j不同，每次维修时更换的寿命件不同，那么发动机全生命周期内的寿命件总成本C就不同。

求解多寿命件机会更换问题就是确定多寿命件更换策略，即确定m、T_j(j＝1,2,···,m)、每次维修时更换的寿命件，使得C最小，其可以形式化表示为式(1)。

式中，为决策变量构成的解向量；N表示自然数；表示所有解向量构成的解空间，表示第j次维修时是否更换，更换取值为1，否则为0；的计算如式(2)所示。

式中，T₀＝0，表示的初始使用时间。

进行解空间分析，多寿命件机会更换问题属于组合优化问题。根据各决策变量的定义，不难求出该问题的解空间规模，如式(3)所示。

可以看出，问题解空间规模极其庞大，主要影响因素为单元体个数p、寿命件总数n、以及发动机总寿命T_lim。即使当发动机总寿命和寿命件数量不太大时，通过完全遍历解空间获得最优解也几乎是不可能的。

不难发现，发动机历次维修具有天然的时间顺序。因此，问题解空间能够自然的表达为树，如图1所示。树的根节点表示初始状态(T＝T₀＝0)，记为N₀；N₀的任一子节点表示第1次维修(T＝T₁)，记为N₁；以此类推。问题解空间树除N₀之外的每个节点均表示一次维修。第j次维修对应的任一节点N_j包含的决策变量为维修时机T_j以及所有寿命件更换情况m对应于从N₀到叶节点的路径的长度。从N₀到任一叶节点的路径对应于该问题的一个解。

执行基于约简规则的搜索算法，为了提高搜索的有效性，本发明提出一种基于约简规则的搜索算法。该算法主要通过以下三个方面减小解空间的规模：(1)只遍历可行解；(2)在确定某个节点的子节点时，只保留可能获得最优解的子节点；(3)及时终止对非最优节点的搜索。首先优化模型约简规则，其中可行性约简规则：对式(1)所示的多寿命件机会更换问题，设N_j-1为解空间树中任意节点，如果该节点有子节点N_j，那么有同时，如果那么

通过式(1)的约束条件可以很容易的得出下面两个引理：

引理1：和(i≠j)是单元体M_k中的两个同类型寿命件，若在T＝T_a时，满足条件则当T＞T_a时，所有适合的更换策略均适用于

引理2：对式(1)所示的多寿命件机会更换问题，假设存在两个可行解路径和若存在时间点T_a使得(k＝1,2,···,p；i_k＝1,2,···,n_k)，则路径也是该问题的可行解。(1)寿命件更换约简规则：包括寿命件更换约简规则1：对式(1)所示的多寿命件机会更换问题，设N_j为解空间树中任意节点，在同一单元体M_k中，如果有寿命件满足那么一定存在不包含节点N_j的可行解，且该可行解要不劣于包含节点N_j的可行解。

该规则说明，当对发动机进行寿命件更换时，对某一单元体中，寿命件的更换应该依照剩余寿命从小到大的顺序。寿命件更换约简规则2：对式(1)所示的多寿命件机会更换问题，设N_j为解空间树中任意节点，在同一单元体M_k中，如果存在那么一定存在不包含节点N_j的可行解，且该可行解不劣于包含节点N_j的可行解。

由寿命件更换约简规则2可知，当对发动机进行维修时，在同一单元体M_k(k＝1,2,···,p)中，到寿的寿命件必须进行更换；同时，单元体中被更换的寿命件需要满足条件：该规则能够以图3进行说明。

(3)维修时机确定约简规则：对式(1)所示的多寿命件机会更换问题，设N_j为解空间树中任意节点，如果存在那么一定存在不包含节点N_j的可行解，且该可行解要不劣于包含节点N_j的可行解。

由维修时机确定约简规则可知，当N_j是多寿命件机会更换问题解空间树的任一节点，对应的维修时机为T_j。如果N_j存在子节点N_j+1，则N_j+1的维修时机可以确定为T_j+1＝T_j+t_res,min(T_j)。

(4)成本约简规则，N_a是解空间树中的一个节点(非叶节点)，所有包含节点N_a的目标函数解的成本评估下限值C_l(N_a)可以通过式(4)进行计算：

式中——圆整为整数。

成本约简规则：对式(1)所示的多寿命件机会更换问题，设C_min为目标函数全局最优值，N_a为解空间中一个节点(非叶节点)，如果C_l(N_a)＞C_min，那么包含节点N_a的解不是最优解。

该规则显然是成立的。通过该规则可知，如果包含当前节点的解的成本评估下界值C_l(N_a)超过了目标函数全局最优解C_min，那么包含当前节点的搜索路径应该被终止。

执行基于约简规则的搜索算法，其为基于约简规则的求解算法：可行性约简规则、寿命件更换约简规则和维修时机确定约简规则作为解空间树中子节点的生成规则，成本约简规则作为在解空间树求解过程中子节点搜寻中止规则。

目前在对发动机进行维修时，首先需要将其分解为单元体，然后再进行后续的维修活动。假设在某次维修中，寿命件和均需要更换，则单元体M_k和都需要进行分解，那么求解时，将这两个单元体合并为一个单元体进行处理可有效减小问题的解空间，提高求解效率。上述四类约简规则对该合并单元体也成立。

下面给出解空间树的子节点生成方法。为了更清楚的说明子节点生成方法，作如下规定：在维修时机T_j时刻，到寿寿命件的集合为到寿寿命件所在单元体的集合为中未到寿寿命件的集合为全部寿命件均未到寿的单元体集合为临时更换方案寿命件集合为R_must和R_chioce，子节点集合为R。确定任意节点N_j的子节点N_j+1集合的步骤如下：

Step1令将S_RES的元素按照从小到大顺序排成一列，由维修时机确定约简规则可分别确定如下集合：

则

Step2将集合中的寿命件的剩余寿命按照从小到大的顺序进行排序，分别记为r₀,r₂,···,r_q，则初始化l＝0(0≤l≤q)，记为中剩余寿命小于等于r_l的寿命件的集合，即

Step3确定单元体集合中更换寿命件的集合为：

Step4确定不包含到寿寿命件的单元体的集合，按单元体编号将中的单元体排成一列，则单元体个数为初始化b＝1，记b为从中选出的单元体的个数。

Step5从中选择b个单元体作为拆发对象，令则共有种方案，将这些方案排成一列，分别记为初始化c＝1，P_c为第c种方案，记方案P_c对应的单元体集合为

Step6记为中全部寿命件的集合，为中单元体中剩余寿命最短的寿命件集合，将中的寿命件的剩余寿命按照从小到大的顺序进行排序，分别记为r₁,r₂,···,r_M，则初始化m＝0，记为中剩余寿命小于等于r_m的寿命件的集合，即

Step7确定不包含寿命件的单元体的寿命件更换方案：即可确定寿命件更换方案子节点N_S：更换R_chioce和R_must中的寿命件。

Step8判断是否满足，则继续；否则，将更换方案节点N_S加入更换方案子节点集合R中，令

Step9令m＝m+1，判断是否满足m＞M，若成立，则继续，否则跳转至Step7。

Step10令c＝c+1，判断是否如果成立，则继续，否则跳转至Step6。

Step11令b＝b+1，判断是否b＞B；如果成立，继续；否则跳转至Step5。

Step12令l＝l+1，判断是否l＞q；如果成立，算法结束，返回更换方案子节点集合R；否则，跳转至Step3。

根据子节点生成方法，提出多寿命件机会更换问题的求解算法，具体步骤如下。

Step1初始化最优值C_min、最优叶节点集合S_min、活节点列表S_L、根节点N₀，C_min设为一个较大的数，S_min为空，S_L为空。

Step2判断是否t_res,min(T₀)≥T_lim。如果是，C_min＝0，S_min＝{N₀}，算法结束；如果否，将N₀加入S_L。

Step3判断S_L是否为空。如果是，算法结束；如果否，指定S_L中最后一个加入的节点为当前节点N_c。

Step4采用子节点生成方法生成当前节点N_c的子节点，子节点构成集合R。

Step5依次判断R中各子节点是否满足如果满足将该节点从R中去掉，否则继续。

Step6依次判断R中各节点中的全部寿命件是否能够使用到T_lim，如果是，根据式(2-1)计算该元素对应的目标函数值，将目标函数值与C_min进行比较，更新C_min和S_min，并从R中去掉该元素；否则将剩余的节点到活结点集合S_L中，返回步骤3。

由算法的求解步骤可以看出，该算法对问题解空间树进行了大量约简，且一定能够获取到发动机多寿命件机会更换问题的最优解。

下面进行算法验证，通过数值实验，采用随机生成多寿命件机会更换问题的方法对提出算法进行评估。令c_b,0～U(100000,300000)，c_b,k～U(4500,20000)，p＝1，(T_lim,n)∈{60000+10000·k|k＝0,1,2,3}×{5+k|k＝0,1,…,7}。对任一(T_lim,n)均随机生成10个问题。算法采用Java实现。在普通计算机上分别采用提出算法对每组问题进行求解。记录下算法求解的平均消耗时间t。表为实验结果。

由表可知，随着全生命周期T_lim和寿命件个数n的增加，问题求解的时间也随之增长，当问题规模较大时，发生内存溢出。例如，当T_lim＝60000时，求解时间随着n的增加而增长，当n＝11时，内存溢出。

表1实验结果

下面以航空公司的某台发动机为例，采用本发明提出算法对多寿命件机会更换问题进行求解。该型号发动机包含20个寿命件，更换一套寿命件的成本约为260万美元。表为该型号发动机含有寿命件的单元体清单，表为该型号发动机的寿命件清单。设c_b,0＝160000美元，T_lim＝60000飞行循环。表为求解结果。

本发明算法共消耗时间14.64min，取得了1个最优解，相应的目标函数值为8142147美元。应用案例表明，本发明提出算法适用于航空发动机的多寿命件机会更换问题。

表2单元体清单

表3寿命件清单

表4求解结果

本发明在综合考虑航空发动机寿命件之间经济相关性和结构相关性的基础上，以全生命周期内寿命件更换总成本最低为优化目标，建立了多寿命件机会更换问题优化模型；针对优化模型的特点，提出了四种模型解空间约简规则，基于提出的规则提出一种基于约简规则的搜索算法，该算法可以获取模型的最优解。最后采用数值实验和应用案例对提出算法进行了评估和验证。结果表明，提出算法能够实现小规模多寿命件机会更换问题的精确求解。