1 MRO概述

MRO是航空维修的简称，即飞机维护、修理和翻修(maintenance, repair and overhaul)。近年来，随着我国经济飞速增长，我国航空事业也在持续快速发展。航空维修业，作为航空产业链条中的重要一环，将对航空制造业产生重要的影响。

MRO公司在整个航空产业链中受很多外界因素的影响，其维修的基本过程以及在整个产业链中的位置如图1所示。航空维修是售后服务体系中最重要的内容，只有用户买到的产品能得到全寿命的保证，才有继续购买制造商所提供产品的信心。所以，发展航空维修产业链，就可以拉动制造业，提高工业部门的整体竞争能力^[1]。

一项调查显示，47%的MRO公司在维修过程中面临着40%~59%不确定工作内容^[2]。Eickemeyer等^[3]形象地介绍了一般MRO过程与潜在所需工作量之间的关系。随着维修过程的不断进行，待维修件的损坏程度以及所需要的维修工作量才能逐步被估计出来，往往只有当待维修件完成组装并检验通过后才能精确得出其所需要的工作量。

随着全球航空维修市场的激烈竞争，MRO公司面临着提高利润和优化运营管理的巨大压力^[4]。生产调度是航空部件维修的基础，有效地解决维修生产调度中的问题将为MRO企业提高生产效率、提升生产能力、优化库存管理以及提高客户满意度等方面带来极大好处。维修生产调度所包含的内容较多，本文主要考虑以下3方面因素，并以此作为本文所研究问题的基础。

1) 拆分-修理-组装的三级结构。任何一个待维修件都将根据BOM(bill of material)结构分解为若干个子部件。根据检验结果，子部件的状态可能是修理、完好、报废3种状态中的一种。对于需要修理的子部件，子部件进入修理车间，通过一系列工序修理，然后运送到组装班组等待组装；对于状态完好的子部件，直接运送到组装班组；而对于需要报废的子部件，则需要采购部门根据规格订购新的子部件，新订购的子部件也将被运送到组装班组。所有被分解出的子部件全部到达组装班组后，在组装班组进行组装，从而得到新的维修件，通过拆分-修理-组装的三级结构完成该维修件的维修过程。

2) 物料匹配需求。由于MRO行业的特殊性，根据原始设备商的服务通报和民航局的适航证要求，所有从同一待维修件上拆下的子部件只能重新组装到该维修件上。同种待维修件所包含的通用件很少，本文不做考虑。

3) 不确定工艺路线和工时。MRO企业修理车间包含很多不同的工序。对于需要修理的子部件，根据其损坏程度不同或客户的修理要求不同，每个子部件在修理车间需要经过的工序种类和顺序也不同，这体现为子部件的维修路线不确定。对于任何一个子部件，根据维修工艺要求，有其最大数量工序的工艺路线。但实际中，只有损坏程度最高的子部件才会经过给出的所有工序，绝大部分的子部件只需要经过部分工序就可以完成维修。此外，子部件在每个工序的加工时间也是不确定的，工时往往是损坏程度的函数。不确定工艺路线和工时给MRO调度问题的建模和求解带来困难，研究不确定情况下的MRO调度对于指导维修运作具有重要意义。

2 国内外研究现状

MRO问题及其复杂特点已经被Guide等^[5-7]在多篇文章中进行描述和总结。Guide^[7]指出，MRO系统比传统制造业系统面临更多的不确定性和复杂性。针对MRO系统的生产计划和调度研究相当必要。然而，这些复杂的特点使得MRO系统的生产计划和调度很难进行。

本文给出再制造的一般过程如图2所示，并将再制造过程划分为3个阶段：分解(disassembly)、再制造(remanufacturing)和组装(reassembly)。

随后，Junior等^[8]针对Guide提出的若干特点，综述了2000~2010年期间所有与之相关的研究成果，发现几乎没有文章同时考虑到所有的特点，注重实际应用的文章偏少。此外，针对不确定路径和不确定工时情况下的计划与调度问题的研究更少。同时Guide等^[9-10]也指出因为缺少有效的综合模型，大多数现有的研究仅是将关注点放在某个特殊功能区域或者只考虑到部分MRO系统的特点。从目前存在的与MRO计划和调度相关的文章来看，文章主要集中在通过寻找适当的调度规则去提高维修运作，很少研究基于数学优化的方法。

