随机耦合约束下的联合更换协调策略

随机耦合约束下的联合更换协调策略

在维护策略研究中，对零件的联合更换是一种重要的组合策略，通过资源共享降低成本。零件更换成本对设备的维护成本具有重要影响。既有的维修策略研究,主要围绕两大类,即“即坏即修”的矫正性维修(CorrectivemaintenanceCM)与以规避风险为目的、预先规定维修间隔的预防性维修(Preventivemaintenance,PM)本文研究的联合更换(Jointreplacement)属于OM问题,需要优化进站检修时机以及每次应更换的零件以降低维修合约期内的总费用.飞机引擎中的零部件分为两类:寿命件(Life-limitedparts,LLP)与非寿命件.基于传统PM,寿命件在达到一定飞行时间后要被强制更换.寿命件到期,即需将整个引擎送往指定的维修站点进行拆解.在没有寿命件到期的情况下,引擎也可能发生故障,包括非寿命件失效以及其他外力造成的不可预测的事故.在这种情况下,引擎也需被拆下送至维修站点,期间需租用备用引擎或者停飞.整个引擎的运输检修的费用以及租用备用引擎或损失机时是维护成本中的另一个重要部分.利用到期或随机故障引发的进站,将未到期的若干寿命件一并更换,这种OM策略可降低合同期内的总维修费用.在供应链管理、生产调度等领域也存在着类似的问题,如联合补货(Jointreplenishment)、串行机器维护等.这一有限时间策略寻优的困难源于非稳态、随机因素和组合效应三重影响,并且可以证明其最优解是非规则型的对于本文所研究的随机优化问题,由于问题内在的随机性,不同的状态分量均是定义在同一个样本空间之上,这使得该问题无法像确定性优化问题那样通过直接引入拉格朗日乘子进行解耦.文献[13-15]中针对单独的情境(类似于本问题中样本空间中的样本轨道)各自进行分解,解决了上述不同状态分量之间的耦合问题.然而当情境数目庞大,且问题无法以较少数目的典型情境替代所有样本轨道时,需优化同阶数目的大量乘子,致使算法面临复杂度问题.对于本文研究的随机优化问题,各样本轨道发生概率平均、总数庞大且随阶段数指数增长,规模原因导致难以应用文献[13-15]中基于情境的方法求解.针对前述困难,本文提出了机会性拉格朗日松弛方法(OpportunisticLagrangianrelaxation,OLR).该方法不依赖于样本空间,利用耦合约束的特征对问题进行解耦,需引入的乘子数目与随机约束个数同阶,不再随问题样本轨道数目一同指数增长.OLR利用随机决策变量所构造的随机耦合约束来判断各时刻是否为适于进站维修的时机,无需依赖预先设定的阈值或周期规则,有助于改善策略性能.在判断进站维修时机的基础上,将零件解耦以求解各自更换策略,并通过迭代的更新乘子不断协调应被联合更换的零件组.由于大型设备的联合更换涉及总金额高,策略制定周期较长,因此对算法所得策略的性能要求高,实时性要求较低.OLR在允许的计算时间内迭代优化策略,可以突破规则和稳态近似的性能瓶颈;较之基于MDP或随机规划的方法,较好地解决了策略规模随零件数、阶段数增加而爆炸的问题.本文组织如下:第1节对该问题进行建模,并分析了模型的随机性和可分性,进而在第2节针对耦合约束为0-1变量的线性随机耦合约束的特点,给出了随机耦合约束的期望值近似及相应的OLR算法.第3节中的仿真结果显示,OLR方法的性能不随随机性增强而受到影响;OLR在解耦决策变量的同时,也将随机因素的影响简化,降低了随机策略的求解难度,同时得到了性能更优的解.1联合更换引擎服务下文中用到的主要符号的定义见表1.1.1零件的联合更换模型考虑合约期为T天的引擎维护问题,每个阶段t=0,···,T-1需考虑其进站更换决策.引擎有N个寿命件,其规定使用寿命分别为S1.1.1剩余寿命x记寿命件n在第t天的剩余寿命为x这里d由上式可知,当引擎处于维修中时,剩余寿命x这里隐含假设:若非在翼,即检修中.在应用中由于引擎成本高,其在翼时间主要由拆检送修影响,极少出现正常工况引擎不在翼的情况,因此可认为这一假设基本满足1.1.2约期确定和随机故障时寿命件剩余白垩系统故障转变模型一个剩余寿命已经为零的寿命件必须被更换,因此有以下强制更换约束:在合约期结束即第t=T天,寿命件n的剩余寿命要保证高于一个给定的水平x引擎综合故障的发生用0-1变量ξ这里I当寿命件到期或者随机故障发生时,需要送修引擎,即当更换决策d以及由于随机故障的存在,寿命件更换决策变量d1.1.3优化目标及期望维修费用分为两部分:1)每次的送修费用c在这个优化问题中,需要求解的决策变量是送修变量∆由于状态及决策变量均为随机变量,这里的优化目标为总费用的期望值.其期望是关于整个合约期[0T-1]内的随机故障发生情况的,即总费用关于随机故障的发生序列{ξ1.2同寿命件的决策变量在第1.1节所述模型中,目标函数关于不同寿命件的决策变量是可加的.此外,所有的约束中,一些只包括单一寿命件的更换决策变量d在第t天,前t天内的随机故障的序列ξ2基于期望的似优化模型和olr算法2.1新耦合约束的建立将上述模型中的随机耦合约束(5)的左式用其期望来代替,即得到一个近似的耦合约束:这个新耦合约束本身是一个确定性的不等式,可知新约束是原来的随机耦合约束成立的必要条件.记约束(9)的左式为由此可知用乘子该拉格朗日函数可以被分解为N个寿命件的子问题和一个进站维修子问题来分别进行最小化,下面将分别加以讨论.2.2寿命件子问题的转移方程寿命件n的子问题的目标函数为要满足的约束为(1)∼(3).寿命件n的状态转移方程中含有进站维修变量∆上式中用max(d从式(12)可以看出L1)在式(12)中,由于各阶段的费用c2)由式(6)可知,随机故障的因素只是通过进站维修的决策∆3)由上可知,决策变量是确定型的,即在寿命件子问题中Ed2.3显式解的生成进站维修子问题的目标函数为注意到该目标函数亦为对于各阶段t线性可加的形式,因此在约束(6)下可以给出显式解如下:这个显式解的含义是,从无惩罚(λ注意到该显式解是一个线性函数,在临界值附近对乘子的取值相当敏感.为了减少震荡,在算法中进站维修的解采用Bang-bang控制的方法,在临界值c2.4引擎维修成本的界面积到此为止已经解决了两类子问题的最优化问题.下面就要在原问题的一组解d因此,Ed其中,步长s则对于每个对偶问题的最优解λ式(18)中q对于寿命件n来讲,其更换的次数为v可以得出:则引擎维修成本的下界由下式给出:其中符号该绝对下界估计方法不依赖于样本空间,所给出的下界是所有样本轨道下问题性能的下界,并非仅仅是均值的下界,这也是本文的贡献之一.3优化算法性能本节给出OLR方法的数值测试及其与OT和OSA方法的比较结果,这三种方法的应用方式如下1)OLR方法.每次进站,根据当前状态优化后续阶段决策,取限定迭代步数内使总费用期望值最小的解.本次进站时只采用当前时刻的决策,后续进站时基于之前的解和乘子进一步迭代寻优,以得到更新后的决策,藉此保证决策的可行性.2)OT方法.遍历[1,min3)OSA方法.每次进站,根据当前状态得到一步前瞻下的最优决策,具体参见文献[2].由于OLR未像OT等方法一样限定解的结构,且直接优化有限阶段的总费用,而未像OSA等方法以平均费用作估计,因此在没有简单形式的最优策略的问题中,理论上OLR应该可以较限定了策略结构的算法得到更好的性能.大体上说,零件越能被同步更换,总费用就越低.零件本身的差异性,包括零件寿命、价格及其初始状态,是影响联合更换同步性的重要因素.在文献[16]中已表明,零件寿命和价格相同,仅初始状态不同时,OLR方法可较OT、OSA更好的同步零件的更换.但对于零件寿命、价格和初始状态均不相同的情况,由于问题本身复杂性大大增加,文献[16]中的方法不易收敛得到足够好的解.本文在文献[16]基础上的改善主要体现在:1)寿命件子问题中新的状态转移方程及相应的求解;2)进站子问题求解中的Bang-bang控制;3)给出一个下界算法,以改善求解对偶问题的步长策略.这里将重点考察本文中经过改善的OLR方法在零件不同的情况下(也是实际中最常见的情况下)的性能.测试用的联合更换问题包括了中等规模和实际规模的算例,每组问题参数下均采用相同的随机数产生仿真样本轨道以比较三种方法所得策略下的平均费用.3.1费用及方差测试OLR方法在直观上将随机耦合约束以其期望代替,其性能势必受到随机因素大小的影响.特别是通过OLR方法将问题分解后,除进站子问题外,零件子问题均转化为确定性的问题,随机因素的影响仅间接通过乘子有所体现.随故障率的不同,随机因素对三个方法性能均有所影响,这里以参数如表2的一组中等规模问题做测试.考虑到实际中故障率为0.1以上的大型设备非常少见,PS1(1)∼PS1(5)的故障率依次为0.1,0.05,0.02,0.01,0.005,其他参数相同.这组测试问题下三种方法的费用均值及方差如表3.由图1可看出,OLR方法的总费用均值要低于其他方法,故障率越低OLR越有优势.考虑统计因素后,OLR方法相对于其他方法仍能体现出优势故障率低时尤为明显.这是由于故障率较低时,即故障次数较少时,每次故障时的更换决策差异会带来显著的性能差异.而当故障率较高时,由于故障次数较多,导致进站频繁发生,与决策无关的进站费用比例升高,可通过更换决策调整的费用的优化空间缩小,OLR方法相对于其他方法的优势不如故障率低时明显,但仍能得到更优的解.对于本文所研究的飞机引擎维修问题,由于设备的安全性对于飞行安全至关重要,因此其故障率往往都较低,在此类情况下,OLR方法相对其他方法优势较为明显.当故障率较低(故障率为0.01以及0.005)时,OLR方法的方差要大于其他方法的方差.原因是OLR在一些样本轨道上可得到费用更低的解,因而拉大了方差.图2和图3分别展示了故障率为0.01以及0.005时三种方法在十条样本轨道上的结果,可可以看出,OLR方法的性能在每条样本轨道上均优于或等于其他方法,体现出了OLR方法在低故障率问题上相对于其他问题的优势.值得指出的是,结果中方差的来源主要是不同样本轨道之间的差异,即发生故障的时刻不同带来的差异.3.2界分也是最大费用分区轨道,但同时也无绝对界段总费用、绝对界轨道间距都存在显著差异尽管引擎、电梯等维修合同通常的订立期限为三至五年,但合同金额却是以年为单位进行约定和重新调整的.表4中给出合同期为一年、包含30个互不相同寿命件的维修问题PS2的参数.限定最大迭代步数50下的OLR与OT和OSA进行比较的结果如表5所示.其中下界为全部样本的绝对下界J,间距为总费用均值与该下界的间距.值得指出的是,OLR方法在测试样本轨道下获得的最小总费用为214,与绝对下界197的间距仅为8.6%,验证了下界估计方法及OLR方法的有效性.由于其他样本轨道的间距也是以197作为基础进行计算的,从而导致了总费用均值与绝对下界的间距要大于最小样本轨道下的间距8.6%.其他样本轨道与最小费用样本轨道的费用存在差异则是由问题本身的随机性(即样本轨道的差异)带来的.具体来讲,最小总费用214所对应的样本轨道,OLR方法可以获得较优解.对于总费用较高的样本轨道,由于其故障发生次数多于最小样本轨道,将导致更多的进站次数以及进站费用,进而导致总费用的增加.相异零件难以看出类似相同零件情况下在实际使用当中,在发生进站后确定零件更换策略时,OLR方法仅需知道故障率,无需知道未来故障发生的时刻即可作出决策.而OT与OSA方法需要知道完整的样本轨道,因此需要对未来可能的样本轨道进行采样以作出决策,这样会引入采样误差.OT与OSA方法得到的结果对于其采样得到的样本轨道效果可能较优,但实际当中难以出现采样的样本轨道完全等同于最终实现的样本轨道这种理想情况.因此OLR方法更适合于实际使用,且不会引入采样带来的误差,为此类随机问题提供了不依赖样本轨道的、具有扩展性的方法,这也是本文的贡献之一.4在估计模型上的应用本文为零件联合更换这一类存在随机因素的多阶段组合型决策问题提供了一种分解协调的算法OLR.该方法利用耦合约束的特征对问题进行解耦进而可避免仿真评价而直接得到当前决策下对未来费用的预期.这使得该方法不依赖于样本空间,需引入的乘子数目与随机约束个数同阶,不再随问题样本轨道数目一同指数增长.这一特性有助于大规模问题可通过对偶方法求得近优解.本文提供的下界估计方法可给出所有样本轨道下的下界,作为对对偶问题最优解的估计,并利用Bang-bang控制策略缓解线性子问题的震荡,从而大大提高对偶问题的求解效率.与已有算法OT与OSA相比,OLR方法无需对未来样本轨道进行采样,避免了由采样带来的对决策评估的误差.同时,OLR方法的乘子提供了不同时间阶段上决策的机会成本,有利于发现额外的问题结构信息.并且,这一信息可以在序贯决策的各阶段被保留并不断更新,从而有助于提高求解效率.值得注意的是,OLR方法尚未像OT/OSA方法一样直接利用最优决策的特征结构除本