陳春良， 劉 彥， 王生鳳， 陳偉龍， 昝 翔

(1. 陸軍裝甲兵學(xué)院裝備保障與再制造系， 北京100072； 2. 陸軍裝甲兵學(xué)院教研保障中心， 北京100072)

信息化條件下的現(xiàn)代戰(zhàn)爭(zhēng)突發(fā)性強(qiáng)、地域廣闊，作戰(zhàn)節(jié)奏越來(lái)越快，作戰(zhàn)進(jìn)程不斷縮短，對(duì)戰(zhàn)時(shí)裝備維修的時(shí)效性提出了更高的要求。如何在有限的維修時(shí)間、維修資源和維修能力約束下合理高效地安排維修任務(wù)，使待修裝備盡快地修復(fù)并歸建作戰(zhàn)部隊(duì)，已成為制約戰(zhàn)時(shí)裝備維修保障效果的重要因素。裝備維修任務(wù)調(diào)度是戰(zhàn)場(chǎng)搶救修理的研究重點(diǎn)和熱點(diǎn)，其通過(guò)合理分配維修資源、科學(xué)規(guī)劃維修任務(wù)順序優(yōu)化調(diào)度目標(biāo)，進(jìn)而提高維修效率，對(duì)戰(zhàn)場(chǎng)搶救修理具有重要的理論意義和應(yīng)用價(jià)值。筆者從調(diào)度理論、調(diào)度策略、調(diào)度模型及調(diào)度算法等方面對(duì)裝備維修任務(wù)調(diào)度研究進(jìn)行綜述，以期為戰(zhàn)時(shí)合理高效地開(kāi)展裝備維修工作提供理論與方法支撐。

1 裝備維修任務(wù)調(diào)度理論

調(diào)度是指在適當(dāng)?shù)臅r(shí)刻運(yùn)用適當(dāng)?shù)姆椒檫m當(dāng)?shù)挠脩舴峙溥m當(dāng)?shù)馁Y源，使系統(tǒng)高效地運(yùn)行，以達(dá)到特定的目的。調(diào)度問(wèn)題(Scheduling Problem)根據(jù)調(diào)度對(duì)象的不同可分為任務(wù)調(diào)度和作業(yè)調(diào)度。作業(yè)是指為完成生產(chǎn)或調(diào)度任務(wù)而執(zhí)行的基本活動(dòng)，任務(wù)是指一組共同提供相關(guān)功能的作業(yè)組合[1]。簡(jiǎn)言之，任務(wù)是由一系列作業(yè)組成，是一系列作業(yè)的統(tǒng)稱，如：裝備維修任務(wù)可分為行動(dòng)部分修理、火力部分修理以及通信部分修理等修理作業(yè)。本文中，具體的修理作業(yè)是維修任務(wù)的細(xì)化，因此將修理作業(yè)的調(diào)度歸為維修任務(wù)調(diào)度。

調(diào)度問(wèn)題自提出以來(lái)就迅速得到了廣泛運(yùn)用和深入研究，解決了許多工程實(shí)際問(wèn)題，如車間調(diào)度、列車調(diào)度和物流配送等，顯著提高了生產(chǎn)效率，并節(jié)約了生產(chǎn)成本。調(diào)度問(wèn)題在軍事領(lǐng)域也得到了廣泛運(yùn)用，如無(wú)人機(jī)任務(wù)調(diào)度[2]、衛(wèi)星偵察調(diào)度[3]和備件供應(yīng)[4]等。隨著組合優(yōu)化思想在工程實(shí)踐中的不斷應(yīng)用，調(diào)度問(wèn)題在軍事領(lǐng)域的研究也逐步得到重視。本文中，裝備維修任務(wù)調(diào)度是指在戰(zhàn)時(shí)裝備維修保障過(guò)程中，根據(jù)現(xiàn)有的保障資源、維修任務(wù)需求以及戰(zhàn)場(chǎng)態(tài)勢(shì)合理地調(diào)度維修任務(wù)，實(shí)現(xiàn)維修任務(wù)優(yōu)化調(diào)度的目的。

1.1 維修任務(wù)調(diào)度分類

1.1.1 搶占調(diào)度與非搶占調(diào)度

根據(jù)任務(wù)執(zhí)行過(guò)程中是否允許任務(wù)中斷，可將調(diào)度問(wèn)題分為搶占調(diào)度與非搶占調(diào)度。搶占調(diào)度[5-6]是指在任務(wù)執(zhí)行過(guò)程中，當(dāng)前執(zhí)行的任務(wù)可被更加重要或緊迫的任務(wù)中斷，相應(yīng)的資源被搶占，當(dāng)搶占任務(wù)完成后繼續(xù)執(zhí)行被搶占任務(wù)。非搶占調(diào)度[7]是指在任務(wù)執(zhí)行過(guò)程中，當(dāng)任務(wù)開(kāi)始執(zhí)行后就不能被中斷，無(wú)論其他任務(wù)有多重要或緊急，都必須等待當(dāng)前執(zhí)行的任務(wù)完成，資源釋放后方可執(zhí)行。

搶占調(diào)度的優(yōu)點(diǎn)是調(diào)度靈活，能夠較好地處理突發(fā)任務(wù)，但容易導(dǎo)致資源待機(jī)時(shí)間長(zhǎng)，特別是對(duì)資源需要轉(zhuǎn)場(chǎng)的任務(wù)，容易導(dǎo)致資源待機(jī)時(shí)間更長(zhǎng)，不利于全局調(diào)度任務(wù)的最優(yōu)化。與搶占調(diào)度比較，非搶占調(diào)度的優(yōu)點(diǎn)是避免了任務(wù)轉(zhuǎn)換的時(shí)間消耗，但調(diào)度不夠靈活，缺乏對(duì)突發(fā)任務(wù)的考慮。

LEVI等[8]以最小化維修費(fèi)用為目標(biāo)，針對(duì)空軍飛機(jī)模塊化系統(tǒng)的維修任務(wù)調(diào)度問(wèn)題，提出了非搶占調(diào)度模型及算法，實(shí)現(xiàn)了飛機(jī)模塊化系統(tǒng)的維修任務(wù)合理化調(diào)度。姚雙印等[9]將軍械裝備的維修任務(wù)調(diào)度問(wèn)題轉(zhuǎn)化為非搶占式調(diào)度車間任務(wù)調(diào)度問(wèn)題，并引入細(xì)菌覓食優(yōu)化算法(Bacteria Foraging Optimization Algorithm, BFOA)進(jìn)行模型求解。崔嘉等[10]考慮了航空定檢修理工作涉及多車間、多工種和多工序的問(wèn)題，對(duì)BFOA進(jìn)行了改進(jìn)，提高了算法的全局尋優(yōu)能力，對(duì)非搶占式維修任務(wù)工序進(jìn)行了調(diào)度優(yōu)化。

對(duì)于裝備維修任務(wù)調(diào)度問(wèn)題，目前國(guó)內(nèi)外的研究大多數(shù)是將其視為非搶占調(diào)度，認(rèn)為裝備維修任務(wù)在執(zhí)行過(guò)程中不能中斷，但由于戰(zhàn)時(shí)任務(wù)的突發(fā)性和緊急性，裝備維修任務(wù)搶占調(diào)度更符合實(shí)際情況，也更具有研究意義，但目前對(duì)裝備維修任務(wù)搶占調(diào)度問(wèn)題仍缺乏深入的研究。

1.1.2 靜態(tài)調(diào)度與動(dòng)態(tài)調(diào)度

根據(jù)任務(wù)分配方式可將調(diào)度問(wèn)題分為靜態(tài)調(diào)度[11]和動(dòng)態(tài)調(diào)度[12]。靜態(tài)調(diào)度是指在任務(wù)調(diào)度時(shí)，所有任務(wù)隊(duì)列中的任務(wù)執(zhí)行順序是確定的，不會(huì)隨著任務(wù)需求或資源約束等外部條件的變化而變化。動(dòng)態(tài)調(diào)度是指在任務(wù)執(zhí)行過(guò)程中需根據(jù)任務(wù)需求及相關(guān)約束確定下一個(gè)任務(wù)的執(zhí)行順序，即在任務(wù)隊(duì)列中不斷地動(dòng)態(tài)調(diào)整任務(wù)的執(zhí)行順序[13]。

靜態(tài)調(diào)度的優(yōu)點(diǎn)是可預(yù)測(cè)性強(qiáng),調(diào)度過(guò)程簡(jiǎn)單，適用于任務(wù)需求確定的調(diào)度問(wèn)題，但調(diào)度的靈活性相對(duì)較差，難以解決任務(wù)需求、任務(wù)執(zhí)行過(guò)程以及調(diào)度過(guò)程中的不確定性問(wèn)題，因此難以實(shí)現(xiàn)全局最優(yōu)。動(dòng)態(tài)調(diào)度較為靈活，能夠根據(jù)不斷出現(xiàn)的任務(wù)需求和不斷變化的資源約束實(shí)時(shí)地調(diào)整調(diào)度任務(wù)的執(zhí)行順序，在工程實(shí)踐中得到了廣泛運(yùn)用。