针对通过数学优化方法的MRO调度问题研究，大多数文献将注意点集中在MRO系统的某些子系统上进行研究。例如，文献[11-13]研究MRO系统的分解子系统；文献[14-15]研究两阶段的组装子系统，这种子系统可以认为是MRO系统中的修理-组装子系统。

一些文献也针对三阶段的MRO系统进行研究，Luh等^[16]建立了三阶段MRO调度问题的数学模型，并且提出相应的算法求解该问题。该文献的模型可以处理很多MRO复杂的特性，比如：不同类型机器容量约束、通用件或专用件的安装约束、不确定的维修件到达时间以及随机的工序加工时间等。文章综合应用拉格朗日松弛、随机动态规划以及启发式方法进行求解，并通过Monte Carlo仿真和大量的算例证明这种方法的质量和效率，同时也说明了企业可以通过安排合理的库存以减少不确定因素对MRO系统的影响。然而，该文的模型并没有考虑到不确定工艺路径的约束，并且其对修理车间的建模只是flow-shop类型，不具备一般性。

仿真优化是一种适合解决含有不确定性调度问题的有效方法，而抽样效率和聚类属性则至关重要。Chen等^[17]提出的OCBA(optimal computing budget allocation)技术可以通过合理分配计算量来取得更大的正确选择概率，或者在实现一定的正确选择概率的基础上大大减少仿真计算量。Xu等^[18]提出的MO²TOS算法(multi-fidelity optimization with ordinal transformation and optimal sampling)框架是一种新的灵活的优化方法。MO²TOS算法用序转换(ordinal transformation, OT)方法在低精度模型下得到聚类属性，虽然低精度模型存在偏差，但是计算速度快；然后，在对应转换的高精度模型空间下使用最优抽样(optimal sampling, OS)技术进行抽样，高精度模型不存在偏差，但是比较耗时。文献[19-20]在验证MO²TOS算法的前提下也对该方法进行优化，其中Molina-Crist’obal等^[19]将多种复杂算法嵌套在MO²TOS框架内，在低精度模型求解时运用一种全局搜索算法以提高效率。

生产计划与调度是MRO系统运行的核心问题，不确定性因素使得该问题的研究趋于复杂化。通过对大量文献的总结可以发现，虽然MRO系统的调度问题复杂，并且包含很多不确定性，但是针对MRO系统调度问题的研究是必须的，对于提高MRO企业维修运作水平、提高企业生产能力、提高客户满意度等意义重大。从建模角度来看，现阶段对MRO调度模型的研究主要集中在某些特定情况，只考虑到部分系统特点，综合考虑到达时间和质量不确定、分解和回收物料质量水平不确定、物料匹配需求和工艺路线不确定、工时不确定等因素的文献并不存在。然而，企业在实际的调度过程中往往受到很多不确定因素的影响，调度目标一般是多目标，如何更贴近企业的实际，建立相应的模型并提出高效的计算方法成为调度问题的关键。

3 MRO调度问题建模 3.1 MRO问题描述

一般的MRO基本流程框架如图3所示(其中M表示机器)，可以将其分为3类车间：分解车间、修理车间和组装车间。为了简便，即使现实中每类车间可能有多个，但本文考虑每类车间只有1个。3个车间各自主要的工序内容如下。

1) 分解车间：分解维修件、清洗以及检测。

2) 修理车间：包含很多不同的工序和机器，一般认为是job-shop类型，子部件在该车间的工艺流程不确定。

3) 组装车间：组装和最后的检验。

