復雜人力資源約束下的搶占式維修工序調度

　　摘 要: 針對維修保障系統(tǒng)內部工序調度問題具有工序多、維修人員種類不同、維修人員等級不同等復雜特性， 本文建立了以維修工時最短和人力資源總負荷最小為目標函數(shù)的多目標多約束優(yōu)化模型，設計了基于關鍵路徑 算法的優(yōu)先權值編碼對搶占式調度問題進行第一層編碼，采用隨機產(chǎn)生方案得出第二層人力資源編碼，進而針 對混合粒子群遺傳算法設計了符合搶占式調度的交叉算子，利用 MATLAB 軟件對實例分別進行了無搶占、一 次搶占、多次搶占調度方案仿真，最后對仿真結果進行對比分析。仿真結果得出多工序在多工種和多等級人力 資源約束下的多次搶占式維修工序調度方案，以及無搶占、一次搶占、多次搶占調度所對應的目標函數(shù)解，決 策者可根據(jù)實際需求設定目標函數(shù)權值以得出最佳調度方案.

　　關鍵詞: 搶占式調度;維修調度;優(yōu)先權值編碼;多目標;混合粒子群遺傳算法;多等級人力資源

　　0 引 言

　　裝備維修保障系統(tǒng)由裝備維修所需的各類維修 資源和管理手段組成，該系統(tǒng)裝備數(shù)量種類復雜 且多，包括維修器材與備件、維修設備以及各種類 個等級維修人員等。維修工序調度優(yōu)化是建立維 修保障系統(tǒng)的一個關鍵步驟，決策者需對有限的維 修資源進行合理地分配，制定詳細且符合實際的維修調度方案，以達到既定目標。若維修資源分配不 合理、優(yōu)化方案及算法設計不周，將導致對資源的 利用率過低，產(chǎn)生較長的維修時間。此問題屬于資 源受限式項目調度問題 (Resource-constrained project scheduling problem，RCPSP)。如何合理地對工序的 維修流程進行安排，分配維修保障資源，形成所需 時間最短的維修調度計劃，使調度方案達到最優(yōu)，對于提高部隊保障能力和裝備保障效益都具有重要 意義[1]。

　　維修工程評職知識：工程機械維修師怎么發(fā)表論文

　　近年來，對于資源受限式項目調度問題的研 究已有不少。為了更加滿足項目的各種需求，可 以將完整的工序劃分為若干個子工序，對各個 子工序進行維修。根據(jù)在工序維修過程中有無 轉移維修資源，將該問題劃分為資源搶占式[2] 和 非資源搶占式[3]。搶占式資源受限項目調度問題 (Preemptive Resource-Constrained Project Scheduling Problem，PRCPSP)可以將當前的維修工序設置暫 停并釋放其所占用的維修資源對優(yōu)先級更高的工序 進行維修。理論上，通過工序搶占、設置優(yōu)先級， 可以更加充分地利用維修資源，從而縮短項目工 期。文獻[4] 提出對 PRCPSP 問題，每個工序的計劃 維修時間段內的每個整數(shù)時刻都可以作為資源搶占 點，也就是說，若工序需要 t 個單位維修時間，則 該工序最多可以被搶占 t-1 次，并將 PRCPSP 劃分為 無搶占(0_PRCPSP)，一次搶占(1_PRCPSP)和多 次搶占(m_PRCPSP)三種情況。其中 m_PRCPSP (m 次資源受限搶占式調度問題)允許工序滿足各 類約束時，在維修過程中的任意整數(shù)間斷點被搶 占 m 次。

　　以往的研究結論顯示，相對于非搶占式 維修調度，搶占式維修調度可顯著縮短工期。對于 工序的優(yōu)先級編碼，主要有基于活動列表的編碼[2] 和基于優(yōu)先權值的編碼[5]，文獻[6] 設計了允許多次 搶占的基于工序優(yōu)先級的編碼策略，文獻[7] 針對 1_PRCPSP，分別設計了基于活動列表的編碼方案 和基于優(yōu)先權值的雙重編碼方案。 在問題的建模和求解方面，研究人員主要通過 建立多約束規(guī)劃模型并利用啟發(fā)式算法對 PRCPSP 進行研究。文獻[8] 針對傳統(tǒng)的優(yōu)先關系不能滿足描 述事件項目調度優(yōu)先關系的要求，引入了廣義優(yōu)先 關系(Generalized priority relation，GPRs)和改進的 單代號網(wǎng)絡圖(Activity-On-Node，AON)來描述任 務的時序關系，并利用改進的布谷鳥算法對問題進 行求解;文獻[9] 提出了移動塊序列(Moving block sequence，MBS)來表示項目調度問題，使得在滿 足優(yōu)先約束和資源需求的情況下，盡可能早的安排 相應項目中的每個活動，并采用多智能體進化算法 (MAEA)求解問題。