在靜態(tài)裝備維修任務(wù)調(diào)度中，可將每次維修任務(wù)執(zhí)行前的決策看作任務(wù)分配，進(jìn)而抽象為指派問(wèn)題進(jìn)行建模與求解。由于裝備維修任務(wù)需求的動(dòng)態(tài)性，目前裝備維修任務(wù)調(diào)度的研究多以動(dòng)態(tài)調(diào)度為主，但涉及的約束條件較為簡(jiǎn)單和理想化，有待根據(jù)戰(zhàn)場(chǎng)情況合理抽象約束條件，對(duì)維修任務(wù)調(diào)度模型進(jìn)行深入研究。

1.2 維修任務(wù)調(diào)度策略

維修任務(wù)調(diào)度策略是維修任務(wù)調(diào)度的關(guān)鍵，常見(jiàn)的維修任務(wù)調(diào)度策略包括時(shí)鐘驅(qū)動(dòng)調(diào)度策略[14]、優(yōu)先級(jí)調(diào)度策略以及其他維修調(diào)度策略。

1) 時(shí)鐘驅(qū)動(dòng)調(diào)度策略與優(yōu)先級(jí)調(diào)度策略

時(shí)鐘驅(qū)動(dòng)調(diào)度策略是指在維修任務(wù)開(kāi)始執(zhí)行后選擇一個(gè)固定的時(shí)刻，當(dāng)?shù)竭_(dá)該時(shí)刻時(shí)對(duì)維修任務(wù)重新調(diào)度，并決定任務(wù)的執(zhí)行順序。優(yōu)先級(jí)調(diào)度策略是指在調(diào)度前對(duì)每個(gè)維修任務(wù)賦予一個(gè)優(yōu)先級(jí)，當(dāng)需要對(duì)多個(gè)維修任務(wù)分配維修力量時(shí)，則根據(jù)維修任務(wù)的優(yōu)先級(jí)高低執(zhí)行任務(wù)，優(yōu)先執(zhí)行優(yōu)先級(jí)高的任務(wù)。

優(yōu)先級(jí)調(diào)度策略是事件驅(qū)動(dòng)，而時(shí)鐘驅(qū)動(dòng)調(diào)度策略是時(shí)鐘驅(qū)動(dòng)，二者之間有本質(zhì)區(qū)別。對(duì)于維修任務(wù)調(diào)度，時(shí)鐘驅(qū)動(dòng)調(diào)度策略易導(dǎo)致當(dāng)前維修任務(wù)還未完成而時(shí)鐘驅(qū)動(dòng)觸發(fā)，維修力量中斷當(dāng)前任務(wù)轉(zhuǎn)而執(zhí)行其他任務(wù)，這一方面與戰(zhàn)時(shí)裝備維修實(shí)際不符，另一方面也增加了維修力量的轉(zhuǎn)場(chǎng)時(shí)間。相對(duì)而言，優(yōu)先級(jí)調(diào)度策略在維修任務(wù)調(diào)度中運(yùn)用更為廣泛，并逐漸演化出固定優(yōu)先級(jí)調(diào)度[15-16]和動(dòng)態(tài)優(yōu)先級(jí)調(diào)度[17-18]。

由戰(zhàn)時(shí)裝備維修任務(wù)及其維修任務(wù)調(diào)度的特點(diǎn)可知：戰(zhàn)時(shí)裝備維修任務(wù)調(diào)度采取優(yōu)先級(jí)調(diào)度策略，或者以優(yōu)先級(jí)調(diào)度策略為主進(jìn)行調(diào)度更符合戰(zhàn)場(chǎng)實(shí)際，而任務(wù)優(yōu)先級(jí)的確定是進(jìn)行優(yōu)先級(jí)調(diào)度的基礎(chǔ)。維修任務(wù)優(yōu)先級(jí)反映了各維修任務(wù)的相對(duì)重要程度，其決定因素包括裝備類型、裝備損傷程度、裝備對(duì)戰(zhàn)斗的重要程度以及待修裝備與維修力量之間的距離等。求解維修任務(wù)優(yōu)先級(jí)的實(shí)質(zhì)是對(duì)維修任務(wù)的重要程度進(jìn)行排序，屬于典型的多屬性決策問(wèn)題[19]。

2) 其他維修調(diào)度策略

其他維修調(diào)度策略主要有故障驅(qū)動(dòng)策略、維修力量驅(qū)動(dòng)策略和維修資源需求策略。其中：故障驅(qū)動(dòng)策略包括先到先服務(wù)(First Come First Sever, FCFS)策略[20]、后到先服務(wù)(Last Come First Sever, LCFS)策略[21]、最短平均處理時(shí)間(Shortest Mean Process Time, SMPT)策略[22]、最長(zhǎng)平均處理時(shí)間(Longest Mean Process Time, LMPT)策略[23]、預(yù)測(cè)最早完工時(shí)間(Estimated Earliest Time To Complete, EETTC)策略[24]、預(yù)測(cè)最遲完工時(shí)間(Estimated Latest Time To Complete, ELTTC)策略[24]和改進(jìn)優(yōu)先級(jí)聯(lián)合策略[25]；維修力量驅(qū)動(dòng)策略包括最近修理(Nearest Dispatch, ND)策略[26]和預(yù)測(cè)性修理(Anticipatory Dispatch, AD)策略[27]；維修資源需求策略包括最小累積資源需求(MINimum Cumulated Resource Demand，MINCRD)策略[28]、最大累積資源需求(MAXimum Cumulated Resource Demand，MAXCRD)策略[28]、先到先服務(wù)與最小累積資源需求混合(FCFS & MINCRD)策略[29]、后到先服務(wù)與最大累積資源需求混合(LCFS & MAXCRD)策略[29]。

總體來(lái)看，在裝備維修任務(wù)調(diào)度策略中，優(yōu)先級(jí)調(diào)度策略的應(yīng)用最為廣泛，多種調(diào)度策略的綜合運(yùn)用是裝備維修任務(wù)調(diào)度策略的發(fā)展趨勢(shì)。在明確裝備維修任務(wù)調(diào)度分類及調(diào)度策略的基礎(chǔ)上，如何構(gòu)建和構(gòu)造裝備維修任務(wù)調(diào)度模型及算法是求解裝備維修任務(wù)調(diào)度問(wèn)題的關(guān)鍵。

2 裝備維修任務(wù)調(diào)度模型研究現(xiàn)狀

維修任務(wù)調(diào)度問(wèn)題是調(diào)度問(wèn)題在軍事學(xué)領(lǐng)域的延伸。從裝備維修保障的角度來(lái)看，若將修理組看作旅行商問(wèn)題的旅行商，則維修任務(wù)調(diào)度問(wèn)題可抽象為旅行商問(wèn)題；若將修理組看作車輛路徑問(wèn)題的車輛，則維修任務(wù)調(diào)度問(wèn)題可抽象為車輛路徑問(wèn)題；若將維修任務(wù)看作項(xiàng)目調(diào)度的項(xiàng)目，則維修任務(wù)調(diào)度問(wèn)題可抽象為項(xiàng)目調(diào)度問(wèn)題；若考慮維修任務(wù)中的各項(xiàng)修理作業(yè)，則維修任務(wù)調(diào)度問(wèn)題可抽象為車間調(diào)度問(wèn)題。因此，筆者重點(diǎn)對(duì)上述4種典型調(diào)度模型及其算法進(jìn)行綜述。

2.1 旅行商問(wèn)題

旅行商問(wèn)題(Traveling Salesman Problem, TSP)[30]又稱為貨郎擔(dān)問(wèn)題，最早可追溯到18世紀(jì)，是組合優(yōu)化領(lǐng)域中的一個(gè)經(jīng)典難題，被證明是NP-Hard (Non-deterministic Polynomial-Hard)問(wèn)題。TSP可簡(jiǎn)單地描述為1個(gè)旅行商人要拜訪N個(gè)城市，從初始城市出發(fā)，每個(gè)城市都必須拜訪且只能拜訪1次，最終回到起點(diǎn)，如何選擇拜訪路徑使總路徑最短[31]。

在傳統(tǒng)TSP中，假設(shè)城市數(shù)量、距離固定不變的條件過(guò)于理想化，不能滿足現(xiàn)實(shí)問(wèn)題的研究需求。國(guó)內(nèi)外學(xué)者對(duì)TSP進(jìn)行了深入研究，使TSP逐漸演化出許多更符合實(shí)際的復(fù)雜TSP，最典型的包括以下3類：

1) 動(dòng)態(tài)旅行商問(wèn)題(Dynamic Traveling Salesman Problem, DTSP)。DTSP是根據(jù)傳統(tǒng)TSP中城市數(shù)量及距離動(dòng)態(tài)變化而演化出來(lái)的，可描述為TSP中城市之間的交通路線權(quán)重(距離)隨時(shí)間等因素動(dòng)態(tài)變化，且在調(diào)度過(guò)程中會(huì)有新城市加入[32]。DTSP問(wèn)題大大增加了模型的復(fù)雜性，但更貼近實(shí)際，可用來(lái)描述貨物配送、快遞員取件等問(wèn)題。

