考慮休息的維修任務調度模型及其求解算法

呂學志,陳樂,尹健,范保新

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

考慮休息的維修任務調度模型及其求解算法

呂學志1,陳樂2,尹健1,范保新1

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

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

兵器科學與技術；維修資源；維修任務；調度；粒子群優化算法

0 引言

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

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

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

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

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

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

1 數學模型

考慮休息的維修任務調度優化模型可以描述為:

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

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

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

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

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

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

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

2 求解算法

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

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

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

2.1 算法框架

PSO算法框架為:

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

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

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

4)判斷是否滿足算法結束條件,若是則轉步驟5,否則轉步驟2;

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

2.2 粒子表示與初始化

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

圖1 項目調度問題的例子Fig.1 Example of project scheduling

2.3 基于優先規則的柔性資源-技能分配算法

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

2.4 解碼過程

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

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

具體算法可簡單描述為:

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

2.5 粒子更新

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

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

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

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

3 計算示例

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

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

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

表2 任務信息Tab.2 Maintenance task information

表3 經優化的維修任務調度方案Tab.3 Optimized maintenance task scheduling plan

維修任務調度方案的甘特圖如圖5所示,橫坐標表示時間,縱坐標表示人員,圖中灰色矩形表示維修任務,矩形所處位置的縱坐標對應分配的人員,矩形內部用“-”分割開的3個數字依次表示維修任務編號、人員編號、技能編號;剖面線矩形表示休息時間,矩形內部用“-”分割開的4個數字依次表示時間段編號、人員編號、休息開始時間與結束時間。

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

4 結論

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

References)

[1] 王正元,嚴小琴,朱昱,等.一種考慮專業的動態維修任務調度的優化方法[J].兵工學報,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] 朱昱,宋建社,王正元.一種基于最大保障時間的戰時裝備維修任務調度[J].系統工程與電子技術,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 經優化的維修任務調度方案的甘特圖Fig.5 Gantt chart of optimized maintenance task scheduling plan

[3] 朱昱,宋建社,曹繼平,等.一種考慮裝備維修流程的多維修任務調度[J].系統工程與電子技術,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] 方晨,王凌.資源約束項目調度研究綜述[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] 喻小光,戰德臣,聶蘭順,等.柔性資源約束的資源水平項目調度問題[J].計算機集成制造系統,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]黃敏鎂,羅榮桂.柔性資源約束下的產品開發項目優化調度研究[J].管理工程學報,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]潘全科,王凌,高亮.離散微粒群優化算法的研究進展[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]鄧林義.資源受限的項目調度問題及其應用研究[D].大連:大連理工大學,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

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