加工時(shí)間不確定的船體分段空間調(diào)度方法

張志英，張風(fēng)薇

(同濟(jì)大學(xué) 機(jī)械工程學(xué)院，上海200092)

目前在大型離散制造企業(yè)如船舶和飛機(jī)制造中，動(dòng)態(tài)空間調(diào)度是一個(gè)典型問(wèn)題，它是指在空間布局的基礎(chǔ)上兼顧時(shí)間效率，綜合考慮空間因素和時(shí)間因素相互制約、相互影響的耦合關(guān)系，從而來(lái)安排生產(chǎn)調(diào)度計(jì)劃.針對(duì)這類(lèi)問(wèn)題，目前專(zhuān)家學(xué)者普遍采用的解決方法是人工智能優(yōu)化算法和基于規(guī)則的啟發(fā)式方法［1］.

針對(duì)船舶建造過(guò)程中的空間調(diào)度問(wèn)題，Lee等提出了基于船舶形狀的啟發(fā)式調(diào)度規(guī)則［2］;鄭俊麗等運(yùn)用形狀相似和工藝相似策略，提出了一種縮短最大完工時(shí)間的船舶分段空間調(diào)度算法［3］;陳潔等運(yùn)用運(yùn)籌學(xué)方法結(jié)合場(chǎng)地平均時(shí)空利用率指標(biāo)構(gòu)建綜合加工優(yōu)先順序、交貨期等因素的非線性規(guī)劃模型［4］.然而，上述方法都將船舶分段空間調(diào)度假定為在一個(gè)確定的生產(chǎn)環(huán)境中進(jìn)行，實(shí)際船舶分段建造過(guò)程中往往存在大量不確定因素如急件插入和隨機(jī)的設(shè)備故障等，而且還存在大量不精確信息如分段開(kāi)工時(shí)間、完工時(shí)間和加工時(shí)間等，以及不完備信息如原材料的質(zhì)量狀況、在制品生產(chǎn)情況等.這些不確定因素、不精確和不完備信息會(huì)導(dǎo)致分段及其關(guān)聯(lián)件的建造不能按照計(jì)劃進(jìn)行，出現(xiàn)提前/拖期等現(xiàn)象，最直接體現(xiàn)在對(duì)加工時(shí)間的影響，使得加工時(shí)間表現(xiàn)為模糊數(shù)［5］或隨機(jī)分布，如正態(tài)分布［6］.因此，這種由隨機(jī)環(huán)境產(chǎn)生的調(diào)度方案也不是唯一的，根據(jù)計(jì)劃人員對(duì)生產(chǎn)環(huán)境給出的不同評(píng)估，在不同影響因子條件下將有不同的調(diào)度方案.這就需要研究不確定環(huán)境下的調(diào)度問(wèn)題，針對(duì)各種置信水平的不確定生產(chǎn)環(huán)境提出可行的調(diào)度解.張麗華等在加工時(shí)間和工件交付期都服從指數(shù)分布的條件下，提出了最優(yōu)調(diào)度的幾個(gè)性質(zhì)，并運(yùn)用動(dòng)態(tài)規(guī)劃的方法給出了求解最優(yōu)解的算法［7］;朱海平等提出一種支持多目標(biāo)和多優(yōu)先級(jí)車(chē)間調(diào)度策略的隨機(jī)規(guī)劃模型，并給出了求解算法，從而在不確定的車(chē)間信息環(huán)境下做出正確調(diào)度策略［8］;R.Tavakkoli-Moghaddam等提出了解決設(shè)備布局問(wèn)題的數(shù)學(xué)模型，運(yùn)用該模型能最小化設(shè)備、廠房布局的總成本［9］.

本文綜合考慮了分段空間調(diào)度問(wèn)題中的時(shí)空耦合性以及不確定因素造成的加工時(shí)間隨機(jī)性，建立加工時(shí)間不確定環(huán)境下的船體分段空間調(diào)度模型，結(jié)合某大型船廠實(shí)際生產(chǎn)數(shù)據(jù)進(jìn)行驗(yàn)證，得出不同置信水平下的調(diào)度解，結(jié)果表明該方法更符合船廠分段建造調(diào)度的實(shí)際情況.

