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

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

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

　　0 引 言

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

　　維修工程評(píng)職知識(shí)：工程機(jī)械維修師怎么發(fā)表論文

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

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

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

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

　　1 基本描述

　　1.1 問(wèn)題描述

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

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

　　1.2 問(wèn)題假設(shè)

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

　　2 模型構(gòu)建

　　2.1 符號(hào)定義及說(shuō)明

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

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

　　4 仿真與分析

　　4.1 示例仿真

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

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

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

　　5 結(jié)論

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

　　參考文獻(xiàn) (References)

　　[1] 李曉宇, 王新閣, 方子立等. 面向任務(wù)的裝備維修保障 資源優(yōu)化配置 [J]. 國(guó)防科技, 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

轉(zhuǎn)載請(qǐng)注明來(lái)自發(fā)表學(xué)術(shù)論文網(wǎng)：http:///jzlw/25479.html