考慮休息的維修任務(wù)調(diào)度模型及其求解算法

呂學(xué)志,陳樂,尹健,范保新

(1.總參謀部炮兵訓(xùn)練基地模擬訓(xùn)練中心,河北宣化 075100;2.裝備學(xué)院指揮與管理系,北京 101400)

考慮休息的維修任務(wù)調(diào)度模型及其求解算法

呂學(xué)志1,陳樂2,尹健1,范保新1

(1.總參謀部炮兵訓(xùn)練基地模擬訓(xùn)練中心,河北宣化 075100;2.裝備學(xué)院指揮與管理系,北京 101400)

由于維修資源通常具有使用周期性,即每工作一段時間需要進行休息,而維修任務(wù)具有緊迫性,需要不間斷地進行,如何在給出維修任務(wù)調(diào)度方案的同時也給出維修資源的休息時間是一個值得探討的問題。文中給出考慮休息的維修任務(wù)調(diào)度問題的假設(shè)條件,并建立了一種混合整數(shù)規(guī)劃模型,對問題進行了數(shù)學(xué)描述。提出一種粒子群求解算法,包括算法框架、粒子表示、資源技能分配算法、粒子解碼過程、更新公式等。通過具體實例,證明了模型與算法的有效性。

兵器科學(xué)與技術(shù)；維修資源；維修任務(wù)；調(diào)度；粒子群優(yōu)化算法

0 引言

裝備是遂行一切軍事行動的物質(zhì)基礎(chǔ),裝備維修保障活動是軍事行動不可或缺的重要組成部分,維修保障活動的好壞直接影響著軍事行動的成敗。維修任務(wù)調(diào)度問題是裝備保障活動中的一個重要決策問題,其主要目的是確定維修任務(wù)起始時間、所需維修資源,該問題解決的好壞決定了維修的執(zhí)行效率。

國內(nèi)外許多研究人員對維修任務(wù)調(diào)度問題進行了研究,對維修任務(wù)調(diào)度問題的構(gòu)成要素、決策目標(biāo)、問題本質(zhì)有了深刻認識,建立了多種維修任務(wù)調(diào)度模型,并給出了模型的求解算法,具有一定的實踐指導(dǎo)意義。國內(nèi)學(xué)者建立了許多獨立的規(guī)劃模型,并使用了啟發(fā)算法、智能算法對其進行求解,但并未將其與項目調(diào)度問題結(jié)合起來。王正元等[1]以盡快恢復(fù)參戰(zhàn)作戰(zhàn)單元的戰(zhàn)斗力為目標(biāo),提出了一種考慮維修專業(yè)的動態(tài)維修任務(wù)調(diào)度的優(yōu)化方法。文獻[2-3]分別建立了基于最大保障時間的維修任務(wù)調(diào)度模型以及考慮維修流程的多單元維修任務(wù)調(diào)度模型,并給出了啟發(fā)算法。

國外學(xué)者多將維修任務(wù)調(diào)度問題看作項目調(diào)度問題,這一點需要我們借鑒。文獻[4]將基地級維修任務(wù)抽象為大規(guī)模復(fù)雜的項目調(diào)度問題,研究了在資源約束下與隨機工期情況下軍用飛機基地級維修任務(wù)調(diào)度的新方法。

資源約束項目調(diào)度問題(RCPSP)研究從時間和資源上合理安排調(diào)度項目的活動,在資源最優(yōu)利用的同時實現(xiàn)既定目標(biāo)的最優(yōu)化[5]。根據(jù)資源、活動、執(zhí)行模式和目標(biāo)函數(shù)等4種屬性可以對RCPSP進行分類,不同類型的組合又形成不同的RCPSP[6]。在項目調(diào)度問題中,資源通常具有一定的柔性,即具有多種能力。而能力指完成某項任務(wù)所需的技能或功能,對于人力資源指技能,對于機器設(shè)備等則指功能。例如,維修人員具有焊接和噴漆技能;機器具有彎板和切割功能。國外學(xué)者在維修任務(wù)調(diào)度問題研究中,考慮到了維修資源的柔性。例如,法國的Bellenguez等[7-8]對多技能員工約束項目調(diào)度問題(MSPSP)進行了深入的研究。MSPSP可以看成是傳統(tǒng)RCPSP的一個推廣。在文獻[7-8]所建的模型中:假設(shè)技能具有一定級別區(qū)分,例如程序員可以分為初級、中級、高級;員工具有一定的不可用期,也就是說員工休假的時候不能被分配來執(zhí)行任何活動。文獻[7-8]給出了一種基于優(yōu)先表的禁忌搜索算法和兩種遺傳算法,還將研究成果應(yīng)用于維修任務(wù)調(diào)度。

