隨機(jī)耦合約束下的聯(lián)合更換協(xié)調(diào)策略

隨機(jī)耦合約束下的聯(lián)合更換協(xié)調(diào)策略

在維護(hù)策略研究中，對(duì)零件的聯(lián)合更換是一種重要的組合策略，通過(guò)資源共享降低成本。零件更換成本對(duì)設(shè)備的維護(hù)成本具有重要影響。既有的維修策略研究,主要圍繞兩大類,即“即壞即修”的矯正性維修(CorrectivemaintenanceCM)與以規(guī)避風(fēng)險(xiǎn)為目的、預(yù)先規(guī)定維修間隔的預(yù)防性維修(Preventivemaintenance,PM)本文研究的聯(lián)合更換(Jointreplacement)屬于OM問題,需要優(yōu)化進(jìn)站檢修時(shí)機(jī)以及每次應(yīng)更換的零件以降低維修合約期內(nèi)的總費(fèi)用.飛機(jī)引擎中的零部件分為兩類:壽命件(Life-limitedparts,LLP)與非壽命件.基于傳統(tǒng)PM,壽命件在達(dá)到一定飛行時(shí)間后要被強(qiáng)制更換.壽命件到期,即需將整個(gè)引擎送往指定的維修站點(diǎn)進(jìn)行拆解.在沒有壽命件到期的情況下,引擎也可能發(fā)生故障,包括非壽命件失效以及其他外力造成的不可預(yù)測(cè)的事故.在這種情況下,引擎也需被拆下送至維修站點(diǎn),期間需租用備用引擎或者停飛.整個(gè)引擎的運(yùn)輸檢修的費(fèi)用以及租用備用引擎或損失機(jī)時(shí)是維護(hù)成本中的另一個(gè)重要部分.利用到期或隨機(jī)故障引發(fā)的進(jìn)站,將未到期的若干壽命件一并更換,這種OM策略可降低合同期內(nèi)的總維修費(fèi)用.在供應(yīng)鏈管理、生產(chǎn)調(diào)度等領(lǐng)域也存在著類似的問題,如聯(lián)合補(bǔ)貨(Jointreplenishment)、串行機(jī)器維護(hù)等.這一有限時(shí)間策略尋優(yōu)的困難源于非穩(wěn)態(tài)、隨機(jī)因素和組合效應(yīng)三重影響,并且可以證明其最優(yōu)解是非規(guī)則型的對(duì)于本文所研究的隨機(jī)優(yōu)化問題,由于問題內(nèi)在的隨機(jī)性,不同的狀態(tài)分量均是定義在同一個(gè)樣本空間之上,這使得該問題無(wú)法像確定性優(yōu)化問題那樣通過(guò)直接引入拉格朗日乘子進(jìn)行解耦.文獻(xiàn)[13-15]中針對(duì)單獨(dú)的情境(類似于本問題中樣本空間中的樣本軌道)各自進(jìn)行分解,解決了上述不同狀態(tài)分量之間的耦合問題.然而當(dāng)情境數(shù)目龐大,且問題無(wú)法以較少數(shù)目的典型情境替代所有樣本軌道時(shí),需優(yōu)化同階數(shù)目的大量乘子,致使算法面臨復(fù)雜度問題.對(duì)于本文研究的隨機(jī)優(yōu)化問題,各樣本軌道發(fā)生概率平均、總數(shù)龐大且隨階段數(shù)指數(shù)增長(zhǎng),規(guī)模原因?qū)е码y以應(yīng)用文獻(xiàn)[13-15]中基于情境的方法求解.針對(duì)前述困難,本文提出了機(jī)會(huì)性拉格朗日松弛方法(OpportunisticLagrangianrelaxation,OLR).該方法不依賴于樣本空間,利用耦合約束的特征對(duì)問題進(jìn)行解耦,需引入的乘子數(shù)目與隨機(jī)約束個(gè)數(shù)同階,不再隨問題樣本軌道數(shù)目一同指數(shù)增長(zhǎng).OLR利用隨機(jī)決策變量所構(gòu)造的隨機(jī)耦合約束來(lái)判斷各時(shí)刻是否為適于進(jìn)站維修的時(shí)機(jī),無(wú)需依賴預(yù)先設(shè)定的閾值或周期規(guī)則,有助于改善策略性能.在判斷進(jìn)站維修時(shí)機(jī)的基礎(chǔ)上,將零件解耦以求解各自更換策略,并通過(guò)迭代的更新乘子不斷協(xié)調(diào)應(yīng)被聯(lián)合更換的零件組.由于大型設(shè)備的聯(lián)合更換涉及總金額高,策略制定周期較長(zhǎng),因此對(duì)算法所得策略的性能要求高,實(shí)時(shí)性要求較低.OLR在允許的計(jì)算時(shí)間內(nèi)迭代優(yōu)化策略,可以突破規(guī)則和穩(wěn)態(tài)近似的性能瓶頸;較之基于MDP或隨機(jī)規(guī)劃的方法,較好地解決了策略規(guī)模隨零件數(shù)、階段數(shù)增加而爆炸的問題.本文組織如下:第1節(jié)對(duì)該問題進(jìn)行建模,并分析了模型的隨機(jī)性和可分性,進(jìn)而在第2節(jié)針對(duì)耦合約束為0-1變量的線性隨機(jī)耦合約束的特點(diǎn),給出了隨機(jī)耦合約束的期望值近似及相應(yīng)的OLR算法.第3節(jié)中的仿真結(jié)果顯示,OLR方法的性能不隨隨機(jī)性增強(qiáng)而受到影響;OLR在解耦決策變量的同時(shí),也將隨機(jī)因素的影響簡(jiǎn)化,降低了隨機(jī)策略的求解難度,同時(shí)得到了性能更優(yōu)的解.1聯(lián)合更換引擎服務(wù)下文中用到的主要符號(hào)的定義見表1.1.1零件的聯(lián)合更換模型考慮合約期為T天的引擎維護(hù)問題,每個(gè)階段t=0,···,T-1需考慮其進(jìn)站更換決策.引擎有N個(gè)壽命件,其規(guī)定使用壽命分別為S1.1.1剩余壽命x記壽命件n在第t天的剩余壽命為x這里d由上式可知,當(dāng)引擎處于維修中時(shí),剩余壽命x這里隱含假設(shè):若非在翼,即檢修中.在應(yīng)用中由于引擎成本高,其在翼時(shí)間主要由拆檢送修影響,極少出現(xiàn)正常工況引擎不在翼的情況,因此可認(rèn)為這一假設(shè)基本滿足1.1.2約期確定和隨機(jī)故障時(shí)壽命件剩余白堊系統(tǒng)故障轉(zhuǎn)變模型一個(gè)剩余壽命已經(jīng)為零的壽命件必須被更換,因此有以下強(qiáng)制更換約束:在合約期結(jié)束即第t=T天,壽命件n的剩余壽命要保證高于一個(gè)給定的水平x引擎綜合故障的發(fā)生用0-1變量ξ這里I當(dāng)壽命件到期或者隨機(jī)故障發(fā)生時(shí),需要送修引擎,即當(dāng)更換決策d以及由于隨機(jī)故障的存在,壽命件更換決策變量d1.1.3優(yōu)化目標(biāo)及期望維修費(fèi)用分為兩部分:1)每次的送修費(fèi)用c在這個(gè)優(yōu)化問題中,需要求解的決策變量是送修變量?由于狀態(tài)及決策變量均為隨機(jī)變量,這里的優(yōu)化目標(biāo)為總費(fèi)用的期望值.其期望是關(guān)于整個(gè)合約期[0T-1]內(nèi)的隨機(jī)故障發(fā)生情況的,即總費(fèi)用關(guān)于隨機(jī)故障的發(fā)生序列{ξ1.2同壽命件的決策變量在第1.1節(jié)所述模型中,目標(biāo)函數(shù)關(guān)于不同壽命件的決策變量是可加的.此外,所有的約束中,一些只包括單一壽命件的更換決策變量d在第t天,前t天內(nèi)的隨機(jī)故障的序列ξ2基于期望的似優(yōu)化模型和olr算法2.1新耦合約束的建立將上述模型中的隨機(jī)耦合約束(5)的左式用其期望來(lái)代替,即得到一個(gè)近似的耦合約束:這個(gè)新耦合約束本身是一個(gè)確定性的不等式,可知新約束是原來(lái)的隨機(jī)耦合約束成立的必要條件.記約束(9)的左式為由此可知用乘子該拉格朗日函數(shù)可以被分解為N個(gè)壽命件的子問題和一個(gè)進(jìn)站維修子問題來(lái)分別進(jìn)行最小化,下面將分別加以討論.2.2壽命件子問題的轉(zhuǎn)移方程壽命件n的子問題的目標(biāo)函數(shù)為要滿足的約束為(1)～(3).壽命件n的狀態(tài)轉(zhuǎn)移方程中含有進(jìn)站維修變量?上式中用max(d從式(12)可以看出L1)在式(12)中,由于各階段的費(fèi)用c2)由式(6)可知,隨機(jī)故障的因素只是通過(guò)進(jìn)站維修的決策?3)由上可知,決策變量是確定型的,即在壽命件子問題中Ed2.3顯式解的生成進(jìn)站維修子問題的目標(biāo)函數(shù)為注意到該目標(biāo)函數(shù)亦為對(duì)于各階段t線性可加的形式,因此在約束(6)下可以給出顯式解如下:這個(gè)顯式解的含義是,從無(wú)懲罰(λ注意到該顯式解是一個(gè)線性函數(shù),在臨界值附近對(duì)乘子的取值相當(dāng)敏感.為了減少震蕩,在算法中進(jìn)站維修的解采用Bang-bang控制的方法,在臨界值c2.4引擎維修成本的界面積到此為止已經(jīng)解決了兩類子問題的最優(yōu)化問題.下面就要在原問題的一組解d因此,Ed其中,步長(zhǎng)s則對(duì)于每個(gè)對(duì)偶問題的最優(yōu)解λ式(18)中q對(duì)于壽命件n來(lái)講,其更換的次數(shù)為v可以得出:則引擎維修成本的下界由下式給出:其中符號(hào)該絕對(duì)下界估計(jì)方法不依賴于樣本空間,所給出的下界是所有樣本軌道下問題性能的下界,并非僅僅是均值的下界,這也是本文的貢獻(xiàn)之一.3優(yōu)化算法性能本節(jié)給出OLR方法的數(shù)值測(cè)試及其與OT和OSA方法的比較結(jié)果,這三種方法的應(yīng)用方式如下1)OLR方法.每次進(jìn)站,根據(jù)當(dāng)前狀態(tài)優(yōu)化后續(xù)階段決策,取限定迭代步數(shù)內(nèi)使總費(fèi)用期望值最小的解.本次進(jìn)站時(shí)只采用當(dāng)前時(shí)刻的決策,后續(xù)進(jìn)站時(shí)基于之前的解和乘子進(jìn)一步迭代尋優(yōu),以得到更新后的決策,藉此保證決策的可行性.2)OT方法.遍歷[1,min3)OSA方法.每次進(jìn)站,根據(jù)當(dāng)前狀態(tài)得到一步前瞻下的最優(yōu)決策,具體參見文獻(xiàn)[2].由于OLR未像OT等方法一樣限定解的結(jié)構(gòu),且直接優(yōu)化有限階段的總費(fèi)用,而未像OSA等方法以平均費(fèi)用作估計(jì),因此在沒有簡(jiǎn)單形式的最優(yōu)策略的問題中,理論上OLR應(yīng)該可以較限定了策略結(jié)構(gòu)的算法得到更好的性能.大體上說(shuō),零件越能被同步更換,總費(fèi)用就越低.零件本身的差異性,包括零件壽命、價(jià)格及其初始狀態(tài),是影響聯(lián)合更換同步性的重要因素.在文獻(xiàn)[16]中已表明,零件壽命和價(jià)格相同,僅初始狀態(tài)不同時(shí),OLR方法可較OT、OSA更好的同步零件的更換.但對(duì)于零件壽命、價(jià)格和初始狀態(tài)均不相同的情況,由于問題本身復(fù)雜性大大增加,文獻(xiàn)[16]中的方法不易收斂得到足夠好的解.本文在文獻(xiàn)[16]基礎(chǔ)上的改善主要體現(xiàn)在:1)壽命件子問題中新的狀態(tài)轉(zhuǎn)移方程及相應(yīng)的求解;2)進(jìn)站子問題求解中的Bang-bang控制;3)給出一個(gè)下界算法,以改善求解對(duì)偶問題的步長(zhǎng)策略.這里將重點(diǎn)考察本文中經(jīng)過(guò)改善的OLR方法在零件不同的情況下(也是實(shí)際中最常見的情況下)的性能.測(cè)試用的聯(lián)合更換問題包括了中等規(guī)模和實(shí)際規(guī)模的算例,每組問題參數(shù)下均采用相同的隨機(jī)數(shù)產(chǎn)生仿真樣本軌道以比較三種方法所得策略下的平均費(fèi)用.3.1費(fèi)用及方差測(cè)試OLR方法在直觀上將隨機(jī)耦合約束以其期望代替,其性能勢(shì)必受到隨機(jī)因素大小的影響.特別是通過(guò)OLR方法將問題分解后,除進(jìn)站子問題外,零件子問題均轉(zhuǎn)化為確定性的問題,隨機(jī)因素的影響僅間接通過(guò)乘子有所體現(xiàn).隨故障率的不同,隨機(jī)因素對(duì)三個(gè)方法性能均有所影響,這里以參數(shù)如表2的一組中等規(guī)模問題做測(cè)試.考慮到實(shí)際中故障率為0.1以上的大型設(shè)備非常少見,PS1(1)～PS1(5)的故障率依次為0.1,0.05,0.02,0.01,0.005,其他參數(shù)相同.這組測(cè)試問題下三種方法的費(fèi)用均值及方差如表3.由圖1可看出,OLR方法的總費(fèi)用均值要低于其他方法,故障率越低OLR越有優(yōu)勢(shì).考慮統(tǒng)計(jì)因素后,OLR方法相對(duì)于其他方法仍能體現(xiàn)出優(yōu)勢(shì)故障率低時(shí)尤為明顯.這是由于故障率較低時(shí),即故障次數(shù)較少時(shí),每次故障時(shí)的更換決策差異會(huì)帶來(lái)顯著的性能差異.而當(dāng)故障率較高時(shí),由于故障次數(shù)較多,導(dǎo)致進(jìn)站頻繁發(fā)生,與決策無(wú)關(guān)的進(jìn)站費(fèi)用比例升高,可通過(guò)更換決策調(diào)整的費(fèi)用的優(yōu)化空間縮小,OLR方法相對(duì)于其他方法的優(yōu)勢(shì)不如故障率低時(shí)明顯,但仍能得到更優(yōu)的解.對(duì)于本文所研究的飛機(jī)引擎維修問題,由于設(shè)備的安全性對(duì)于飛行安全至關(guān)重要,因此其故障率往往都較低,在此類情況下,OLR方法相對(duì)其他方法優(yōu)勢(shì)較為明顯.當(dāng)故障率較低(故障率為0.01以及0.005)時(shí),OLR方法的方差要大于其他方法的方差.原因是OLR在一些樣本軌道上可得到費(fèi)用更低的解,因而拉大了方差.圖2和圖3分別展示了故障率為0.01以及0.005時(shí)三種方法在十條樣本軌道上的結(jié)果,可可以看出,OLR方法的性能在每條樣本軌道上均優(yōu)于或等于其他方法,體現(xiàn)出了OLR方法在低故障率問題上相對(duì)于其他問題的優(yōu)勢(shì).值得指出的是,結(jié)果中方差的來(lái)源主要是不同樣本軌道之間的差異,即發(fā)生故障的時(shí)刻不同帶來(lái)的差異.3.2界分也是最大費(fèi)用分區(qū)軌道,但同時(shí)也無(wú)絕對(duì)界段總費(fèi)用、絕對(duì)界軌道間距都存在顯著差異盡管引擎、電梯等維修合同通常的訂立期限為三至五年,但合同金額卻是以年為單位進(jìn)行約定和重新調(diào)整的.表4中給出合同期為一年、包含30個(gè)互不相同壽命件的維修問題PS2的參數(shù).限定最大迭代步數(shù)50下的OLR與OT和OSA進(jìn)行比較的結(jié)果如表5所示.其中下界為全部樣本的絕對(duì)下界J,間距為總費(fèi)用均值與該下界的間距.值得指出的是,OLR方法在測(cè)試樣本軌道下獲得的最小總費(fèi)用為214,與絕對(duì)下界197的間距僅為8.6%,驗(yàn)證了下界估計(jì)方法及OLR方法的有效性.由于其他樣本軌道的間距也是以197作為基礎(chǔ)進(jìn)行計(jì)算的,從而導(dǎo)致了總費(fèi)用均值與絕對(duì)下界的間距要大于最小樣本軌道下的間距8.6%.其他樣本軌道與最小費(fèi)用樣本軌道的費(fèi)用存在差異則是由問題本身的隨機(jī)性(即樣本軌道的差異)帶來(lái)的.具體來(lái)講,最小總費(fèi)用214所對(duì)應(yīng)的樣本軌道,OLR方法可以獲得較優(yōu)解.對(duì)于總費(fèi)用較高的樣本軌道,由于其故障發(fā)生次數(shù)多于最小樣本軌道,將導(dǎo)致更多的進(jìn)站次數(shù)以及進(jìn)站費(fèi)用,進(jìn)而導(dǎo)致總費(fèi)用的增加.相異零件難以看出類似相同零件情況下在實(shí)際使用當(dāng)中,在發(fā)生進(jìn)站后確定零件更換策略時(shí),OLR方法僅需知道故障率,無(wú)需知道未來(lái)故障發(fā)生的時(shí)刻即可作出決策.而OT與OSA方法需要知道完整的樣本軌道,因此需要對(duì)未來(lái)可能的樣本軌道進(jìn)行采樣以作出決策,這樣會(huì)引入采樣誤差.OT與OSA方法得到的結(jié)果對(duì)于其采樣得到的樣本軌道效果可能較優(yōu),但實(shí)際當(dāng)中難以出現(xiàn)采樣的樣本軌道完全等同于最終實(shí)現(xiàn)的樣本軌道這種理想情況.因此OLR方法更適合于實(shí)際使用,且不會(huì)引入采樣帶來(lái)的誤差,為此類隨機(jī)問題提供了不依賴樣本軌道的、具有擴(kuò)展性的方法,這也是本文的貢獻(xiàn)之一.4在估計(jì)模型上的應(yīng)用本文為零件聯(lián)合更換這一類存在隨機(jī)因素的多階段組合型決策問題提供了一種分解協(xié)調(diào)的算法OLR.該方法利用耦合約束的特征對(duì)問題進(jìn)行解耦進(jìn)而可避免仿真評(píng)價(jià)而直接得到當(dāng)前決策下對(duì)未來(lái)費(fèi)用的預(yù)期.這使得該方法不依賴于樣本空間,需引入的乘子數(shù)目與隨機(jī)約束個(gè)數(shù)同階,不再隨問題樣本軌道數(shù)目一同指數(shù)增長(zhǎng).這一特性有助于大規(guī)模問題可通過(guò)對(duì)偶方法求得近優(yōu)解.本文提供的下界估計(jì)方法可給出所有樣本軌道下的下界,作為對(duì)對(duì)偶問題最優(yōu)解的估計(jì),并利用Bang-bang控制策略緩解線性子問題的震蕩,從而大大提高對(duì)偶問題的求解效率.與已有算法OT與OSA相比,OLR方法無(wú)需對(duì)未來(lái)樣本軌道進(jìn)行采樣,避免了由采樣帶來(lái)的對(duì)決策評(píng)估的誤差.同時(shí),OLR方法的乘子提供了不同時(shí)間階段上決策的機(jī)會(huì)成本,有利于發(fā)現(xiàn)額外的問題結(jié)構(gòu)信息.并且,這一信息可以在序貫決策的各階段被保留并不斷更新,從而有助于提高求解效率.值得注意的是,OLR方法尚未像OT/OSA方法一樣直接利用最優(yōu)決策的特征結(jié)構(gòu)除本