1 問(wèn)題描述與假設(shè)

在船舶分段建造中，空間調(diào)度問(wèn)題普遍存在.與以往生產(chǎn)知識(shí)確定下的分段調(diào)度相比，該類(lèi)問(wèn)題主要體現(xiàn)在分段建造的時(shí)間還受到其關(guān)聯(lián)件的影響，并且加工時(shí)間不再是唯一確定的，而是服從隨機(jī)分布的變量.而一般的船體分段建造空間調(diào)度問(wèn)題可以簡(jiǎn)化為分段最大包絡(luò)投影面積以及時(shí)間因素的三維裝箱模型，在時(shí)間約束方面，若分段之間具有緊前緊后關(guān)系，那么后續(xù)分段只有在前面的分段生產(chǎn)完畢后才能開(kāi)始生產(chǎn)，而如果分段帶有旁板等關(guān)聯(lián)件的，分段和旁板的加工時(shí)間必須滿足它們的關(guān)聯(lián)約束.在空間方面，分段和分段之間不允許出現(xiàn)干涉現(xiàn)象，分段放置也不允許超出場(chǎng)地邊界.若假設(shè)場(chǎng)地和分段的投影都為矩形，則分段建造空間調(diào)度模型如圖1所示.

圖1 包含5 個(gè)分段 B={B1，B2，B3，B4，B5}，其中 P1、P2分別是 B1、B2的旁板，受 B1、B2的關(guān)聯(lián)約束作用.當(dāng)旁板P2在建造過(guò)程中遇到不確定因素，加工時(shí)間延長(zhǎng)同時(shí)直接影響到B2、B52個(gè)分段.由于P2的拖期使得B2的加工時(shí)間也相應(yīng)地增加，此外B5拖期會(huì)超出整個(gè)場(chǎng)地的生產(chǎn)周期.在這種情況下，需要重新安排分段和旁板在場(chǎng)地上的位置，使得分段能按計(jì)劃完工，減少因不確定因素額外產(chǎn)生的成本.而一般旁板開(kāi)工時(shí)間和對(duì)應(yīng)分段開(kāi)工時(shí)間有關(guān)聯(lián)約束，因此旁板的調(diào)整需考慮對(duì)應(yīng)分段的時(shí)間和空間的安排，對(duì)于圖1的模型，當(dāng)產(chǎn)生上述不確定情況時(shí)，一種調(diào)整方法是將B5重新布局，如圖2所示.

圖1 分段空間調(diào)度模型Fig.1 Block spatial scheduling model

由圖2可知，經(jīng)過(guò)調(diào)整后的分段和旁板滿足時(shí)間和空間約束，同時(shí)減少了因不確定因素對(duì)其他分段產(chǎn)生的影響，具有較高的生產(chǎn)效率.

在船體分段建造的諸多不確定因素中，加工時(shí)間不確定最常見(jiàn)，這里主要考慮因分段關(guān)聯(lián)件旁板加工時(shí)間而引起分段加工時(shí)間的不確定性.因此，該類(lèi)問(wèn)題可描述為:在一個(gè)調(diào)度計(jì)劃周期內(nèi)有n個(gè)待調(diào)度的船體分段 B={B1，…Bi，…，Bn}，每個(gè)分段Bi對(duì)應(yīng)有若干個(gè)旁板，總共有x個(gè)旁板(其中i代表分段編號(hào)，i≥1;x代表旁板總數(shù)，x≥0)，將所有旁板按最早開(kāi)工時(shí)間排序得旁板集合P={P1，…，Pg，…，Px}，分段和旁板在m個(gè)場(chǎng)地上加工.

圖2 調(diào)整后的調(diào)度結(jié)果Fig.2 The schedu ling result after adjust ment

在加工時(shí)間不確定的分段建造動(dòng)態(tài)空間調(diào)度問(wèn)題中需要滿足以下約束:

1)待調(diào)度的分段和旁板抽象為其垂直投影的最小包絡(luò)矩形，假設(shè)矩形只有0°和90°2種放置狀態(tài)，令長(zhǎng)邊li/lg平行于x軸的狀態(tài)為1，反之為0;

2)場(chǎng)地形狀假設(shè)為矩形.場(chǎng)地k長(zhǎng)度為L(zhǎng)k，寬度為Wk，設(shè)場(chǎng)地左下角為坐標(biāo)原點(diǎn)(0，0)，建立以長(zhǎng)度方向?yàn)閤軸，寬度方向?yàn)閥軸，豎直方向?yàn)闀r(shí)間z軸的三維坐標(biāo)系(以上均為正方向);

3)一個(gè)分段和旁板不能同時(shí)在不同的加工平臺(tái)上加工，且一旦開(kāi)始加工，必須等到完成后才能移出;

4)由于分段和旁板的加工時(shí)間受不確定因素影響，在實(shí)際生產(chǎn)中體現(xiàn)為以計(jì)劃給出的加工時(shí)間為均值，服從某種隨機(jī)分布的變量.本文假定分段和旁板的實(shí)際開(kāi)工時(shí)間、加工時(shí)間和完工時(shí)間都服從正態(tài)分布，而僅有最早開(kāi)工時(shí)間和交貨期為確定值;

5)假設(shè)人員充分，設(shè)備無(wú)故障，忽略分段和旁板的吊運(yùn)時(shí)間和其他物料的準(zhǔn)備時(shí)間，即認(rèn)為僅有旁板加工過(guò)程中的不確定性能傳遞給與它相應(yīng)的分段，并且這種不確定性能積累從而影響到分段建造的空間調(diào)度結(jié)果，最直觀表現(xiàn)為分段和旁板的加工時(shí)間為服從正態(tài)分布的隨機(jī)變量.

在滿足上述約束條件下，由于生產(chǎn)環(huán)境不確定因素影響造成分段建造的提前和拖期，提前完工產(chǎn)生存儲(chǔ)成本，拖期完工產(chǎn)生延遲成本.本文以旁板建造加工時(shí)間的偏差作為整體分段建造調(diào)度過(guò)程中唯一不確定影響因素，建立加工時(shí)間不確定條件下的分段建造空間調(diào)度模型.為了描述這個(gè)模型，這里引入時(shí)空占用成本(time-space occupied costs，TSOC)指標(biāo).

由于分段建造提前完工和拖期完工產(chǎn)生的成本不一樣，一般拖期完工比提前完工產(chǎn)生的成本要大很多，而不同分段由于尺寸差異，占用的空間成本也不同.本文以分段和旁板的最大包絡(luò)投影面積和實(shí)際完工時(shí)間對(duì)交貨期的偏差量乘積為時(shí)空占用成本，有以下相關(guān)定義:

定義1 對(duì)長(zhǎng)為l，寬為w的分段，若完工時(shí)間c早于交貨期d，則它的提前時(shí)空占用成本:

其中α是分段的提前完工懲罰成本.

定義2 對(duì)長(zhǎng)為l，寬為w的分段，若完工時(shí)間c晚于交貨期d，則它的拖期時(shí)空占用成本:

其中β是分段的拖期完工懲罰成本.

定義3 對(duì)帶關(guān)聯(lián)約束的分段，還有旁板加工時(shí)間偏差累積產(chǎn)生的偏差時(shí)空占用成本:

其中，|var(p)|表示分段加工時(shí)間p受不確定因素影響的偏差值，ξp表示概率P條件下，服從標(biāo)準(zhǔn)正態(tài)分布的變量.

對(duì)于選定生產(chǎn)周期內(nèi)的分段和旁板總的時(shí)空占用成本，由于它既包含提前時(shí)空占用成本和拖期時(shí)空占用成本，還有旁板加工時(shí)間偏差累積產(chǎn)生的偏差時(shí)空占用成本，因此總的時(shí)空占用成本為這三部分成本的累加和.

