復(fù)雜人力資源約束下的搶占式維修工序調(diào)度

所屬分類：建筑論文閱讀次時間：2021-01-12 10:34

本文摘要：摘要: 針對維修保障系統(tǒng)內(nèi)部工序調(diào)度問題具有工序多、維修人員種類不同、維修人員等級不同等復(fù)雜特性，本文建立了以維修工時最短和人力資源總負荷最小為目標函數(shù)的多目標多約束優(yōu)化模型，設(shè)計了基于關(guān)鍵路徑算法的優(yōu)先權(quán)值編碼對搶占式調(diào)度問題進行第一層

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

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

維修工序

　　0 引言

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

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

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

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

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

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

　　1 基本描述

　　1.1 問題描述

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

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

　　1.2 問題假設(shè)

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

　　2 模型構(gòu)建

　　2.1 符號定義及說明

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

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

　　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 倍向后取整。結(jié) 合本文所提出的雙重編碼方案和改進的混合粒子群遺傳算法，利用 MATLAB 軟件對該數(shù)值案例進行求解分析。 4.2 結(jié)果分析

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

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

　　5 結(jié)論

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

　　參考文獻 (References)

　　[1] 李曉宇, 王新閣, 方子立等. 面向任務(wù)的裝備維修保障資源優(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