基于PERT與CPM的船舶分段建造計(jì)劃協(xié)調(diào)與優(yōu)化

張 光 發(fā)， 劉 玉 君， 紀(jì) 卓 尚， 楊 海 天

（1.大連理工大學(xué) 船舶工程學(xué)院，遼寧 大連 116024；2.大連海洋大學(xué) 海洋工程學(xué)院，遼寧 大連 116023）

0 引 言

現(xiàn)代船舶制造模式是按照“以中間產(chǎn)品為導(dǎo)向”的原則進(jìn)行組織的，每個分段都可以看作是一個中間產(chǎn)品，每個分段產(chǎn)品的生產(chǎn)制造都可以看成一項(xiàng)具體的任務(wù)，船舶生產(chǎn)企業(yè)均以分段產(chǎn)品為單位組織生產(chǎn)和制定生產(chǎn)計(jì)劃.殼舾涂一體化的船舶分段建造計(jì)劃是船廠建造計(jì)劃的核心部分，它以船廠分段場地、起重能力、勞動力等資源為約束，以交船日和船廠年度（或三年）滾動生產(chǎn)計(jì)劃為基準(zhǔn)和依據(jù)，平衡協(xié)調(diào)生產(chǎn)資源及其成本，優(yōu)化生產(chǎn)周期，提高各制造平臺的利用率和生產(chǎn)量.由于分段產(chǎn)品及其生產(chǎn)過程復(fù)雜，且涉及各部門間的協(xié)調(diào)合作，船舶分段建造計(jì)劃的制定非常困難.

一般的項(xiàng)目進(jìn)度計(jì)劃常采用Excel表格進(jìn)行任務(wù)分解和工作量估計(jì)以后，利用甘特圖安排日程，雖然簡單明了，形象直觀，但甘特圖在反映各項(xiàng)工作之間的邏輯關(guān)系時比較困難，因而難以確定某項(xiàng)工作推遲對完成工期的影響，不適合船舶生產(chǎn)制造這樣的大型和復(fù)雜工程項(xiàng)目（其任務(wù)可能多達(dá)幾萬項(xiàng)）.另外，如果需要根據(jù)條件計(jì)算每項(xiàng)任務(wù)的開始時間和結(jié)束時間，則需要在OFFICE－PROJECT日程計(jì)劃基礎(chǔ)上利用VBA進(jìn)行二次開發(fā)，以實(shí)現(xiàn)其協(xié)調(diào)優(yōu)化算法，并在已有計(jì)劃的基礎(chǔ)上進(jìn)行計(jì)劃與進(jìn)度的偏差調(diào)整.

國內(nèi)外學(xué)者利用各種技術(shù)，對船舶建造計(jì)劃的制定和優(yōu)化進(jìn)行了研究.Lee等[1]在研究船廠資源及其計(jì)劃組織方式的基礎(chǔ)上，開發(fā)了能力需求計(jì)劃 CRP（capacity requirement planning）系統(tǒng).Neumann[2]基于 MAR II利用調(diào)度網(wǎng)絡(luò)混合的方法，對船舶建造計(jì)劃及其日程表的制定和管理進(jìn)行了研究.Park等[3]對船廠分段制造日程計(jì)劃進(jìn)行了研究，考慮分段的生產(chǎn)日程及其空間布局，提出了部分枚舉和分解調(diào)度的算法，設(shè)計(jì)了啟發(fā)式搜索程序.劉建峰等[4]根據(jù)國內(nèi)船廠的生產(chǎn)實(shí)際，構(gòu)造船舶生產(chǎn)排序函數(shù)以及分段進(jìn)出場地的規(guī)則，對船舶分段制造日程計(jì)劃進(jìn)行了模擬與優(yōu)化.姜禮玲[5]利用模擬與仿真技術(shù)，對船舶建造過程及其計(jì)劃進(jìn)行了分析和優(yōu)化.

