復(fù)雜形狀船舶分段建造空間調(diào)度優(yōu)化算法

王津劍，杜吉旺，范秀敏，2+，何其昌，2

（1.上海交通大學(xué) 機(jī)械與動力工程學(xué)院，上海 200240；2.上海市網(wǎng)絡(luò)化制造與企業(yè)信息化重點(diǎn)實(shí)驗(yàn)室，上海 200230）

0 引言

船舶建造作為傳統(tǒng)產(chǎn)業(yè)，隨著精益生產(chǎn)、成組技術(shù)等新技術(shù)在該領(lǐng)域的應(yīng)用，催生了新的現(xiàn)代船舶建造模式，在此模式下，船舶以分段為單元制定生產(chǎn)計(jì)劃并進(jìn)行生產(chǎn)［1］。分段是由船體的零件、部件組成的局部結(jié)構(gòu)，由于分段建造占用大量空間區(qū)域和設(shè)施資源，對分段生產(chǎn)進(jìn)行安排，在滿足調(diào)度約束的條件下獲得最優(yōu)的動態(tài)空間布局即為分段空間調(diào)度問題［2］。

船舶分段空間調(diào)度是NP完全問題，一般采用啟發(fā)式調(diào)度算法求解。Lee等［2-3］最早對船舶分段空間調(diào)度問題進(jìn)行了研究，提出最大剩余空間利用規(guī)則、初始定位規(guī)則、邊規(guī)則和混合規(guī)則等啟發(fā)式調(diào)度規(guī)則，用時(shí)空坐標(biāo)系對分段進(jìn)行三維空間調(diào)度，基于此開發(fā)了韓國大宇造船廠的DAS-CURVE軟件。此后，國內(nèi)外對空間調(diào)度算法進(jìn)行了深入研究并進(jìn)行了改進(jìn)。Lee［4］研究了空間調(diào)度專家系統(tǒng)的搜索空間，證明了對于投影形狀是多邊形的分段，以頂（角）點(diǎn)為搜索空間的啟發(fā)式算法在空間調(diào)度上是有效的，但是并沒有考慮分段擺放方向。Liu等［5］針對矩形分段，將分段邊界延長線的交點(diǎn)增加到啟發(fā)式算法的搜索空間，但是隨著分段的增加，搜索空間的容量急劇增加。Varghese等［6］采用類似于“二維裝箱”的算法，采用最下最左（Button Left，BL）的啟發(fā)式定位策略，計(jì)算矩形分段的布局。Shin等［7］先使用矩形計(jì)算分段的初步位置，再換上實(shí)際形狀，調(diào)整分段的局部位置，使分段布局緊湊。張志英等［8］采用最小包絡(luò)多邊形的方法對不規(guī)則的分段進(jìn)行多邊形處理，采用懸掛檢測方法對分段位置干涉進(jìn)行檢測，但是當(dāng)待布局的分段尺寸較大時(shí)，存在將正在加工的分段覆蓋的問題，此時(shí)懸掛檢測方法失效。陶寧蓉等［9］將分段加工的時(shí)間窗與時(shí)空坐標(biāo)系相結(jié)合，提出基于極點(diǎn)的定位規(guī)則，應(yīng)用工藝簇和形狀簇策略解決分段調(diào)度序列，改進(jìn)了空間調(diào)度的啟發(fā)式算法。郭美娜等［10］提出一種基于深度優(yōu)先樹搜索的動態(tài)調(diào)度方法，在每個(gè)時(shí)間片內(nèi)使用局部啟發(fā)調(diào)度算法進(jìn)行空間布置搜索。張志英等［11］采用改進(jìn)粒子群算法來優(yōu)化分段調(diào)度序列，獲得了很好的效果。馬少輝等［12］采用遺傳算法對分段的調(diào)度序列進(jìn)行了優(yōu)化，并對算法進(jìn)行了驗(yàn)證。這些研究都是在兩方面對空間調(diào)度算法進(jìn)行改進(jìn)：一是優(yōu)化分段位置定位的策略或逼近分段的實(shí)際投影形狀，以提高啟發(fā)式算法的效率；二是優(yōu)化分段調(diào)度序列，以提高分段建造區(qū)域的利用率。

