基于微粒群算法的艦艇計(jì)劃修理資源調(diào)度優(yōu)化*

劉 磊 王 平

(海軍工程大學(xué)管理工程系 武漢 430033)

?

基于微粒群算法的艦艇計(jì)劃修理資源調(diào)度優(yōu)化*

劉 磊 王 平

(海軍工程大學(xué)管理工程系 武漢 430033)

為解決艦艇修理計(jì)劃中時(shí)間和資源制約帶來的問題,提出了基于微粒群算法的艦艇計(jì)劃修理資源調(diào)度優(yōu)化方法。將不確定性多項(xiàng)式的求解問題轉(zhuǎn)化為優(yōu)先級(jí)搜索問題,并利用微粒群算法實(shí)現(xiàn)了問題的快速有效求解。工程實(shí)例的求解得到了合理有效的分配方案,解決了在資源制約下最小化工期的問題。

微粒群算法; 計(jì)劃修理; 資源調(diào)度; 優(yōu)先級(jí)

Class Number U674.7

1 引言

艦艇的修理受到時(shí)間和資源兩方面的制約。當(dāng)前艦艇計(jì)劃修理中,由于承修單位同時(shí)承修多個(gè)項(xiàng)目,因而對(duì)于單個(gè)修理項(xiàng)目,其修理所配備的人力、物力等資源都是有限的。繼而提出了在以縮短修理工期為前提的計(jì)劃修理中如何優(yōu)化調(diào)度有限資源的問題[1]。

計(jì)劃修理資源調(diào)度優(yōu)化是一個(gè)不確定性多項(xiàng)式求解問題,在工程管理方面現(xiàn)行的主要方法是關(guān)鍵路徑法,但是該方法以時(shí)間最短為前提,無法滿足資源條件的約束,容易出現(xiàn)資源超負(fù)荷的問題。

2 艦艇計(jì)劃修理進(jìn)度安排優(yōu)化模型

一個(gè)艦艇修理工程由多個(gè)有序的修理項(xiàng)目構(gòu)成,每個(gè)修理項(xiàng)目都有明確的工期要求以及資源需求。修理進(jìn)度安排優(yōu)化的目標(biāo)是充分利用有限的資源,在盡可能短的工期內(nèi)完成項(xiàng)目,每個(gè)項(xiàng)目進(jìn)行過程中不能中斷,尋優(yōu)解為各個(gè)項(xiàng)目開始與結(jié)束的時(shí)間。

2.1 艦艇維修工程網(wǎng)絡(luò)計(jì)劃圖

特定的艦艇修理工程中,各修理項(xiàng)目之間具有前后約束關(guān)系,即各修理項(xiàng)目有固定的開工先后順序,將某修理項(xiàng)目之前需要完成的修理項(xiàng)目集合稱為該項(xiàng)目的緊前修理項(xiàng)目,反之為緊后修理項(xiàng)目。通常,用網(wǎng)絡(luò)計(jì)劃圖表達(dá)各維修項(xiàng)目之間的前后約束。

工程網(wǎng)絡(luò)計(jì)劃圖的實(shí)質(zhì)是有向無環(huán)圖(Directed Acyclic Graph,DAG),可以用鄰接矩陣表示。如圖1所示,圖1(a)為一個(gè)工程網(wǎng)絡(luò)計(jì)劃圖,{x1,x2,…,x6}該維修工程所包含的六個(gè)維修項(xiàng)目。每個(gè)項(xiàng)目對(duì)應(yīng)節(jié)點(diǎn)的父節(jié)點(diǎn)即為其緊前項(xiàng)目,子節(jié)點(diǎn)即為其緊后項(xiàng)目。為了統(tǒng)一工程開始和結(jié)束的時(shí)間,x1和x6為虛項(xiàng)目,所需工時(shí)為0。

圖1 工程網(wǎng)絡(luò)計(jì)劃圖及其鄰接矩陣

2.2 艦艇計(jì)劃修理進(jìn)度安排數(shù)學(xué)模型

艦艇計(jì)劃修理進(jìn)度優(yōu)化的目標(biāo)是縮短工期,約束條件包括三項(xiàng): 1) 修理項(xiàng)目順序制約; 2) 各個(gè)修理項(xiàng)目的固定工期; 3) 各種資源限制。其數(shù)學(xué)模型可表達(dá)如下[2]:

mintN
s.t.ti-tj≥dj, ?j∈Zi,i=1,2,…,N

(1)

(2)

其中,N為維修工程包含的項(xiàng)目總數(shù),tN為維修工程的總工期。ti和tj為項(xiàng)目i和項(xiàng)目j的開始時(shí)間,di為維修項(xiàng)目i所需要的工期,Zi為項(xiàng)目i的緊前修理項(xiàng)目,m為維修需要的資源種類,rik為修理項(xiàng)目所需要第k類資源的數(shù)量,bk為維修工程所配備的第k類資源總量。