上述方法，有的計(jì)算復(fù)雜，需要編制特殊的程序和軟件，有的輸入數(shù)據(jù)和信息比較繁瑣，對使用者和決策者在技術(shù)方面要求比較高，都不太適合于或者實(shí)用于船廠計(jì)劃部門在船舶建造初期的計(jì)劃制定.

網(wǎng)絡(luò)計(jì)劃技術(shù)可以有效解決這些問題.目前，網(wǎng)絡(luò)計(jì)劃技術(shù)主要包括兩種計(jì)劃方法：關(guān)鍵路徑法（critical path method，簡稱CPM）和計(jì)劃評審技術(shù)（program evaluation and review technique，簡稱PERT）.這兩種方法利用網(wǎng)絡(luò)圖分析制定計(jì)劃以及對計(jì)劃予以評價.PERT網(wǎng)絡(luò)圖能描繪出項(xiàng)目所包含的各種活動和任務(wù)的先后次序，標(biāo)明每項(xiàng)活動的時間或相關(guān)的成本.在PERT的基礎(chǔ)上，結(jié)合CPM的分析方法，可以方便地比較不同行動方案在進(jìn)度和成本方面的效果，能協(xié)調(diào)整個計(jì)劃的各道工序，合理安排人力、物力、時間、資金，加速計(jì)劃的完成.在現(xiàn)代計(jì)劃的編制和分析手段上，PERT被廣泛使用，是現(xiàn)代化管理的重要手段和方法.

本文在詳細(xì)分析船舶分段產(chǎn)品制造流程的基礎(chǔ)上，利用網(wǎng)絡(luò)計(jì)劃技術(shù)，結(jié)合CPM和PERT，自動生成船舶分段產(chǎn)品制造計(jì)劃，在工期和成本方面對制造計(jì)劃進(jìn)行協(xié)調(diào)與優(yōu)化；并基于 MSProject軟件，用VBA編制實(shí)用程序，以大連某船廠建造的某油船建造計(jì)劃為實(shí)例進(jìn)行計(jì)算和分析.

1 船舶分段建造流程及其生產(chǎn)計(jì)劃

現(xiàn)代造船模式是殼舾涂一體化的區(qū)域造船作業(yè)模式，該模式將造船工藝過程分解為船體分道制造、區(qū)域舾裝與區(qū)域涂裝三大工藝流程，在設(shè)計(jì)和建造過程中對船舶舾裝與涂裝進(jìn)行統(tǒng)籌安排.船廠將造船作業(yè)分解為一定粒度的生產(chǎn)流程，以船舶分段產(chǎn)品為單位，組織生產(chǎn)計(jì)劃.船舶建造流程一般情況如圖1所示[5]，主要生產(chǎn)流程如下.

（1）船體作業(yè)流程，其主要節(jié)點(diǎn)包括：零部件加工、部件制作、構(gòu)件裝配、分段合攏、船體大合攏.

（2）舾裝作業(yè)流程，其主要節(jié)點(diǎn)包括：材料設(shè)備采購、單元組裝、分段預(yù)舾裝、船上安裝、設(shè)備系統(tǒng)運(yùn)轉(zhuǎn)及試驗(yàn).

（3）涂裝作業(yè)流程，其主要節(jié)點(diǎn)包括：鋼材預(yù)處理、管材涂裝、分段涂裝、單元涂裝、跟蹤補(bǔ)涂、完工涂裝.

圖1 船舶分段建造流程Fig.1 Block construction process of shipbuilding

按照上述船舶制造流程，一般采取倒排計(jì)劃和逐級分解的方法制定船舶分段建造計(jì)劃.先根據(jù)交船日期制定建造計(jì)劃總線表，再根據(jù)分段/總段劃分情況和建造方針，初步確立船舶大節(jié)點(diǎn)計(jì)劃.船臺（或船塢）屬于船廠緊缺資源，要先根據(jù)分段劃分圖，結(jié)合船廠設(shè)備及其他資源制定船臺（或船塢）施工計(jì)劃（即船臺搭載網(wǎng)絡(luò)圖），再以此為基礎(chǔ)，倒排各分段的建造日程計(jì)劃和其他計(jì)劃，正排下水后的碼頭作業(yè)計(jì)劃、船臺（或船塢）內(nèi)的舾裝計(jì)劃和密性試驗(yàn)計(jì)劃等.