2) 多目標(biāo)旅行商問(wèn)題(Multi-Objective Traveling Salesman Problem, MOTSP)。MOTSP是傳統(tǒng)TSP的擴(kuò)展，其目標(biāo)不僅包括TSP總距離最短，也包括時(shí)間最短、費(fèi)用最小、風(fēng)險(xiǎn)最低、增加客戶滿意度等多種目標(biāo)。MOTSP的求解方法一般包括2種：一是通過(guò)目標(biāo)轉(zhuǎn)換、決策偏好加權(quán)等方法將多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題進(jìn)行求解[33]；二是求解多目標(biāo)的Pareto優(yōu)化解集[34]。

3) 多人旅行商問(wèn)題(Multi-Person Traveling Salesman Problem, MPTSP)。MPTSP將TSP中單個(gè)旅行商擴(kuò)展為多個(gè)旅行商[35]，根據(jù)旅行商出發(fā)城市及終點(diǎn)的不同又可細(xì)分為多類。MPTSP自提出以來(lái)，各國(guó)學(xué)者就不斷地尋找求解方法，GAVISH等[36]通過(guò)改進(jìn)分支界定法求解MPTSP，將TSP的求解空間規(guī)模擴(kuò)大到100個(gè)城市；SINGH等[37]將遺傳算法中染色體編碼運(yùn)用到MPTSP中；SONG等[38]運(yùn)用改進(jìn)的模擬退火算法解決了3個(gè)旅行商400個(gè)城市的MPTSP?？傮w來(lái)看，現(xiàn)有研究可較好地解決規(guī)模較小的MPTSP，但復(fù)雜的MPTSP仍然是人們關(guān)心的問(wèn)題。

目前，雖然TSP得到廣泛應(yīng)用和研究，但幾乎沒(méi)有學(xué)者將裝備維修任務(wù)調(diào)度問(wèn)題抽象為旅行商問(wèn)題進(jìn)行研究。然而，對(duì)于裝備維修任務(wù)調(diào)度，當(dāng)考慮伴隨修理以及巡回修理時(shí)，可將修理組看作旅行商，將待修裝備看作城市，從而將裝備維修任務(wù)調(diào)度問(wèn)題轉(zhuǎn)化為TSP，并可根據(jù)修理組數(shù)量、調(diào)度目標(biāo)數(shù)量以及待修裝備是否動(dòng)態(tài)出現(xiàn)等特性進(jìn)一步細(xì)化調(diào)度模型，確定約束條件，構(gòu)造相應(yīng)算法進(jìn)行調(diào)度模型的求解。

2.2 車輛路徑問(wèn)題

車輛路徑問(wèn)題(Vehicle Routing Problem，VRP)可看作TSP與背包問(wèn)題(Knapsack Problem，KP)的組合，其作為TSP的一個(gè)衍生問(wèn)題最早由DANTZIG等[39]于1959年首次提出，VRP可描述為由1組車輛從1個(gè)或多個(gè)車場(chǎng)點(diǎn)出發(fā)對(duì)一系列顧客點(diǎn)進(jìn)行服務(wù)，要求每個(gè)顧客點(diǎn)都必須被服務(wù)且只能由1輛車服務(wù)，所有車輛都從車場(chǎng)出發(fā)，最終回到車場(chǎng)，目標(biāo)是總費(fèi)用最小[40]。VRP自提出以來(lái)廣泛運(yùn)用于現(xiàn)實(shí)生活，如校車接送安排、城市垃圾收集、牛奶配送和快遞配送等。對(duì)于維修任務(wù)調(diào)度，也可將其視為特殊的VRP。

隨著各國(guó)學(xué)者對(duì)VRP研究的不斷深入，引入了各種更貼近實(shí)際的限制條件，演化出一系列VRP擴(kuò)展問(wèn)題。VRP的構(gòu)成要素包括車輛、車場(chǎng)點(diǎn)、顧客、道路與邊約束[41]以及調(diào)度目標(biāo)等。根據(jù)構(gòu)成要素對(duì)VRP擴(kuò)展問(wèn)題進(jìn)行分類梳理，如表1所示。

1) 帶容量限制的車輛路徑問(wèn)題(Capacitated Vehicle Routing Problem，CVRP)[42]。CVRP是指對(duì)于VRP中的每輛車輛，都有裝載能力的限制。

2) 帶時(shí)間窗限制的車輛路徑問(wèn)題(Vehicle Routing Problem with Time Windows，VRPTM)。VRPTM是對(duì)VRP中的每個(gè)顧客增加了服務(wù)窗口限制，即車輛對(duì)于每個(gè)顧客的服務(wù)必須在相應(yīng)的時(shí)間窗內(nèi)完成。根據(jù)時(shí)間窗的性質(zhì)不同，VRPTM可進(jìn)一步分為硬時(shí)間窗車輛路徑問(wèn)題(Vehicle Routing Problem with Hard Time Windows，VRPHTM)和軟時(shí)間窗車輛路徑問(wèn)題(Vehicle Routing Problem with Soft Time Windows，VRPSTM)，其中：VRPHTM是指車輛對(duì)每個(gè)顧客的服務(wù)必須在相應(yīng)的時(shí)間窗內(nèi)完成，如果超出時(shí)間窗，則認(rèn)為該次調(diào)度無(wú)效，即為非可行解[43]；VRPSTM是指車輛對(duì)每個(gè)顧客的服務(wù)可不在相應(yīng)的時(shí)間窗內(nèi)完成，若超出該時(shí)間窗則對(duì)目標(biāo)函數(shù)進(jìn)行懲罰[44]。

表1 車輛路徑問(wèn)題及其演化問(wèn)題分類

3) 帶分割的車輛路徑問(wèn)題(Vehicle Routing Problem with Split Deliveries，VRPSD)。VRPSD由DROR等[45]于1989年首次提出，與傳統(tǒng)VRP中每個(gè)顧客的服務(wù)需求必須由1輛車來(lái)滿足不同，VRPSD中顧客的服務(wù)需求可由多輛車分割服務(wù)[46]。VRPSD在現(xiàn)實(shí)生活中應(yīng)用廣泛，MULLASERIL等[47]將卡車配送牧場(chǎng)飼料的問(wèn)題抽象為VRPSD；SIERKSMA等[48]將VRPSD引入直升機(jī)航班安排；LAI等[49]運(yùn)用VRPSD解決了食物配送問(wèn)題。除此之外，VRPSD還廣泛運(yùn)用于物資配送[50]、海上游輪調(diào)度[51]和搶險(xiǎn)救災(zāi)問(wèn)題[52]等。

4) 開(kāi)放式車輛路徑問(wèn)題(Open Vehicle Routing Problem，OVRP)。OVRP由SCHRAGE[53]于1981年首次提出，與傳統(tǒng)VRP中車輛必須返回出發(fā)車場(chǎng)不同，OVRP中的車輛完成顧客服務(wù)后不必返回車場(chǎng)。

5)異型車輛路徑問(wèn)題(Heterogeneous Fleet Vehicle Routing Problem，HFVRP)。HFVRP作為VRP的變異問(wèn)題，更加貼近實(shí)際，其與傳統(tǒng)VRP的區(qū)別是HFVRP中允許存在不同的車輛。

6)動(dòng)態(tài)車輛路徑問(wèn)題(Dynamic Vehicle Routing Problem，DVRP)。DVRP由PSARAFITS[54]于1988年首次提出，與靜態(tài)車輛路徑問(wèn)題不同，DVRP是指在調(diào)度前只知道部分顧客需求信息，其他信息將在調(diào)度過(guò)程中相繼明確，且顧客需求在調(diào)度過(guò)程中會(huì)發(fā)生改變[40]。

根據(jù)服務(wù)需求信息可將VRP問(wèn)題分成4類：靜態(tài)確定問(wèn)題、靜態(tài)隨機(jī)問(wèn)題、動(dòng)態(tài)確定問(wèn)題和動(dòng)態(tài)隨機(jī)問(wèn)題[55]。其中，前二類是傳統(tǒng)意義上的VRP，后二類構(gòu)成了DVRP。對(duì)于靜態(tài)確定問(wèn)題，模型中所有的輸入在進(jìn)行車輛調(diào)度前是已知的，不會(huì)隨著調(diào)度的執(zhí)行而改變[56]。對(duì)于靜態(tài)隨機(jī)問(wèn)題，模型的部分輸入是隨機(jī)變量，并在調(diào)度過(guò)程中逐漸明確，通常包括隨機(jī)顧客、隨機(jī)時(shí)間和隨機(jī)需求3種主要形式：1) 隨機(jī)顧客，即所需服務(wù)的顧客是隨機(jī)的；2) 隨機(jī)時(shí)間，即服務(wù)的時(shí)間或旅行時(shí)間是隨機(jī)的；3) 隨機(jī)需求，即顧客的需求是隨機(jī)的。對(duì)于動(dòng)態(tài)確定問(wèn)題，部分或全部輸入是未知的，在制訂調(diào)度計(jì)劃或調(diào)度過(guò)程中會(huì)動(dòng)態(tài)明確[57]。對(duì)于動(dòng)態(tài)隨機(jī)問(wèn)題，部分或全部輸入是未知的，在制訂調(diào)度計(jì)劃或調(diào)度過(guò)程中顧客、顧客需求以及服務(wù)時(shí)間會(huì)發(fā)生動(dòng)態(tài)的變化[58]。

