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

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）PERT

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

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

項目總體估計標(biāo)準(zhǔn)差

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

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

（2）CPM

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

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

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

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

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

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

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

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

（6）工期－成本（資源）優(yōu)化.CPM 是解決工期－成本優(yōu)化的一種較科學(xué)的方法.它包含兩方面的內(nèi)容：一是在滿足成本最低的要求下，尋求最佳工期；二是根據(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 求項目的關(guān)鍵路徑.

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

步驟3 對關(guān)鍵路徑中單位時間成本最小（即總成本增加最少）并且可以壓縮的分段工序進(jìn)行工期壓縮.

步驟4 計算項目總成本，輸出壓縮方案（項目工期及其成本）.

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

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

以如圖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，項目總工期15 d，總成本25.9萬元（路徑R1—R2的工期11 d，成本17.2萬元；路徑R3—R4的工期15 d，成本8.7萬元）.

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

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

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

第四次壓縮，計算可得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 編程實現(xiàn)及實例分析

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

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

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

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

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

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

5 結(jié) 語

結(jié)合CPM的PERT網(wǎng)絡(luò)分析法是一種有效的項目事前控制方法，并能根據(jù)工期與成本間的關(guān)系，對計劃進(jìn)行協(xié)調(diào)和優(yōu)化.船舶建造項目事前可以根據(jù)船廠的實際情況制定比較準(zhǔn)確和穩(wěn)定的建造工藝，并且能根據(jù)船廠的經(jīng)驗數(shù)據(jù)較準(zhǔn)確地估計各分段建造過程中各工序所需時間和資源，這樣的項目適宜于利用PERT網(wǎng)絡(luò)分析法對之進(jìn)行計劃與控制.利用PERT和CPM結(jié)合的方法，比較好地解決了船舶分段建造的計劃協(xié)調(diào)與優(yōu)化問題，方法簡潔適用，加速了計劃的完成，能夠幫助船廠在船舶建造初期制定切實可行的建造計劃.該方法的缺點(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)長春.船體分段制造日程計劃的模擬與優(yōu)化[J].中國造船，2000，41（4）：13－20

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