制定船舶分段建造計(jì)劃時，要遵循如下原則和要求：單件分段合攏完成的時間滿足船體大合攏的進(jìn)度，以避免在船體鋪龍骨前儲備大量的分段而浪費(fèi)場地資源，從而節(jié)約大量堆放分段的場地和轉(zhuǎn)運(yùn)分段的成本.

2 PERT與CPM網(wǎng)絡(luò)分析方法的基本思想

CPM和PERT是獨(dú)立發(fā)展起來的網(wǎng)絡(luò)計(jì)劃技術(shù).CPM是以經(jīng)驗(yàn)數(shù)據(jù)為基礎(chǔ)來確定各項(xiàng)工作的時間，而PERT則把各項(xiàng)工作的時間作為隨機(jī)變量來處理.前者往往被稱為確定性網(wǎng)絡(luò)計(jì)劃技術(shù)，其以縮短時間、提高投資效益為目的；而后者往往被稱為不確定性網(wǎng)絡(luò)計(jì)劃技術(shù)，其能指出縮短時間、節(jié)約費(fèi)用的關(guān)鍵所在.在實(shí)際使用過程中，如果將兩者有機(jī)結(jié)合，可獲得更顯著的效果.

（1）PERT

PERT以網(wǎng)絡(luò)計(jì)劃技術(shù)為基礎(chǔ)，將工程項(xiàng)目中各個工序任務(wù)的工作時間看作不確定的待定值.通常情況，針對各任務(wù)先估計(jì)一個初始的工期時間，其延誤率為未知，在實(shí)際實(shí)施的過程中處于一種被動變化的狀態(tài).由于組成網(wǎng)絡(luò)計(jì)劃的各項(xiàng)工作可變因素多，其工期統(tǒng)計(jì)資料不足，不能確定出一個肯定的工期.在PERT中引入概率計(jì)算方法對項(xiàng)目的各項(xiàng)任務(wù)進(jìn)行估計(jì)，假設(shè)各項(xiàng)任務(wù)的工期服從β分布，近似地用三時估計(jì)法估算出3個工期值，即最長、最短和最可能工期，再加權(quán)平均算出期望值作為任務(wù)的工期，把三時估計(jì)變?yōu)閱我粫r間估計(jì)，將非確定型轉(zhuǎn)化為確定型，其計(jì)算公式為

式中：ti為任務(wù)i的平均工期，ai為其最短工期（亦稱樂觀估計(jì)時間），bi為其最長工期（亦稱悲觀估計(jì)時間），ci為其正常工期.ai和bi兩種工期一般由統(tǒng)計(jì)方法進(jìn)行估算，而ci可由施工定額（歷史資料）估算.項(xiàng)目的總工期為項(xiàng)目某條路徑上所有任務(wù)的工期和，即D＝∑ti，同時，利用任務(wù)i方差σ2i及其標(biāo)準(zhǔn)差σi對總工期的偏差進(jìn)行估算和分析：

項(xiàng)目總體估計(jì)標(biāo)準(zhǔn)差

另外，PERT把風(fēng)險因素引入到項(xiàng)目計(jì)劃中，考慮按網(wǎng)絡(luò)計(jì)劃在指定的工期下，完成項(xiàng)目任務(wù)的可能性有多大，即計(jì)劃的成功概率，或稱可靠度，并基于此對工程計(jì)劃進(jìn)行風(fēng)險估計(jì).

項(xiàng)目在T時間內(nèi)完工的概率可通過式（4）和查正態(tài)分布函數(shù)表求得.

（2）CPM