以上研究針對的分段投影形狀主要是矩形，其形狀復(fù)雜程度較低。雖然有少數(shù)學(xué)者研究了形狀復(fù)雜的分段，但是缺乏有效的分段位置干涉檢測方法。目前采用的啟發(fā)式算法能夠解決分段的位置計(jì)算，然而不同形狀的分段需要不同的啟發(fā)式操作規(guī)則。雖然智能算法用于分段序列優(yōu)化的效果明顯，但都是針對一個(gè)分段建造區(qū)域，當(dāng)有多個(gè)分段建造區(qū)域時(shí)，這些算法都沒有考慮集中使用部分區(qū)域來減少資源的投入。

為了解決上述問題，本文針對復(fù)雜形狀分段間的位置干涉檢測，采用點(diǎn)—射線法進(jìn)行判斷，并將柵格遍歷方法和遺傳算法相結(jié)合，形成兩階段混合調(diào)度方法，對包含多個(gè)分段建造區(qū)域的分段建造調(diào)度計(jì)劃進(jìn)行調(diào)整與優(yōu)化，并以船廠實(shí)例來驗(yàn)證方法的有效性與實(shí)用性。

1 問題描述

分段按照生產(chǎn)計(jì)劃在裝焊工場中并行建造，可以縮短造船周期、提高生產(chǎn)效率。然而船廠的場地資源有限，分段并行建造常常無法按照計(jì)劃執(zhí)行，分段建造已經(jīng)成為船舶建造過程中的一個(gè)瓶頸，因此需要對分段建造過程進(jìn)行合理安排優(yōu)化，以提高場地資源的利用率。

1.1 分段建造區(qū)域數(shù)學(xué)模型

裝焊工場由若干個(gè)矩形的跨組成，如圖1所示。分段在跨上進(jìn)行建造，建造完成后通過大型液壓平板車將其運(yùn)輸?shù)狡渌麉^(qū)域，完成后續(xù)工作。裝焊工場的數(shù)學(xué)表達(dá)為

式中：Ji表示第i跨；Li和Bi表示跨的長度和有效寬度；M表示跨的數(shù)量。

1.2 分段數(shù)學(xué)模型

分段一旦在裝焊工場中確定位置就不能移動，其所占的位置不能被其他分段占用。分段是放置在裝焊工場的工作面上進(jìn)行建造的，高度信息在空間調(diào)度時(shí)不考慮。分段在裝焊工場的實(shí)際占地用其投影形狀描述為

式中：Si為第i個(gè)分段的投影形狀；ni為分段形狀序號；（ai，bi，ci，…）為分段的投影尺寸參數(shù)，尺寸參數(shù)數(shù)量取決于分段投影形狀，分段的形狀如表1中的“實(shí)際投影形狀”列所示；N為分段的數(shù)量。

表1 分段近似多邊形和形狀參數(shù)

分段建造需要在其時(shí)間窗內(nèi)完成，即在最早開工時(shí)間E和最晚完工時(shí)間F之間開工并完成。分段建造時(shí)間窗和分段開工時(shí)間T、分段生產(chǎn)周期P滿足如下條件：

式中i=1，2，…，N。

分段在裝焊工場占用的區(qū)域D用坐標(biāo)和分段形狀表示為

式中：Di為第i個(gè)分段在裝焊工場占用的區(qū)域；（xi，yi，ri，Ji）為分段定位點(diǎn)的坐標(biāo)，定位點(diǎn)是分段的左下點(diǎn)，Ji為分段所在跨的編號，xi和yi表示參考點(diǎn)在Ji個(gè)跨上的坐標(biāo)，ri表示分段的擺放方向（默認(rèn)方向逆時(shí)針轉(zhuǎn)動0°）；Si為第i個(gè)分段形狀，如圖2所示。

1.3 分段空間調(diào)度數(shù)學(xué)模型

為了節(jié)約場地和設(shè)備資源，分段應(yīng)該盡量集中布置。單個(gè)跨采用場地有效利用率U進(jìn)行描述和評價(jià)：

式中：Ui為第i個(gè)跨的有效利用率，sj為j分段的投影占地面積，Ni為第i個(gè)跨中的分段數(shù)量，ELi為第i個(gè)跨的使用長度，M為跨的數(shù)量，有效利用率U越大，表示跨的使用情況越好，其示意圖如圖3所示。