國內(nèi)學(xué)者也開始對柔性資源約束項目調(diào)度問題(FRCPSP)進行研究,但沒有將其應(yīng)用于維修任務(wù)調(diào)度問題中。喻小光等[9]提出了柔性資源約束的資源水平項目調(diào)度問題,建立了問題的數(shù)學(xué)模型,設(shè)計了基于改進串行調(diào)度生成模式和網(wǎng)絡(luò)最大流柔性資源分配模型的路徑重連算法。黃敏鎂等[10]針對解決具有柔性資源約束的產(chǎn)品開發(fā)項目調(diào)度問題,以遺傳算法和最大流理論為基礎(chǔ),提出了問題求解的改進遺傳算法。

在軍用裝備維修時,維修資源通常還具有周期性,例如,維修人員(維修設(shè)備)需要每工作一定時間必須休息一段時間,而目前的維修任務(wù)研究中還沒有考慮到維修資源的使用周期,在給出維修任務(wù)調(diào)度方案的同時并不能夠給出維修資源的休息時間。本文將給出了一種考慮休息的維修任務(wù)調(diào)度優(yōu)化模型及其求解算法。

1 數(shù)學(xué)模型

考慮休息的維修任務(wù)調(diào)度優(yōu)化模型可以描述為:

1)整個維修任務(wù)的結(jié)構(gòu)可以用一張活動節(jié)點圖G=(J,Q)表示,G中節(jié)點J表示維修任務(wù)集合, Q表示維修任務(wù)之間的關(guān)系;|J|表示維修任務(wù)集合J中維修任務(wù)的數(shù)量;維修任務(wù)之間存在著由于技術(shù)等要求產(chǎn)生的時序約束,記Pj為任務(wù)j的緊前任務(wù)集合;定義任務(wù)1和任務(wù)|J|是唯一最早開始和最晚結(jié)束的任務(wù)且均為虛任務(wù),它們不消耗資源并且執(zhí)行時間為0,分別稱為源任務(wù)和收尾任務(wù);非虛任務(wù)數(shù)為|J|-2;維修任務(wù)j的工期為dj.

2)C表示與維修任務(wù)執(zhí)行相關(guān)的全部技能集合,|C|表示技能集合C中技能的數(shù)量;對于維修任務(wù)的每項維修任務(wù)而言,其對資源的技能需求是不同的,即維修任務(wù)j需要一組技能Cj,Cj∈C;維修任務(wù)與技能的關(guān)系也可以用任務(wù)-技能矩陣MJ來表示這種關(guān)系,其中矩陣元素m表示維修任務(wù)j對技能c的需求量。

3)R表示維修資源集合,|R|表示維修資源集合R中資源的數(shù)量;本文中的維修資源屬于柔性資源,具有柔性。柔性資源是指可以應(yīng)用于一種以上的不同場合的可更新資源;柔性是資源具備多種技能的屬性,可用資源-技能矩陣MR表示,定義MR=其中m表示資源r具備技能c的水平,m∈{0,1},r∈R,c∈C;若m=l,資源r完全具備技能c,l為時間段的下標(biāo)(l∈L={1,…,|L|}),其中|L|為調(diào)度時間范圍內(nèi)時間段的數(shù)量。|L|= ceil(T|J|/λ),T|J|為整個維修任務(wù)的期限,單位為h, ceil()是向上取整函數(shù),如ceil(2.2)=3;若m=0,資源r完全不具備技能c;資源在資源-技能矩陣的限定下執(zhí)行維修任務(wù)。

4)維修資源除了具有柔性之外,還具有使用周期性。人員必須每λ小時休息τ小時。