　　文獻[10] 研究了在最大分割 次 數(shù)和最小連續(xù)執(zhí)行周期的約束下，在離散時間點 上 對每個活動進行分割(考慮分割后的懲罰時 間)的資源約束項目調度問題，設計了一種遺傳算法對問題進行求解;文獻[11] 建立了多個技能種類 的資源受限式項目調度問題，并對禁忌搜索算法進行改進以 求解該調度問題;針對資源受限式項目調度問題， 文獻[12] 提出了分散搜索的混合元啟發(fā)式算法進 行 求解;文獻[13] 針對多技能資源約束項目調度問 題， 規(guī)定恢復一個被搶占的活動需要額外的懲罰 成本， 并提出了一種基于蟻群的元啟發(fā)式算法來 求解模 型;文獻[14] 建立了考慮勝任力差異的人 力資源受 限多目標項目調度問題模型，并采用提出 的兩階段 優(yōu)化算法求解模型;文獻[15] 對連續(xù)時 間條件下具 有柔性資源配置的資源約束項目調度問 題，即每個任務可以在任何時間點開始、結束或改 變其資源分 配，進行了研究;文獻[16] 提出了一種 項目活動時間 隨機的資源約束型項目調度問題，采 用預處理和在 線調度的兩階段策略，并采用兩階段 局部搜索進行 優(yōu)化。

　　現(xiàn)有的人力資源有限項目調度問題多針對工期 最小的單目標函數(shù)進行優(yōu)化求解，或考慮人員多技 能，或考慮人員勝任力差異，但對實際的維修工序 調度問題，需要同時考慮人員多工種類型和人員等 級不同等問題，且單一的目標函數(shù)往往難以得出符 合實際的調度方案。基于以上分析，本文對具有人 員多工種類型、人員技能等級不同的雙目標—工期 最小和人力資源總負荷最小的多約束問題進行優(yōu) 化，根據(jù)具體問題設計了基于實數(shù)編碼的雙重編碼 方案對調度問題進行多次隨機搶占，并采用改進的 混合粒子群—遺傳算法求解模型，得出更符合實際 需求的維修工序調度方案。

　　1 基本描述

　　1.1 問題描述

　　復 雜 人 力資 源受 限式 工 序 調 度問 題采用 圖 G = (V, E) 描述，其中節(jié)點集合 V 用以表示項 目中工序集合 J，有向弧集合 E 用以表示工序間的 前后關系。每個項目包含 n + 2 個工序，其中開始 0 節(jié)點和結束 n + 1 節(jié)點為虛擬工序。對于某維修任 務，工期為 SJ，給定 M 個、K 種維修人員，需要 盡可能快且在工期上限 T 時刻之前完成維修，且維 修消耗的人力資源代價盡可能小。該問題即為復雜 人力資源約束下的工序調度問題，需要針對該問題 中的維修工序進行無搶占、一次搶占、多次搶占式 調度優(yōu)化，分析并對比結果，得出最符合實際要求 的維修工序調度方案。每個工序需要遵守兩種約束 關系：

　　(1)資源約束關系。工序進行維修的任意時 刻，其所占用的維修人員總數(shù)必須小于總維修人員 數(shù)量。(2)時序約束關系。根據(jù)實際工序維修要求，某些工序之間存在緊前約束關系，即若工序維修尚 未結束，則工序不能開始維修。 以往的研究，多是針對單一優(yōu)化目標—維修工 期最短的調度優(yōu)化問題，然而，在實際的裝備維修 保障過程中，單目標難以評價出一個調度方案的好 壞，決策者必須建立多個優(yōu)化目標并對其進行協(xié)調， 但多個目標通常都相互制約、相互聯(lián)系，直接對多 個目標進行比較相當困難，因此，需要在這些指標 之間進行衡量，找到最優(yōu)平衡點。本文建立維修工 期最短和人力資源總負荷最小—雙目標模型，在滿 足任務時序約束和人力資源約束的條件下，合理地 調度工序和人員，達到既定的維修目標。

　　1.2 問題假設

　　(1)假設不可更新資源(配件、原材料等)充 足; (2)對于可更新資源，本文只考慮人力資源; (3)維修工序所需必要維修時間已給定; (4)不同等級維修人力資源對相應專業(yè)的每 項工序進行維修所需的時間由平時經(jīng)驗數(shù)據(jù)計算已 經(jīng)得出; (5)每個工序只需要某一種維修人員對其進行維修。

　　2 模型構建

　　2.1 符號定義及說明

　　2.2 建立調度模型 基于以上分析，本文建立以維修工期最短和維 修人員總負荷最小為雙目標的 m_PRCPSP(m 次搶 占資源受限項目調度問題)數(shù)學模型。工序 j 的開 始時間為 sj，工序 j 的緊前工序集合為 vj，t 表示 時刻;除初始工序 0 和結束工序 n + 1 外，其余的 工序均可被搶占為 W 部分，即 j1，j2，…，jW ，每 一部分的開始時刻分別為 sj1 ，sj2，…，sjW ，工時 分別為非負整數(shù) pj1，pj2，…，pjW 。