定義4 對(duì)于選定生產(chǎn)周期內(nèi)的分段和旁板總的時(shí)空占用成本:

針對(duì)加工時(shí)間不確定的分段空間建造模型，它的目標(biāo)是最小化TSOC，以得到不同置信水平下的調(diào)度解.根據(jù)以上假設(shè)，含關(guān)聯(lián)約束的加工時(shí)間不確定分段建造空間調(diào)度問(wèn)題解可表示為

其中:η為根據(jù)實(shí)際生產(chǎn)情況選擇的置信水平;i、g表示分段號(hào)和旁板號(hào);xi、yi表示分段i左下點(diǎn)坐標(biāo);xg、yg表示旁板g左下點(diǎn)坐標(biāo);zi表示分段i實(shí)際開(kāi)工時(shí)間;zg表示旁板g實(shí)際開(kāi)工時(shí)間;dxi/dxg表示分段i/旁板g相對(duì)于場(chǎng)地的放置方向，若長(zhǎng)邊li/lg平行于x軸，則dxi/dxg為1，反之為0;fi/fg表示分段i/旁板g經(jīng)過(guò)計(jì)劃后放置的場(chǎng)地.

2 不確定空間調(diào)度模型

2.1 機(jī)會(huì)約束下的不確定規(guī)劃模型

分段空間調(diào)度問(wèn)題通常用非線性規(guī)劃模型來(lái)描述.而考慮不確定因素的調(diào)度問(wèn)題，由于目標(biāo)函數(shù)和約束條件已經(jīng)不能按通常意義理解，因此要考慮有別于確定條件下調(diào)度模型的新理論和算法.機(jī)會(huì)約束規(guī)劃就是這樣一類(lèi)符合不確定條件下含隨機(jī)變量的新規(guī)劃理論，其特點(diǎn)是隨機(jī)約束條件至少以一定的置信水平成立.下面引入文獻(xiàn)［16］給出的機(jī)會(huì)約束和不確定規(guī)劃的概念.

假設(shè)x是一個(gè)決策向量，E是一個(gè)概率分布已知的隨機(jī)向量，由x和E確定的n個(gè)目標(biāo)函數(shù)記為fi=(x，e)，1 ≤ i≤ n，它受制于 m 個(gè)約束函數(shù)gj=(x，e)，1≤j≤m.由于目標(biāo)函數(shù)和約束函數(shù)都具有隨機(jī)性，因此只能通過(guò)置信概率的形式對(duì)目標(biāo)和約束進(jìn)行描述.因此，對(duì)應(yīng)的機(jī)會(huì)約束可以表示為P{gj(x，E)≤0}≥α j，1≤j≤m，其中 P 表示隨機(jī)事件gj(x，E)≤0發(fā)生的概率，αj為置信概率;若規(guī)劃問(wèn)題的目標(biāo)是fi=(x，E)，1≤i≤n盡可能小，可取置信概率為βi，則任一目標(biāo)函數(shù)表示為

基于多機(jī)會(huì)約束的多目標(biāo)不確定性規(guī)劃模型可表示為

2.2 不確定空間調(diào)度策略

在船舶分段建造過(guò)程中，分段在場(chǎng)地上的加工時(shí)間是服從某種分布的隨機(jī)變量，因此分段的完工時(shí)間也是不確定的，分段建造空間調(diào)度約束可以描述為機(jī)會(huì)約束.假設(shè)有n種置信水平，則受關(guān)聯(lián)約束的加工時(shí)間不確定分段建造空間調(diào)度模型將產(chǎn)生n個(gè)調(diào)度解，分別歸為集合 S1，S2，…，Sn，每個(gè)集合對(duì)應(yīng)的置信概率分別為 α1，α2，…，αn，令空間調(diào)度的空間和時(shí)間約束為

減少因提前、拖期產(chǎn)生的時(shí)空占用成本是調(diào)度的主要目標(biāo).設(shè)不同隨機(jī)因素的影響下，置信概率分別為 η1，η2，…，ηr，用機(jī)會(huì)約束描述為