上述優(yōu)化模型中,s.t.(1)隱含約束ti-tj≥0對(duì)應(yīng)于前文的約束條件(1)和(2),表示緊后維修項(xiàng)目必須在緊前維修項(xiàng)目完成的前提下進(jìn)行,并且項(xiàng)目工期必須足夠。s.t.(2)對(duì)應(yīng)于約束條件(3)為資源約束。

2.3 優(yōu)化模型的轉(zhuǎn)換

2.2節(jié)描述的數(shù)學(xué)模型是一個(gè)不確定性多項(xiàng)式(NP)問題,需要借助搜索算法尋找問題的解。對(duì)于特定的工程網(wǎng)絡(luò)計(jì)劃圖,其網(wǎng)絡(luò)結(jié)構(gòu)確定,節(jié)點(diǎn)權(quán)值(項(xiàng)目完成時(shí)間)確定,因此可以轉(zhuǎn)化為節(jié)點(diǎn)排序的次優(yōu)求解問題。即將問題的求解轉(zhuǎn)化為尋找一種項(xiàng)目的優(yōu)先排序(優(yōu)先級(jí)越高的項(xiàng)目,在資源足夠的條件下,越先進(jìn)行),使得在該順序之下,維修工程的總計(jì)劃工期最短。

由于每個(gè)項(xiàng)目的工期固定,為滿足s.t.(1),只需保證緊前項(xiàng)目的優(yōu)先級(jí)大于緊后項(xiàng)目,且緊前項(xiàng)目工期足夠。由于工期所需資源固定,可將s.t.(2)轉(zhuǎn)化為固定資源的分配,即一旦資源不足,優(yōu)先級(jí)低的維修項(xiàng)目便需要等待前期項(xiàng)目完成再進(jìn)行資源分配。

3 基于微粒群算法的優(yōu)化搜索

微粒群算法(Particle Swarm Optimization,PSO)是由美國心理學(xué)家Kennedy和電氣工程師Eberhart于1995年提出的一種模擬鳥類群體覓食行為的仿生智能計(jì)算方法[3～4]。PSO模型簡(jiǎn)單、易于實(shí)現(xiàn)、無需梯度信息并在各種連續(xù)型優(yōu)化問題中表現(xiàn)出良好求解效果[5～8]。

微粒群算法的基本思想是通過群體中個(gè)體之間的協(xié)作和信息共享來尋找最優(yōu)解。微粒群算法將每個(gè)個(gè)體看作是在n為搜索空間中的一個(gè)沒有重量和體積的微粒,并在搜索空間中以一定的速度飛行,該飛行速度由個(gè)體的飛行經(jīng)驗(yàn)和群體的飛行經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)調(diào)整[9～10]。

3.1 PSO的搜索方案

(3)

設(shè)群體中微粒數(shù)為s,群體中所有微粒所經(jīng)歷過的最好位置為B(t),B(t)∈{P0(t),P1(t),…,Ps(t)},

T(B(t))=min{T(G1(t)),T(G2(t)),…,T(Gs(t))}

(4)

微粒群算法的進(jìn)化方程可描述為

(5)

式中,下標(biāo)“i”表示微粒的第i維,即第i個(gè)項(xiàng)目的優(yōu)先級(jí);“k”表示微粒k;t表示第t代;c1、c2為加速常數(shù);為兩個(gè)相互獨(dú)立的隨機(jī)函數(shù)。

3.2 目標(biāo)函數(shù)的計(jì)算

維修工程需要的總工期是模型的優(yōu)化目標(biāo),對(duì)于一個(gè)優(yōu)化方案P,其工程的總工期T(P)的計(jì)算方法如圖2所示。具體步驟如下:

Step1 初始化項(xiàng)目調(diào)度表,令T(P)=0,調(diào)度項(xiàng)目Xj指向虛項(xiàng)目X1。

Step2 查詢調(diào)度項(xiàng)目Xj的緊后項(xiàng)目Sj。

Step3 查詢Sj中優(yōu)先級(jí)最高的項(xiàng)目。若該項(xiàng)目已調(diào)度過,轉(zhuǎn)入Step2,否則轉(zhuǎn)入Step4。

Step4 查詢項(xiàng)目的緊前項(xiàng)目,若完成,轉(zhuǎn)入Step5,否則轉(zhuǎn)入Step3。

Step6 判斷項(xiàng)目是否全部調(diào)度完畢,若未完成,存儲(chǔ)已調(diào)度項(xiàng)目序號(hào),并令j=j+1,轉(zhuǎn)入Step2,否則,轉(zhuǎn)入Step7。