5)進一步做以下假設(shè):A1維修任務(wù)執(zhí)行期間不允許中斷;A2只有同時具備技能組合Cj時,維修任務(wù)j才能開始;A3在任一時刻維修人員至多能使用一項技能,也就是說每個維修人員被認為是一元資源;A4維修資源的休息時間也不允許中斷;A5維修任務(wù)的工期不能超過每個時間段最長工作時間。

6)問題的解是確定維修任務(wù)與休息的開始時間及資源-技能分配方案。

目標(biāo)(1)式表示最小化維修任務(wù)最終完成時間。約束(2)式表示按照維修任務(wù)對技能的要求(即每個維修任務(wù)的每種技能所需的人員)來分配維修人員;根據(jù)假設(shè)A2、A3,為了防止維修人員使用不同技能執(zhí)行同一個維修任務(wù),約束(3)式限定了每個維修人員在每項維修任務(wù)中最多使用一種技能。約束(4)式表示如果維修任務(wù)j是維修任務(wù)j′的緊前任務(wù),則維修任務(wù)j在j′開始之前完成。約束(5)式和(6)式限制了每個休息時間段的時間范圍,根據(jù)假設(shè)A4維修資源的休息時間也不允許中斷。約束(7)式限定了Yjj′,其中Δ是無窮大的數(shù),表示如果Yjj′=1,即j在j′之前完成,則j′的開始時間至少要比j的開始時間遲dj,如果Yjj′=0,恒成立;根據(jù)假設(shè)A3中的一元資源假設(shè)。約束(8)式與(9)式分別限定了、.約束(10)式與(11)式限定了維修任務(wù)與休息時間的序列。約束(12)式根據(jù)假設(shè)A5限定了維修任務(wù)的工期不能超過每個時間段最長工作時間。約束(13)式與(14)式表示對變量的約束。

2 求解算法

本文提出的維修任務(wù)調(diào)度問題是標(biāo)準(zhǔn)FRCPSP的一種變形,同時也是經(jīng)典RCPSP的一個特例和拓展。FRCPSP是一個更為一般化的單模式RCPSP,與多模式RCPSP(MRCPSP)相似,這是因為任務(wù)可以通過多種模式進行,每種模式中資源的組成不同。但是,MRCPSP僅僅描述了通過時間與資源權(quán)衡來執(zhí)行任務(wù),并不能體現(xiàn)資源的柔性,這也是FRCPSP與MRCPSP的本質(zhì)區(qū)別。隨著任務(wù)技能需求與人員技能數(shù)量的增加,FRCPSP中的模式數(shù)量將急速增長。

相比較典型的資源約束項目調(diào)度模型,本文提出的維修任務(wù)調(diào)度模型更加復(fù)雜:一是由于維修資源具有柔性,存在任務(wù)-技能-資源的兩層映射,需要考慮資源-技能分配問題;二是由于需要考慮維修資源的休息時間,在安排維修任務(wù)起始時間的同時要給出維修資源的休息時間;三是維修時間的安排也會影響到資源的分配。所以,由于經(jīng)典RCPSP是NP-hard問題,本文提出的維修任務(wù)調(diào)度問題是其更為一般化的形式,所以本文提出的維修任務(wù)調(diào)度問題也是NP-hard問題。

智能算法是求解NP-hard問題的有效方法。粒子群優(yōu)化(PSO)算法已經(jīng)應(yīng)用于經(jīng)典RCPSP的求解,并且取得很好的效果[11-12]。所以,下文將提出一種基于PSO算法的求解算法。

2.1 算法框架

PSO算法框架為:

1)產(chǎn)生初始粒子群。評價初始粒子群粒子,確定粒子的個體極值pi、全局最優(yōu)pg;

2)迭代次數(shù)加1,對粒子進行更新;

3)對整個種群進行評價,確定粒子的個體極值pi和整個種群中的全局最優(yōu)pg;

4)判斷是否滿足算法結(jié)束條件,若是則轉(zhuǎn)步驟5,否則轉(zhuǎn)步驟2;

5)利用已知全局最優(yōu)解生成項目(維修任務(wù))調(diào)度計劃(包括維修任務(wù)的開始時間、維修人員在每個時間段的休息開始時間,資源-技能分配方案),算法結(jié)束。

