基于調(diào)度優(yōu)先規(guī)則的海工項(xiàng)目并行進(jìn)度計(jì)劃編制

韓端鋒，王學(xué)營，李敬花

（哈爾濱工程大學(xué) 船舶工程學(xué)院，哈爾濱 150001）

0 引言

目前，船舶及海工裝備制造業(yè)在項(xiàng)目的進(jìn)度計(jì)劃管理中，基本都是由專門的項(xiàng)目計(jì)劃人員來進(jìn)行進(jìn)度計(jì)劃的編制和控制。隨著造船技術(shù)的不斷發(fā)展，模塊化造船、殼舾涂一體化的應(yīng)用越來越普遍，造船效率也有了穩(wěn)步的提升[1]。項(xiàng)目進(jìn)度管理是造船過程中不可或缺的一部分，是提高造船效率的關(guān)鍵環(huán)節(jié)，勢必進(jìn)一步發(fā)展才能適應(yīng)現(xiàn)代的造船流程，為縮短船舶和海工裝備制造周期更好的服務(wù)。海洋工程是復(fù)雜的多元化工程，其建造環(huán)節(jié)繁復(fù)，投資巨大，有效的進(jìn)度計(jì)劃不僅可以提高項(xiàng)目建造進(jìn)程，而且在很大程度上還可降低由于準(zhǔn)備不充分而產(chǎn)生錯(cuò)誤的概率。事實(shí)證明，人工的計(jì)劃編制不僅費(fèi)時(shí)費(fèi)力，在龐大的船舶計(jì)劃系統(tǒng)下，人工編制計(jì)劃還會(huì)有更大的機(jī)率出現(xiàn)失誤，傳統(tǒng)的進(jìn)度計(jì)劃編制機(jī)制在一定程度上已經(jīng)表現(xiàn)出不適應(yīng)性。因此，對海工項(xiàng)目進(jìn)度計(jì)劃編制問題的探討有著一定的理論意義和現(xiàn)實(shí)意義。

1 海工項(xiàng)目進(jìn)度四級計(jì)劃編制

就海工企業(yè)目前的項(xiàng)目管理水平，一般將項(xiàng)目計(jì)劃劃分為三級，并由項(xiàng)目計(jì)劃人員專門制定[2]。文章中的項(xiàng)目進(jìn)度計(jì)劃劃分以企業(yè)的實(shí)際生產(chǎn)進(jìn)程為依據(jù)，將海工項(xiàng)目的進(jìn)度計(jì)劃由上到下劃分為四層，簡稱“四級進(jìn)度計(jì)劃”。

1）一級進(jìn)度計(jì)劃。即里程碑計(jì)劃（圖1），一般由船東提出重要事件節(jié)點(diǎn)，并以此為付款依據(jù)，而海工企業(yè)則據(jù)此來具體安排施工。里程碑計(jì)劃一般包括項(xiàng)目開工、設(shè)計(jì)、采辦、建造、海上安裝調(diào)試、項(xiàng)目交付，采辦中還包括關(guān)鍵設(shè)備到貨日期、長線設(shè)備到貨日期。里程碑計(jì)劃是所有進(jìn)度計(jì)劃的指導(dǎo)及約束，必須嚴(yán)格按照里程碑計(jì)劃完成預(yù)定工作。

2）二級進(jìn)度計(jì)劃（圖2）。在里程碑計(jì)劃的基礎(chǔ)上，對里程碑計(jì)劃的細(xì)化，劃分依據(jù)以海工建造的不同階段為依據(jù)。比如設(shè)計(jì)可劃分為初步設(shè)計(jì)、詳細(xì)設(shè)計(jì)、生產(chǎn)設(shè)計(jì)等，采辦根據(jù)不同材料屬性不同可分為鋼材、油漆、機(jī)械設(shè)備、電氣設(shè)備等，生產(chǎn)則依據(jù)海洋平臺(tái)的模塊劃分為上層建筑、立柱、浮體結(jié)構(gòu)、撐管、鉆臺(tái)等部分。

圖1 一級進(jìn)度計(jì)劃

圖2 二級進(jìn)度計(jì)劃

圖3 三級進(jìn)度計(jì)劃

圖4 三級進(jìn)度計(jì)劃