由于DVRP的研究對(duì)解決現(xiàn)實(shí)生活中的物流配送、交通運(yùn)輸和出租車載客等問(wèn)題具有重大意義[59]，因此國(guó)內(nèi)外研究者對(duì)DVRP進(jìn)行了深入研究。在DVRP模型方面，BERTSIMAS等[60]在靜態(tài)VRP模型的基礎(chǔ)上，引入排隊(duì)論模型較好地解決了修理員動(dòng)態(tài)修理問(wèn)題；MINKOFF[61]針對(duì)小規(guī)模DVRP提出了馬爾可夫模型；TEODOROVIC等[62]通過(guò)用模糊數(shù)來(lái)表示信息的模糊性以及決策者的偏好，建立了模糊顧客需求的DVRP模型；PAVONE等[63]考慮顧客等待耐心的因素，通過(guò)引入懲罰函數(shù)建立了DVRP模型；謝秉磊等[64]考慮路網(wǎng)結(jié)構(gòu)、容量限制以及負(fù)載均衡，建立了帶臨時(shí)補(bǔ)充點(diǎn)的融雪劑撒布車輛路徑模型；葛顯龍等[65]針對(duì)商業(yè)中心相對(duì)分散的問(wèn)題，以運(yùn)輸距離、運(yùn)輸成本為目標(biāo)，構(gòu)建了城市物流聯(lián)合配送DVRP模型；陳偉龍等[66]將進(jìn)攻作戰(zhàn)搶修任務(wù)調(diào)度問(wèn)題抽象為開(kāi)放式多車場(chǎng)車輛路徑問(wèn)題，以二次作戰(zhàn)時(shí)間為目標(biāo)函數(shù)，設(shè)計(jì)了變體遺傳算法進(jìn)行了模型求解，并驗(yàn)證了模型的可行性；陳偉龍等[67]還考慮了搶修時(shí)間、搶修能力以及修復(fù)狀態(tài)的不確定性等因素，將進(jìn)攻作戰(zhàn)搶修任務(wù)調(diào)度問(wèn)題抽象為動(dòng)態(tài)車輛路徑問(wèn)題，針對(duì)多目標(biāo)優(yōu)化問(wèn)題設(shè)計(jì)了遺傳算法求解Pareto解。以上研究為車輛路徑問(wèn)題在裝備維修任務(wù)調(diào)度方面的研究提供了良好的思路。

在裝備維修任務(wù)調(diào)度中，可將修理組看作VRP中的車輛，各修理組攜帶的備品備件有攜帶能力限制，將各修理組攜帶的備品備件限制看作車輛的容量限制，則維修任務(wù)調(diào)度問(wèn)題可轉(zhuǎn)化為帶容量限制的車輛路徑問(wèn)題(CVRP)；若考慮待修裝備對(duì)修復(fù)時(shí)間的要求，則可將裝備維修任務(wù)調(diào)度問(wèn)題抽象為特殊的帶時(shí)間窗限制的車輛路徑問(wèn)題(VRPTM)；若裝備維修任務(wù)需要多個(gè)修理組協(xié)同完成，則可將裝備維修任務(wù)調(diào)度問(wèn)題抽象為特殊的帶分割的車輛路徑問(wèn)題(VRPSD)；在伴隨維修中，修理組在完成既定任務(wù)后還需要伴隨保障部隊(duì)進(jìn)行后續(xù)作戰(zhàn)任務(wù)，修理組不會(huì)返回原出發(fā)點(diǎn)，則可將裝備維修任務(wù)調(diào)度問(wèn)題看成是開(kāi)放式車輛路徑問(wèn)題(OVRP)；各修理組的維修能力存在差異，各修理組攜帶的備品備件存在差異，則可將裝備維修任務(wù)調(diào)度問(wèn)題看成是異型車輛路徑問(wèn)題(HFVRP)；由于裝備不斷發(fā)生戰(zhàn)損，調(diào)度方案隨著待修裝備的出現(xiàn)需要?jiǎng)討B(tài)調(diào)整，則可將裝備維修任務(wù)調(diào)度抽象為動(dòng)態(tài)車輛路徑問(wèn)題(DVRP)。

2.3 項(xiàng)目調(diào)度問(wèn)題

項(xiàng)目調(diào)度問(wèn)題(Project Scheduling Problem，PSP)是指在時(shí)間和資源的限制下合理計(jì)劃和安排項(xiàng)目進(jìn)度以高效達(dá)到項(xiàng)目目標(biāo)[68]。由于資源約束是項(xiàng)目調(diào)度的最常見(jiàn)約束，因此資源受限的項(xiàng)目調(diào)度問(wèn)題(Resource-Constrained Project Scheduling Problem，RCPSP)得到廣泛研究。

RCPSP通常從資源、任務(wù)以及目標(biāo)函數(shù)3方面進(jìn)行分類[69]，三者之間隨機(jī)組合構(gòu)成了各種類型的RCPSP。資源可分為可更新資源、不可更新資源以及雙重約束資源[70]，其中：可更新資源是指在調(diào)度的各個(gè)階段可隨時(shí)補(bǔ)充的、固定不變的資源，對(duì)于裝備維修任務(wù)調(diào)度，若不考慮維修人員的傷亡及維修設(shè)備的損壞，則可將維修人員及維修設(shè)備看作可更新資源；不可更新資源是指在調(diào)度過(guò)程中隨著使用而不斷消耗的資源，對(duì)于裝備維修任務(wù)調(diào)度，若認(rèn)為修理組攜帶的備件數(shù)量有限，則可將備件看作不可更新資源；雙重約束資源是指在調(diào)度的各個(gè)階段都有約束，且在整個(gè)調(diào)度過(guò)程的總量也有限制的資源[71]，對(duì)于裝備維修任務(wù)調(diào)度，若考慮整個(gè)維修時(shí)限及各階段的維修時(shí)限，則可將時(shí)間視為雙重約束資源。近年來(lái)，研究者提出了部分可更新資源概念[72]，其介于可更新資源與不可更新資源之間，對(duì)于裝備維修任務(wù)調(diào)度，若考慮維修人員的休息時(shí)間及設(shè)備的維修保養(yǎng)時(shí)間，則可將維修人員及設(shè)備視為部分可更新資源。

RCPSP根據(jù)項(xiàng)目數(shù)量可分為單項(xiàng)目RCPSP和多項(xiàng)目RCPSP；根據(jù)執(zhí)行模式可分為單模式RCPSP和多模式RCPSP[73]；根據(jù)任務(wù)是否可搶占可分為可搶占RCPSP和不可搶占RCPSP；根據(jù)資源的特性演化出柔性資源約束項(xiàng)目調(diào)度問(wèn)題(Flexible Resource-Constrained Project Scheduling Problem，F(xiàn)RCPSP)。呂學(xué)志等[25]將任務(wù)間隔期裝備維修任務(wù)調(diào)度問(wèn)題抽象為FRCPSP，并將其稱為柔性資源約束維修任務(wù)調(diào)度問(wèn)題(Maintain Test-Flexible Resource Constrained Project Scheduling Problem，MT-FRCPSP)。

總體來(lái)說(shuō)，項(xiàng)目調(diào)度模型是時(shí)間、資源約束調(diào)度問(wèn)題的基本模型，許多實(shí)際問(wèn)題都能抽象為帶實(shí)際約束的項(xiàng)目調(diào)度問(wèn)題，并可通過(guò)啟發(fā)式算法或智能算法求解，為解決實(shí)際生活中的調(diào)度問(wèn)題提供了模型基礎(chǔ)，如作業(yè)車間調(diào)度問(wèn)題、流水車間調(diào)度問(wèn)題等。呂學(xué)志等[25]將維修人員、設(shè)備看作可更新的柔性資源，將任務(wù)間隔期內(nèi)的裝備維修任務(wù)調(diào)度問(wèn)題抽象為RCPSP，分別考慮柔性資源約束、隨機(jī)工期約束以及技能差異約束，構(gòu)建了任務(wù)間隔期維修任務(wù)調(diào)度模型，具有一定的借鑒意義。但其研究的前提是任務(wù)間隔期內(nèi)的維修任務(wù)調(diào)度問(wèn)題，而戰(zhàn)時(shí)裝備維修特別是戰(zhàn)術(shù)級(jí)裝備維修通常采取伴隨修理為主，巡回修理與定點(diǎn)修理相結(jié)合的方式。因此,將裝備維修任務(wù)調(diào)度問(wèn)題抽象為RCPSP，對(duì)定點(diǎn)修理具有一定指導(dǎo)意義，但對(duì)伴隨修理和巡回修理并不是很合理。

對(duì)于定點(diǎn)修理或基地級(jí)修理的裝備維修任務(wù)調(diào)度問(wèn)題，可將維修人員、設(shè)備和備品備件等作為項(xiàng)目調(diào)度(PSP)中的資源。根據(jù)調(diào)度實(shí)際抽象出資源約束條件，結(jié)合修理工期等時(shí)間約束、修理技能等能力約束，抽象為資源受限的項(xiàng)目調(diào)度問(wèn)題(RCPSP)，并采取啟發(fā)式算法或智能算法進(jìn)行求解。