待维修件到达后首先在分解车间根据BOM结构完成分解，形成若干个子部件。每个子部件根据规格书进行检测，根据客户的需求或者检测的结果，子部件的状态可能是修理、完好、报废3种状态中的一种。对于需要修理的子部件，子部件进入修理车间。修理车间包含多种不同的机器或工序，为了更具一般性，修理车间可以是job-shop类型。根据待维修件在分解车间的检测结果，子部件在修理车间可能有多种不同的维修工艺路线。例如：根据检测结果，子部件可能跳过一些工序；也就是说，对于任何一个子部件，根据维修规程，其在修理车间有一个最长的工艺路线。这条路线上需要经过的工序最多，然而这条维修工艺路线只是一个最差情况下的路线。实际中，根据检测结果，绝大多数的子部件只需要经过这条路线上的部分工序即可完成修理。因此，每个子部件的实际工艺路线是不知道的，直到待维修件完成分解和检测工序；此外，因为子部件损坏程度不同，即使对于两个相同的子部件，其在同一个工序上的加工时间也存在不确定性。

可见，整个维修过程受到很多约束条件，下文给出高效的调度模型。在我们的问题中，对于N个给定的待维修件，决策变量是待维修件在分解车间分解的先后顺序、拆分出的子部件在修理车间每个工序上的修理顺序以及子部件在组装车间的组装顺序。优化目标是期望权重延误时间之和最小。

3.2 MRO调度问题的多精度仿真模型

如上文所述，MRO问题不确定性因素多(不确定达到时间，不确定加工时间，不确定工艺路线等)，问题结构复杂。为了实现对该问题的求解，结合作者在一家航空维修企业的项目经历，首先建立一个基于混合整数线性规划的仿真模型。不失一般性，本文对所研究的这类MRO调度问题作出以下假设。

1) 整个MRO系统只由一个分解车间、一个修理车间和一个组装车间构成；

2) 分解车间和组装车间分别由一个工序组成，每种工序只包含一个机器；

3) 修理车间有多种工序类型，每个子部件在修理车间的工艺路线是不确定的；

4) 修理车间每个工序只包含一个机器；

5) 每个拆分出的子部件都只能组装到原主部件上；

6) 每个机器同一时间只能加工一个部件。

此外，因为本文重点关注对MRO问题不确定因素的处理，故简化了对修理车间生产组织方式复杂性的考虑：假设修理车间是flow-shop类型，每个待维修件在调度开始时刻已经到达维修车间。如图4所示(其中OP代表工序)，假设一个待维修件可以被分解成多个子部件，如C₁和C₂。根据客户需求或在分解车间对每个子部件的检测结果，每个子部件在修理车间可能会经过几条不同维修工艺路线中的一条，例如子部件C₁可能经过两条路径中的一条，各自的概率分别为P₁，P₂。每条工艺路线上的工序个数和种类不同。此外，根据企业历史数据，同一个子部件可能会经过每一条工艺路线的概率以及在每个工序上的加工时间分布是已知的。

1) 参数。

N为待维修件集合， N = { 1 , 2 , … , n } ；

L为子部件集合；

O_l为修理车间第l条维修工艺路线上的工序集合；

G为大数；

P i D 为待维修件i在分解车间的加工时间；

P i l o R 为待维修件i的子部件l在修理车间第o个工序上的加工时间；

P i A 为待维修件i在组装车间的加工时间；

α i l o 表示如果待维修件i的子部件l在修理车间的工序o上加工，则等于1；否则等于0；

d_i为待维修件i的交期；

T_i为待维修件i的延迟(tardiness)；

λ_i为待维修件i的延迟(tardiness)权重。

2) 决策变量。

x i j D 表示如果在分解车间，待维修件i在j之前加工，则等于1，否则为0；

x i j l o R 表示如果在修理车间，待维修件i的第l个子部件在待维修件j的第l个子部件之前在机器o上加工，则等于1，否则为0；

x i j A 表示如果在组装车间，待维修件i在j之前加工，则等于1，否则为0；

C i D 为待维修件i在分解车间的完工时间；

C i l o R 为待维修件i的第l个子部件在修理车间工序o上的完工时间；

C i A 为待维修件i在组装车间的完工时间。

3) 数学模型。

min E [ ∑ i λ i T i ] 。

(1)

s.t.

T i ≥ 0 , i ∈ N ;

(2)

