摘 要 零部件的联合更换是通过协调不同零部件的更换决策使其尽可能共享资源以节约费用的优化问题. 这类随机组合策略优化问题在实际中大量存在, 对生产生活的经济性起着重要影响. 由于随机因素和组合效应, 其有限阶段的策略求解非常困难. 本文针对飞机引擎维护中的零部件联合更换问题, 利用问题中随机耦合约束的特征, 给出了一个可分解的模型及相应的分解协调方法机会性Lagrangian松弛(Opportunistic Lagrangian relaxation, OLR). 与现有的两种利用先验最优策略规则的方法相比, OLR 方法可在无先验知识的情况下直接得到更佳的协调效果.
关键词 联合更换, 策略优化, 随机耦合约束, 机会性Lagrangian松弛
Opportunistic Lagrangian Relaxation for Joint Replacement Policy
Abstract Joint replacement of multiple parts is an optimization problem where the total cost is to be minimized bycoordinating the timing of replacing various parts to share resources or setup costs. Searching for a good policy for sucha multi-stage combinatorial optimization problem with uncertainty could be prohibitive complex. This paper providesa solution method for a joint replacement problem of engine parts. By utilizing the characteristics of the stochasticcoupling constraints, a decomposable model and the corresponding opportunistic Lagrangian relaxation (OLR) methodare developed. Numerical testing shows that OLR outperforms two prevalent rule-based methods which rely on prioriknowledge of the problem.
Key words Joint replacement, policy optimization, stochastic coupling constraints, opportunistic Lagrangian relaxation(OLR)
　　在维修策略研究中, 零部件的联合更换(Jointreplacement) 是通过资源共享来降低费用的一类重要的组合策略优化问题. 零部件联合更换的费用对设备维修的经济性有着重要影响[1]. 以飞机引擎、电力设备的零部件更换为例, 一方面其费用对运营成本、安全等影响甚大, 另一方面一些维修服务对产品提供方的利润贡献甚至超过产品本身, 因此设备维修的优化成为近年来渐受关注的研究课题[2¡3]..
　　既有的维修策略研究, 主要围绕两大类, 即\即坏即修" 的矫正性维修(Corrective maintenance,CM)与以规避风险为目的、预先规定维修间隔的预防性维修(Preventive maintenance, PM)[4¡5].出于经济性和操作性的原因, 这两大类模式逐渐走向融合, 发展为目前应用广泛的机会性维修(Opportunistic, or opportunity-triggered mainte-nance, OM)[6]. 机会性维修可在一定的维修规范下(例如固定的时间间隔下),按照设备的当前情况增减部分维修项目, 或者允许在随机故障发生的时刻比原计划提前更换一些零件. 这种灵活性使得维修决策可以利用新的信息并可以协同多个零件[7¡8], 且已证明机会维修可降低故障率, 改善系统的可用度[9].文献[10] 利用马尔科夫决策过程(Markovian deci-sion process, MDP) 求解了两个零件的稳态策略的问题, 并通过敏感性分析证实在PM中引入OM可提升策略的经济性. 目前OM研究以阈值型或间隔型等基于规则的稳态策略为主[3;10¡12], 并未考虑实际问题中有限时间下非稳态策略的优化, 或只能处理零件数目较少的情况.264 自 动 化 学 报 39卷
　　本文研究的联合更换(Joint replacement) 属于OM问题, 需要优化进站检修时机以及每次应更换的零件以降低维修合约期内的总费用. 飞机引擎中的零部件分为两类: 寿命件(Life-limited parts,LLP)与非寿命件. 基于传统PM,寿命件在达到一定飞行时间后要被强制更换. 寿命件到期, 即需将整个引擎送往指定的维修站点进行拆解. 在没有寿命件到期的情况下, 引擎也可能发生故障, 包括非寿命件失效以及其他外力造成的不可预测的事故. 在这种情况下, 引擎也需被拆下送至维修站点, 期间需租用备用引擎或者停飞. 整个引擎的运输检修的费用以及租用备用引擎或损失机时是维护成本中的另一个重要部分. 利用到期或随机故障引发的进站, 将未到期的若干寿命件一并更换, 这种OM策略可降低合同期内的总维修费用. 在供应链管理、生产调度等领域也存在着类似的问题, 如联合补货(Jointreplenishment)、串行机器维护等.
　　这一有限时间策略寻优的困难源于非稳态、随机因素和组合效应三重影响, 并且可以证明其最优解是非规则型的[2]. 多个零件由于共同进站而导致其状态、更换决策均相互耦合, 因此决策的优化面临组合爆炸的困难. 随机故障的存在, 进一步增加了优化OM时机与联合更换的零件组的难度. 将联合更换决策转化为对剩余寿命的阈值进行优化是常见的办法. 对飞机引擎零件的联合更换问题, 文献[3] 采用神经元动态规划(Neuro-dynamic pro-gramming, NDP)的方法来寻找最优阈值型策略(Optimal threshold, OT).文献[2] 中的单阶段方法(One-stage analysis, OSA) 则利用阈值规则, 将零件按剩余寿命排序并搜索单阶段稳态指标下的更换阈值. 由于阈值及稳态近似, OT 及OSA所解得策略的性能及所处理问题的规模难以进一步提升.
　　对于本文所研究的随机优化问题, 由于问题内在的随机性, 不同的状态分量均是定义在同一个样本空间之上, 这使得该问题无法像确定性优化问题那样通过直接引入拉格朗日乘子进行解耦. 文献[13¡15]中针对单独的情境(类似于本问题中样本空间中的样本轨道)各自进行分解, 解决了上述不同状态分量之间的耦合问题. 然而当情境数目庞大, 且问题无法以较少数目的典型情境替代所有样本轨道时, 需优化同阶数目的大量乘子, 致使算法面临复杂度问题. 对于本文研究的随机优化问题, 各样本轨道发生概率平均、总数庞大且随阶段数指数增长, 规模原因导致难以应用文献[13¡15]中基于情境的方法求解. 针对前述困难, 本文提出了机会性拉格朗日松弛方法(Opportunistic Lagrangian relaxation,OLR).该方法不依赖于样本空间, 利用耦合约束的特征对问题进行解耦, 需引入的乘子数目与随机约束个数同阶, 不再随问题样本轨道数目一同指数增长.
　　OLR利用随机决策变量所构造的随机耦合约束来判断各时刻是否为适于进站维修的时机, 无需依赖预先设定的阈值或周期规则, 有助于改善策略性能. 在判断进站维修时机的基础上, 将零件解耦以求解各自更换策略, 并通过迭代的更新乘子不断协调应被联合更换的零件组. 由于大型设备的联合更换涉及总金额高, 策略制定周期较长, 因此对算法所得策略的性能要求高, 实时性要求较低. OLR 在允许的计算时间内迭代优化策略, 可以突破规则和稳态近似的性能瓶颈; 较之基于MDP或随机规划的方法, 较好地解决了策略规模随零件数、阶段数增加而爆炸的问题.
　　本文组织如下: 第1节对该问题进行建模, 并分析了模型的随机性和可分性, 进而在第2节针对耦合约束为0-1变量的线性随机耦合约束的特点, 给出了随机耦合约束的期望值近似及相应的OLR算法. 第3节中的仿真结果显示, OLR 方法的性能不随随机性增强而受到影响; OLR 在解耦决策变量的同时, 也将随机因素的影响简化, 降低了随机策略的求解难度, 同时得到了性能更优的解.
　　1 引擎零件联合更换服务
　　下文中用到的主要符号的定义见表1.表1 主要符号定义表Table 1 Symbols lists符号 定义T 合约期N 零部件个数Sn 第n个部件的寿命期限xn;t 第n个部件的剩余寿命期限rt 阶段t时的故障率»t 发生随机故障的指示变量¢t 阶段t进站送修的0-1决策变量dn;t 阶段t更换第n个部件的0-1决策变量cs进站送修的设置成本cpn更换第n个部件的成本¸kn;t松弛第n个耦合约束的乘子在第k次迭代的取值¸¤n;t松弛第n个耦合约束的最优乘子sk第k次迭代的乘子更新步长g 次梯度
　　1.1 零件联合更换模型
　　考虑合约期为T天的引擎维护问题, 每个阶段t = 0,¢ ¢ ¢ ; T¡1需考虑其进站更换决策. 引擎有N3期 涂国煜等: 联合更换策略的机会性Lagrangian松弛方法 265个寿命件, 其规定使用寿命分别为Sn, n= 1,¢ ¢ ¢,N. 寿命件的剩余寿命随着在翼时间逐渐递减, 即每工作一天寿命减少一天, 若当天引擎被维修, 则剩余寿命不减少. 在一个寿命件剩余寿命减少到零之前必须将引擎送修以更换该寿命件. 其他由非寿命件的失效、引擎本身或外力引起的故障, 统一被建模为随机故障, 并给定故障率rt, t = 0;¢ ¢ ¢ ; T ¡1.在寿命件到期或随机故障发生时, 引擎送修均有固定费用cs, 每更换的一个寿命件n会额外产生零件费用cpn. 为了优化引擎送修决策及零件更换决策, 使得T天内的总维修费用最小, 应遵循如下系统动态方程及约束条件所构成的零件联合更换模型.
　　1.1.1 动态方程记寿命件n在第t 天的剩余寿命为xn;t. 在合约开始时的剩余寿命已知, 为xn;0. 剩余寿命随在翼时间递减, 每单位时间的使用会导致xn;t减少一个时间单位. 若第t 天引擎被送修, 引擎送修变量¢t记为1,否则记为0. 如果引擎维修时更换了寿命件n, 则该寿命件的剩余寿命恢复为新件寿命Sn; 如果在维修中没有被更换, 该寿命件的剩余寿命仍保持为维修前的数值. 于是, 寿命件剩余寿命的动态方程可写为xn;t+1=xn;t¡1 + ¢t+dn;t(Sn¡xn;t); 8n; t(1)这里dn;t为0-1决策变量, 取1为在t 时刻更换零件n, 取0为不更换.由上式可知, 当引擎处于维修中时, 剩余寿命xn;t不随t 递减. 维修的最小时长为一个时间单位,若需要连续维修超过一个时间单位, 需要额外增加对¢t 的约束条件, 或转化为合约期限的调整[16]. 为简化方法的分析, 在本文中暂不考虑此类情形.这里隐含假设: 若非在翼, 即检修中. 在应用中由于引擎成本高, 其在翼时间主要由拆检送修影响,极少出现正常工况引擎不在翼的情况, 因此可认为这一假设基本满足[17].
　　1.1.2 约束条件一个剩余寿命已经为零的寿命件必须被更换,因此有以下强制更换约束:1¡xn;t¡dn;t·0; 8n; t (2)在合约期结束即第t =T天, 寿命件n的剩余寿命要保证高于一个给定的水平xT. 这一到期状态约束为xn;T ¸xTn; 8n (3)引擎综合故障的发生用0-1变量»t 表示, 发生故障时取1,反之为零. 其分布由给定故障率表示:Pr(»t) =rtIf»t=1g+ (1¡rt)If»t=0g(4)这里IA为示性函数, 即A事件为真时取1否则为0. 引擎的综合故障率假定与时间无关, 且与寿命件状态相独立. 下面的模型和解法里面并不局限于与时间无关的情况.当寿命件到期或者随机故障发生时, 需要送修引擎, 即当更换决策dn;t或故障变量»t 为1时, 引擎送修变量¢t 必为1.故这两个约束可写为dn;t¡¢t ·0; (a:s:) 8n; t (5)以及»t¡¢t ·0; (a:s:) 8n; t (6)由于随机故障的存在, 寿命件更换决策变量dn;t与引擎的送修变量¢t 均为随机变量. 从寿命件的状态方程(1) 可以看出, 其剩余寿命也为随机变量. 上面约束(5) 和(6) 需要在任何情况下均被满足, 这是该决策问题难解的关键之一.
　　1.1.3 目标函数维修费用分为两部分: 1) 每次的送修费用cs,包括运输费用、检修所需的耗材、人工费、修理费等, 为按次的固定费用; 2) 每更换一个寿命件所需的费用, 包括新寿命件的价格、拆卸安装费用、人工费等. 因此每天的费用可写为Ct(xt; dt;¢t) =cs¢t+Xncpndn;t(7)在这个优化问题中, 需要求解的决策变量是送修变量¢t 和寿命件更换变量d1;t;¢ ¢ ¢ ; dN;t. 待优化的总费用是T个时间单位的总维修费用, 即:minfdt;¢tgJ0; J0 ´E"T¡1 Xt=0Ct(xt; dt;¢t)#(8)由于状态及决策变量均为随机变量, 这里的优化目标为总费用的期望值. 其期望是关于整个合约期[0,T¡1]内的随机故障发生情况的, 即总费用关于随机故障的发生序列f»0;¢ ¢ ¢ ; »T¡1g求期望.1
　　.2 模型分析
　　在第1.1节所述模型中, 目标函数关于不同寿命件的决策变量是可加的. 此外, 所有的约束中, 一些只包括单一寿命件的更换决策变量dn;t, 比如约束(2) 和(3), 或只包括引擎送修变量¢t, 如约束(6).而在约束(5)中, 则同时包括了在同一时间单位t 内的寿命件的更换决策变量dn;t和引擎送修变量¢t,约束(5) 因此被称作耦合约束. 可以看出, 耦合约束(5) 中各决策变量是以线性组合形式出现的; 另一方面, 目标函数(8) 亦是关于各决策变量的线性和. 在确定性问题中, 线性耦合约束与加性目标函数这两个条件是模型可分解的充要条件. 通过用乘子松弛266 自 动 化 学 报 39卷相应的耦合约束, 生成的拉格朗日函数中原目标函数部分与惩罚项部分均为决策变量的线性组合, 因而可以转化为若干相互独立的子问题求解. 对于寿命件动态方程(1) 中的引擎的送修变量¢t, 在求解时认为已给定, 仍然将式(1) 作为只与单个寿命件决策变量dn;t相关的约束. 对于在这里给定¢t 可能带来的偏差, 将在后面算法中给予补偿.在第t 天, 前t 天内的随机故障的序列»0;t¡1=f»0, ¢ ¢ ¢, »tg会导致寿命件的剩余寿命不同, 这N个寿命件的剩余寿命的组合作为决策的状态空间(x1;t, ¢ ¢ ¢, xN;t), 不同状态需要不同的决策与之对应. 因此在第t 天的随机耦合约束, 相当于2t个确定性的耦合约束, 这成为使得决策问题难解的关键之一.
　　2 在期望意义下的近似优化模型及OLR算法
　　2.1 在期望意义下的近似优化模型将上述模型中的随机耦合约束(5) 的左式用其期望来代替, 即得到一个近似的耦合约束:E(dn;t¡¢t)·0; 8n; t (9)这个新耦合约束本身是一个确定性的不等式, 可知新约束是原来的随机耦合约束成立的必要条件. 记约束(9) 的左式为¹gn;t, 由于两个决策变量都是0-1变量, 可以推出:¹gn;t= Pr(dn;t= 1)¡Pr(¢t = 1) =X!Pr(dn;t(!) = 1) Pr(¢t(!) = 0)¡X!Pr(dn;t(!) = 0) Pr(¢t(!) = 1) (10)由此可知¹gn;t的值给出的是原先随机耦合约束被违反的概率与其成为自由约束(即不等式约束不起作用)的概率之差. 因此, 使¹gn;t的值减小的优化方向,等价于使原随机约束更容易满足的方向. 据此可以得到与原问题优化目标一致的一个近似问题, 即由原目标函数(8), 约束(1)»(4)、(6) 和(9) 所定义的新问题: 这是一个具有确定性耦合约束的问题.用乘子f¸n;t¸0g将相应的约束(9) 松弛, 可以得到拉格朗日函数如下:L(¢t; dn;t; ¸n;t) =Xt"cs¡Xn¸n;t#E¢t+Xn;t(cpn+¸n;t) Edn;t(11)该拉格朗日函数可以被分解为N个寿命件的子问题和一个进站维修子问题来分别进行最小化, 下面将分别加以讨论.
　　2.2 寿命件子问题寿命件n的子问题的目标函数为Ln(¸) = ET¡1 Xt=0(cpn+¸n;t)dn;t=T¡1 Xt=0(cpn+¸n;t)Edn;t; n = 1;¢ ¢ ¢ ; N(12)要满足的约束为(1)»(3). 寿命件n的状态转移方程中含有进站维修变量¢t, 反映了引擎送修所占用的时间. 在这段时间内, 寿命件的状态不发生改变.进站维修变量¢t 是一个不确定的决策变量, 需通过单独的子问题求解, 其在寿命件子问题中出现会影响寿命件更换决策的求解. 作为近似, 在求解寿命件子问题时, 采用如下的状态转移方程作为替代:xn;t+1=xn;t¡1 + max(dn;t;¢t) +dn;t(Sn¡xn;t); 8n; t (13)上式中用max(dn;t;¢t)来代替¢t 的原因在于: 问题分解后, 求解子问题分别得到的决策dn;t和¢t 难以保证满足原约束(5), 会导致状态演变不正确. 用替代项后, 无论当前¢t 的解是否满足原约束(5),均可保证寿命件自身到期更换(即dn;t= 1)时状态演变正确; 并且, 当寿命件自身不需更换, 但¢t 的当前解反映出有其他原因需进站时, 替代项能保证该寿命件剩余寿命不减少.从式(12)可以看出Ln关于各阶段t 是可分的,因此在状态转移方程(3)、更换约束(2) 和期末状态约束(3) 下, 对Ln 的最小化可以用动态规划求解.值得指出的是, 我们在求解寿命件子问题时, 决策变量变为确定性的变量, 因此只需求解一个确定型的动态规划问题. 具体的理由和做法是这样的:1)在式(12)中, 由于各阶段的费用cpn+¸n 为确定的实数, 期望值符号可以依次与求和和乘积作交换. 因此在优化目标函数时, 只需要知道Edn;t而不需要知道具体的dn;t.2)由式(6) 可知, 随机故障的因素只是通过进站维修的决策¢t 影响整个问题的. 在替代的状态转移约束(13) 中, ¢t 的存在引入了随机因素并影响了寿命件的状态转移概率, 但由贝尔曼最优性原理可知, 最小化未来期望费用的最优决策必定存在一个确定型的解, 故我们在这个子问题中不需要考虑随机型的决策dn;t.3)由上可知, 决策变量是确定型的, 即在寿命件子问题中Edn;t=dn;t. 在下文提到\决策变量"时,3期 涂国煜等: 联合更换策略的机会性Lagrangian松弛方法 267将不对Edn;t和dn;t加以区分.
　　2.3 进站维修子问题进站维修子问题的目标函数为La(¢t) = EXt[cs¡Xn¸n;t]¢t =Xt[cs¡Xn¸n;t]E¢t(14)注意到该目标函数亦为对于各阶段t 线性可加的形式, 因此在约束(6) 下可以给出显式解如下:E¢t =8><>:rt; cs¡Pn¸n;t>01; cs¡Pn¸n;t<0任意值2[0; rt]; cs¡Pn¸n;t= 0(15)这个显式解的含义是, 从无惩罚(¸n;t= 0)无进站的解出发, 对于gn;t =dn;t¡¢t >0的情况加大惩罚(提高¸n;t),当对违反约束的惩罚足够高, 即乘子之和高于进站维修的固定费用的时候, 相应时刻t会得出进站维修的1决策, 否则保持0决策.注意到该显式解是一个线性函数, 在临界值附近对乘子的取值相当敏感. 为了减少震荡, 在算法中进站维修的解采用Bang-bang控制的方法, 在临界值cs附近, 若乘子之和的改变量低于一个小正数的容忍度" >0,即使按照式(28)相应的解¢t 应当发生变化, 也并不改变.
　　2.4 对偶问题到此为止已经解决了两类子问题的最优化问题.下面就要在原问题的一组解d(k)n;t, ¢(k)t 下, 对对偶问题q(¸)关于¸求解. 由于两个子问题中都直接给出了决策变量的期望值Edn;t 和E¢t, 所以对偶问题不存在随机因素, 其目标函数是一个关于确定型¸的线性函数, 写为q(¸) =Xn(Edn;t¡E¢t)¸n;t+csXtE¢t+XncpnXtEdn;t(16)因此, Edn;t¡E¢t 是q(¸)的次梯度方向, 乘子¸按下式用次梯度法迭代求解:¸k+1n;t=¸kn;t+sk(Edkn;t¡E¢kt) (17)其中, 步长sk取满足以下条件(18) 的正数[18]. 若乘子¸k非最优乘子, 且所有的更新步长均满足如下不等式[18]:0< sk<2(q¤¡q(¸k))kgkk2(18)则对于每个对偶问题的最优解¸¤, 都有:k¸k+1¡¸¤k2<k¸k¡¸¤k2(19)式(18) 中q¤是对偶问题的最优解, 通常需要利用可行解和对偶解进行估计. 下面给出原问题的一个下界作为q¤的估计值.对于寿命件n来讲, 其更换的次数为vn, 其初始寿命为xn;0. 该寿命件的使用会持续整个时间区间, 除了由于那些无需更换寿命件n的引擎进站维修所导致的暂停. 考虑各零件更换与引擎进站完全同步的理想情况下其解是性能下界, 那么vn 和进站维修的次数V 应满足下面三个关系式:(vn¡1)Sn+ (V¡vn) +xn;0+ 1< T (20)vnSn+ (V¡vn) +xn;0+ 1¸T (21)vn·V (22)可以得出:V¸maxnT¡xn;0¡1Sn(23)vn¸T¡V¡xn;0¡1Sn+ 1(24)则引擎维修成本的下界由下式给出:J=csmax(V;T¡1 Xt=0rt)+Xncpnvn(25)其中V =»maxnT¡xn;0¡1Sn¼(26)vn =»T¡V¡xn;0¡1Sn+ 1¼(27)符号d¢e表示向上取整.该绝对下界估计方法不依赖于样本空间, 所给出的下界是所有样本轨道下问题性能的下界, 并非仅仅是均值的下界, 这也是本文的贡献之一.
　　3 仿真测试与结果分析
　　本节给出OLR方法的数值测试及其与OT和OSA方法的比较结果, 这三种方法的应用方式如下:1) OLR方法. 每次进站, 根据当前状态优化后续阶段决策, 取限定迭代步数内使总费用期望值最小的解. 本次进站时只采用当前时刻的决策, 后续进站时基于之前的解和乘子进一步迭代寻优, 以得到更新后的决策, 藉此保证决策的可行性.2) OT方法. 遍历[1;minnSn] 区间内所有值作为阈值, 以得到全部仿真样本下费用均值最小的阈值为最优阈值th. 相应地, 进站时的更换决策为268 自 动 化 学 报 39卷dthn;t(xn;t) =(0; xn;t> th1; xn;t·th(28)最优阈值下的费用均值即为OT的性能指标, 实际这也是固定阈值型策略可达到的性能极限.3) OSA方法. 每次进站, 根据当前状态得到一步前瞻下的最优决策, 具体参见文献[2].由于OLR未像OT等方法一样限定解的结构,且直接优化有限阶段的总费用, 而未像OSA等方法以平均费用作估计, 因此在没有简单形式的最优策略的问题中, 理论上OLR应该可以较限定了策略结构的算法得到更好的性能.大体上说, 零件越能被同步更换, 总费用就越低. 零件本身的差异性, 包括零件寿命、价格及其初始状态, 是影响联合更换同步性的重要因素. 在文献[16] 中已表明, 零件寿命和价格相同, 仅初始状态不同时, OLR 方法可较OT、OSA更好的同步零件的更换. 但对于零件寿命、价格和初始状态均不相同的情况, 由于问题本身复杂性大大增加, 文献[16] 中的方法不易收敛得到足够好的解. 本文在文献[16] 基础上的改善主要体现在: 1) 寿命件子问题中新的状态转移方程及相应的求解; 2) 进站子问题求解中的Bang-bang控制; 3) 给出一个下界算法, 以改善求解对偶问题的步长策略. 这里将重点考察本文中经过改善的OLR方法在零件不同的情况下(也是实际中最常见的情况下)的性能.测试用的联合更换问题包括了中等规模和实际规模的算例, 每组问题参数下均采用相同的随机数产生仿真样本轨道以比较三种方法所得策略下的平均费用.3.1 在中等规模参数下测试OLR特性OLR方法在直观上将随机耦合约束以其期望代替, 其性能势必受到随机因素大小的影响. 特别是通过OLR方法将问题分解后, 除进站子问题外, 零件子问题均转化为确定性的问题, 随机因素的影响仅间接通过乘子有所体现. 随故障率的不同, 随机因素对三个方法性能均有所影响, 这里以参数如表2的一组中等规模问题做测试. 考虑到实际中故障率为0.1以上的大型设备非常少见, PS 1 (1)»PS 1 (5)的故障率依次为0.1, 0.05, 0.02, 0.01, 0.005,其他参数相同. 这组测试问题下三种方法的费用均值及方差如表3.表3 PS 1在不同故障率下OLR/OT/OSA结果比较Table 3 Performance of OLR/OT/OSA under di®erentfailure rates for PS 1OLR OT OSA均值 37.6 38.4 38.4PS 1(1)标准差 6.54 7.06 5.36均值 31.6 31.9 32.2PS 1(2)标准差 5.40 5.40 5.77均值 26.4 27.5 28.1PS 1(3)标准差 2.68 3.21 3.11均值 23.8 25.6 25.6PS 1(4)标准差 1.69 1.35 1.35均值 23.4 25.2 25.2PS 1(5)标准差 1.26 0.63 0.63由图1可看出, OLR 方法的总费用均值要低于其他方法, 故障率越低OLR越有优势. 考虑统计因素后, OLR 方法相对于其他方法仍能体现出优势,故障率低时尤为明显. 这是由于故障率较低时, 即故障次数较少时, 每次故障时的更换决策差异会带来显著的性能差异. 而当故障率较高时, 由于故障次数图1 OLR/OT/OSA性能随故障率的变化Fig. 1 Performance of OLR/OT/OSA w.r.t failure rates表2 PS 1的参数表Table 2 Parameters of PS 1N T xTcscpS rt(1) rt(2) rt(3) rt(4) rt(5)5 60 0 4 [1,1,1,1,1] [18,25,31,16,27] 0.1 0.05 0.02 0.01 0.0053期 涂国煜等: 联合更换策略的机会性Lagrangian松弛方法 269较多, 导致进站频繁发生, 与决策无关的进站费用比例升高, 可通过更换决策调整的费用的优化空间缩小, OLR 方法相对于其他方法的优势不如故障率低时明显, 但仍能得到更优的解. 对于本文所研究的飞机引擎维修问题, 由于设备的安全性对于飞行安全至关重要, 因此其故障率往往都较低, 在此类情况下, OLR 方法相对其他方法优势较为明显.当故障率较低(故障率为0.01以及0.005)时,OLR方法的方差要大于其他方法的方差. 原因是OLR在一些样本轨道上可得到费用更低的解, 因而拉大了方差. 图2和图3分别展示了故障率为0.01以及0.005时三种方法在十条样本轨道上的结果, 可图2 故障率为0.01下的三种方法不同样本轨道上的性能比较Fig. 2 Performance of OLR/OT/OSA on di®erentsamples withrt = 0.01图3 故障率为0.005下的三种方法不同样本轨道上的性能比较Fig. 3 Performance of OLR/OT/OSA on di®erentsamples withrt = 0.005可以看出, OLR 方法的性能在每条样本轨道上均优于或等于其他方法, 体现出了OLR方法在低故障率问题上相对于其他问题的优势. 值得指出的是, 结果中方差的来源主要是不同样本轨道之间的差异, 即发生故障的时刻不同带来的差异.3.2 实际规模参数下的OLR性能尽管引擎、电梯等维修合同通常的订立期限为三至五年, 但合同金额却是以年为单位进行约定和重新调整的. 表4中给出合同期为一年、包含30个互不相同寿命件的维修问题PS 2的参数.限定最大迭代步数50下的OLR与OT和OSA进行比较的结果如表5所示.其中下界为全部样本的绝对下界J, 间距为总费用均值与该下界的间距.值得指出的是, OLR 方法在测试样本轨道下获得的最小总费用为214,与绝对下界197的间距仅为8.6 %,验证了下界估计方法及OLR方法的有效性. 由于其他样本轨道的间距也是以197作为基础进行计算的, 从而导致了总费用均值与绝对下界的间距要大于最小样本轨道下的间距8.6 %. 其他样本轨道与最小费用样本轨道的费用存在差异则是由问题本身的随机性(即样本轨道的差异)带来的. 具体来讲, 最小总费用214所对应的样本轨道, OLR 方法可以获得较优解. 对于总费用较高的样本轨道, 由于其故障发生次数多于最小样本轨道, 将导致更多的进站次数以及进站费用, 进而导致总费用的增加.相异零件难以看出类似相同零件情况下[16]的明显同步效果, 但通过图4比较样本路径仍可看出三种方法的差异. 在t = 30和t = 76两次由故障引起进站时, OLR 和OT更好地利用故障进站更换了零件, 因此进站次数较OSA少. 而OLR进一步在更换的零件总量和价格上考虑了阶段效应, 相比OT节约了零件更换费用. 遍历所有取值得到最佳固定阈值th的策略OT已无法进一步提高性能. 从OLR样本轨道上, 可以看出t = 30和t = 76两次进站, 零件更换遵循了不同的阈值; 也就是说OLR方法提供了一个动态阈值的策略.在实际使用当中, 在发生进站后确定零件更换策略时, OLR 方法仅需知道故障率, 无需知道未来故障发生的时刻即可作出决策. 而OT与OSA方法需要知道完整的样本轨道, 因此需要对未来可能的样本轨道进行采样以作出决策, 这样会引入采样误差. OT 与OSA方法得到的结果对于其采样得到的样本轨道效果可能较优, 但实际当中难以出现采样的样本轨道完全等同于最终实现的样本轨道这种理想情况. 因此OLR方法更适合于实际使用, 且不会引入采样带来的误差, 为此类随机问题提供了不依赖样本轨道的、具有扩展性的方法, 这也是本文的贡献之一.270 自 动 化 学 报 39卷表4 PS 2的参数表Table 4 Parameters of PS 2N rt T xTcscpS[1, 3, 1, 2, 3, 3, 1, 1, 1, 3, [120, 253, 149, 132, 212, 278, 125, 249, 156, 244,30 0.015 365 0 10 1, 2, 2, 2, 2, 1, 2, 1, 1, 3, 54, 212, 216, 247, 120,128, 216, 96, 134, 277,2, 1, 1, 1, 2, 1, 1, 2, 1, 3] 211, 110, 191, 190, 129, 239, 261, 196, 169, 131]表5 PS 2: OLR/OT/OSA结果比较Table 5 Performance of OLR/OT/OSA for PS 2方法 下界J总费用间距(%)均值 标准差OLR 197.0 233.2 12.91 18.38OT { 237.2 12.35 20.41OSA { 240.2 14.58 21.93图4 OLR/OT/OSA策略下样本路径比较Fig. 4 Sample path comparison of OLR/OT/OSA
　　4 结论
　　本文为零件联合更换这一类存在随机因素的多阶段组合型决策问题提供了一种分解协调的算法OLR.该方法利用耦合约束的特征对问题进行解耦,进而可避免仿真评价而直接得到当前决策下对未来费用的预期. 这使得该方法不依赖于样本空间, 需引入的乘子数目与随机约束个数同阶, 不再随问题样本轨道数目一同指数增长. 这一特性有助于大规模问题可通过对偶方法求得近优解. 本文提供的下界估计方法可给出所有样本轨道下的下界, 作为对对偶问题最优解的估计, 并利用Bang-bang控制策略缓解线性子问题的震荡, 从而大大提高对偶问题的求解效率. 与已有算法OT与OSA相比, OLR 方法无需对未来样本轨道进行采样, 避免了由采样带来的对决策评估的误差. 同时, OLR 方法的乘子提供了不同时间阶段上决策的机会成本, 有利于发现额外的问题结构信息. 并且, 这一信息可以在序贯决策的各阶段被保留并不断更新, 从而有助于提高求解效率.值得注意的是, OLR 方法尚未像OT/OSA方法一样直接利用最优决策的特征结构[3]即可得到性能更佳的解. 在后续研究中, 可将最优决策的特征结构结合于OLR方法中, 有望进一步改善求解效果.同时, 可从考察绝对下界的紧度方面寻求改善的方法.除本文所研究的引擎维修问题, OLR 方法还适用于求解如设备维护、批量订购等通过共享资源优化成本的决策调度问题. 这类随机序贯决策问题具有以下特征: 1) 决策分量相互耦合; 2) 决策及状态分量仅在随机事件发生时耦合; 3) 分量间耦合关系可建模为线性耦合约束; 4) 优化目标是使得状态分量尽量同步. 对于随机事件为小概率事件时效果较为理想.LR过去被用于资源约束类的问题, 通过价格机制来分配被竞争的资源. 本文所研究的问题与资源分配相反, 属于协调问题. 各个部件越同步越能够节约费用, 本文的实验结果说明以\惩罚"为目的价格机制同样可以鼓励资源的共享. 用价格机制优化协调问题也是一个有趣的研究方向.
    References1 Mayer D. Life-limited parts prove a problem for FMS cus-tomers [Online], available: http://www.wpafb.af.mil/news/story.asp?id=123077131, March 31, 20122 Sun T, Zhao Q C, Luh P B, Tomastik R N. Optimization ofjoint replacement policies for multipart systems by a rolloutframework. IEEE Transactions on Automation Science andEngineering, 2008, 5(4): 609¡6193 Xia L, Zhao Q C, Jia Q S. A structure property of op-timal policies for maintenance problems with safety-criticalcomponents.IEEE Transactions on Automation Science andEngineering, 2008, 5(3): 519¡5314 Jia Xi-Sheng.The Decision Models for Reliability CenteredMaintenance. Beijing: National Defense Industry Press,2007(贾希胜. 以可靠性为中心的维修决策模型. 北京: 国防工业出版社,2007)5 Sheng Tian-Wen, Chen Xiao-Hui, Yi Shu-Ping. Preventivemaintenance policy for life-type equipment.Computer Inte-grated Manufacturing Systems, 2009, 15(3): 598¡6033期 涂国煜等: 联合更换策略的机会性Lagrangian松弛方法 271(盛天文, 陈晓慧, 易树平. 寿命型设备的预防维修策略研究. 计算机集成制造系统, 2009, 15(3): 598¡603)6 Nowakowski T, Werbi¶nka S. On problems of multicompo-nent system maintenance modelling.International Journalof Automation and Computing, 2009, 6(4): 364¡3787 Rao A N, Bhadury B. Opportunistic maintenance of multi-equipment system: a case study.Quality and Reliability En-gineering International, 2001, 16(6): 487¡5008 Cheng Zhi-Jun, Guo Bo. Availability analysis of system un-der the opportunistic maintenance policy.Mathematics inPractice and Theory, 2006, 36(10): 137¡140(程志君, 郭波. 机会维修策略下的系统可用度分析. 数学的实践与认识, 2006, 36(10): 137¡140)9 Cui L R, Li H J. Opportunistic maintenance for multi-component shock models.Mathematical Methods of Oper-ations Research, 2006, 63(3): 493¡51110 Zhang Z Q, Wu S, Li B F. A condition-based and oppor-tunistic maintenance model for a two-unit deteriorating sys-tem. In: Proceedings of the 2011 International Conferenceon Quality, Reliability, Risk, Maintenance, and Safety En-gineering. Xi0an, China: IEEE, 2011. 590¡59511 Jain S. Opportunistic Maintenance Policy of a Multi-unitSystem under Transient State [Ph. D. dissertation], Univer-sity of South Florida, USA, 200512 Cheng Zhi-Jun, Guo Bo. The optimal analysis of oppor-tunistic maintenance model of multi-components system.In-dustrial Engineering Journal, 2007, 10(5): 66¡69(程志君, 郭波. 多部件系统机会维修优化模型. 工业工程, 2007,10(5): 66¡69)13 Rockafellar R T, Wets R J B. Scenarios and policy aggre-gation in optimization under uncertainty. Mathematics ofOperations Research, 1991, 16(1): 119¡14714 Rockafellar R T, Wets R J B. A dual strategy for the im-plementation of the aggregation principle in decision mak-ing under uncertainty. Applied Stochastic Models and DataAnalysis, 1992, 8(3): 245¡25515 Nowak M P, RÄomisch W. Stochastic Lagrangian relaxationapplied to power scheduling in a hydro-thermal systemunder uncertainty.Annals of Operations Research, 2000,100(1¡4): 251¡27216 Tu G Y, Luh P B, Zhao Q C, Tomastik R N. An optimiza-tion method for joint replacement decisions in maintenance.In: Proceedings of the 43rd IEEE Conference on Decisionand Control. Nasau, Bahamas: IEEE, 2004. 3674¡367917 Rong Xiang, Zuo Hong-Fu, Zhang Hai-Jun. Control methodof time on wing for civil aeroengine.Journal of Tra±c andTransportation Engineering, 2008, 8(3): 28¡32(戎翔, 左洪福, 张海军. 民用航空发动机在翼时间控制方法. 交通运输工程学报, 2008, 8(3): 28¡32)18 Bertsekas D P.Nonlinear Programming. New York: AthenaScienti¯c, 2003. 610¡612