2.4 車間調(diào)度問(wèn)題

車間調(diào)度問(wèn)題(Shop Scheduling Problem，SSP)是項(xiàng)目調(diào)度問(wèn)題的進(jìn)一步演化，是一種資源分配與調(diào)度問(wèn)題，可簡(jiǎn)單地描述為n個(gè)工件在m臺(tái)機(jī)器上加工，每個(gè)工件有多道工序，機(jī)器可執(zhí)行多道工序，但各機(jī)器可執(zhí)行的工序不完全相同，主要解決如何為各工件安排機(jī)器，為工件安排加工次序及加工起止時(shí)間，進(jìn)而實(shí)現(xiàn)調(diào)度目標(biāo)的最優(yōu)化[74]。根據(jù)機(jī)器功能、工件工序以及工序順序,可將車間調(diào)度問(wèn)題分為以下3類[75]：

1) 作業(yè)車間調(diào)度問(wèn)題(Job-shop Scheduling Problem，JSP)。系統(tǒng)中有多臺(tái)功能不同的機(jī)器，各工件有多道工序，每道工序只能在1臺(tái)機(jī)器上執(zhí)行，各工件的加工路徑不同，各工序間有順序要求。

2) 流水車間調(diào)度問(wèn)題(Flow Shop Scheduling Problem，F(xiàn)SSP)。與JSP的條件一樣。

3) 開(kāi)放車間調(diào)度問(wèn)題(Open Shop Scheduling Problem，OSSP)。各工件加工路徑?jīng)]有約束，各工序的加工順序沒(méi)有約束。

隨著車間調(diào)度問(wèn)題研究的不斷深入，在以上3類問(wèn)題的基礎(chǔ)上逐漸演化出柔性作業(yè)車間調(diào)度問(wèn)題(Flexible Job-shop Scheduling Problem，F(xiàn)JSP)、多目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題(Multi-Objective Flexible Job-shop Scheduling Problem，MOFJSP)、混合流水車間調(diào)度問(wèn)題(Hybrid Flow Shop Scheduling Problem，HFSSP)等多種新問(wèn)題，實(shí)際車間加工過(guò)程一般是多種車間調(diào)度問(wèn)題的混合問(wèn)題。

在裝備維修任務(wù)調(diào)度方面，孫志剛等[76]考慮了定點(diǎn)維修機(jī)構(gòu)內(nèi)維修專業(yè)的設(shè)置問(wèn)題，將批量維修任務(wù)調(diào)度問(wèn)題抽象為置換流水車間調(diào)度問(wèn)題，并采用最長(zhǎng)加工時(shí)間啟發(fā)式算法進(jìn)行了模型求解。朱昱等[77]針對(duì)裝備維修廠(所)的維修任務(wù)調(diào)度問(wèn)題，考慮到維修流程，將多單元維修任務(wù)調(diào)度問(wèn)題抽象為置換流水車間調(diào)度問(wèn)題，并設(shè)計(jì)了NEH(Nawaz,Enscore and Ham)迭代式算法用于模型求解。

總體來(lái)說(shuō)，在裝備維修任務(wù)調(diào)度方面，對(duì)于定點(diǎn)修理或基地級(jí)修理，在某種程度上可將裝備維修任務(wù)進(jìn)一步細(xì)化，考慮各修理工種及工序的相關(guān)約束，將裝備維修任務(wù)調(diào)度問(wèn)題轉(zhuǎn)換為車間調(diào)度問(wèn)題(SSP)，并考慮維修資源、維修專業(yè)和維修流程等現(xiàn)實(shí)問(wèn)題，合理確定調(diào)度目標(biāo)并抽象出約束條件，從而選擇合適的調(diào)度算法進(jìn)行模型求解。

3 維修任務(wù)調(diào)度算法研究現(xiàn)狀

隨著TSP、VRP、PSP和SSP等調(diào)度模型問(wèn)題研究的不斷完善和深入，調(diào)度模型求解問(wèn)題已逐漸成為維修任務(wù)調(diào)度研究的重點(diǎn)，涌現(xiàn)出許多求解算法。總體來(lái)說(shuō)，維修任務(wù)調(diào)度模型的求解算法可分為精確算法[78]與啟發(fā)式算法[79]。精確算法通過(guò)搜索整個(gè)問(wèn)題的解空間以求得最優(yōu)解，當(dāng)模型復(fù)雜、求解規(guī)模較大時(shí)，精確算法所需的求解時(shí)間急劇增加，容易發(fā)生指數(shù)爆炸問(wèn)題，因此，在應(yīng)用中具有一定的局限性。啟發(fā)式算法不需要求出確切的最優(yōu)解，僅以在合理時(shí)間內(nèi)得出滿意解為目標(biāo)，因此，相對(duì)精確算法而言，其應(yīng)用更為廣泛。

各種算法在求解調(diào)度模型時(shí)都具有自身的局限性，所構(gòu)造的調(diào)度模型類型、約束條件和調(diào)度目標(biāo)等因素均會(huì)影響調(diào)度算法的選擇，同時(shí)，算法的計(jì)算時(shí)間、收斂速度、魯棒性和可靠性等也是衡量算法優(yōu)劣的重要因素。筆者僅針對(duì)不同維修任務(wù)調(diào)度模型來(lái)綜述相應(yīng)模型求解算法的研究現(xiàn)狀。

3.1 旅行商問(wèn)題求解算法

隨著TSP研究的不斷深入，相應(yīng)的求解算法已成為TSP研究的重點(diǎn)，主要有精確算法和啟發(fā)式算法2個(gè)方向。求解TSP的精確算法主要包括分支界定法[80]、線性規(guī)劃法和動(dòng)態(tài)規(guī)劃法等。由于精確算法需要精確求解，當(dāng)TSP規(guī)模較大時(shí)，其計(jì)算復(fù)雜度呈指數(shù)增長(zhǎng)，需要消耗巨大的時(shí)間代價(jià)[81]，因此在實(shí)踐中的運(yùn)用并不廣泛。啟發(fā)式算法能在合理時(shí)間內(nèi)得到近似解甚至最優(yōu)解，因此，得到了廣泛應(yīng)用和發(fā)展。啟發(fā)式算法可進(jìn)一步分為構(gòu)造型算法與改進(jìn)型算法[79]。構(gòu)造型算法從非法解出發(fā)，通過(guò)某些策略不斷迭代改進(jìn)解的質(zhì)量直到合法解，常見(jiàn)的構(gòu)造型算法有最近鄰域算法[82]和隨機(jī)貪婪算法[83]等。改進(jìn)型算法是在構(gòu)造型算法的基礎(chǔ)上運(yùn)用智能算法進(jìn)行改進(jìn)，常見(jiàn)的改進(jìn)型算法有模擬退火算法[84]、遺傳算法[85]、禁忌搜索算法[86]、蟻群算法[87]、粒子群算法[88]、螢火蟲(chóng)算法[89]、狼群算法[90]、生物地理遷移算法[91]、帝國(guó)主義競(jìng)爭(zhēng)算法[92]、離散狀態(tài)轉(zhuǎn)移算法[93]以及這些算法的混合運(yùn)用及改進(jìn)[94]。

3.2 車輛路徑問(wèn)題求解算法

在VRP算法方面，DVRP作為VRP中應(yīng)用最廣泛的類型，被證明是NP-Hard問(wèn)題，其約束條件比傳統(tǒng)TSP更多，而由于DVRP具有多時(shí)間維度、動(dòng)態(tài)性、開(kāi)放性、不確定性和信息更新機(jī)制等特點(diǎn)，對(duì)求解算法的要求更高，因此應(yīng)用精確算法很難求解DVRP，一般采用啟發(fā)式算法及其改進(jìn)算法進(jìn)行求解。CHEN等[95]提出了推—碰—擲3階段改進(jìn)的遺傳算法來(lái)求解模糊服務(wù)時(shí)間的DVRP；LIAO等[96]將掃描法與禁忌搜索算法相結(jié)合，通過(guò)掃描法確定車輛數(shù)，再根據(jù)動(dòng)態(tài)信息進(jìn)行禁忌搜索來(lái)求得可行解，可在一定程度上彌補(bǔ)禁忌搜索收斂速度慢的不足；CHEUNG等[97]提出了基于抽樣的啟發(fā)算法求解需求點(diǎn)隨機(jī)的DVRP；吳天羿等[98]針對(duì)模糊需求的DVRP，將掃描算法、遺傳算法以及差分進(jìn)化算法相結(jié)合，通過(guò)構(gòu)造差分掃描變異算子提高遺傳算法的求解性能，進(jìn)而求解了模糊需求的DVRP；謝秉磊等[99]針對(duì)隨機(jī)顧客和隨機(jī)需求的DVRP，提出了多回路優(yōu)化策略，改進(jìn)了混合領(lǐng)域結(jié)構(gòu)的模擬退火算法，提高了模擬退火算法的收斂速度。

3.3 項(xiàng)目調(diào)度問(wèn)題求解算法