T i ≥ C i A − d i , i ∈ N ;

(3)

x i j D + x j i D = 1 , i , j ∈ N , j ＞ i ;

(4)

C i D − P i D ≥ C j D − G x i j D , i , j ∈ N , j ≠ i ;

(5)

C i D − P i D ≥ 0 , i ∈ N ；

(6)

x i j l o R + x j i l o R = 1 , i , j ∈ N , j ＞ i , l ∈ L , o ∈ O l ;

(7)

x i j l o R ≥ 1 − α i l o , i , j ∈ N , j ≠ i , l ∈ L , o ∈ O l ;

(8)

C i l o R ​ − ​ P i l o R α i l o ​ ≥ C j l o R ​ − G x i j l o R i , j ​ ∈ ​ N , j ​ ≠ ​ i , l ​ ∈ ​ L , o ​ ∈ ​ O l ;

(9)

C i l 1 R − P i l 1 R α i l 1 ≥ C i D , i ∈ N , l ∈ L ;

(10)

C i l ( o + 1 ) R ​ − P i l ( o + 1 ) R α i l ( o + 1 ) ​ ≥ C i l o R ; i ∈ N , l ∈ L , o ∈ O l ;

(11)

x i j A + x j i A = 1 , i , j ∈ N , j ＞ i ;

(12)

C i A − P i A ≥ C j A − G x i j A , i , j ∈ N , j ≠ i ;

(13)

C i A − P i A ≥ C i l | O l | R ; i ∈ N , l ∈ L ;

(14)

C i D , C i l o R , C i A ≥ 0 , i ∈ N , l ∈ L , o ∈ O l ;

(15)

x i j D , x i j l o R , x i j A ∈ { 0 , 1 } , i , j ∈ N , o ∈ O l 。

(16)

其中式(1)为目标函数，表示所有待维修件的加权tardiness之和的期望值最小；式(2)、(3)定义每个待维修件的延迟(tardiness)，其中， T i = max ( C A i − d i , 0 ) ，本文是最小化加权延期时间和，所以当工件在交期之前完成，其延迟为0；式(4)、(7)、(12)确保待维修件之间的前后关系；式(5)、(9)、(13)保证只有当前一个部件加工完成后下一个部件才能开始加工；式(6)表示待维修件的分解开始时间要大于或等于其到达时间；式(8)表示当一个子部件不需要在某工序上加工时，该子部件也不需要在该工序前排队；式(10)、(11)、(14)表示下一道工序的开始时间要大于或等于上一道工序的完工时间，其中|O_l|是指修理车间第l条维修工艺路线上的工序集合中最后一道工序；式(15)、(16)为定义决策变量的范围。

3.2.1 高精度仿真模型

高精度模型通常用于描述系统的具体特征，包含很多不确定性。本文采用前面建立的混合整数线性规划模型作为高精度模型。为了便于叙述，本文以第2节给出的MRO的基本流程为基础，MRO系统的高精度模型描述如图5。

在该高精度模型中，OP₁ 和OP₈ 分别表示分解车间和组装车间，剩余工序表示修理车间。假设调度开始时刻，n个待维修件已经可以被安排调度，所有待维修件在每个机器上的加工顺序是相同的。这个顺序也是要决策的。其中OP₄和OP₅ 各自拥有两个不同的机器处理不同的工作内容，并且各自拥有一个概率值。这体现出MRO系统在修理车间的工艺路线不确定性。基于实际的维修企业信息，并不是所有的工序的加工时间都是不确定的，例如，清洗工序。因此，本文只假设OP₆ 和OP₇有不确定的加工时间。其他工序加工时间是确定的。

可见，高精度仿真模型包含MRO系统的所有复杂特点。如果子部件个数和不确定工时的工序个数增加，则运行该仿真模型是非常耗时的，但是它可以对解进行精确估计。

3.2.2 低精度仿真模型

在高精度仿真模型中，包含很多不确定性(如不确定工艺路线和不确定工时)，为了对一个解作出评价，往往需要运行很多次仿真模型以便获得稳定解。显然，当问题规模变大时，这将非常耗时。因此需要建立低精度模型来近似该高精度仿真模型。