裝焊工場有多個(gè)跨，其場地有效利用率U和跨的有效利用率存在區(qū)別，如式（6）所示，可以將其作為分段空間調(diào)度的目標(biāo)。分段調(diào)度計(jì)劃還應(yīng)滿足時(shí)間約束，本文定義為將分段的建造開始時(shí)間與制造周期限定在某一時(shí)間窗內(nèi)，如式（7）所示；空間約束是分段投影區(qū)域要在裝焊工場跨的有效使用區(qū)域內(nèi)且分段投影區(qū)域之間不能重疊，如式（8）所示。分段空間調(diào)度的數(shù)學(xué)模型如下：

式中i=1，2，…，N，k=1，2，…，N且i≠k。

2 復(fù)雜形狀分段空間調(diào)度優(yōu)化算法

分段空間調(diào)度的難點(diǎn)在于單個(gè)分段空間定位、多個(gè)分段調(diào)度序列優(yōu)化。分段空間定位需要解決兩個(gè)問題，即分段之間的位置干涉檢測和分段位置的遍歷與選擇。完工分段移除也是空間調(diào)度算法的組成部分，其實(shí)現(xiàn)過程簡單，不是空間調(diào)度算法的重點(diǎn)。分段位置干涉檢測與分段空間定位相輔相成，是復(fù)雜形狀分段空間調(diào)度優(yōu)化算法的核心內(nèi)容，具體關(guān)系如圖4所示。

2.1 分段位置干涉檢測

分段空間調(diào)度的空間約束要求分段投影之間不能存在重疊區(qū)域，即不能出現(xiàn)分段位置干涉。然而分段平面投影形狀各異，有些還包含不規(guī)則的曲線，這給分段位置干涉檢測帶來了困難?？梢圆捎谩耙灾贝钡姆椒?，將這些投影形狀用包絡(luò)多邊形進(jìn)行近似，如圖5 中連接點(diǎn)的虛線構(gòu)成的包絡(luò)多邊形。多邊形之間的位置干涉可以通過判斷點(diǎn)與多邊形的位置關(guān)系實(shí)現(xiàn)。

對于任意多邊形（如圖6），以點(diǎn)Q為起點(diǎn)做任意一條射線，如果射線與多邊形的交點(diǎn)數(shù)是奇數(shù)，則Q在多邊形內(nèi)；如果交點(diǎn)數(shù)是偶數(shù)，則Q在多邊形外。圖6中，點(diǎn)Q2和Q5在多邊形內(nèi)部，點(diǎn)Q4在多邊形外，檢測點(diǎn)是否在多邊形內(nèi)需要注意兩個(gè)問題：①點(diǎn)已經(jīng)在多邊形上，如Q1，此時(shí)點(diǎn)與多邊形的位置關(guān)系已經(jīng)確定；②做出的射線與圖形的交點(diǎn)是多邊形的角點(diǎn)，如以Q3和Q6為起點(diǎn)做出的射線（用虛線表示），此時(shí)不能判斷點(diǎn)與多邊形的位置，需要改變射線的方向，如Q3和Q6用直線表示的射線，此時(shí)可以判斷Q3在多邊形內(nèi)，Q6在多邊形外。為了便于檢測，射線的方向首選豎直或水平方向，當(dāng)都不能判斷點(diǎn)和多邊形的關(guān)系時(shí)，取與多邊形的邊平行的方向，極端情況下取任意方向。

判斷點(diǎn)與多邊形位置關(guān)系的流程如圖7所示。如果兩個(gè)多邊形存在位置干涉，即存在重疊區(qū)域，則它們的某個(gè)角點(diǎn)Q在另一個(gè)多邊形內(nèi)。分段投影的包絡(luò)多邊形邊數(shù)越多，近似圖形就越接近真實(shí)形狀，從而增加了分段位置干涉檢測的計(jì)算復(fù)雜度，因此在確保形狀精度的同時(shí)應(yīng)盡量減少多邊形的近似程度。

2.2 分段空間定位算法

裝焊工場跨的工作區(qū)域內(nèi)遍布直立的胎架，這些胎架高度可調(diào)，分段就在這些胎架的支撐下建造。胎架之間的間隔是1m～1.5m，分段位置的精度可設(shè)置為1m。對裝焊工場中跨的工作區(qū)域進(jìn)行網(wǎng)格劃分，網(wǎng)格大小為1m×1m，以這些網(wǎng)格點(diǎn)作為分段位置的搜索空間，按照一定的順序遍歷和篩選，就可以得到分段的最優(yōu)位置。