3）三級進(jìn)度計(jì)劃（圖3）。在二級計(jì)劃的基礎(chǔ)上進(jìn)一步細(xì)化，設(shè)計(jì)計(jì)劃中把各分設(shè)計(jì)計(jì)劃按照平臺(tái)劃分為比如上層建筑的初步設(shè)計(jì)、立柱的初步設(shè)計(jì)、浮體結(jié)構(gòu)的初步設(shè)計(jì)等；上層建筑的詳細(xì)設(shè)計(jì)、立柱的詳細(xì)設(shè)計(jì)、浮體結(jié)構(gòu)的詳細(xì)設(shè)計(jì)等；上層建筑的生產(chǎn)設(shè)計(jì)、立柱的生產(chǎn)設(shè)計(jì)、浮體結(jié)構(gòu)的生產(chǎn)設(shè)計(jì)等。采辦在材料為依據(jù)的劃分基礎(chǔ)上，制定了不同材料的不同批次到貨節(jié)點(diǎn)。生產(chǎn)則進(jìn)一步將不同的模塊劃分成各個(gè)分段的項(xiàng)目進(jìn)度計(jì)劃，比如上層建筑分段一、上層建筑分段二等，立柱分段一、立柱分段二等，浮體結(jié)構(gòu)分段一、浮體結(jié)構(gòu)分段二。

4）四級進(jìn)度計(jì)劃（圖4）。明確并詳細(xì)劃分三級進(jìn)度計(jì)劃下的各個(gè)子計(jì)劃。設(shè)計(jì)將各分段的不同設(shè)計(jì)進(jìn)行詳細(xì)的劃分，比如不同圖紙的提交節(jié)點(diǎn)。四級生產(chǎn)計(jì)劃把海洋平臺(tái)不同模塊的各分段劃分到組立層次。

2 活動(dòng)調(diào)度優(yōu)先規(guī)則及并行進(jìn)度方案

2.1 活動(dòng)調(diào)度優(yōu)先規(guī)則

多年來，研究者在工程實(shí)踐和理論研究中，總結(jié)并積累了多種多樣的優(yōu)先規(guī)則，應(yīng)用不同的調(diào)度優(yōu)先規(guī)則所得的調(diào)度順序也并不盡相同。調(diào)度的優(yōu)先規(guī)則大致可分為以下幾種類型：

1）基于關(guān)鍵路徑

基于關(guān)鍵路徑的調(diào)度規(guī)則是以關(guān)鍵路徑為依據(jù)來進(jìn)行活動(dòng)的調(diào)度，最常用的調(diào)度方法是以項(xiàng)目活動(dòng)的總浮動(dòng)時(shí)間節(jié)點(diǎn)來進(jìn)行優(yōu)先活動(dòng)的選擇。典型的基于關(guān)鍵路徑的調(diào)度優(yōu)先規(guī)則有：最早開始時(shí)間優(yōu)先、最晚開始時(shí)間優(yōu)先、最早結(jié)束時(shí)間優(yōu)先、最晚結(jié)束時(shí)間優(yōu)先等。

2）基于網(wǎng)絡(luò)圖

基于網(wǎng)絡(luò)圖的調(diào)度規(guī)則考慮的是目標(biāo)項(xiàng)目在網(wǎng)絡(luò)圖中所呈現(xiàn)的內(nèi)容，比如：項(xiàng)目各活動(dòng)間的緊前約束關(guān)系、緊后約束關(guān)系及活動(dòng)后續(xù)任務(wù)的數(shù)目。典型的基于網(wǎng)絡(luò)圖的調(diào)度優(yōu)先規(guī)則有：最小工時(shí)優(yōu)先、最多緊前活動(dòng)優(yōu)先、最多緊后活動(dòng)優(yōu)先等。

3）基于資源優(yōu)先

基于資源優(yōu)先的項(xiàng)目調(diào)度規(guī)則主要是依據(jù)不同的項(xiàng)目活動(dòng)對資源需求量的不同來進(jìn)行活動(dòng)安排。典型的基于資源的項(xiàng)目調(diào)度規(guī)則有：資源最大需求總量優(yōu)先、最大資源利用率優(yōu)先。

調(diào)度優(yōu)先規(guī)則的選擇對項(xiàng)目的活動(dòng)安排會(huì)起到關(guān)鍵作用，所以要選擇適當(dāng)?shù)膬?yōu)先規(guī)則，表1對一些規(guī)則進(jìn)行了列舉[4]。