CPM體現(xiàn)在項(xiàng)目關(guān)鍵路徑計(jì)算以及基于此的項(xiàng)目計(jì)劃的優(yōu)化上.在項(xiàng)目網(wǎng)絡(luò)計(jì)劃圖中，項(xiàng)目的總工期決定于項(xiàng)目最長的路徑，即關(guān)鍵路徑.計(jì)算關(guān)鍵路徑并對關(guān)鍵路徑上的任務(wù)進(jìn)行工期和資源優(yōu)化，在此基礎(chǔ)上，再對其他路徑上的任務(wù)進(jìn)行調(diào)整，即可達(dá)到對項(xiàng)目總體計(jì)劃優(yōu)化的目的.

3 結(jié)合PERT與CPM協(xié)調(diào)和優(yōu)化船舶分段建造計(jì)劃

對船舶分段建造流程和工序進(jìn)行分析，結(jié)合工廠定額數(shù)據(jù)，利用PERT對各工序進(jìn)行工作量估計(jì)，構(gòu)造船舶分段建造流程PERT網(wǎng)絡(luò)圖，在此基礎(chǔ)上，利用CPM計(jì)算關(guān)鍵路徑，分配和優(yōu)化工期、資源與成本.將PERT與CPM相結(jié)合，協(xié)調(diào)和優(yōu)化船舶分段建造計(jì)劃，其基本步驟如下：

（1）根據(jù)船舶分段建造的特點(diǎn)，分解、定義各分段的建造流程和各工序任務(wù)之間的邏輯關(guān)系，表1分析和總結(jié)了詳細(xì)的船舶制造流程及其相應(yīng)的施工場所，并對其進(jìn)行了編號，以方便編程處理.

（2）根據(jù)分段信息，利用PERT詳細(xì)估計(jì)各分段工序的工作量和工期（如表2所示）.

（3）根據(jù)船廠歷史資料和生產(chǎn)實(shí)際，分析和計(jì)算各分段工序的應(yīng)急（最短）工期及其相應(yīng)的應(yīng)急成本，并為其分配資源，編制成工作任務(wù)表（如表3～5），表中所列的工期為根據(jù)大連某船廠的生產(chǎn)實(shí)際對某油船估算的結(jié)果，基本符合當(dāng)前該廠的實(shí)際情況，用來作為實(shí)際算例的基本數(shù)據(jù).

（4）根據(jù)工序間的邏輯關(guān)系以及工期估計(jì)的數(shù)據(jù)，繪制（構(gòu)造）PERT網(wǎng)絡(luò)圖（如圖2所示）.

（5）計(jì)算PERT網(wǎng)絡(luò)圖的關(guān)鍵路徑、完工期及其概率.完工概率按式（4）計(jì)算.式中計(jì)算的路徑為關(guān)鍵路徑，各工序也為關(guān)鍵路徑上的工序，T為關(guān)鍵路徑總時間.

（6）工期－成本（資源）優(yōu)化.CPM 是解決工期－成本優(yōu)化的一種較科學(xué)的方法.它包含兩方面的內(nèi)容：一是在滿足成本最低的要求下，尋求最佳工期；二是根據(jù)計(jì)劃規(guī)定的期限，規(guī)劃最低成本.工期－成本優(yōu)化的內(nèi)容主要是對關(guān)鍵路徑中的單位時間成本最小的任務(wù)進(jìn)行壓縮和平衡，其具體步驟和算法如下所述.

表1 船舶分段建造流程節(jié)點(diǎn)Tab.1 Nodes of ship block construction flow

表2 PERT工作量估算Tab.2 Workload estimation with PERT

表3 分段制造工序任務(wù)（部分）Tab.3 Procedure tasks of block construction（partial）

表4 總段制造工序任務(wù)（部分）Tab.4 Procedure tasks of assembly construction（partial）

表5 船體大合攏工序任務(wù)（部分）Tab.5 Procedure tasks of hull erection（partial）

圖2 PERT網(wǎng)絡(luò)示意圖Fig.2 PERT network chart

步驟1 求項(xiàng)目的關(guān)鍵路徑.