綜合2.1和2.2節(jié)，受關(guān)聯(lián)約束的加工時(shí)間不確定的分段建造空間調(diào)度問(wèn)題在已知分段和旁板的尺寸、交貨期，加工時(shí)間均值和偏差的情況下不確定規(guī)劃模型為

根據(jù)以上理論和假設(shè)，對(duì)受關(guān)聯(lián)約束的加工時(shí)間不確定的分段建造空間調(diào)度模型進(jìn)行建模，詳見(jiàn)2.3 節(jié).

2.3 數(shù)學(xué)規(guī)劃模型

空間調(diào)度非線性規(guī)劃模型如下:

目標(biāo)函數(shù)(1)表示在不同置信水平η(ξP)下，將旁板建造隨機(jī)性對(duì)分段建造產(chǎn)生的影響最小化，同時(shí)所引起的分段建造提前、拖期成本也最小化.

約束(2)表示旁板最早開(kāi)工時(shí)間和分段最早開(kāi)工時(shí)間之間的關(guān)系.其中，ti、tg分別代表分段i旁板g的最早開(kāi)工時(shí)間;a代表旁板上胎和分段上胎的時(shí)間關(guān)系.

約束(3)～(9)表示同一場(chǎng)地內(nèi)的分段和旁板的放置位置不允許重合.其中，xi、yi、zi代表分段 i的左下前坐標(biāo)，xg、yg、zg代表旁板g的左下前坐標(biāo);lig、rig、fig、big、uig、vig、Sik、Sgk是決策變量，當(dāng)分段 i在旁板g的左邊時(shí)，lig等于1，否則為0;當(dāng)分段i在旁板g的右邊時(shí)，rig等于1，否則為0;當(dāng)分段i在旁板g的前邊時(shí)，fig等于1，否則為0;當(dāng)分段 i在旁板g的后邊時(shí)，big等于1，否則為0;當(dāng)分段i比旁板g先加工時(shí)，uig等于1，否則為0;當(dāng)分段i比旁板g后加工時(shí)，vig等于1，否則為0;當(dāng)分段i/旁板g被安排在場(chǎng)地k上加工時(shí)，Sik/Sgk等于1，否則為0.

約束(10)～(16)表示同一場(chǎng)地內(nèi)的分段和分段的位置放置不允許重合.

約束(17)～(23)表示同一場(chǎng)地內(nèi)的旁板和旁板的位置不允許重合.

約束(24)和(25)表示加工過(guò)程中的分段和旁板位置唯一，只有等加工完畢后才允許從胎位移出.

約束(26)～(29)表示待調(diào)度分段和旁板不能超過(guò)場(chǎng)地邊界.

約束(30)和(31)表示待調(diào)度分段和旁板只能在所有前序工作提供完善生產(chǎn)資料的情況下才能開(kāi)始加工.

約束(32)表示待調(diào)度分段和旁板的參考點(diǎn)坐標(biāo)都為非負(fù).該模型考慮旁板建造對(duì)分段建造的影響，將旁板加工時(shí)間進(jìn)行隨機(jī)處理，以分段建造提前或拖期產(chǎn)生的時(shí)空占用成本最小化為目標(biāo)，對(duì)分段加工涉及的時(shí)間和空間因素給出調(diào)度結(jié)果.

3 實(shí)例驗(yàn)證與分析

3.1 實(shí)驗(yàn)例證

為了驗(yàn)證上述模型的正確性，本文以上海某大型船廠的分段和旁板建造空間調(diào)度數(shù)據(jù)為例，利用LINGO 11.0 軟件，在處理器為 1.86 GHz，內(nèi)存為1 GB的計(jì)算機(jī)上進(jìn)行求解.實(shí)驗(yàn)包括以下輸入?yún)?shù):

1)待調(diào)度分段的數(shù)量、尺寸、最早加工時(shí)間、加工時(shí)間、交貨時(shí)間、提前完工懲罰成本、拖期完工懲罰成本;

