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

（1.上海交通大學 機械與動力工程學院，上海 200240；2.上海市網絡化制造與企業(yè)信息化重點實驗室，上海 200230）

0 引言

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

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

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

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

1 問題描述

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

1.1 分段建造區(qū)域數學模型

裝焊工場由若干個矩形的跨組成，如圖1所示。分段在跨上進行建造，建造完成后通過大型液壓平板車將其運輸到其他區(qū)域，完成后續(xù)工作。裝焊工場的數學表達為

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

1.2 分段數學模型

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

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

表1 分段近似多邊形和形狀參數

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

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

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

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

1.3 分段空間調度數學模型

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

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

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

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

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

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

2.1 分段位置干涉檢測

分段空間調度的空間約束要求分段投影之間不能存在重疊區(qū)域，即不能出現分段位置干涉。然而分段平面投影形狀各異，有些還包含不規(guī)則的曲線，這給分段位置干涉檢測帶來了困難。可以采用“以直代曲”的方法，將這些投影形狀用包絡多邊形進行近似，如圖5 中連接點的虛線構成的包絡多邊形。多邊形之間的位置干涉可以通過判斷點與多邊形的位置關系實現。

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

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

2.2 分段空間定位算法

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

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

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

2.3 空間調度混合遺傳算法

當多個分段需要同時調度時，它們之間的調度順序會影響裝焊工場的空間利用率。本文采用遺傳算法對分段的調度序列進行優(yōu)化。

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

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

2.3.1 編碼設計

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

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

2.3.2 遺傳算法適應度函數

遺傳算法的目標是使裝焊工場的場地等效有效利用率最大，且跨的數量最少，即編號小的跨盡量放置多的分段，其適應度函數f相對于分段空間調度目標函數U進行修正，可取

式中：wj為第j跨有效利用率的權重，M為跨的數量，Nj為第j跨中分段的數量，sj，i為第j跨中第i個分段的投影占地面積，Bj和ELj為第j個跨的寬和使用長度?？绲挠行Ю寐蕶嘀貪M足w1＞w2＞…＞wM，通過賦予編號靠前的跨更大的權重，使其在調度中優(yōu)先放置分段，減少跨的總使用數量。適應度f越大，表示個體的質量越好。

2.3.3 遺傳操作算子

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

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

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

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

2.4 空間調度算法實現

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

3 案例驗證與算法比較

3.1 案例驗證

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

表2 分段形狀和生產計劃（部分）

續(xù)表2

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

表3 10次遺傳算法適應度收斂值（2014-3-1調度）

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

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

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

對空間調度優(yōu)化中裝焊工場的利用率進行統(tǒng)計，計算平均利用率，可知裝焊工場的平均利用率達到0.800，如圖14 所示。對優(yōu)化結果進行統(tǒng)計，統(tǒng)計結果與實際生產調度利用率的對比如表4所示。實際生產調度時場地平均利用率一般只有0.6，而且分段的占地面積使用的是矩形面積，如果使用實際分段投影形狀，則場地的平均利用率將小于0.6?？梢姴捎帽疚乃崴惴軌蚝芎玫亟鉀Q復雜形狀船舶分段空間調度問題。

表4 空間調度優(yōu)化與實際調度結果比較

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

3.2 算法之間比較分析

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

表5 算法結果對比

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

4 結束語

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

［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ā)，劉玉君，紀卓尚.船舶分段建造計劃仿真與優(yōu)化［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ī)則空間調度方法［J］.上海交通大學學報，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）.［陶寧蓉，蔣祖華，劉建峰.帶時間窗約束的船體分段空間調度問題［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)空間調度方法［J］.計算機工程與應用，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）.［張志英，楊克開，于瑾維，等.改進粒子群算法的動態(tài)空間調度方法［J］.哈爾濱工程大學學報，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)空間調度的混合遺傳算法［J］.運籌與管理，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］.保定：華北電力大學，2010.］