步驟2 計(jì)算每項(xiàng)任務(wù)的單位時間成本，計(jì)算公式為其中tn、Cn為正常時間、成本，te、Ce為應(yīng)急時間、成本.

步驟3 對關(guān)鍵路徑中單位時間成本最?。纯偝杀驹黾幼钌伲┎⑶铱梢詨嚎s的分段工序進(jìn)行工期壓縮.

步驟4 計(jì)算項(xiàng)目總成本，輸出壓縮方案（項(xiàng)目工期及其成本）.

步驟5 掃描所有工序節(jié)點(diǎn)，檢驗(yàn)是否還可壓縮.如果還有可壓縮的節(jié)點(diǎn)，則進(jìn)行步驟1，再進(jìn)行下一輪壓縮.

步驟6 對所有輸出的方案，根據(jù)輸出的工期及其成本進(jìn)行決策，得到最優(yōu)計(jì)劃.

以如圖3所示的網(wǎng)絡(luò)圖為例，其中，tn、Cn為各工序的正常時間、成本，te、Ce為各工序的應(yīng)急時間、成本.比較正常工期和應(yīng)急工期兩種情況下的關(guān)鍵路徑和成本，可得出：

①在正常工期的情況下，關(guān)鍵路徑為R3—R4，總工期18 d，總成本20.0萬元（路徑R1—R2的工期16 d，成本13萬元；路徑R3—R4的工期18 d，成本7萬元）.

②當(dāng)全部工序均在它們各自的應(yīng)急時間內(nèi)完成，關(guān)鍵路徑為R3—R4，項(xiàng)目總工期15 d，總成本25.9萬元（路徑R1—R2的工期11 d，成本17.2萬元；路徑R3—R4的工期15 d，成本8.7萬元）.

③利用工期 －成本平衡法對那些使總成本增加最少的工序的工期進(jìn)行壓縮，以確定項(xiàng)目最短完成時間.在壓縮過程中，由于項(xiàng)目的總工期由關(guān)鍵路徑的工期決定，優(yōu)先壓縮關(guān)鍵路徑；從關(guān)鍵路徑上具有最低的單位成本的工序開始壓縮.

第一次壓縮，對關(guān)鍵路徑R3—R4進(jìn)行優(yōu)化.計(jì)算單位時間成本，k4＝0.6，k3＝0.5，k2＝1.0，k1＝0.6.k3最小，將工序R3的工期壓縮1 d后項(xiàng)目周期變?yōu)?7 d，總成本20.5萬元.

第二次壓縮，再次找出關(guān)鍵路徑，兩個路徑的工期分別為16、17 d，關(guān)鍵路徑是R3—R4，再次壓縮路徑R3—R4.由于此時工序R3已達(dá)到其應(yīng)急工期9 d，只能加速工序R4的進(jìn)程，將工序R4的工期壓縮1 d，于是項(xiàng)目工期變?yōu)?6 d，總成本21.1萬元.

第三次壓縮，計(jì)算可得R1—R2和R3—R4均為關(guān)鍵路徑.將每個路徑都加速1 d.壓縮路徑R1—R2的工序R1，壓縮路徑R3—R4的工序R4，項(xiàng)目周期縮短為15 d，總成本22.3萬元.

第四次壓縮，計(jì)算可得R1—R2和R3—R4均為關(guān)鍵路徑，其工期相同.將兩條路徑同時加速1 d.但由于路徑R3—R4已達(dá)到其應(yīng)急時間，加速路徑R1—R2的進(jìn)程沒有意義.停止優(yōu)化過程.

④最后輸出如表6所示的工期－成本優(yōu)化結(jié)果，決策者再根據(jù)該表進(jìn)行工期－成本平衡決策.

圖3 工期－成本優(yōu)化示例PERT網(wǎng)絡(luò)圖Fig.3 PERT network chart for demonstrating optimization of duration－cost

表6 工期－成本平衡決策示例Tab.6 Decision－making demonstration for duration－cost balancing

4 編程實(shí)現(xiàn)及實(shí)例分析