以图5描述的高精度仿真模型为基础，尝试将不确定参数变为确定的，并以此作为低精度仿真模型。对于子部件Sub₁ 和Sub₂ 的不确定工艺路线，可以通过使用最大概率的工艺路线或者建立虚拟工序的方法进行确定化。本文采取第2种方法，用两个虚拟工序分别刻画两个子部件的不确定工艺路线特性，如图5中的OP₄和OP₅，其工时用两条概率工艺路线上所有工序工时和的期望值表示。对于其他包含不确定工时的工序，都使用其期望工时表示。这样，低精度仿真模型就变成确定性的flow-shop问题。

可见，低精度仿真模型不包含不确定参数，仿真运行时间大大缩短，但是其计算结果显然会存在很大的波动性或偏差。

4 基于多精度仿真模型的MRO调度问题算法研究 4.1 MO²TOS算法框架

MO²TOS算法框架由两部分组成：OT(ordinal transformation，序转化) 和OS(optimal sampling，最优抽样)。其中OT基于低精度模型将整个解空间转化为一维有序空间，OS基于高精度模型和转化的一维有序空间进行寻优。MO²TOS算法框架的基本思想是尽管低精度模型存在波动性和偏差，但是通过低精度模型可以发现可行解的变化趋势，这种趋势与高精度模型具有较强的相关性。这样可以通过低精度模型将整个解空间转化成一维有序空间，通过该一维有序空间可以得到聚类属性，这将会有效提高OS过程。MO²TOS算法基本框架如图6所示。

MO²TOS算法的第1步是基于低精度模型l(x)估计所有可行解l(x_i)，i=1，2…，ns，其中ns表示可行解的个数；第2步是对得到的估计值进行排序；第3步是将排序后可行解序列进行分割，分成包含相同个数可行解的若干组。假设h(x)表示高精度模型，δ(x)=h(x)–l(x)表示低精度模型的偏差。ρ表示h(x)和l(x)之间的相关系数，根据文献[18]的证明可知，OT后的分组具有组内方差小组间距离大的特点。

在MO²TOS框架中，使用OCBA作为最优抽样(OS)技术。当一个组距离当前最优组较远并且该组内方差较小时，分配到该组内的抽样点个数将会较少，因为该组不可能包含更好的解。显然，使用这种方法将会提高抽样效率。

本文设计一个简单的算例来解释MO²TOS算法框架的基本原则和潜在的优势。这里设置待维修件数量是6，则可行解个数为6！=720，由于解空间并不大，可以基于高精度仿真模型计算出所有解的目标函数值。此外，设置每个待维修件的权重为1，总预算为132，每次增加的预算为6，分组个数为6。每个工序的工时、工艺路线的概率以及交期值的生成方式与下一节“算例设计与结果分析”中描述的一致。

对于每一个解，基于高精度仿真模型运行1 000次仿真以便消除噪音获得稳定表现。图7给出基于高精度模型的原始解空间下每个解的目标函数值。针对该结果将整个解空间划分为6部分。从图中可以看出，所有解的目标函数值的平均值几乎是一条水平线。显然，每两个相邻组间距离较少，而每个组内的方差较大。

因为低精度模型是确定的，同样可以得到基于低精度模型的每个解的目标函数值。根据目标函数值的升序对所有可行解进行排序。图8给出了基于排序后的可行解空间下高精度模型和低精度模型的相对表现。在该图中，如果将解空间划分为6组，与图7相比，每两个相邻组间距离增大，而每个组内的方差变小。在这种情况下，使用OCBA技术将会使计算更加高效，并提高求解质量。

在OS阶段，图9展示了在不同总预算情况下，3种相似的方法MO²TOS、OCBA和Equal计算得到的最优值。其中OCBA方法没有OT步骤，Equal方法意味着每个组内分配相同的抽样数。从图中可见，MO²TOS算法更具有优势。表1给出不同算法的计算时间和获得的最优目标函数值。因为问题规模较少，只含有6个待维修件，所有可行解的目标函数值均可以被仿真给出，如图8所示。该问题的最优解是(3, 2, 4, 5, 1, 6)，对应的目标函数值是15.8，从表1中可以发现，对于该算例，MO²TOS算法找到最优解。