在海工項(xiàng)目進(jìn)度管理中，首要考慮的是時(shí)間問題，如何使項(xiàng)目在最短的時(shí)間內(nèi)完成是問題的關(guān)鍵，所以文章選擇以最大最早完成時(shí)間為首要規(guī)則，即對具有最大最早完成時(shí)間的活動(dòng)優(yōu)先調(diào)度。其次，資源需求量作為項(xiàng)目調(diào)度的約束條件，理應(yīng)考慮在內(nèi)，故選擇資源需求總量作為優(yōu)先調(diào)度規(guī)則。最后，海工項(xiàng)目的活動(dòng)調(diào)度，并不能盲目的尋求最短工期，還要考慮到海工企業(yè)總體效益。因此，活動(dòng)資源成本也作為優(yōu)先調(diào)度規(guī)則。

表1 調(diào)度優(yōu)先規(guī)則

2.2 并行進(jìn)度方案

當(dāng)前應(yīng)用較廣泛的進(jìn)度生成方案主要有串行進(jìn)度方案（Serial Scheduling Generation Scheme，SSGS）和并行進(jìn)度方案（Parallel Scheduling Generation Scheme，PSGS）[5]。串行進(jìn)度方案在每一個(gè)階段只為項(xiàng)目進(jìn)度安排一項(xiàng)活動(dòng)，而并行進(jìn)度方案不同于串行進(jìn)度方案的地方在于其每一個(gè)階段針對可行活動(dòng)集En中的所有活動(dòng)進(jìn)行安排，每一階段只受項(xiàng)目資源約束。

文章采用并行進(jìn)度方案。設(shè)階段m的完成時(shí)刻Fm，已完成的活動(dòng)集合為Cm，在Fm時(shí)刻正在進(jìn)行的活動(dòng)集合為Am，此時(shí)可行工序集合為：

其中Pi為工序i的緊前工序集合，rikρ為活動(dòng)i每天對資源k的資源需求量，Rikρ為資源k的每日可用量。并行方案與串行方案之間很大的區(qū)別在于串行方案未考慮資源的約束。應(yīng)用并行進(jìn)度方案步驟如下：

1）由階段m的數(shù)據(jù)計(jì)算Fm+1，Cm+1和Am+1；

2）更新各種資源的剩余量Rk和Em+1；

3）按優(yōu)先權(quán)從高到低順序從Em中選擇活動(dòng)i，若當(dāng)前資源剩余量大于活動(dòng)i的需求量，則安排活動(dòng)i；

4）更新各種資源剩余量和Em；

5）重復(fù)以上步驟可知Em為空。

具體過程可用圖5進(jìn)行描述[6]。

3 數(shù)學(xué)模型及算法設(shè)計(jì)

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

為滿足對初始進(jìn)度計(jì)劃的數(shù)學(xué)描述，定義初始進(jìn)度計(jì)劃滿意率&，定義，F(xiàn)n為項(xiàng)目最后一項(xiàng)活動(dòng)的完成時(shí)間。項(xiàng)目最后一項(xiàng)活動(dòng)的完成時(shí)間代表項(xiàng)目的工期，工期越短，對項(xiàng)目進(jìn)度計(jì)劃的滿意度越高，對滿意率的求解轉(zhuǎn)化為最后一項(xiàng)活動(dòng)的完成時(shí)間最早。

進(jìn)行項(xiàng)目進(jìn)度計(jì)劃的編制，建立如下數(shù)學(xué)模型：

其中：式(2)為目標(biāo)函數(shù)，表示項(xiàng)目工期最短；式(3)保證開始階段的活動(dòng)安排數(shù)為0；式(4)約束每項(xiàng)活動(dòng)的資源使用量不多于資源總量；式(5)代表緊前約束關(guān)系；式(6)確保每項(xiàng)活動(dòng)的安排不為空；式(7)保證資源的剩余量為有效；式(8)表示最后一項(xiàng)活動(dòng)的完成時(shí)間滿足最長工期要求。

對數(shù)學(xué)模型的求解應(yīng)用并行調(diào)度方案，Em為空則完成一個(gè)循環(huán)，進(jìn)入下一個(gè)循環(huán)。如果在并行調(diào)度的執(zhí)行過程中存在某個(gè)被調(diào)度活動(dòng)的開始時(shí)間小于0，則說明并行調(diào)度方案不能得到問題的解，此時(shí)停止并行調(diào)度操作。

表5 并行進(jìn)度方案圖例

3.2 編碼機(jī)制