　　3 改進的混合粒子群遺傳算法 本章結合資源受限維修調度問題的特點設計了 符合本文模型的雙重編碼，同時對混合混沌粒子群 算法和遺傳算法進行改進以適應調度方案并對其進 行求解，擴大算法的搜索范圍，提高優(yōu)化質量。

　　4 仿真與分析

　　4.1 示例仿真

　　數(shù)值試驗以某型車輛維修保養(yǎng)的三級保養(yǎng)作業(yè) 為例，配置維修人員數(shù)量為 15 人，每種(共三種) 維修人員種類分配 5 名維修人員，分別為 2 名初 級維修人員、2 名中級維修人員、1 名高級維修人 員。初始種群數(shù)量為 80，迭代次數(shù)為 200，變異概 率 0.5。車輛維修保養(yǎng)的三級保養(yǎng)作業(yè)數(shù)據(jù)采用文 獻[17] 中表 4-1 的數(shù)據(jù)，表中的維修工時均為中級維 修人員對該工序進行維修需要的工時，初級維修人 員工時為中級維修人員的 1.1 倍向后取整，高級維 修人員工時為中級維修人員的 0.9 倍向后取整。結 合本文所提出的雙重編碼方案和改進的混合粒子群 遺傳算法，利用 MATLAB 軟件對該數(shù)值案例進行 求解分析。 4.2 結果分析

　　車輛維修保養(yǎng)的三級保養(yǎng)作業(yè)維修調度部分方案。

　　(1)79 個工序根據(jù)大工序所需維修時間的比例限定搶占次數(shù)，本文中搶占次數(shù)為 18min 的整數(shù) 倍，例如：大工序 24 所需工時為 60min，則其有60/18=3 個隨機搶占點; (2)給出多次搶占式維修調度的第一個 Pareto 解所對應的調度方案，數(shù)據(jù)第一列表示 79 個 大工序被隨機斷點被搶占后產(chǎn)生的 158 個子工序的 維修順序，第二列為子工序所屬的搶占前大工序序 號，第三列顯示子工序屬于大工序的第幾部分，第 四列為對該子工序進行維修的維修人員的技術等級 (1,2,3 分別代表初、中、高級人員)，第五列為該維 修人員所屬的工種類別(有 A、B、C 三種專業(yè)類 別);第六、七列分別代表該子工序的開始維修時 間和終止維修時間。例如：第一行數(shù)據(jù)表示第 7 個 大工序按照其工時被隨機搶占點搶占為三段，第一 段為第 10 個子工序，派兩個 B 類初級維修人員對 其進行維修，開始維修時間為 0min，終止維修時間 為 10min; (3)3、4、5 分別為無搶占、一次搶占、多 次搶占維修工序時間圖�？梢钥闯觯�維修全過程， 沒有 15 個維修人員同時進行維修的過程，最多為 12 個維修人員同時進行維修，這是由于其他未進行 維修的人員在等待參與下一次維修，這樣的調度方 案在短時間內看起來不是最優(yōu)的，但對于整個維修 過程來說卻是最優(yōu)的。

　　5 結論

　　對考慮維修人員等級和維修人員種類的資源受 限維修工序調度優(yōu)化問題，本文建立以維修時間最 小和人力資源總負荷最小為目標函數(shù)的多約束優(yōu) 化模型，設計了基于關鍵路徑法的優(yōu)先權值編碼方 案，對混合粒子群遺傳算法進行改進，設計了符合 搶占式資源受限項目調度的粒子交叉方案，并結合 實例對無搶占、一次搶占以及多次搶占方案進行對 比，結果顯示，在多目標約束下，多次搶占式調度 方案略占優(yōu)勢，但對搶占次數(shù)較多的多次搶占式調 度，反而會增加維修時間，因此，設計搶占式工序 調度方案，應根據(jù)實際問題考慮多次搶占的次數(shù)。 下一步將考慮帶有懲罰時間的無限制多次隨機 搶占方案在實際維修調度中的應用。

　　參考文獻 (References)

　　[1] 李曉宇, 王新閣, 方子立等. 面向任務的裝備維修保障 資源優(yōu)化配置 [J]. 國防科技, 2011, 000(003):48-52. (Li X Y, Wang X G, Fang Z L, etc. Task-oriented equipment maintenance support resource optimization allocation [J]. National Defense Science and Technology, 2011, 000(003):48-52.)

　　[2] Ballestín, F., Valls, V., Quintanilla, S. Pre-emption in resource-constrained project scheduling[J]. European Journal of Operational Research, 2008, 189(3):1136-1152.

　　[3] Kaplan, Lori A. Resource-constrained Project Scheduling With Preemption of Jobs.[J]. Michigan： University of Michigan，1988.

　　作者：孫笑1,† , 宋衛(wèi)星2 , 班利明2 , 齊小剛1

轉載請注明來自發(fā)表學術論文網(wǎng)：http:///jzlw/25479.html