資源受限條件下車輛維修工序調度優(yōu)化

湯潤之， 班利明， 錢樂， 雷爭軍， 宋衛(wèi)星,3

(1.陸軍工程大學 國防工程學院， 江蘇 南京 210007； 2.32272部隊， 甘肅 蘭州 730000；3.陸軍工程大學石家莊校區(qū) 裝備指揮與管理系， 河北 石家莊 050003)

0 引言

車輛維修保障是一個對象繁雜(數量大、種類多、技術標準各異)、要素全面(備件與器材、設施與設備、人員與訓練、技術與資料等)的系統(tǒng)化工程[1]。其中維修資源分配、工序調度是關鍵，其優(yōu)化效果直接影響了車輛裝備的完備性和使用效能[2]。特別是部隊在執(zhí)行任務時，面對維修時間和人力配置受到限制的條件下，如何最大化利用現有資源分配調撥，形成最優(yōu)維修保障調度方案，顯得尤為重要。

資源調度優(yōu)化問題多視為資源受限項目調度問題(RCPSP)進行求解，即通過合理調配使有限資源在滿足要素內部優(yōu)先關系和資源約束的前提下，對項目內部活動進行合理調度，達到壓縮項目工期或減小項目成本等目標。基于RCPSP的研究，有學者提出了搶占式資源受限項目調度問題(PRCPSP)，該問題屬于NP難問題，作為RCPSP的重要衍生問題，通過允許任務在進程中靈活中斷的方式，暫時釋放任務占用資源以滿足其他緊前任務執(zhí)行的需要，提升了任務進程調度與執(zhí)行的靈活性和可操作性。Sorli[3]總結了無搶占、單搶占和多次搶占3種活動搶占模式，并通過比較大多數實例后得出以下結論：一次搶占相比無搶占能夠顯著縮短進程時間，而多次搶占相比一次搶占對于縮短進程時間的貢獻較小。此外，根據日常經驗，反復地停止和重啟一項活動，在實際操作過程中較難實現，工程實踐意義不強[4]。綜上所述，一次搶占式RCPSP(1_RCPSP)對于車輛維修保障系統(tǒng)中的調度任務，具有較好的現實應用價值。

在編碼方面，文獻[5]在任務進程列表融合優(yōu)先權值基礎方案中插入搶占點，將經典RCPSP升級為1_RCPSP，并針對該搶占式模型設計了新的編碼及解碼方案；文獻[6]利用優(yōu)先值方法編碼求解RCPSP的算法，其編碼方式不考慮時序約束。而基于活動列表的編碼對每個活動的開始時間[7-8]、完成時間[9]以及活動位置[10]進行解碼，得到了相對應的優(yōu)先權值。此外，一些優(yōu)先值微小更新并沒有改變活動調度的實際順序[11]，使得其組合不同編碼產生相同調度的可能性增大。基于以上分析，在求解質量方面，基于活動列表的編碼在某種程度上要優(yōu)于基于優(yōu)先權值的編碼[12]。

在求解算法方面，RCPSP主要采用元啟發(fā)式算法進行求解。文獻[13]引入了廣義優(yōu)先關系和改進的單代號網絡圖對項目活動的緊前關系進行描述，并對布谷鳥算法進行改進，以求解該模型。文獻[14]對項目調度問題的表示，提出了移動塊序列的方案，在問題求解方面，利用多智能體進化算法進行求解。文獻[15]研究在最大分割次數和最小連續(xù)執(zhí)行周期的約束下，設計改進的遺傳算法，對考慮懲罰時間的RCPSP進行求解。文獻[16]針對多工種RCPSP，對禁忌搜索算法進行改進并求解模型。文獻[17]基于分散搜索，提出了混合式元啟發(fā)算法求解RCPSP. 文獻[18]提出考慮搶占懲罰時間的多工種PRCPSP，利用改進的蟻群算法求解模型。文獻[19]考慮到維修人員掌握的維修技能水平不同問題，建立多目標優(yōu)化模型，利用兩階段優(yōu)化算法求解模型。文獻[20]提出一種項目活動時間隨機的RCPSP，采用預處理和在線調度的兩階段策略，并采用兩階段局部搜索進行優(yōu)化。近年來又出現了不少新型混合算法，如混合了蟻群和分散搜索的優(yōu)化模型[21]，它們在解決RCPSP問題時取得了良好的效果。