2.2 粒子表示與初始化

算法采用基于任務(wù)序列的粒子表示方法。粒子所表示的任務(wù)序列對應(yīng)一個先序可行的任務(wù)序列,任務(wù)在序列中的位置表示任務(wù)調(diào)度的優(yōu)先順序。粒子維數(shù)為維修任務(wù)的總數(shù),即D=|J|,粒子適應(yīng)值對應(yīng)其生成調(diào)度的工期。如粒子xi=(xi1,…,xij,…,xi|J|),前|J|個分量對應(yīng)于任務(wù)xij,j∈J,任務(wù)xij在粒子轉(zhuǎn)化為調(diào)度方案時,其調(diào)度次序為j,粒子的適應(yīng)值對應(yīng)其生成調(diào)度的工期。圖1是調(diào)度問題實例的網(wǎng)絡(luò)結(jié)構(gòu)圖,任務(wù)1是虛擬開始任務(wù),任務(wù)13是虛擬結(jié)束任務(wù),該項目的一個可行粒子為x1= (1,2,3,4,10,8,5,6,11,7,9,12,13).

圖1 項目調(diào)度問題的例子Fig.1 Example of project scheduling

2.3 基于優(yōu)先規(guī)則的柔性資源-技能分配算法

圖2 基于優(yōu)先規(guī)則的柔性資源-技能分配算法流程圖Fig.2 Flow chart of resources-skills allocation algorithm based on priority rules

2.4 解碼過程

該算法中,一個粒子代表一個可行解。算法采用了改進的并行調(diào)度生成方案將粒子轉(zhuǎn)化為可行的調(diào)度方案。下面介紹改進的并行調(diào)度生成方案,它含有柔性資源-技能分配算法,在給出維修任務(wù)調(diào)度方案的同時還可以安排維修資源的休息時間[13]。

改進的并行調(diào)度生成方案最多包含|J|個階段,階段n對應(yīng)一個調(diào)度時間tn,一個完工任務(wù)集En,一個活動任務(wù)集Bn和一個決策任務(wù)集Dn.其中完工任務(wù)集En是指到tn時刻已經(jīng)完成的任務(wù)組成的集合,即En={j|T′j≤tn};活動任務(wù)集Bn是指在tn時刻正在進行的任務(wù)組成的集合,即Bn={j|Tj≤tn＜T};決策任務(wù)集Dn指在tn時刻滿足時序約束的未參加排序的任務(wù)組成的集合,即Dn={j|j?En∪Bn, Pj?En};令柔性資源-技能分配算法表示為函數(shù)[Xj,Zj]=F(M,A,MR).

具體算法可簡單描述為:

解碼過程流程圖如圖3所示。從以上的算法可以看出,維修資源的休息時間是在“當(dāng)前時間”之前安排的,當(dāng)其空閑時間長度不小于τ時即進行安排,也就是只要有機會就安排;安排維修資源執(zhí)行維修任務(wù)的時候,不考慮那些如果執(zhí)行維修任務(wù)就可能在本周期段不能休息的維修資源;在每個周期段結(jié)束的時候,對那些沒有安排休息的資源安排休息。這種算法體現(xiàn)了以維修任務(wù)為重,休息時間盡量選擇維修資源的空閑時間,必須保證休息時間的思想。

2.5 粒子更新

圖3 解碼過程流程圖Fig.3 Flow chart of decode process

算法采用的粒子更新公式[14]為 (19)式～(21)式中:c、、w為算法控制參數(shù)。粒子的擾動和粒子的信息繼承可分別采用變異或交叉來實現(xiàn):

1)粒子的擾動。這里引入一種基于任務(wù)序列的隨機插入法對更新后的粒子xi進行擾動。該方法分為:隨機生成一個位置點a1∈[2,|J|-1],設(shè)該位置點的任務(wù)為xia1,找到該任務(wù)的所有緊前任務(wù)在此任務(wù)序列中的最后位置a2及所有緊后任務(wù)在任務(wù)序列中最前面的位置a3,然后在a2到a1和a1到a3中隨機選擇一個位置,將此任務(wù)插在該位置。