分段位置確定采用最左最下策略，網(wǎng)格遍歷按照從下至上、從左至右的方向進(jìn)行，如圖8所示。如果分段在跨內(nèi)，且不與其他分段存在位置干涉，則遍歷停止；如果不存在分段的合適位置，則換到下一個(gè)跨進(jìn)行遍歷。分段位置計(jì)算的實(shí)現(xiàn)流程如圖9所示。

圖9中：r表示分段的方向，a表示分段方向的遞增值，分段一般呈水平或豎直方向放置，因此取a=90°。如果一個(gè)跨中的分段在多個(gè)擺放方向都存在合適位置，則計(jì)算出這些方向?qū)?yīng)分段的重心位置，取重心最左最下對應(yīng)的分段位置和方向作為最終分段的布局；如果未能成功獲取分段的位置，則將分段推遲到下一個(gè)工作日調(diào)度。

2.3 空間調(diào)度混合遺傳算法

當(dāng)多個(gè)分段需要同時(shí)調(diào)度時(shí)，它們之間的調(diào)度順序會影響裝焊工場的空間利用率。本文采用遺傳算法對分段的調(diào)度序列進(jìn)行優(yōu)化。

同時(shí)調(diào)度的分段中可能有部分為延期調(diào)度，為保證分段建造的進(jìn)度，這些延期的分段需要優(yōu)先調(diào)度。為了使延期時(shí)間越長的分段越優(yōu)先調(diào)度，引入優(yōu)先級Td，

優(yōu)先級大的分段優(yōu)先調(diào)度，對于優(yōu)先級相同的分段，分段的序列是可變的，通過遺傳算法對序列進(jìn)行優(yōu)化。

2.3.1 編碼設(shè)計(jì)

遺傳算法采用多參數(shù)級聯(lián)的符號編碼方式。首先對分段進(jìn)行符號編碼（0，1，2，…，m）然后將相同優(yōu)先級Td的分段編號放置在一起，按照優(yōu)先級由大到小排列，分段按照編碼順序調(diào)度，如圖10所示。

其中：分段編號為bi1bi2…bili的優(yōu)先級都是Tdi，Td1＞Td2＞…＞Tdn，共有n個(gè)不同的分段優(yōu)先級；優(yōu)先級同為Tdi的分段有l(wèi)i個(gè)。

2.3.2 遺傳算法適應(yīng)度函數(shù)

遺傳算法的目標(biāo)是使裝焊工場的場地等效有效利用率最大，且跨的數(shù)量最少，即編號小的跨盡量放置多的分段，其適應(yīng)度函數(shù)f相對于分段空間調(diào)度目標(biāo)函數(shù)U進(jìn)行修正，可取

式中：wj為第j跨有效利用率的權(quán)重，M為跨的數(shù)量，Nj為第j跨中分段的數(shù)量，sj，i為第j跨中第i個(gè)分段的投影占地面積，Bj和ELj為第j個(gè)跨的寬和使用長度。跨的有效利用率權(quán)重滿足w1＞w2＞…＞wM，通過賦予編號靠前的跨更大的權(quán)重，使其在調(diào)度中優(yōu)先放置分段，減少跨的總使用數(shù)量。適應(yīng)度f越大，表示個(gè)體的質(zhì)量越好。

2.3.3 遺傳操作算子

由于采用符號編碼方式，傳統(tǒng)的交叉算子和變異算子都會使個(gè)體出現(xiàn)非法解，需要對其進(jìn)行重新設(shè)計(jì)，同時(shí)也需要加快算法的收斂速度、增加個(gè)體的多樣性。

（1）選擇算子 為了加速選擇而不失公平性，采用最優(yōu)保存與輪盤賭相結(jié)合的策略，隨機(jī)生成需要選擇復(fù)制的代數(shù)m（m＞1），直接復(fù)制適應(yīng)度最好的個(gè)體到下一代，剩下m-1個(gè)個(gè)體按照適應(yīng)度的大小采用輪盤賭的方法進(jìn)行選擇復(fù)制，從而增加個(gè)體的多樣性。