結合不同算法的優(yōu)缺點，本文將針對資源受限條件下的車輛維修工序調度問題建立基于人員工種及維修能力的綜合模型，以人力資源工種分類、人員等級進行雙目標多約束優(yōu)化，采用1_RCPSP建立搶占式資源調度模型，采用帶精英策略的非支配排序遺傳算法(NSGA-II)對案例進行求解分析。

1 問題描述

裝備維修保障資源調度問題可以轉化為搶占式RCPSP進行求解，在考慮人力資源總量和各專業(yè)各等級維修人員數量的情況下[22]，兼顧維修工序的緊前約束條件，合理調度維修資源，安排其對各工序進行維修，以達到優(yōu)化目標。

1.1 問題假設

根據實際情況為簡明問題，本文提出以下5個假設說明：1)維修工序在維修過程中，允許對工序進行一次中斷，釋放維修資源，去維修優(yōu)先級更高的工序；2)被搶占工序可以在發(fā)生額外的時間與費用的條件下重啟；3)為提高實際合理性，搶占點只設置在整數時間點上；4)若搶占點發(fā)生在工序初始或結束時，或者工序被搶占后瞬間啟動，則忽略工序搶占過程；5)關于維修資源，假定維修備件無限供應，僅對維修人力資源進行調度。

1.2 模型建立

每個工序有如下兩種約束關系：

1)人力資源總約束和各工種各等級維修人員數量約束，即對工序進行維修中任意時刻，正在進行維修的維修人員總數及各種類各等級維修人員數量，不得超過相對應的維修人員數量。

2)緊前約束關系，例如工序ji和工序jk具有緊前約束關系，則工序jk必須于工序ji后發(fā)生。

戰(zhàn)時車輛維修要求在合理安排人力資源對工序進行維修的同時使得維修時間最短，即合理利用維修資源，盡快完成維修任務。因此，本文將以維修用時最短以及特殊人力資源(維修工時最長的維修人員)總負荷最小為目標函數，建立一次搶占維修工序調度問題的數學模型。用Qg表示第g類維修人員的總負荷，sji表示工序ji的開始時間，vji表示工序ji的緊前活動集合，t表示時間點，eji表示項目最晚結束時間；除工序0和工序n+1外其他工序ji均可被拆分為兩部分ji1和ji2，其開始時間分別表示為sji1和sji2，工期分別為非負整數pji1和pji2，且pji1+pji2=pji；此外，t時刻正在進行的工序集合用At表示。

雙目標一次搶占模型如下：

minf1=sji+1，

(1)

(2)

s.t.sjk2+pjk2≤sjk1，?jk∈vji，

(3)

sji1+pji1≤sji2，

(4)

pji1+pji2=pji，

(5)

sj0=0，

(6)

(7)

(8)

以上公式中對工序運行情況進行了限制：(1)式表示第1個目標函數——整個維修任務完成所耗費的總時間最小；(2)式表示第2個目標函數——人力資源總負荷，即所有維修人員的總工作時長最小化；(3)式、(4)式約束確保遵守工序間的優(yōu)先關系；(5)式確保任務部分工期之和為該項任務的總工期；(6)式表示項目初始時間為0；(7)式、(8)式確保不違背資源約束條件。

2 算法求解

2.1 編碼方案

文獻[12]指出，優(yōu)先值表示的方法相對于活動列表的表示，在求解質量和解算效率上都差強人意。因此，對于1_RCPSP，本文采用基于活動列表的編碼方案得出一層編碼方案，以保證產生的編碼方案滿足緊前約束關系。工序列表為項目網絡圖的一個拓撲排序。每個工序被隨機產生的搶占點分為兩部分，則共有2n個工序。基于工序列表的編碼方案如表1所示。基于活動列表的編碼為維修工序網絡圖的一個拓撲排序，即第1重編碼為符合時序約束的一個工序排序，一次搶占式維修工序調度將每個工序分為兩部分，縮小了維修人員的休息時隙，提高了維修人員的利用率，從而縮短了項目完工時間。以上論述證明，只要對維修資源進行合理合時的調度，安排其對某個子工序在最早開工時間時開始維修，便可以縮小維修人員的等待時間或維修人員的停工次數。