2)待調(diào)度旁板的數(shù)量、尺寸、最早加工時(shí)間、旁板上胎與分段上胎時(shí)間關(guān)系、旁板加工時(shí)間均值和偏差，其中偏差為計(jì)算機(jī)隨機(jī)產(chǎn)生的符合標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù);

3)場(chǎng)地?cái)?shù)量和尺寸.具體輸入數(shù)據(jù)見(jiàn)表1～3.

表1 待調(diào)度分段信息Table 1 Scheduling blocks information

表2 待調(diào)度旁板信息Table 2 Scheduling subsidiary parts information

表3 場(chǎng)地信息Table 3 Platform in formation m

通過(guò)不同置信水平對(duì)分段建造空間調(diào)度問(wèn)題的求解，得到調(diào)度結(jié)果如表4所示，模型運(yùn)行參數(shù)如表5.

表4 實(shí)驗(yàn)驗(yàn)證結(jié)果Table 4 Experiment results

表5 部分模型運(yùn)行參數(shù)Table 5 Part of model operation parameters

3.2 實(shí)驗(yàn)結(jié)果分析

以上實(shí)驗(yàn)結(jié)果給出了不確定環(huán)境下分段和旁板的具體加工信息.其中，置信水平越高，表示該種生產(chǎn)水平越接近確定條件下的生產(chǎn)環(huán)境.用該模型得到的可行調(diào)度方案是較優(yōu)的，相對(duì)確定條件下的生產(chǎn)環(huán)境更接近船廠實(shí)際的生產(chǎn)情況.由于目標(biāo)函數(shù)、變量和約束中都含有隨機(jī)變量、隨機(jī)約束，此外該模型涉及多場(chǎng)地的空間調(diào)度方法，因此這個(gè)模型的計(jì)算工作量相對(duì)較大，求解的模型規(guī)模不宜過(guò)大.從表4、5可以看出，當(dāng)模型規(guī)模為5個(gè)分段和2個(gè)旁板時(shí)，模型求解時(shí)間在5 min左右，而模型求解時(shí)間和目標(biāo)最優(yōu)值與置信水平并沒(méi)有嚴(yán)格的相關(guān)關(guān)系.如當(dāng)置信水平為0.95時(shí)，CPU運(yùn)行時(shí)間為00:04:02，分段提前、拖期時(shí)空占用成本為1 047.028 0;而當(dāng)置信水平下降為0.85時(shí)，CPU運(yùn)行時(shí)間減少為00:03:13，分段提前、拖期時(shí)空占用成本減少為661.951 0;當(dāng)置信水平繼續(xù)下降為0.75時(shí)，CPU運(yùn)行時(shí)間又增加為00:08:06，分段提前、拖期時(shí)空占用成本減少為429.631 7.由此可見(jiàn)，加工時(shí)間不確定條件下的空間調(diào)度的時(shí)空占用成本并不唯一，它取決于不確定環(huán)境的置信水平.而空間調(diào)度問(wèn)題在考慮了旁板對(duì)分段的關(guān)聯(lián)約束后，問(wèn)題變得更為復(fù)雜，需要考慮更多的約束，這樣就大大增加了計(jì)算量.

3.3 確定條件下空間調(diào)度實(shí)驗(yàn)分析

確定條件下的空間調(diào)度問(wèn)題是不確定條件下空間調(diào)度問(wèn)題的一個(gè)特殊子問(wèn)題.當(dāng)置信水平為1，分段和旁板加工時(shí)間等于它們的均值，偏差為0時(shí)，隨機(jī)空間調(diào)度問(wèn)題就轉(zhuǎn)化為確定性問(wèn)題.由于不存在不確定因素造成的分段提前或拖期時(shí)空占用成本，目標(biāo)函數(shù)改變?yōu)榉侄?旁板加工場(chǎng)地時(shí)空利用率最大化，如下