圖4 粒子的信息繼承Fig.4 Information inheritance of particle

3 計算示例

下面考慮一個維修任務(wù)調(diào)度實例。該維修任務(wù)由13項維修任務(wù)組成,由12名維修人員完成,維修資源每工作24 h至少休息8 h.維修人員所具有的技能用資源-技能矩陣表示,如表1所示。第1項任務(wù)和最后一項任務(wù)分別為虛擬開始和虛擬結(jié)束任務(wù),維修任務(wù)時間、先后時序約束、所需技能如表2所示。采用本文提出的PSO算法進行求解(資源-技能分配算法中使用了最少技能數(shù)資源優(yōu)先規(guī)則),種群規(guī)模20,迭代次數(shù)80,w=0.75,c′1=0.25, c′2=0.75.

表1 資源-技能矩陣Tab.1 Resources-skillsmatrix

經(jīng)過計算,求得最優(yōu)的維修任務(wù)序列為:(j1, j3,j4,j2,j5,j6,j8,j7,j9,j10,j11,j12).表3給出了維修任務(wù)各項維修任務(wù)開工時間和完工時間的進度安排,以及資源-技能分配方案,如:維修任務(wù)j2在6 h開始并于10 h結(jié)束,完成該任務(wù)需要具有技能c1的兩單位資源由人員r8、r11負責(zé)。休息時間如表4所示。

表2 任務(wù)信息Tab.2 Maintenance task information

表3 經(jīng)優(yōu)化的維修任務(wù)調(diào)度方案Tab.3 Optimized maintenance task scheduling plan

維修任務(wù)調(diào)度方案的甘特圖如圖5所示,橫坐標(biāo)表示時間,縱坐標(biāo)表示人員,圖中灰色矩形表示維修任務(wù),矩形所處位置的縱坐標(biāo)對應(yīng)分配的人員,矩形內(nèi)部用“-”分割開的3個數(shù)字依次表示維修任務(wù)編號、人員編號、技能編號;剖面線矩形表示休息時間,矩形內(nèi)部用“-”分割開的4個數(shù)字依次表示時間段編號、人員編號、休息開始時間與結(jié)束時間。

表4 休息時間安排Tab.4 Optimized maintenance task scheduling plan

4 結(jié)論

本文建立考慮休息的維修任務(wù)調(diào)度優(yōu)化模型,并給出了求解該模型的PSO算法,在粒子解碼過程中運用了基于優(yōu)先規(guī)則的柔性資源-能力分配模型。并通過具體實例,證明了模型與算法的有效性。該模型適用于決策者同時給出維修任務(wù)調(diào)度方案與維修資源休息方案。今后,可以研究休息時間可以拆分的維修任務(wù)調(diào)度模型,以及考慮將最長工作時間約束、人員偏好與休息場所限制納入到維修任務(wù)調(diào)度模型中。

References)

[1] 王正元,嚴(yán)小琴,朱昱,等.一種考慮專業(yè)的動態(tài)維修任務(wù)調(diào)度的優(yōu)化方法[J].兵工學(xué)報,2009,30(2):252-256.

WANG Zheng-yuan,YAN Xiao-qin,ZHU Yu,et al.An optimal method on dynamicmaintenance task schedulingwith subject taken into account[J].Acta Armamentarii,2009,30(2):252-256. (in Chinese)

[2] 朱昱,宋建社,王正元.一種基于最大保障時間的戰(zhàn)時裝備維修任務(wù)調(diào)度[J].系統(tǒng)工程與電子技術(shù),2007,29(11): 1900-1903.

ZHU Yu,SONG Jian-she,WANG Zheng-yuan.Schedulingmodel of the battle equipmentmaintenance task based on themostsupport time[J].Systems Engineering and Electronics,2007,29(11): 1900-1903.(in Chinese)

圖5 經(jīng)優(yōu)化的維修任務(wù)調(diào)度方案的甘特圖Fig.5 Gantt chart of optimized maintenance task scheduling plan

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

ZHU YU,SONG Jian-she,CAO Ji-ping,et al.Maintenance task schedulingmodel of multiunit considering armament maintenance process[J].Systems Engineering and Electronics,2008,30(7): 1366-1369.(in Chinese)