表1 單次搶占編碼

對于染色體二重編碼，在由第1重編碼得出符合緊前約束的子工序序列后，對應每個子工序，在滿足人力資源約束和人員種類的情況下，根據每個子工序所需的各種類人力資源，從初、中、高等級中隨機選擇符合約束條件的人員rji,g次，選擇結果串聯合并作為染色體的第2重編碼。

2.2 算法設計

本文所建1_RCPSP模型為雙目標多約束優(yōu)化模型，對該問題采用適合求解多目標的NSGA-II，并對其改進，以適應實際維修問題對模型進行求解。

2.2.1 選擇算子

采用傳統(tǒng)的精英保留策略，即首先對當前種群進行非支配排序，其次對等級最高的非支配集合利用二元錦標賽(BTS)選擇算子選出最優(yōu)的二分之一染色體作為精英染色體，直接進入下一代；其余的二分之一染色體并入常規(guī)種群進行后續(xù)操作。該操作可以使得最優(yōu)解單調遞增逐代提升性能，同時避免龐大集合導致的種群早熟。

2.2.2 交叉算子

交叉算子按照某種交叉方式對常規(guī)種群進行重組交叉，產生新的染色體。本文采用基于部分映射策略的兩點隨機交叉策略，對于常規(guī)種群中每一對染色體的第1重編碼，隨機產生整數τ1和τ2，其中1≤τ1≤τ2≤2n，交換這對染色體中位于[τ1,τ2]區(qū)間內的染色體片段。由于搶占點的產生具有隨機性，交換完成后可能導致以下兩種錯誤情況：

1)染色體第m個工序的第1、第2部分未被安排維修的同時，導致第n個工序的第1、第2部分重復安排維修；

2)交叉后產生的對第m個工序第1、第2部分進行維修的時間與第m個工序的第2、第1部分進行維修的時間之和,不等于第m個工序所需的總維修時長。

對以上兩種錯誤情況進行修復：

1)將交換后重復安排的維修工序n的第1、第2部分用未被安排維修的第m個工序的第1、第2部分進行替換；

2)以交叉前第m個工序的第1、第2部分為準，調整交叉后的第2、第1部分的維修時間，變更搶占點，使搶占后工序的1、第2部分維修時間之和等于該工序的總維修時間。

交換完成后，結合第1重編碼和第2重編碼進行染色體合法性檢驗，即對每個子工序所對應的人力資源種類及總數量約束進行檢驗，若不合法，則根據交叉后的第1重編碼序列及人力資源約束條件，重新產生第2重編碼序列。

2.2.3 變異算子

以某一變異概率對染色體進行重新初始化。

3 仿真與分析

3.1 示例仿真

實驗以某型車輛維修保養(yǎng)的3級保養(yǎng)作業(yè)(車輛3級維修保養(yǎng)以維修人員為中心，進行以保為主、保修并重的車輛維修保養(yǎng)制度，維修人員按照車輛的專業(yè)對其分配維修作業(yè))為例進行仿真計算并分析結果，配置維修人員數量12人，每個工種(共3類分別為A、B、C)人員分配4名維修人員，分別為2名初級人員、1名中級人員、1名高級人員。本文算法設定80個初始染色體，算法上限迭代200次，變異概率設為0.08. 表2展示了車輛維修三級保養(yǎng)作業(yè)關系，該型號車輛維修保養(yǎng)時間按軍用標準表中規(guī)定為90工時，標準班組作業(yè)一般編制員額12名修維修人員，單人作業(yè)時間450 min.

表2 某型車輛維修保養(yǎng)的3級保養(yǎng)作業(yè)

3.2 結果分析

采用本文算法對表2算例進行計算，得出的部分工序調度結果如表3所示，為方便閱讀，表3中只顯示下面結果分析1～6出現中的相關數據，對部分過程數據進行了省略。

表3 部分工序調度方案

1～6中重點對關鍵拆分節(jié)點進行分析，并結合維修時間圖對比了無搶占和一次搶占的調度方式優(yōu)劣情況：