假設(shè)有n個(gè)項(xiàng)目活動(dòng)，對其按持續(xù)時(shí)間長短順序排列后各活動(dòng)有整數(shù)編號(hào)i，Hn=[i1,i2,…,in]是這n的待安排活動(dòng)的一個(gè)排列，在排列Hn中為每個(gè)活動(dòng)定義屬性活動(dòng)時(shí)間ti，資源約束ri和緊前約束xi，則Z=[(i1,t1,r2,x3),(i2,t2,r2,x2),…,(in,tn,rn,xn)]就是遺傳個(gè)體的染色體編碼。其中：ij是排列中第j個(gè)活動(dòng)的編號(hào)，tj是第j個(gè)活動(dòng)的持續(xù)時(shí)間，rj是第j個(gè)活動(dòng)的資源需求，xj是第j個(gè)活動(dòng)的緊前約束關(guān)系。

假設(shè)進(jìn)行活動(dòng)安排時(shí)，各項(xiàng)目活動(dòng)的時(shí)間固定，資源需求固定，對項(xiàng)目活動(dòng)的安排僅限對活動(dòng)順序的調(diào)度。根據(jù)活動(dòng)調(diào)度優(yōu)先規(guī)則的定義，約束條件相似的活動(dòng)間，具有更早LST的項(xiàng)目活動(dòng)有較高的調(diào)度優(yōu)先級，其次為活動(dòng)的資源需求GRD。因此定義：

其中，令α+β=0，α＞β＞0，即認(rèn)為優(yōu)先考慮項(xiàng)目活動(dòng)的最早完成時(shí)間。

由此定義個(gè)體適應(yīng)度評價(jià)函數(shù)：

如果F(xi)＞F(xj)，則說明活動(dòng)個(gè)體xi優(yōu)先進(jìn)行安排將獲得更優(yōu)的結(jié)果。

3.3 選擇運(yùn)算

為了將種群中的最優(yōu)化個(gè)體保留在群體中，設(shè)定適應(yīng)度值越高的個(gè)體被遺傳到下一代的概率越大，定義個(gè)體Xi被選擇的概率為，選擇運(yùn)算過程中，隨機(jī)生成一個(gè)[0,1]的數(shù)G，如果有，則個(gè)體Xi被選擇遺傳到下一代。

3.4 變異運(yùn)算

考慮到資源的平衡問題，文章算法只進(jìn)行變異操作而不進(jìn)行交叉。根據(jù)不同屬性的類型不同，運(yùn)算過程中會(huì)產(chǎn)生基因變異，由于各染色體的屬性固定不變，因此僅考慮基因的排序變異。排序變異即染色體編碼位置的變換，隨機(jī)挑選兩個(gè)位置不同的基因，并交換對應(yīng)位置的基因編碼[8]。變異實(shí)例如表2所示。

表2 排序變異實(shí)例

3.5 退火操作

由種群兩個(gè)父代個(gè)體p1和p2經(jīng)過變異運(yùn)算后，生成兩個(gè)子代c1和c2，父代個(gè)體和子代個(gè)體分別組成兩個(gè)組p1，c1和p2，c2，進(jìn)化過程中以一定概率P接受父代個(gè)體為下一代種群中的個(gè)體，以概率1-p接受子代個(gè)體為新種群個(gè)體。其中：

式中： Fp和Fc分別為父代和子代個(gè)體對應(yīng)的個(gè)體適應(yīng)度；T為溫度參數(shù)，其大小根據(jù)問題規(guī)模選取。

3.6 終止條件

結(jié)合算法融合的特點(diǎn)給出以下三種終止準(zhǔn)則：

1）迭代計(jì)算達(dá)到一定程度之后，適應(yīng)度函數(shù)值在連續(xù)多次迭代中，無明顯變化，終止計(jì)算。

2）最大迭代次數(shù)達(dá)到用戶設(shè)定的要求時(shí)，停止計(jì)算。

3）按平均適應(yīng)度終止原則。如果多次迭代后，群體之間的平均適應(yīng)度差值小于用戶設(shè)定的平均適應(yīng)度差值常數(shù)，則認(rèn)為算法已收斂，終止進(jìn)化[9]。

3.7 求解步驟

初始種群的規(guī)模對算法的執(zhí)行效率有一定的影響，過高的種群規(guī)模會(huì)較大的提高計(jì)算的復(fù)雜度，文章算法取N=30。變異概率的設(shè)置可以較好的控制優(yōu)秀基因的流失，避免較優(yōu)解在搜索過程中因變異而改變，取變異概率Pm=0.001。其他基本參數(shù)設(shè)置：Metropolis鏈長度為9000，初溫2000，溫度衰減參數(shù)取200，平均適應(yīng)度差值常數(shù)為0.0001，最大迭代數(shù)為200?；具z傳算法步驟如下[10]：

表6 算法流程

1）設(shè)置編碼長度、種群規(guī)模、Metropolis鏈長、初溫、冷卻參數(shù)、進(jìn)化代數(shù)、平均適應(yīng)差值常數(shù)等。