[4] Gemmill D.Shop floor scheduling for program depotmaintenance considering stochastic repair needs[R].US:Air Force Office of Scientific Research,2000.

[5] Kolisch R.Serial and parallel resource-contrained project schedulingmethods revisited:theory and computation[J].European Journal of Operational Research,1996,90(2):320-333.

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

FANG Chen,WANG Ling.Survey on resource-constrained project scheduling[J].Control and Decision,2010,25(5):641-651. (in Chinese)

[7] Bellenguez-Morineau O.Methods to solve multi-skill project scheduling problem[J].4OR:A Quarterly Journal of Operation Research,2008,6(1):85-88.

[8] Bellenguez O,Ne′ron E.Lower bounds for themulti-skill project scheduling problem with hierarchical levels of skills[J].Lecture Notes in Computer Science,2005,3616:229-243.

[9] 喻小光,戰(zhàn)德臣,聶蘭順,等.柔性資源約束的資源水平項目調(diào)度問題[J].計算機集成制造系統(tǒng),2010,16(9):1967-1976.

YU Xiao-guang,ZHAN De-Chen,NIE Lan-shun,et al.Flexible resource constrained resource leveling project scheduling problem [J].Computer Integrated Manufacturing Systems,2010,16(9): 1967-1976.(in Chinese)

[10]黃敏鎂,羅榮桂.柔性資源約束下的產(chǎn)品開發(fā)項目優(yōu)化調(diào)度研究[J].管理工程學(xué)報,2010,24(4):143-148.

HUANG Min-mei,LUO Rong-gui.Study on flexible-resource-constrained product development project scheduling[J].Journal of Industrial Engineering/Engineering Management,2010,24(4): 143-148.(in Chinese)

[11]Zhang H,Li X,Li H.Particle swarm optimization-based schemes for resource-constrained project scheduling[J].Automation in Construction,2005,14(3):393-404.

[12]Jarboui B,Damak N,Siarry P.A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems[J].Applied Mathematics and Computation, 2008,195(1):299-308.

[13]Sprecher A,Kolisch R,Drexl A.Semi-acitive,active,and nondelay schedules for the resource-constrained project scheduling problem[J].European Journal of Operational Research,1995, 80(1):94-102.

[14]潘全科,王凌,高亮.離散微粒群優(yōu)化算法的研究進展[J].控制與決策,2009,24(10):1441-1449.

PAN Quan-ke,WANG Ling,GAO Liang.The-state-of-art of discrete particle swarm optimization algorithms[J].Control and Decision,2009,24(10):1441-1449.(in Chinese)

[15]鄧林義.資源受限的項目調(diào)度問題及其應(yīng)用研究[D].大連:大連理工大學(xué),2008.

DENG Lin-yi.Research on the resource-constrained project scheduling problem with its application abstract[D].Dalian:Dalian University of Technology,2008.(in Chinese)

M aintenance Task Scheduling M odel Considering Rest Time and its Solving Algorithm

LYU Xue-zhi1,CHEN Le2,YIN Jian1,FAN Bao-xin1
(1.Simulation Training Center,Artillery Training Base of the General Staff,Xuanhua 075100,Hebei,China; 2.Department of Command and Management,Equipment Academy,Beijing 101400,China)

As themaintenance resources are periodically used,namely,theymust have rest after running for a period of time,amaintenance task usually is urgent,which must be going on without interruption, how to give outmaintenance task scheduling plan and rest times ofmaintenance resources at same time is an issue being worth to be discussed.A hybrid integer-programming model is established based on the model assumption.A PSO-based solving algorithm is proposed,which includes algorithm framework,particle representation,resources-skills allocation algorithm,particle decoding algorithm and update methods.The validity and feasibility of themodel and resolving algorithm are verified by an example.

ordnance science and technology;maintenance resource;maintenance task;scheduling; PSO algorithm

TP307

A

1000-1093(2014)12-2116-08

10.3969/j.issn.1000-1093.2014.12.027

2013-11-19

呂學(xué)志(1979—),男,高級講師。E-mail:ghostsheep@tom.com