4.2 算例设计与结果分析

为了评价MO²TOS算法，本小节设计随机产生多个算例进行计算。其中待维修个数n分别为6，8，10，工序数量为8，对于每一个待维修件，随机产生5个问题，对于每个问题，每个工序的加工时间从U(1, 10)中随机产生，其中U(a, b)表示一个在区间[a, b]内的均匀分布。对于工时不确定的工序，其工时分布为两点分布(a, b)，每个值的概率从U(0, 1) 中随机产生并保证和为1，其中a和b为从U(1, 10)中随机产生的整数。此外，每个待维修件的权重从U(1, 3) 中随机产生，交期为所有工序的工时之和加上从U(1, 15)中产生的随机数。不确定工艺路线的概率从U(0, 1)中随机产生。

本节所有算法程序都使用Matlab编码，并在英特尔酷睿i3，主频3.40 GHz的CPU和4.00 GB内存的64 位win7电脑上进行运算。当n=6，设置总预算TT=120，ΔTT=6，组数为6；当n=8，设置总预算TT=1000，ΔTT=50，组数为10；当n=10，设置总预算TT=1 000，ΔTT=60，组数为20；对于每个解，设置仿真次数为1 000以消除噪音获得稳定目标函数值。

表2给出不同算法的计算结果，这些算法对于所有问题都可以在可以接受的时间内计算。当n=6时，MO²TOS、OCBA和Equal 3种算法的计算时间基本相等，对于算法MO²TOS，与OCBA算法相比其目标值平均提高18.39%。当n=8时，3种算法的计算时间也基本相等，对于任何一个算例，MO²TOS算法获得的目标函数值都是最小的，这说明MO²TOS算法比其它3种方法更好。对于n=6和n=8时，因为OT步骤的计算时间大概1s，所以MO²TOS、OCBA和Equal 3种算法的计算时间基本一致。当n=10时，OT步骤的时间大概200 s，所以MO²TOS算法更加耗时，从目标函数值方面看，MO²TOS算法获得的目标函数值依旧都是最小的，与OCBA算法相比其平均提高16.46%，与EDD调度规则相比其平均提高20.82%。这说明MO²TOS算法依然表现最好。

然而，当问题规模继续增大时，MO²TOS算法将不再适合求解该问题。在MRO调度问题中，当n>10 时，可行解空间大小大于10!，可见，即使在低精度模型下的OT步骤中对所有解进行储存已是不可能实现的，所以未来如何利用问题解的聚类属性而不是利用低精度模型去评价和储存所有解将是一个有意义的研究方向。

5 结论

本文应用MO²TOS算法框架求解包含很多不确定性的MRO调度问题。首先建立高精度仿真模型，该模型包含随机参数，直接运行该模型非常耗时。通过简化，建立相应的低精度仿真模型，并将该低精度仿真模型应用到MO²TOS算法框架的OT阶段。在OT阶段将整个可行解空间转换成一维有序空间。接着对该一维有序空间进行划分，并用OCBA方法进行抽样。通过大量算例证明了MO²TOS算法框架在计算MRO调度问题方面的高效性。然而，当问题规模继续增大时，由于解空间巨大，此时MO²TOS算法将不再适合求解该问题。下一步有以下研究方向。

1) OT阶段需要对所有可行解排序，当可行解空间较大时，对所有解进行评价仍然需要耗费大量时间，如何利用聚类属性替代对所有解一一评价是未来的一个研究方向。

2) MO²TOS算法框架是一种随机搜索方法，当寻找到好的解时，并不能判定解的好坏程度，因此，需要研究紧下界用于评判解的质量。如何计算一个紧下界是另一个研究方向。

3) 为了寻找较优解，ρ值不能太小。然而，在实际大规模问题中ρ值很难获得，因此如何在低精度模型设计时保证ρ值不会太小也是一个很好的研究方向。