2）進(jìn)行迭代計(jì)數(shù)器初始化操作，設(shè)置t=0。

3）隨機(jī)產(chǎn)生初始種群p0(t)。

4）個(gè)體評價(jià)，即計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度，并保存種群當(dāng)前最優(yōu)個(gè)體。

5）按選擇概率Ps，執(zhí)行選擇算子，從當(dāng)前種群中選擇部分個(gè)體進(jìn)入下一代種群。

6）按變異概率Pm，對種群進(jìn)行變異操作，得到新的種群p1(t)。

7）基于模擬退火的Metropolis準(zhǔn)則，對種群個(gè)體操作產(chǎn)生新種群p2(t)。

8）進(jìn)行種群個(gè)體選擇與復(fù)制操作，得到種群p3(t)=Re-Produce[p(t),p2(t)]。

9）計(jì)算種群p3(t)的適應(yīng)度，采用退火操作產(chǎn)生新的種群p(t+1)。

10）終止條件判斷，若不滿足終止條件，則t=t+1，轉(zhuǎn)步驟4；若滿足條件，則執(zhí)行步驟11。

11）輸出滿足條件的解。

算法流程如圖6所示。

4 實(shí)例驗(yàn)證及結(jié)論

為了驗(yàn)證調(diào)度原則和算法的有效性，文章以某自升式海洋平臺(tái)為例，進(jìn)行初始進(jìn)度計(jì)劃的生成。表3中給出了平臺(tái)四級計(jì)劃層中某一部分的活動(dòng)及數(shù)據(jù)。應(yīng)用遺傳模擬退火算法進(jìn)行計(jì)算后生產(chǎn)如圖7所示的初始進(jìn)度計(jì)劃。

文章針對海工項(xiàng)目的進(jìn)度計(jì)劃編制問題，根據(jù)海工企業(yè)的實(shí)際項(xiàng)目生產(chǎn)進(jìn)程提出了基于平臺(tái)結(jié)構(gòu)的四級進(jìn)度計(jì)劃，明確具體劃分細(xì)節(jié)，引入項(xiàng)目活動(dòng)的調(diào)度優(yōu)先規(guī)則和并行調(diào)度規(guī)則，采用遺傳模擬退火融合算法對進(jìn)度計(jì)劃編制問題進(jìn)行求解。融合后的算法克服了各自算法局部搜索能力和全局搜索能力的缺點(diǎn)，實(shí)現(xiàn)了優(yōu)勢互補(bǔ)，并成功應(yīng)用到了海工項(xiàng)目實(shí)例中。

表3 某自升式海洋平臺(tái)參數(shù)

表7 初始方案節(jié)點(diǎn)圖

[1]賈恒濤.船舶壓載艙殼舾涂一體化技術(shù)要求研究[J].造船技術(shù), 2010, 4: 40-42.

[2]李筱磊.CCPM在造船項(xiàng)目計(jì)劃管理中的應(yīng)用研究[D].大連:大連理工大學(xué).2010.

[3]Wysocki.R.K., McGary.R.Effective Project Management[M].Indiana: Wiley Publishing.2010.

[4]朱曉璐.基于灰色斜率分析的資源受限項(xiàng)目調(diào)度問題研究與應(yīng)用[D].重慶:重慶大學(xué).2011.

[5]Peter Brucker, Andreas Drexl.Resource-constrained project scheduling:Notation, classification, models, and methods[J].European Journal of Operational Research,1999, 3(41):4-41.

[6]李倩, 劉霽.基于蟻群算法的工程項(xiàng)目資源受限施工進(jìn)度優(yōu)化[J].中南林業(yè)科技大學(xué)學(xué)報(bào), 2011, 31(8):147-151.

[7]James M.Erickson, C.Ranganathan.Project Management Capabilities: Key to Application Development Offshore Outsourcing[C].2006 IEEE Proceedings of the 39th Hawaii International Conference on System Sciences, 2006:1-10.

[8]Fayez F, Boctor.A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes[J].European Journal of Operational Research, 1996,90: 349-361.

[9]楊利宏, 楊東.基于遺傳算法的資源約束型項(xiàng)目調(diào)度優(yōu)化[J].管理科學(xué), 2008, 21(4):60-68.

[10]李敬花, 樊付見, 王昊, 等.遺傳模擬退火融合算法求解工程二維排樣問題[J].計(jì)算機(jī)集成制造系統(tǒng), 2011,17(9):1962-1967.