Step7 令T(P)=TE(Xj)。

圖2 總工期計(jì)算流程

4 實(shí)例

選取某艦艇維修工程實(shí)例部分計(jì)劃進(jìn)行優(yōu)化分析。該工程所需人力資源包括電工、鉗工和銅工三種,每天可調(diào)度人數(shù)分別為30、10、20。圖3為該維修計(jì)劃的工程網(wǎng)絡(luò)計(jì)劃圖,表1為各個(gè)項(xiàng)目所需工期和資源。

圖3 工程網(wǎng)絡(luò)計(jì)劃圖

項(xiàng)目編號(hào)工期(天)電工(人)鉗工(人)銅工(人)X10000X21810010X3240010X42101010X5910010X6122000X715101010X8181000X9150010X101810100X11920010X121510100X130000

為了滿足微粒群體搜索范圍的有效性,設(shè)定群體規(guī)模s為10,加速常數(shù)c1、c2均為0.5,采用Matlab2009R編程,Win7操縱環(huán)境,搜索結(jié)束條件為運(yùn)行100代(t=100),或最優(yōu)目標(biāo)值保持不變10代。

圖4 優(yōu)化搜索過程

圖4為優(yōu)化搜索的過程,如圖所示,隨著搜索代數(shù)的增加,維修工程的總工期(圖中取值為所有微粒最好位置時(shí)的工期)逐漸縮短,優(yōu)化呈現(xiàn)收斂態(tài)勢(shì)。在第44代時(shí)到達(dá)最優(yōu)維修工期87天,最優(yōu)值保持10代到達(dá)54代時(shí)搜索停止。

根據(jù)總工期計(jì)算流程,可以得到修理工程計(jì)劃調(diào)度如表2所示。

表2 修理工程計(jì)劃調(diào)度表

5 結(jié)語

解決資源受限的計(jì)劃維修項(xiàng)目調(diào)度問題,其難點(diǎn)是NP問題的尋優(yōu)求解。本文將NP問題轉(zhuǎn)化為優(yōu)先級(jí)的尋優(yōu)搜索,利用PSO算法求得調(diào)度方案。所研究方法具有一定的工程實(shí)用價(jià)值。

[1] 高健.船舶修理管理研究及信息系統(tǒng)開發(fā)[D].上海:上海海事大學(xué),2007.

[2] 周世雷,鄭映烽,劉子楊,等.艦艇計(jì)劃修理資源約束性項(xiàng)目調(diào)度優(yōu)化[J].四川兵工學(xué)報(bào),2013,34(8):86-89.

[3] Kennedy J, Eberhart R C. Particle swarm optimization[C]//Proceeding of 1995 IEEE International Conference on Neural Networks. New York, NY, USA: IEEE,1995:1942-1948.

[4] 謝曉鋒,張文俊,楊之廉.微粒群算法綜述[J].控制與決策,2003,18(2):129-134.

[5] 沙立成,宋珺琤.基于改進(jìn)粒子群優(yōu)化LS-SVM的變壓器故障氣體預(yù)測(cè)[J].華北電力大學(xué)學(xué)報(bào),2011,38(1):35-38.

[6] 朱童,李小凡,魯明文.位置加權(quán)的改進(jìn)粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(5):4-6.

[7] 趙志剛,常成.帶變異算子的自適應(yīng)粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(17):42-44.

[8] 任子暉,王堅(jiān).加速收斂的粒子群優(yōu)化算法[J].控制與決策,2011,26(2):201-206.

[9] 梁昔明,董淑華.動(dòng)態(tài)慣性權(quán)重和維變異的粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(5):29-31.

[10] 高浩,冷文浩,須文波.一種全局收斂的PSO算法及收斂分析[J].控制欲決策,2009,24(2):196-201.

Optimization of Resource-Constrained Ship Project Scheduling Based on PSO

LIU Lei WANG Ping

(Department of Management Engineering, Naval University of Engineering, Wuhan 430033)

To solve the problem caused by the time and resource constraints in the ship scheduled repair, the particle swarm optimization algorithm for resource scheduling is put forward. The problem of solving polynomial uncertainty is converted into priority search problem, and then the particle swarm algorithm is used to achieve a rapid and effective solving. The engineering examples has been solved reasonably and effectively, solving the problem of minimal with the chemicals resource constraints.

particle swarm optimization, scheduled repair, resource scheduling, priority

2014年11月19日,

2014年12月30日

劉磊,男,碩士研究生,研究方向:軍事運(yùn)籌、裝備保障。王平,男,教授,碩士生導(dǎo)師,研究方向:指揮等。

U674.7

10.3969/j.issn1672-9730.2015.05.029