呂學(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)

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 求解算法

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

相比較典型的資源約束項(xiàng)目調(diào)度模型,本文提出的維修任務(wù)調(diào)度模型更加復(fù)雜:一是由于維修資源具有柔性,存在任務(wù)-技能-資源的兩層映射,需要考慮資源-技能分配問題;二是由于需要考慮維修資源的休息時(shí)間,在安排維修任務(wù)起始時(shí)間的同時(shí)要給出維修資源的休息時(shí)間;三是維修時(shí)間的安排也會(huì)影響到資源的分配。所以,由于經(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)生初始粒子群。評(píng)價(jià)初始粒子群粒子,確定粒子的個(gè)體極值pi、全局最優(yōu)pg;

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

3)對(duì)整個(gè)種群進(jìn)行評(píng)價(jià),確定粒子的個(gè)體極值pi和整個(gè)種群中的全局最優(yōu)pg;

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

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

2.2 粒子表示與初始化

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

圖1 項(xiàng)目調(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 解碼過程

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

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

具體算法可簡(jiǎn)單描述為:

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

2.5 粒子更新

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

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

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

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

3 計(jì)算示例

下面考慮一個(gè)維修任務(wù)調(diào)度實(shí)例。該維修任務(wù)由13項(xiàng)維修任務(wù)組成,由12名維修人員完成,維修資源每工作24 h至少休息8 h.維修人員所具有的技能用資源-技能矩陣表示,如表1所示。第1項(xiàng)任務(wù)和最后一項(xiàng)任務(wù)分別為虛擬開始和虛擬結(jié)束任務(wù),維修任務(wù)時(shí)間、先后時(shí)序約束、所需技能如表2所示。采用本文提出的PSO算法進(jìn)行求解(資源-技能分配算法中使用了最少技能數(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)過計(jì)算,求得最優(yōu)的維修任務(wù)序列為:(j1, j3,j4,j2,j5,j6,j8,j7,j9,j10,j11,j12).表3給出了維修任務(wù)各項(xiàng)維修任務(wù)開工時(shí)間和完工時(shí)間的進(jìn)度安排,以及資源-技能分配方案,如:維修任務(wù)j2在6 h開始并于10 h結(jié)束,完成該任務(wù)需要具有技能c1的兩單位資源由人員r8、r11負(fù)責(zé)。休息時(shí)間如表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)表示時(shí)間,縱坐標(biāo)表示人員,圖中灰色矩形表示維修任務(wù),矩形所處位置的縱坐標(biāo)對(duì)應(yīng)分配的人員,矩形內(nèi)部用“-”分割開的3個(gè)數(shù)字依次表示維修任務(wù)編號(hào)、人員編號(hào)、技能編號(hào);剖面線矩形表示休息時(shí)間,矩形內(nèi)部用“-”分割開的4個(gè)數(shù)字依次表示時(shí)間段編號(hào)、人員編號(hào)、休息開始時(shí)間與結(jié)束時(shí)間。

表4 休息時(shí)間安排Tab.4 Optimized maintenance task scheduling plan

4 結(jié)論

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

References)

[1] 王正元,嚴(yán)小琴,朱昱,等.一種考慮專業(yè)的動(dòng)態(tài)維修任務(wù)調(diào)度的優(yōu)化方法[J].兵工學(xué)報(bào),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] 朱昱,宋建社,王正元.一種基于最大保障時(shí)間的戰(zhàn)時(shí)裝備維修任務(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] 方晨,王凌.資源約束項(xiàng)目調(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)德臣,聶蘭順,等.柔性資源約束的資源水平項(xiàng)目調(diào)度問題[J].計(jì)算機(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ā)項(xiàng)目優(yōu)化調(diào)度研究[J].管理工程學(xué)報(bào),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ìn)展[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]鄧林義.資源受限的項(xiàng)目調(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—),男,高級(jí)講師。E-mail:ghostsheep@tom.com