（2）交叉算子 采用重復(fù)交叉的方式對單點(diǎn)交叉進(jìn)行改進(jìn)。例如父代Parent1和Parent2分別是（0，1，2，3，4，9，8，7，6，5），（4，6，8，7，3，9，2，5，1，0），其交叉流程如圖11所示。具體步驟如下：①隨機(jī)生成單點(diǎn)交叉位置；②交換Parent1和Parent2交叉點(diǎn)后的基因，生成中間代Temp 1和Temp 2；③取出Temp 1中相同的基因，交叉點(diǎn)后的基因按照交叉點(diǎn)前的順序排列，將Temp 2進(jìn)行同樣的處理，從而增加個(gè)體的多樣性；④交換Temp 1和Temp 2交叉點(diǎn)后重新排列順序的基因，生成子代Child1和Child2。

（3）變異算子 在同優(yōu)先級區(qū)域隨機(jī)產(chǎn)生兩個(gè)變異位置k和q，對k和q位置上的基因進(jìn)行互換變異。

2.4 空間調(diào)度算法實(shí)現(xiàn)

復(fù)雜形狀分段空間調(diào)度算法主要實(shí)現(xiàn)開工分段調(diào)度和完工分段移除，算法流程如圖12 所示。圖12中，t（單位：d）為調(diào)度時(shí)刻，t0為調(diào)度起始時(shí)刻；Δ為調(diào)度時(shí)間間隔，通常取Δ=1d?？臻g調(diào)度以天為調(diào)度循環(huán)間隔進(jìn)行，所有分段完成建造之后空間調(diào)度結(jié)束。空間調(diào)度循環(huán)步驟如下：①進(jìn)行開工分段調(diào)度，提取t時(shí)刻開工的分段后用遺傳算法對調(diào)度序列進(jìn)行優(yōu)化；②按照調(diào)度序列對分段進(jìn)行空間定位，如果分段存在位置，則將其添加到“已開工分段”，否則將其開工時(shí)間推遲Δ后重新放回“未開工分段”；③更新場地布局，并將調(diào)度信息寫入“分段調(diào)度信息”，完成開工分段調(diào)度后，進(jìn)行完工分段移除，提取t時(shí)刻完工的分段，并將這些分段的信息追加到“分段調(diào)度信息”，更新場地布局。

3 案例驗(yàn)證與算法比較

3.1 案例驗(yàn)證

為了驗(yàn)證復(fù)雜形狀分段空間調(diào)度算法的有效性，選取上海某船舶企業(yè)的實(shí)際數(shù)據(jù)進(jìn)行計(jì)算分析。遺傳算法中的各參數(shù)取值如下：最大迭代次數(shù)50，種群規(guī)模取調(diào)度分段數(shù)的4倍［13］，交叉概率0.5，變異概率0.2；裝焊工場中的跨2個(gè)，長度150m，有效寬度25m；分段數(shù)量86個(gè)，分段的近似多邊形及其形狀參數(shù)描述如表1所示，部分分段形狀和生產(chǎn)計(jì)劃如表2所示。

表2 分段形狀和生產(chǎn)計(jì)劃（部分）

續(xù)表2

采用VS2010 MFC軟件作為編程工具，實(shí)現(xiàn)復(fù)雜形狀分船舶分段空間的調(diào)度算法，并繪制裝焊工場動態(tài)的布局。算法使用不同的初始化種群，對上述86個(gè)分段進(jìn)行調(diào)度優(yōu)化，共進(jìn)行10次實(shí)驗(yàn)，每次實(shí)驗(yàn)都得到了較好的結(jié)果。表3統(tǒng)計(jì)了第一天調(diào)度遺傳算法的適應(yīng)度收斂值。

表3 10次遺傳算法適應(yīng)度收斂值（2014-3-1調(diào)度）

圖13給出了表3中的最優(yōu)解收斂過程，最優(yōu)解適應(yīng)度值為0.874。由圖可知解的集合是逐漸收斂的，在25代后個(gè)體多樣性開始消失，最優(yōu)解開始收斂。結(jié)果表明，依據(jù)本文設(shè)計(jì)的分段空間調(diào)度算法對裝焊工場進(jìn)行空間調(diào)度，可以提高調(diào)度期間裝焊工場的有效利用率。

本文算法采用有效利用率對裝焊工場的利用情況進(jìn)行分析，而一般情況則使用平均利用率評價(jià)一段時(shí)間內(nèi)裝焊工場的利用情況，平均利用率是場地每天利用率的平均值，td的利用率U（t）定義為