在RCPSP算法方面，由于精確算法求解時(shí)間長(zhǎng)，一般在求解時(shí)采用啟發(fā)式算法及智能算法。DAVIS等[100]提出了多路算法，用于生成可行調(diào)度解；LI等[101]提出了正向-逆向調(diào)度算法，通過(guò)交替進(jìn)行正、逆向調(diào)度，有效地提高了解的質(zhì)量；KLEIN[102]通過(guò)引入禁忌搜索算法將活動(dòng)列表生成串行調(diào)度策略，較好地解決了時(shí)變資源約束的RCPSP;鄭曉龍等[103]在果蠅算法中引入?yún)f(xié)作進(jìn)化環(huán)節(jié)，提出了基于序的果蠅算法,用于解決隨機(jī)工期的RCPSP；靳金濤等[104]將船舶分段建造問(wèn)題抽象為空間資源受限的RCPSP，提出了一種人工蜂群算法，并通過(guò)不同規(guī)模的實(shí)例對(duì)比驗(yàn)證了算法的優(yōu)越性；劉欣儀等[105]針對(duì)作業(yè)時(shí)間依賴資源分配決策的RCPSP，提出了1-opt和2-opt局部搜索改進(jìn)遺傳算法，并通過(guò)數(shù)據(jù)試驗(yàn)驗(yàn)證了算法的可行性。

3.4 車間調(diào)度問(wèn)題求解算法

國(guó)內(nèi)外研究者對(duì)不同類型的車間調(diào)度問(wèn)題進(jìn)行了深入研究，以作業(yè)車間調(diào)度問(wèn)題(JSP)為代表的車間調(diào)度問(wèn)題被證明是NP-Hard問(wèn)題[106]，于是研究重點(diǎn)轉(zhuǎn)向了啟發(fā)式算法及智能算法。FATTAHI等[107]將禁忌搜索算法與模擬退火算法相結(jié)合，改善了模擬退火算法的收斂速度及局部收斂問(wèn)題，用于解決柔性作業(yè)車間調(diào)度問(wèn)題；SU等[108]針對(duì)混合流水車間調(diào)度問(wèn)題(HFSSP)，將活動(dòng)調(diào)度技術(shù)與遺傳算法相結(jié)合，構(gòu)造了EGTGA(Extend Giffler Thompson Genetic Algorithm)算法，并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了EGTGA算法的搜索效率得到了提高；徐華等[109]以最大完工時(shí)間、生產(chǎn)成本以及生產(chǎn)質(zhì)量為調(diào)度目標(biāo)構(gòu)建了多目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題(MOFJSP)，設(shè)計(jì)了混合離散蝙蝠算法，較好地避免了算法早熟問(wèn)題，并通過(guò)實(shí)例驗(yàn)證了算法的性能；李知聰?shù)萚110]在生物地理學(xué)算法的基礎(chǔ)上引進(jìn)了改進(jìn)策略，增強(qiáng)了算法的搜索能力和收斂速度，并將其運(yùn)用于混合流水車間調(diào)度問(wèn)題(HFSSP)的求解；趙博選等[111]針對(duì)MOFJSP中作業(yè)分配與作業(yè)排序2階段的特性，設(shè)計(jì)了2階段的混合Pareto蟻群算法，并通過(guò)與其他文獻(xiàn)的對(duì)比驗(yàn)證了該算法可提高解的質(zhì)量。

4 研究展望

綜上所述，已有的研究工作對(duì)維修任務(wù)調(diào)度問(wèn)題進(jìn)行了深入研究，但在裝備維修任務(wù)調(diào)度的模型及算法方面還存在一定的不足，有待進(jìn)一步開(kāi)展研究，具體表現(xiàn)在以下4個(gè)方面：

1) 目前關(guān)于裝備維修任務(wù)調(diào)度的研究大多將其視為非搶占調(diào)度，認(rèn)為在維修任務(wù)執(zhí)行過(guò)程中不能中斷，然而戰(zhàn)時(shí)戰(zhàn)場(chǎng)態(tài)勢(shì)瞬息萬(wàn)變，待修裝備重要程度、任務(wù)緊急程度等因素交錯(cuò)復(fù)雜，僅考慮維修任務(wù)的非搶占調(diào)度缺乏對(duì)任務(wù)突發(fā)性及緊急性的考慮，容易導(dǎo)致維修任務(wù)調(diào)度不合理、維修資源利用不充分等問(wèn)題。因此，針對(duì)裝備維修任務(wù)調(diào)度問(wèn)題，在貼近戰(zhàn)場(chǎng)實(shí)際的基礎(chǔ)上，根據(jù)調(diào)度目標(biāo)對(duì)維修任務(wù)的搶占調(diào)度進(jìn)行深入研究,是合理調(diào)度裝備維修任務(wù)的有效途徑。

2) 裝備維修任務(wù)調(diào)度策略作為維修任務(wù)調(diào)度的核心，是開(kāi)展裝備維修任務(wù)調(diào)度的基礎(chǔ)。目前裝備維修任務(wù)調(diào)度多以靜態(tài)優(yōu)先級(jí)調(diào)度策略為主，忽略了待修裝備維修優(yōu)先級(jí)會(huì)隨著戰(zhàn)斗階段的改變而動(dòng)態(tài)變化的問(wèn)題。應(yīng)在定量分析維修任務(wù)動(dòng)態(tài)優(yōu)先級(jí)的基礎(chǔ)上，根據(jù)修理方式及調(diào)度目標(biāo)將維修任務(wù)動(dòng)態(tài)優(yōu)先級(jí)調(diào)度策略與其他調(diào)度策略相結(jié)合，以實(shí)現(xiàn)調(diào)度目標(biāo)的最優(yōu)化。

3) 裝備維修任務(wù)調(diào)度問(wèn)題作為復(fù)雜的組合優(yōu)化問(wèn)題，目前針對(duì)裝備維修任務(wù)調(diào)度模型的研究多是寬泛地將其整個(gè)過(guò)程抽象為TSP等模型，忽略了不同維修方式及修理范圍對(duì)模型構(gòu)建的影響。事實(shí)上，對(duì)于不同的維修方式，應(yīng)建立不同的維修任務(wù)調(diào)度模型，如：對(duì)于伴隨修理及巡回修理，適合于抽象為旅行商問(wèn)題或車輛路徑問(wèn)題；對(duì)于定點(diǎn)修理及基地級(jí)修理適合于抽象為項(xiàng)目調(diào)度問(wèn)題或車間調(diào)度問(wèn)題。在具體模型構(gòu)建過(guò)程中,還應(yīng)考慮調(diào)度目標(biāo)、約束條件等因素。

4) 裝備維修任務(wù)調(diào)度問(wèn)題作為工程實(shí)際問(wèn)題，涉及的約束條件及影響因素眾多，因此在模型構(gòu)建前要根據(jù)戰(zhàn)場(chǎng)實(shí)際明確調(diào)度的目標(biāo)函數(shù)和約束條件。不同的調(diào)度算法其適應(yīng)性也不同，在求解調(diào)度模型時(shí)，應(yīng)綜合考慮模型算法的收斂速度、魯棒性和可靠性等因素，針對(duì)其缺陷進(jìn)行合理的改進(jìn)，且多種算法互補(bǔ)結(jié)合是調(diào)度模型算法研究的趨勢(shì)。

參考文獻(xiàn)：

[1] 巴巍,實(shí)時(shí)系統(tǒng)動(dòng)態(tài)優(yōu)先級(jí)任務(wù)調(diào)度算法的研究[D].大連:大連理工大學(xué),2010：4.

[2] 姚敏,王緒芝,趙敏.無(wú)人機(jī)群協(xié)同作戰(zhàn)任務(wù)分配方法研究[J].電子科技大學(xué)學(xué)報(bào),2013,42(5):723-727.

[3] 陳盈果.面向任務(wù)的快速響應(yīng)空間微型部署優(yōu)化設(shè)計(jì)方法研究[D].長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué),2014：5-9.

[4] 宋業(yè)新,陳綿云,張曙紅.多目標(biāo)指派問(wèn)題及其在軍械物資供應(yīng)中的應(yīng)用[J].系統(tǒng)工程理論與實(shí)踐,2001,21(11):141-144.

[5] 王沁,袁玲玲,張燕.固定優(yōu)先級(jí)搶占任務(wù)調(diào)度算法下非周期任務(wù)實(shí)時(shí)性能研究[J].小型微型計(jì)算機(jī)系統(tǒng),2011,32(6):1025-1029.

[6] 彭浩,韓江洪,陸陽(yáng),等.多處理器硬實(shí)時(shí)系統(tǒng)的搶占閾值調(diào)度研究[J].計(jì)算機(jī)研究與發(fā)展,2015,52(5):1177-1186.

[7] ZHAO W,RAMAMRITHAM K,STANKOVIC J.Preemptive scheduling under time and resource constraints[J].IEEE transactions on computers,1987,36(8):949-960.

[8] LEVI R,MAGNANTI T,MUCKSTADT J,et al.Maintenance scheduling for modular systems:modeling and algorithms[J].Naval research logistics,2014,61(6):472-488.

[9] 姚雙印,韓慶田.BFOA在軍械裝備維修任務(wù)調(diào)度中的應(yīng)用[J].海軍航空工程學(xué)院學(xué)報(bào),2011,26(5):558-560.