1)表3中數據第1列表示79個工序根據隨機斷點拆分為158個工序后的小工序序號，第2列為小工序所屬的拆分前大工序序號，第3列小工序為大工序的第1或第2部分，第4列表示小工序進行維修的維修人員能力等級(1、2、3分別對應初、中、高級)，第5列為對該小工序進行維修的維修人員種類；第6列表示該小工序的開始維修時間，第7列為該小工序的維修完工時間。例如：第1行數據表示第22個大工序被拆分后的第2部分，即小工序的第44個，安排A工種的高級維修人員對其進行維修，開始維修時間為0 min，結束維修時間為9 min.

2)大工序22被拆分為2部分，第2部分為小工序的第44個，第1部分為小工序的第43個，由A工種維修人員中的高級人員在第48 min時開始維修，第73 min時結束維修。

3)搶占發(fā)生在整數時間點，開始、結束維修時刻為小數，是因為給定工序的維修人員為初級維修人員時，其維修工時按照中級人員維修工時的1.2倍進行計算，高級人員維修工時按照中級人員維修工時的0.8倍進行計算。

4)大工序共有9個工序，需要2個維修人員同時對其進行維修，因此拆分為小工序后共有18個小工序，需要2個維修人員同時對其進行維修。例如大工序10的第1部分，即小工序的第19個，規(guī)劃B工種的初級和高級維修人員在125～154 min對其進行維修，在179～230 min由B工種的初級和高級維修人員對大工序10的第2部分，即小工序的第20個進行維修。

5)圖1、圖2分別為無搶占、一次搶占維修工序時間圖。維修過程中，為達到整體目標最優(yōu)，安排部分維修人員暫時休息，等待參與下一個工序維修，舍棄局部短時間內調度方案最優(yōu)，從而導致最多有12個維修人員同時進行維修，而不是15人同時進行。

圖1 無搶占維修工序調度人員維修圖Fig.1 Maintenance personnel and time in non-preemptive maintenance scheduling

圖2 一次搶占維修工序調度人員維修圖Fig.2 Maintenance personnel and time in one-time preemptive maintenance scheduling

6)圖1顯示無搶占模式維修很少有12名維修人員同時進行維修，在維修時刻250 min前一直保持7名以上維修人員同時進行維修，但在250 min以后大量維修人員開始進入休息狀態(tài)，只有少數維修人員繼續(xù)工作，導致維修總時長較長。由圖2可知，一次搶占模式雖沒有12名維修人員同時維修的狀態(tài)，但大致在280 min之前都是7名以上維修人員同時進行維修，同時進行維修的維修人員數量下降趨勢緩慢，人員工作與休息時間分布均衡，是導致維修總工期和關鍵人力資源符合小于無搶占模式的原因。一次搶占模式放棄了局部調度最優(yōu)，保證了全局調度結果最優(yōu)。

表4所示為不同模式調度目標值。由表4可見：利用無搶占RCPSP模式安排調度方案，最短工期為358 min，關鍵人力資源總負荷為306 min；利用1_RCPSP模式安排調度方案，最短工期為339 min，關鍵人力資源總負荷為302 min；對于戰(zhàn)時車輛維修工序調度問題，無論是對于時間優(yōu)化目標還是人員優(yōu)化目標，1_RCPSP模式均優(yōu)于無搶占RCPSP模式。

表4 不同模式調度目標值對比

4 結論

本文采用基于活動列表編碼的一次搶占式人力資源調度，結合實際任務中多工種多技術等級的情況，以四要素為約束條件，建立多目標優(yōu)化模型進行求解，結果表明，對戰(zhàn)時多目標車輛維修人力資源進行調度，1_RCPSP方案明顯優(yōu)于無搶占RCPSP方案。同時在傳統(tǒng)NSGA-Ⅱ基礎上，對等級最高的非支配集合利用BTS選擇算子選出精英染色體進入下一代，使得最優(yōu)解單調遞增逐代提升性能，避免了龐大集合導致的種群早熟，提升了傳統(tǒng)算法性能。

本文假定維修備件無限供應，僅對維修人力資源進行調度，相較于真實作戰(zhàn)的復雜情況目標和約束條件都有待進一步增加，后續(xù)工作還需要增加對于經濟效益相關因素的考量，近一步提升方法的實用性，在更加有限的資源下提升模型調度效果。