為比較2種情況下的空間調(diào)度問(wèn)題，應(yīng)用相同數(shù)據(jù)進(jìn)行調(diào)度實(shí)驗(yàn)，調(diào)度結(jié)果見(jiàn)表6，模型運(yùn)行參數(shù)見(jiàn)表7.

表6 確定條件下的實(shí)驗(yàn)驗(yàn)證結(jié)果Table 6 Experimental results in the certain environment

表7確定條件下部分模型運(yùn)行參數(shù)Table 7 Part of model operation parameters in the certain environment

將表5和表7進(jìn)行比較可以發(fā)現(xiàn)，當(dāng)不確定問(wèn)題轉(zhuǎn)變?yōu)榇_定問(wèn)題時(shí)，在變量數(shù)和約束數(shù)相同前提下，相同規(guī)模的空間調(diào)度問(wèn)題的模型求解時(shí)間卻大大減少.而由于問(wèn)題的確定化，使得場(chǎng)地的利用率也大大提高，只需要在3號(hào)場(chǎng)地完成即可.因此，在不考慮不確定因素的前提下，該算法可以求解較大規(guī)模的模型，并且得到較優(yōu)的仿真結(jié)果.而不確定因素由于將問(wèn)題隨機(jī)化，通常要結(jié)合機(jī)會(huì)約束和不確定規(guī)劃等理論進(jìn)行建模，主要解決的是不同置信水平下調(diào)度問(wèn)題的求解，因此模型需要考慮開(kāi)工時(shí)間、加工時(shí)間、完工時(shí)間等隨機(jī)變量，此外還要考慮旁板對(duì)相關(guān)分段的關(guān)聯(lián)約束，這就比確定條件下不具有關(guān)聯(lián)關(guān)系的調(diào)度模型復(fù)雜得多，CPU運(yùn)行時(shí)間就會(huì)大大增加.

4 結(jié)論

本文考慮了船廠生產(chǎn)過(guò)程中存在的不確定因素，提出針對(duì)不確定加工時(shí)間的分段建造空間調(diào)度非線性規(guī)劃模型，重點(diǎn)分析因旁板生產(chǎn)中產(chǎn)生的提前、拖期因素導(dǎo)致的分段建造計(jì)劃的偏離.旁板加工時(shí)間用正態(tài)分布隨機(jī)數(shù)表達(dá)，而不同的置信水平將產(chǎn)生不同的隨機(jī)偏差，這些偏差對(duì)對(duì)應(yīng)分段的空間布局和加工時(shí)間產(chǎn)生影響.通過(guò)Lingo11.0對(duì)該非線性模型的求解，得出了不同置信水平下比較理想的調(diào)度解.由于該模型相對(duì)以往的研究加入了隨機(jī)變量因素和關(guān)聯(lián)件的時(shí)空影響，使得該模型更為復(fù)雜，也更接近于船廠的實(shí)際生產(chǎn)情況.

另一方面，該模型對(duì)于大規(guī)模空間調(diào)度問(wèn)題很難進(jìn)行求解.因此在今后的研究中，擬將問(wèn)題規(guī)模縮小化或引入變量將非線性模型線性化，使得該模型也能適用于大規(guī)模的空間調(diào)度模型，此外在提高計(jì)算效率方面也有很多研究工作要深入開(kāi)展.

［1］RYU C，SHIN JG，KWON O H，et al.Development of integrated and interactive spatial planning systems of assembly blocks in shipbuilding［J］.International Journal of Computer Integrated Manufacturing，2008，21(8):911-922.

［2］LEE JK，LEEK J，PARK H K，etal.Developing scheduling systems for Daewoo shipbuilding:DAS project［J］.European Journal of Operational Research，1997，97(2):380-395.

［3］鄭俊麗，陳峰，江志斌，等.縮短最大完工時(shí)間的船舶分段空間調(diào)度算法［J］.上海交通大學(xué)學(xué)報(bào)，2009，43(4):663-668.ZHENG Junli，CHEN Feng，JIANG Zhibin，et al.A spatiotemporal scheduling algorithm minimizing make span［J］.Journal of Shanghai Jiao Tong University，2009，43(4):663-668.