[10] 崔嘉,楊林,胡衛(wèi)民.改進(jìn)的細(xì)菌覓食算法在航空裝備維修任務(wù)調(diào)度優(yōu)化中的應(yīng)用[J].海軍航空工程學(xué)院學(xué)報(bào),2011,26(2):189-194.

[11] 王建華,黃賢鳳,梅強(qiáng),等.離散可調(diào)度時(shí)段下多供應(yīng)商敏捷供應(yīng)鏈靜態(tài)調(diào)度優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng),2015,21(10):2739-2745.

[12] NELSON R T,HOLLOWAY C A,WANG R M L.Centralized scheduling and priority implementation heuristics for a dynamic job shop model[J].AIIE transactions,1977,9(1):95-102.

[13] 張國(guó)輝,王永成,張海軍.多階段人機(jī)協(xié)同求解動(dòng)態(tài)柔性作業(yè)車間調(diào)度問(wèn)題[J].控制與決策,2016,31(1):169-172.

[14] HAN C C,LIN K J,HOU C J.Distance-constrained scheduling and its applications to real-time systems[J].IEEE transactions on computers,1996,45(7):814-826.

[15] BUTTAZZO G C.Rate monotonic vs EDF:judgment days[J].Real time systems,2005(29):5-26.

[16] WANG Y,SAKSENA M.Scheduling fixed-priority tasks with preemption threshold[C]∥Proceedings of the 6th International Conference on Real Time Computing Systems and Applications.Hong Kong:IEEE Computer Society Press,1999:328-335.

[17] 夏家莉,陳輝,楊兵.一種動(dòng)態(tài)優(yōu)先級(jí)實(shí)時(shí)任務(wù)調(diào)度算法[J].計(jì)算機(jī)學(xué)報(bào),2012,35(12):2685-2695.

[18] LEVCHUK G M,LEVCHK Y M,LUO J,et al.Normative design of organizations:part I:mission planning[J].IEEE transactions on systems,man,and cybernetics：part a system and humans,2002,32(3):346-359.

[19] 徐玖平,吳巍.多屬性決策的理論與方法[M].北京:清華大學(xué)出版社,2006:78-81.

[20] 軒華.基于FCFS策略的帶時(shí)間窗車隊(duì)調(diào)度問(wèn)題研究[J].交通運(yùn)輸系統(tǒng)工程與信息,2013,13(6):140-146,175.

[21] JOUINI O.Analysis of a last come first served queueing system with customer abandonment[J].Computers & operations research,2012(39):3040-3045.

[22] 呂學(xué)志,于永利,張柳,等.伴隨修理中的維修任務(wù)調(diào)度策略[J].系統(tǒng)工程理論與實(shí)踐,2013,33(1):209-214.

[23] 唐恒永,趙傳立.排序引論[M].北京:科學(xué)出版社,2002:68-69.

[24] GLAD R F,PIERCE R T.A comparison of selected scheduling heuristics for TAC F-4E maintenance organization[R].Ohio:Air Force Institute of Technology,Wright-Patterson Air Force Base,1976.

[25] 呂學(xué)志,于永利.面向任務(wù)的裝備作戰(zhàn)單元維修決策[M].北京:國(guó)防工業(yè)出版社,2014:147-149.

[26] 任帆,呂學(xué)志,王憲文,等.巡回修理中的維修任務(wù)調(diào)度策略[J].火力與指揮控制,2013,38(12):171-175.

[27] MISHRA S,BATTA R,SZCZERBA R J.A rule based approach for aircraft dispatching to emerging targets[J].Military operations research,2004,9(3):17-30.

[28] LOVE A,TORMOS P.Analysis of scheduling schemes and heuristic rules performance in resource-constrained multiproject scheduling[J].Annals of operations research,2001(102):263-286.

[29] 呂學(xué)志,王憲文,范保新,等.定點(diǎn)修理中維修任務(wù)調(diào)度策略的仿真評(píng)估[J].火力與指揮控制,2015,40(1):70-76.

[30] UGUR A,AYDIN D.An interactive simulation and analysis software for solving TSP using ant colony optimization algorithms[J].Advances in engineering software,2009,40(5):341-349.

[31] 張?chǎng)锡?陳秀萬(wàn),肖漢,等.一種求解旅行商問(wèn)題的新型帝國(guó)競(jìng)爭(zhēng)算法[J].控制與決策,2016,31(4):586-592.

[32] 李鋒,魏瑩.基于仿真的遺傳算法求解動(dòng)態(tài)旅行商問(wèn)題[J].系統(tǒng)管理學(xué)報(bào),2009,18(5):591-595.

[33] ELAOUD S,TEGHEM J,LOUKIL T.Multiple crossover genetic algorithm for the multiobjective traveling salesman problem[J].Electronic notes in discrete mathematics,2010(36):939-946.

[34] 李鋒.基于偏好信息的多目標(biāo)旅行商問(wèn)題Pareto優(yōu)化求解[J].系統(tǒng)工程學(xué)報(bào),2011,26(5):592-598.

[35] BEKTAS T.The multiple traveling salesman problem:an overview of formulations and solution procedures[J].Omega,2006(34):209-219.

[36] GAVISH B,SRIKANTH K.An optimal solution method for large-scale multiple traveling salesman problems[J].Operations research,1986,34(5):698-717.

[37] SINGH A,BAGHEL A S.A new grouping genetic algorithm approach to the multiple traveling salesperson problem[J].Soft comput,2009(13):95-101.

[38] SONG C H,LEE K,LEE W D.Extended simulated annealing for augmented TSP and multi-salesmen TSP[C]∥ Proceeding of the International Joint Conference on Neural Networks.Oregon,USA:IEEE,2003,3:2340-2343.

[39] DANTZIG G B,RAMSER J H.The truck dispatching problem[J].Management science,1959,6(1):80-91.

[40] PILLAC V,GENDREAU M,CHRISTELLE G,et al.A review of dynamic vehicle routing problem[J].European journal of operational research,2013(225):1-11.

[41] 李相勇.車輛路徑問(wèn)題模型及算法研究[D].上海:上海交通大學(xué),2007:11-13.

[42] TLILI T,FAIZ S,KRICHEN S.A hybrid metaheuristic for the distance-constrained capacitated vehicle routing problem[J].Procedia-social and behavioral sciences,2014(109):779-783.

[43] KALLEHAUGE B.Formulations and exact algorithms for the vehicle routing problem with time windows[J].Computers & operations research,2008(35):2307-2330.

[44] KOHL N,MADSEN O B G.An optimization algorithm for the vehicle routing problem with time windows based on lagrangian relaxation[J].Operations research,1997,45(3):395-406.

[45] DROR M,TRUDEAU P.Savings by split delivery routing[J].Transportation science,1989,23(2):141-145.

[46] DROR M,TRUDEAU P.Split delivery routing[J].Naval research logistics,1990,37(7):383-402.

[47] MULLASERIL P A,DROR M,LEUNG J.Split-delivery routing heuristics in livestock feed distribution[J].Journal of the operational research society,1997,48(2):107-166.

[48] SIERKSMA G,TIJSSEN G A.Routing helicopters for crew exchanger on off-shore location[J].Annals of operations research,1998,76(1):261-286.

[49] LAI M,BATTARRA M,FRANCESCO M D,et al.An adaptive guidance meta-heuristic for vehicle routing problem with splits and clustered backhauls[J].Journal of the operational research society,2015,66(7):1222-1236.

[50] YAN S Y,CHU J C,HSIAO F Y,et al.A planning mode and solution algorithm for multi-trip split-delivery vehicle routing and scheduling problems with time windows[J].Computers & industrial engineering,2015(87):383-393.

[51] LEE J S,KIM B I.Industrial ship routing problem with split delivery and two types of vessels[J].Expert systems with applications,2015(42):9012-9023.

[52] WANG H,DU L,MA S.Multi-objective open location-routing model with split delivery for optimized relief distribution in post-earthquake[J].Transportation research part E:logistics and transportation review,2014,69:160-179.

[53] SCHRAGE L.Formulation and structure of more complex realistic routing and scheduling problem[J].Networks,1981,11(2):229-232.

[54] PSARAFTIS H N.Dynamic vehicle routing problems[J].Vehicle routing methods & studies,1988,23(8):661-673.

[55] BERTSIMAS D J,SIMCHI L D.A new generation of vehicle routing research:robust algorithms,addressing uncertainty[J].Operation research,1996,44(2):286-304.

[56] LAPORTE G.Fifty years of vehicle routing[J].Transportation science,2009,43(4):408-416.

[57] JAILLET P,WAGNER M R.Generalized online routing:new competitive ratios,resource augmentation,and asymptotic analyses[J].Operations research,2008,56(3):745-757.

[58] BROTCORNE L,LAPORTE G,SEMET F.Ambulance location and relocation models[J].European journal of operational research,2003(147):451-463.

[59] 韓娟娟,李永先.動(dòng)態(tài)車輛路徑問(wèn)題研究綜述[J].綠色科技,2015(5):285-287.

[60] BERTSIMAS D J,RYZIN G.V.A stochastic and dynamic vehicle routing problems in the Euclidean plane[J].Operations research,1991,39(4):601-615.

[61] MINKOFF A S.A markov decision mode land decomposition heuristic for dynamics vehicle dispatching[J].Operations research,1993,41(1):77-90.