基于 MS－Project軟件，利用VBA對上述方法進(jìn)行了編程實(shí)現(xiàn)，并以大連某船廠生產(chǎn)的某油船的建造為實(shí)例，編制了分段建造計(jì)劃PERT圖，并進(jìn)行了優(yōu)化計(jì)算和分析.

程序的輸入數(shù)據(jù)包括：（1）分/總段數(shù)據(jù)，主要有分段各工序標(biāo)準(zhǔn)工作量及成本估計(jì)數(shù)據(jù)、分段合攏順序、總段合攏順序；（2）船舶交工期；（3）分段可進(jìn)入場地開始時間，及其他優(yōu)化限定時間和工期.見表2～5.

輸出數(shù)據(jù)包括：（1）工期－成本平衡決策表，如表7所示；（2）大節(jié)點(diǎn)計(jì)劃表；（3）詳細(xì)節(jié)點(diǎn)計(jì)劃表，如表8所示；（4）分段制造計(jì)劃表；（5）船體大合攏計(jì)劃表.

該船共有114個分段，船體大合攏前共計(jì)32個總段或分段.通過分析計(jì)算，船舶制造總工期（至下水）從最初的104 d縮短到85 d，縮短了18.3%，總成本也由1380萬元縮減到1260萬元，減少了8.7%；通過計(jì)劃協(xié)調(diào)，使每一個分段合攏完成的時間能夠正好滿足船體大合攏的進(jìn)度，使分段合攏的進(jìn)度滿足船體大合攏、分段搭載的生產(chǎn)節(jié)拍要求，最終的計(jì)劃滿足了連續(xù)不斷的準(zhǔn)時生產(chǎn)的現(xiàn)代精益造船要求.

表7 工期－成本平衡決策表Tab.7 Decision－making table for duration－cost balancing

表8 詳細(xì)節(jié)點(diǎn)計(jì)劃表Tab.8 Schedule table of planning nodes

5 結(jié) 語

結(jié)合CPM的PERT網(wǎng)絡(luò)分析法是一種有效的項(xiàng)目事前控制方法，并能根據(jù)工期與成本間的關(guān)系，對計(jì)劃進(jìn)行協(xié)調(diào)和優(yōu)化.船舶建造項(xiàng)目事前可以根據(jù)船廠的實(shí)際情況制定比較準(zhǔn)確和穩(wěn)定的建造工藝，并且能根據(jù)船廠的經(jīng)驗(yàn)數(shù)據(jù)較準(zhǔn)確地估計(jì)各分段建造過程中各工序所需時間和資源，這樣的項(xiàng)目適宜于利用PERT網(wǎng)絡(luò)分析法對之進(jìn)行計(jì)劃與控制.利用PERT和CPM結(jié)合的方法，比較好地解決了船舶分段建造的計(jì)劃協(xié)調(diào)與優(yōu)化問題，方法簡潔適用，加速了計(jì)劃的完成，能夠幫助船廠在船舶建造初期制定切實(shí)可行的建造計(jì)劃.該方法的缺點(diǎn)是將船廠的資源相對于單船建造來說認(rèn)為是無限滿足的，即沒有綜合考慮船舶建造企業(yè)的資源約束問題.

[1]LEE T E，SONG J S.Searched－based heuristic algorithms for basic planning in a large shipyard[J].Journal of Ship Production，1996，12（4）：211－219

[2]NEUMANN R J.Network scheduling development in an MRPⅡenvironment [J].Journal of Ship Production，1994，10（4）：223－232

[3]PARK K，LEE K，PARK S，etal.Modeling and solving the spatial block scheduling problem in a shipbuilding company [J].Computers ＆ Industrial Engineering，1996，30（3）：357－364

[4]劉建峰，秦士元，應(yīng)長春.船體分段制造日程計(jì)劃的模擬與優(yōu)化[J].中國造船，2000，41（4）：13－20

[5]姜禮玲.船臺（塢）總裝網(wǎng)絡(luò)規(guī)劃及其仿真研究[D].上海：上海交通大學(xué)，2008