［4］張志英，楊克開(kāi)，于瑾維，等.改進(jìn)粒子群算法的動(dòng)態(tài)空間調(diào)度方法［J］.哈爾濱工程大學(xué)學(xué)報(bào)，2009，30(12):1344-1350.ZHANG Zhiying，YANG Kekai，YU Jinwei，etal.Dynamic spatial scheduling approach based on improved particle swarm optimization algorithm［J］.Journal of Harbin Engineering University，2009，30(12):1344-1350.

［5］張志英，陳潔.空間調(diào)度問(wèn)題的非線性規(guī)劃分析求解方法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2010，16(6):1272-1277.ZHANG Zhiying，CHEN Jie.Nonlinear programming approach for spatial scheduling problem［J］.Computer Integrated Manufacturing Systems，2010，16(6):1272-1277.

［6］郭美娜，李波.基于樹(shù)搜索的一種動(dòng)態(tài)空間調(diào)度方法［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43(14):180-184.GUO Meina，LI Bo.Dynamic spatial scheduling approach based on tree-search［J］.Computer Engineering and Applications，2007，43(14):180-184.

［7］王蕾，張志英.基于規(guī)則的船體曲面分段空間調(diào)度方法［J］.上海交通大學(xué)學(xué)報(bào)，2009，43(11):1709-1714.WANG Lei，ZHANG Zhiying.Research on rule-based spatial scheduling in hull curved block construction［J］.Journal of Shanghai Jiao Tong University，2009，43(11):1709-1714.

［8］ENEA M，GALANTE G，PANASCIA E.The facility layout problem approached using a fuzzy model and a genetic search［J］.Journal of Intelligent Manufacturing，2005，16:303-316.

［9］GU Jinwei，GU Xingsheng，GU Manzhan.A novel parallel quantum genetic algorithm for stochastic job shop scheduling［J］.Journal of Mathematical Analysis and Applications，2009，355:63-81.

［10］張麗華，涂豐生.一個(gè)批處理機(jī)隨機(jī)E/T調(diào)度問(wèn)題研究［J］.系統(tǒng)工程理論與實(shí)踐，2005，10:114-119.ZHANG Lihua，TU Fengsheng.An earliness and tardiness stochastic scheduling problem on a batch processor［J］.Systems Engineering——Theory ＆ Practice，2005，10:114-119.

［11］李素粉，朱云龍，尹朝萬(wàn).具有隨機(jī)加工時(shí)間和機(jī)器故障的流水車(chē)間調(diào)度［J］.計(jì)算機(jī)集成制造系統(tǒng)，2005，11(10):1425-1428.LISufen，ZHU Yunlong，YIN Chaowan.Flow shop scheduling with stochastic processing times and machine breakdowns［J］.Computer Integrated Manufacturing Systems，2005，11(10):1425-1428.

［12］朱海平，邵新宇，張國(guó)軍.不確定信息條件下的車(chē)間調(diào)度策略研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2006，12(10):1637-1642.ZHU Haiping，SHAO Xinyu，ZHANG Guojun.Job-shop scheduling strategy under uncertain information environment［J］.Computer Integrated Manufacturing Systems，2006，12(10):1637-1642.

［13］TAVAKKOLI-MOGHADDAM R，JAVADIAN N，JAVADI B，et al.Design of a facility layout problem in cellular manufacturing systems with stochastic demands［J］.Applied Mathematics and Computation，2007，184:721-728.

［14］VáZQUEZ-ROMáN R，LEE Jinhan，JUNG Seungho，et al.Optimal facility layout under toxic release in process facilities:a stochastic approach［J］.Computer and Chemical Engineering，2010，34:122-133.

［15］YANG T，HUNG C C.Multiple-attribute decision making methods for plant layout design problem ［J］.Robotics and Computer-Integrated Manufacturing，2007，23:126-137.

［16］劉寶碇，趙瑞清，王綱.不確定規(guī)劃及應(yīng)用［M］.北京:清華大學(xué)出版社，2003:79-87.