[62] TEODOROVIC D,PAVKOVIC G.The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain[J].Fuzzy sets and systems,1996(82):307-317.

[63] PAVONE M,BISNIK N,FRAZZOLI E,et al.A stochastic and dynamic vehicle routing problem with time windows and customer impatience[J].Mobile networks & applications,2009(14):350-364.

[64] 謝秉磊,李穎,劉敏.帶臨時(shí)補(bǔ)充點(diǎn)的融雪劑撒布車輛路徑問(wèn)題[J].系統(tǒng)工程理論與實(shí)踐,2014,34(6):1593-1598.

[65] 葛顯龍,徐茂增,王偉鑫.基于聯(lián)合配送的城市物流配送路徑優(yōu)化[J].控制與決策,2016,31(3):503-512.

[66] 陳偉龍,陳春良,史憲銘,等.基于變體GA的進(jìn)攻作戰(zhàn)搶修任務(wù)動(dòng)態(tài)調(diào)度[J].系統(tǒng)工程與電子技術(shù),2017,39(3):577-583.

[67] 陳偉龍,陳春良,陳康柱,等.考慮不確定性的進(jìn)攻作戰(zhàn)搶修任務(wù)動(dòng)態(tài)調(diào)度[J].兵工學(xué)報(bào),2017,38(5):1011-1019.

[68] 熊燕華,沈厚才,周晶,等.工程項(xiàng)目調(diào)度技術(shù)研究綜述[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2013,43(21):1-14.

[69] HARTMANN S.Project scheduling under limited resources:Models,methods,and applications [M].Berlin:Springer,1999:21-22.

[70] 張松.資源受限項(xiàng)目調(diào)度若干問(wèn)題研究[D].合肥:中國(guó)科學(xué)技術(shù)大學(xué),2014:13-14.

[71] 方晨,王凌.資源約束項(xiàng)目調(diào)度研究綜述[J].控制與決策,2010,25(5):641-650.

[73] ELMAGHRABY S.Activity networks:project planning and control by network models[M].New York:John Wiley& Sons,1977:33-34.

[74] 張國(guó)輝.柔性作業(yè)車間調(diào)度方法研究[D].武漢:華中科技大學(xué),2009:5-6.

[75] 李崢?lè)?多時(shí)間因素作業(yè)車間調(diào)度問(wèn)題的研究與工程應(yīng)用[D].武漢:華中科技大學(xué),2010:5.

[76] 孫志剛,朱小東,李鋒.一種考慮權(quán)重的多專業(yè)流水式批量維修任務(wù)調(diào)度模型[J].裝甲兵工程學(xué)院學(xué)報(bào),2012,26(2):24-28.

[77] 朱昱,宋建社,曹繼平,等.一種考慮裝備維修流程的多維修任務(wù)調(diào)度[J].系統(tǒng)工程與電子技術(shù),2008,30(7):1366-1369.

[78] 曾華.隨機(jī)顧客和需求的配送優(yōu)化模型與算法[D].山東:山東大學(xué),2012:18-19.

[79] DORIGO M,BIRATTARI M,STUTZLE T.Ant colony optimization[J].IEEE computational intelligence magazine,2007,1(4):28-39.

[80] 曹平方,李靈,李詩(shī)珍.基于分支界定的VRP模型精確算法研究及應(yīng)用[J].包裝工程,2014,35(17):97-101.

[81] 饒衛(wèi)振,金淳,黃英藝.求解TSP問(wèn)題的最近鄰域與插入混合算法[J].系統(tǒng)工程理論與實(shí)踐,2011,31(8):1419-1428.

[82] 王海鵬,熊偉,何友,等.集中式多傳感器概率最近鄰域算法[J].儀器儀表學(xué)報(bào),2010,31(11):2500-2507.

[83] 陳榮光,李春升,陳杰,等.基于貪婪算法的近空間平臺(tái)區(qū)域覆蓋優(yōu)化設(shè)計(jì)[J].北京航空航天大學(xué)學(xué)報(bào),2009,35(5):547-550.

[84] KIRKPATRICK S,GELATT C D,VECCHI M P.Optimization by simulated annealing[J].Science,1983，220(4598):671-680.

[85] LIU C,KROLL A.On designing genetic algorithms for solving small and medium-scale traveling salesman problems[J].Lecture notes in computer science,2012(7269):283-291.

[86] 余麗,陸鋒,楊林.交通網(wǎng)絡(luò)旅行商路徑優(yōu)化的遺傳禁忌搜索算法[J].測(cè)繪學(xué)報(bào),2014,43(11):1197-12303.

[87] NECULA R,BREABAN M,RASCHIP M.Performance evaluation of ant colony systems for the single-depot multiple traveling salesman problem[J].Lecture notes in computer science,2015(9121):257-268.

[88] LIAO Y F,YAU D H,CHEN C L.Evolutionary algorithm to tra-veling salesman problems[J].Computers and mathematics with applications,2012(64):788-797.

[89] 于宏濤,高立群,韓希昌.求解旅行商問(wèn)題的離散人工螢火蟲(chóng)算法[J].華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,43(1):126-131.

[90] 吳虎勝,張鳳鳴,李浩,等.求解TSP問(wèn)題的離散狼群算法[J].控制與決策,2015,30(10):1861-1867.

[91] MO H W,XU L F.Biogeography migration algorithm for traveling salesman problem[J].International journal of intelligent computing and cybernetics,2010(6145):405-414.

[92] YOUSEFIKHOSHBAKHT M,SEDIGHPOUR M.New imperialist competitive algorithm to solve the travelling salesman problem[J].International journal of computer mathematics,2013,90(7):1495-1550.

[93] YANG C H,TANG X L,ZHOU X J,et al.A discrete state transition algorithm for traveling salesman problem[J].Control theory and applications,2013,30(8):1040-1046.

[94] ALBAYRAK M,ALLAHVERDI N.Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms[J].Expert systems with applications,2011(38):1313-1320.

[95] CHEN R,GEN M,TOZAWA T.Vehicle routing problem with fuzzy due-time using genetic and systems algorithms[J].Journal of Japan society for fuzzy theory and systems,1995,7(5):1050-1061.

[96] LIAO T Y,HU T Y.An object-oriented evaluation framework for dynamic vehicle routing problems under real-time information[J].Expert systems with applications,2011(38):12548-12558.

[97] CHEUNG R K,XU D,GUAN Y.A solution method for a two-dispatch delivery problem with stochastic customers[J].Journal of mathematical modeling and algorithms,2007(6):87-107.

[98] 吳天羿,許繼恒.基于混合遺傳算法的模糊需求車輛路徑問(wèn)題[J].解放軍理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,15(5):475-483.

[99] 謝秉磊,安實(shí),郭輝煌.隨機(jī)車輛路徑問(wèn)題的多回路優(yōu)化策略[J].系統(tǒng)工程理論與實(shí)踐,2007,27(2):167-171.

[100] DAVIS E W,PATTERSON J H.A comparison of heuristic and optimum solutions in resource-constrained project scheduling[J].Management science,1975,21(8):944-955.

[101] LI K Y,WILLIS R J.An iterative scheduling technique for resource-constrained project scheduling[J].European journal of operational research,1992(56):370-379.

[102] KLEIN R.Project scheduling with time-varying resource constraints[J].International journal of production research,2000,38(16):3937-3952.

[103] 鄭曉龍,王凌.隨機(jī)資源約束項(xiàng)目調(diào)度問(wèn)題基于序的果蠅算法[J].控制理論與應(yīng)用,2015,32(4):540-545.

[104] 靳金濤,聶蘭順,戰(zhàn)德臣,等.基于人工蜂群的空間資源受限項(xiàng)目調(diào)度算法[J].計(jì)算機(jī)集成制造系統(tǒng),2014,20(5):1088-1098.

[105] 劉欣儀,陸志強(qiáng).作業(yè)時(shí)間依賴資源分配決策的項(xiàng)目調(diào)度問(wèn)題建模與算法[J].上海交通大學(xué)學(xué)報(bào),2017,51(1):82-89.

[106] MARICHELVAM M K,PRABAHARAN T,YANG X S.Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan[J].Applied soft computing,2014(19):93-101.

[107] FATTAHI P,MEHRABAD M S,JOLAI F.Mathematical modeling and heuristic approaches to flexible job shop scheduling problems[J].Journal of intelligent manufacturing,2007(18):331-342.

[108] SU Z X,LI T.Genetic algorithm for minimizing the makespan in hybrid flow shop scheduling problem[C]∥Proceedings of the 3rd International Conference on Management and Service Sciences.Washington,USA:IEEE,2009:1-4.

[109] 徐華,張庭.混合離散蝙蝠算法求解多目標(biāo)柔性作業(yè)車間調(diào)度[J].機(jī)械工程學(xué)報(bào),2016,52(18):201-212.

[110] 李知聰,顧幸生.改進(jìn)的生物地理學(xué)算法在混合流水車間調(diào)度中的應(yīng)用[J].化工學(xué)報(bào),2016,67(3):751-757.

[111] 趙博選,高建民,陳琨.求解多目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題的兩階段混合Pareto蟻群算法[J].2016,50(7):145-151.