式中：M為跨的數(shù)量，Ni（t）為t時(shí)刻第i跨中的分段數(shù)量，Bi和Li為第i跨的長度和寬度，S（i，j，t）為t時(shí)刻第i跨中的第j個(gè)分段面積。等效利用率越大，裝焊工場在相同時(shí)間段內(nèi)的分段布局越緊密，放置的分段越多，場地利用率也越大。

對空間調(diào)度優(yōu)化中裝焊工場的利用率進(jìn)行統(tǒng)計(jì)，計(jì)算平均利用率，可知裝焊工場的平均利用率達(dá)到0.800，如圖14 所示。對優(yōu)化結(jié)果進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)結(jié)果與實(shí)際生產(chǎn)調(diào)度利用率的對比如表4所示。實(shí)際生產(chǎn)調(diào)度時(shí)場地平均利用率一般只有0.6，而且分段的占地面積使用的是矩形面積，如果使用實(shí)際分段投影形狀，則場地的平均利用率將小于0.6。可見采用本文所提算法能夠很好地解決復(fù)雜形狀船舶分段空間調(diào)度問題。

表4 空間調(diào)度優(yōu)化與實(shí)際調(diào)度結(jié)果比較

圖15所示為裝焊工場部分的布局圖。圖15中3d 的裝焊工場有效利用率分別為0.845，0.870，0.841，場地利用率分別為0.471，0.847，0.833。最大等效利用率超過0.87，最大利用率超過0.84，可見本文所提方法可以有效提高裝焊工場的利用率。調(diào)度第一天（如圖15a），進(jìn)入分段的數(shù)量有限，不能占滿裝焊工場，分段都集中放置在第1跨中，第2跨中的分段也是集中在跨的左側(cè)，從而可以集中使用裝焊工場的設(shè)備；圖15b中的分段數(shù)量較多，幾乎完全占據(jù)了裝焊工場；圖15c中的分段與分段之間留有間隙，因?yàn)檎{(diào)度時(shí)裝焊工場中存在的分段將跨空閑區(qū)域分割成若干區(qū)域，部分區(qū)域太小，不能放置分段。

3.2 算法之間比較分析

為了進(jìn)一步驗(yàn)證算法的有效性，對比了4種算法的實(shí)驗(yàn)結(jié)果，如表5所示，其中延遲開工指分段開工時(shí)間T大于最早開工時(shí)間E，即T＞E。算法1即為本文采用的算法。算法2與算法1之間的區(qū)別在于分段調(diào)度序列排序方式不同，算法2采用常規(guī)的按最早交貨期（Early Due Date，EDD）升序排列的方式，而算法1則基于遺傳算法排列；算法3與算法1的區(qū)別在于分段位置的搜索方法不同，算法3的分段定位方式采用文獻(xiàn)［4］中的分段位置搜索空間的方法，即將跨的角點(diǎn)和跨內(nèi)分段的角點(diǎn)作為待定位分段位置的搜索空間，而算法1采用的是柵格遍歷的方法；算法4與算法1的區(qū)別在于分段定位策略不同，算法4采用的是文獻(xiàn)［6］中的分段定位點(diǎn)BL策略，而算法1 采用的是分段重心最左最下的策略。

表5 算法結(jié)果對比

從表5可見，本文所提算法1在裝焊工場利用率、完工時(shí)間和延遲開工分段等性能指標(biāo)上均最優(yōu)。與算法2相比，算法1采用遺傳算法對調(diào)度序列進(jìn)行優(yōu)化，性能指標(biāo)上占優(yōu)。算法3性能較差，雖然也采用了遺傳算法對調(diào)度序列進(jìn)行優(yōu)化，但是對于復(fù)雜形狀的分段，取跨和跨內(nèi)分段角點(diǎn)作為位置搜索空間明顯不夠，還需要通過其他方法擴(kuò)大搜索空間，然而擴(kuò)大搜索空間的過程十分麻煩，遠(yuǎn)不如采用柵格遍歷的方式便捷。算法4的性能較差，主要原因是分段定位點(diǎn)的BL策略不適用于復(fù)雜多邊形形狀的分段。

4 結(jié)束語

本文對復(fù)雜形狀的船舶分段提出了統(tǒng)一的位置干涉檢測方法，最后采用柵格遍歷搜索方法，在保證分段位置精度的基礎(chǔ)上更好地解決了復(fù)雜形狀的分段的位置分配問題；通過改進(jìn)的遺傳算法對分段的調(diào)度序列進(jìn)行優(yōu)化，提高了場地的利用率。采用實(shí)例進(jìn)行計(jì)算，分析了算法的收斂性、裝焊工場地利用情況和分段布局，并與其他算法進(jìn)行了比較，驗(yàn)證了本文所提算法和分段位置干涉方法的有效性。但是，本文提出的算法是在理想情況下，不考慮分段建造的影響因素，這些因素使實(shí)際調(diào)度結(jié)果和算法計(jì)算結(jié)果存在較大的差別，后續(xù)研究將從分段建造的影響因素出發(fā)，進(jìn)一步提高算法的實(shí)用性。

［1］ZHANG Guangfa，LIU Yujun，JI Zhuoshang.Simulation and optimization of ship block-building planning［J］.Computer Integrated Manufacturing Systems，2011，17（12）：2643-2651（in Chinese）.［張光發(fā)，劉玉君，紀(jì)卓尚.船舶分段建造計(jì)劃仿真與優(yōu)化［J］.計(jì)算機(jī)集成制造系統(tǒng)，2011，17（12）：2643-2651.］

［2］LEEK J，LEE J K，CHOI S Y.A spatial scheduling system and its application to shipbuilding：DAS-Curve［J］.Expert Systems with Applications，1996，10（3）：311-324.

［3］LEEJ K，LEE K J，PARK H K，et al.Developing scheduling systems for Daewoo shipbuilding：DAS project［J］.European Journal of Operational Research，1997，97（2）：380-395.

［4］LEEK J.Sufficient search space for spatial expert systems［J］.Expert Systems with Applications，2000，19（1）：1-8.

［5］LIU Z，HUAT D C K，WEE K H.Scheduling dynamic block assembly in shipbuilding through hybrid simulation and spatial optimization［J］.International Journal of Production Research，2012，50（20）：5986-6004.

［6］VARGHESE R J，YOON D Y.Dynamic spatial block arrangement scheduling in shipbuilding industry using genetic algorithm［C］／／Proceedings of the 3rd International IEEE Conference on Industrial Informatics.Washington，D.C.，USA：IEEE，2005：444-449.

［7］SHIN J G，KWON O H，RYU C.Heuristic and metaheuristic spatial planning of assembly blocks with process schedules in an assembly shop using differential evolution［J］.Production Planning &Control，2008，19（6）：605-615.

［8］ZHANG Zhiying，YANG Kekai，YU Jinwei.Two-dimensional irregular spatial scheduling method for hull block construction in shipbuilding［J］.Journal of Shanghai Jiaotong University，2012，46（4）：651-656（in Chinese）.［張志英，楊克開，于瑾維.面向船體分段建造的二維不規(guī)則空間調(diào)度方法［J］.上海交通大學(xué)學(xué)報(bào)，2012，46（4）：651-656.］

［9］TAO Ningrong，JIANG Zuhua，LIU Jianfeng.Spatial scheduling problem with time window constraint for block assembly in shipbuilding［J］.Computer Integrated Manufacturing Systems，2010，12（16）：2674-2679（in Chinese）.［陶寧蓉，蔣祖華，劉建峰.帶時(shí)間窗約束的船體分段空間調(diào)度問題［J］.計(jì)算機(jī)集成制造系統(tǒng)，2010，12（16）：2674-2679.］

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

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

［12］MA Shaohui，WANG Jingqiu，LU Chunxia，et al.A dynamic spatial scheduling approach based on hybrid genetic algorithm［J］.Operations Research and Management Science，2013，22（2）：99-104（in Chinese）.［馬少輝，王景秋，陸春霞，等.動態(tài)空間調(diào)度的混合遺傳算法［J］.運(yùn)籌與管理，2013，22（2）：99-104.］

［13］LIU Xiaoxia.Research on the effects of population size on genetic algorithm performance［D］.Baoding：North China Electric Power University，2010（in Chinese）.［劉曉霞.種群規(guī)模對遺傳算法性能影響的研究［D］.保定：華北電力大學(xué)，2010.］