侯俊，張志英

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

船廠鋼板堆場(chǎng)混合存儲(chǔ)分配及出入庫(kù)調(diào)度研究

侯俊，張志英

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

為符合造船廠提出的“分段集批，段齊交貨”原則，本文在驗(yàn)證混合存儲(chǔ)可行性的同時(shí)，優(yōu)化出入庫(kù)倒垛作業(yè)方案，減少研究周期內(nèi)出庫(kù)倒垛次數(shù)、降低作業(yè)時(shí)間和操作成本，從而提高堆場(chǎng)利用率。針對(duì)建立的整數(shù)規(guī)劃模型，提出了基于模擬退火接收準(zhǔn)則的雙層遺傳算法(SA-HGA)，在垛位存儲(chǔ)分布均勻的基礎(chǔ)上制定堆場(chǎng)劃分方案，然后根據(jù)堆場(chǎng)當(dāng)前存儲(chǔ)狀態(tài)為將要進(jìn)入堆場(chǎng)中的兩類分段屬性的鋼板預(yù)分配垛位，為需求計(jì)劃制定作業(yè)方案包括倒垛和出庫(kù)作業(yè)組合計(jì)劃。利用該算法對(duì)出入庫(kù)作業(yè)及倒垛方案進(jìn)行優(yōu)化，最后將該算法與傳統(tǒng)遺傳算法作對(duì)比，實(shí)驗(yàn)證明算法具有有效性和收斂性，并在不同作業(yè)規(guī)模下，降低了成本預(yù)算(4.9%～21.3%)及操作時(shí)間(7.6%～10.1%)。

造船廠； 鋼板堆場(chǎng)； 分段； 堆場(chǎng)作業(yè)計(jì)劃； 雙層遺傳算法； 模擬退火

船舶生產(chǎn)過程為分批分段建造，物料需求具有嚴(yán)格的順序性，船體不同段位需求的鋼板規(guī)格、數(shù)量及期限也嚴(yán)格列出。分段，即鋼板生產(chǎn)部門根據(jù)船廠生產(chǎn)計(jì)劃將鋼板依次運(yùn)輸至堆場(chǎng)存儲(chǔ)，并為其中指定段位所用鋼板設(shè)分段屬性標(biāo)識(shí)。由于生產(chǎn)順序和周期與需求之間的差異性，存儲(chǔ)垛位先入后出的規(guī)則，多批次不同類型鋼板相互積壓，形成倒垛操作。另一方面，船體不同段位所需鋼板規(guī)格種類繁多，造船廠對(duì)船板供應(yīng)商提出 “分段集批，段齊交貨”的原則。鋼板堆場(chǎng)出入庫(kù)作業(yè)成本是存儲(chǔ)和操作成本中占比不可忽視的一部分。目前造船業(yè)相關(guān)研究主要集中于實(shí)現(xiàn)自動(dòng)化和信息化管理，相近領(lǐng)域也有煉鋼廠熱軋板堆場(chǎng)作業(yè)優(yōu)化的研究。造船領(lǐng)域中，施敏等提出了垛位自動(dòng)預(yù)約技術(shù)以實(shí)現(xiàn)船板自動(dòng)入庫(kù)空間分配[1]。徐萍等為應(yīng)對(duì)管理現(xiàn)狀與供貨要求，提出了構(gòu)建堆場(chǎng)管理信息系統(tǒng)的開發(fā)方案[2]。劉建峰等為船板入庫(kù)滾動(dòng)作業(yè)建立了基于優(yōu)化算法的仿真模型，研究鋼板入庫(kù)分配策略[3]。在熱軋煉鋼行業(yè)，蔣如宏等針對(duì)板坯出庫(kù)作業(yè)建立靜態(tài)和動(dòng)態(tài)數(shù)字化仿真模型，提高堆場(chǎng)管理信息化水平[4]。唐立新等針對(duì)倒垛問題提出了整數(shù)規(guī)劃模型，采用動(dòng)態(tài)啟發(fā)式算法優(yōu)化解決方案[5]，李耀華等為熱軋板坯出庫(kù)建立倒垛決策模型，運(yùn)用粒子群算法以最小化倒垛量[6]。以上研究從不同角度探討了堆場(chǎng)管理改進(jìn)方案。但無委托熱軋板堆場(chǎng)相關(guān)研究主要對(duì)出入庫(kù)或倒垛作業(yè)進(jìn)行優(yōu)化，不考慮指定分段的特殊屬性。造船廠鋼板堆場(chǎng)為帶分段屬性板單獨(dú)分配存儲(chǔ)區(qū)域，忽略了指定分段屬性鋼板獨(dú)立存儲(chǔ)方式的潛在問題。如因缺少部分段位延遲交貨、占用堆場(chǎng)空間、堆積變形、垛位過高和存儲(chǔ)周期過長(zhǎng)等。

針對(duì)鋼板堆場(chǎng)部分鋼板帶有指定分段的屬性，存儲(chǔ)限制條件苛刻，需求必須及時(shí)響應(yīng)的問題特殊性。在上述研究的基礎(chǔ)上，本文將研究指定分段和無指定分段兩種鋼板混合存儲(chǔ)方式，由于混合存儲(chǔ)方式可能帶來分段屬性不同的鋼板相互積壓增加倒垛量的問題，因此從出入庫(kù)作業(yè)成本、時(shí)間和倒垛量三個(gè)維度，建立基于入庫(kù)決策的出庫(kù)整數(shù)規(guī)劃分配決策模型。并提出了高度適應(yīng)問題特殊性的基于模擬退火概率接受準(zhǔn)則的雙層遺傳算法，通過實(shí)驗(yàn)分析對(duì)比驗(yàn)證算法的有效性。

1 問題描述

1.1問題背景

船廠鋼板堆場(chǎng)管理流程具體描述為：1)根據(jù)生產(chǎn)計(jì)劃匯總訂單合同，鋼板到達(dá)堆場(chǎng)后進(jìn)入緩沖區(qū)堆放，按分段、尺寸等屬性分類，等待入庫(kù)操作；2)確定入庫(kù)序列，橋吊空閑時(shí)依次從緩沖堆取出鋼板移入堆場(chǎng)指定垛位，存儲(chǔ)在主堆場(chǎng)中；3)確定出庫(kù)集合，按出庫(kù)計(jì)劃從指定的位置取出目標(biāo)鋼板，若目標(biāo)板在頂層，則直接移至預(yù)處理臨時(shí)垛位并轉(zhuǎn)5)，否則轉(zhuǎn)4)；4)目標(biāo)板上積壓有其他鋼板，為倒垛集合中的鋼板選擇然后移至新的存儲(chǔ)垛位，直到目標(biāo)板暴露在頂層，取出鋼板并移至預(yù)處理臨時(shí)垛位；5)在截止時(shí)間前依次將經(jīng)過預(yù)處理的鋼板放置在出場(chǎng)傳送帶上，組合出庫(kù)。

主堆場(chǎng)中的鋼板堆放限制條件包括：規(guī)格較大鋼板不能壓在小鋼板之上；屬性(包括分段號(hào)、終端用戶、交貨地、厚度、材質(zhì)強(qiáng)度等級(jí))相同或接近的鋼板放置在同垛；垛位累積不能超過最大高度；每個(gè)垛位只能放置同一天出庫(kù)的鋼板[7]?；诒疚难芯康亩褕?chǎng)布局，假設(shè)當(dāng)前堆場(chǎng)以混合存儲(chǔ)方式堆放大量鋼板，以此為初始狀態(tài)。如圖1所示，建立堆場(chǎng)坐標(biāo)，X/Y分別代表垛位列/行編號(hào)順序：

1)主堆場(chǎng)垛位數(shù)量Y=RC，堆場(chǎng)以左上角為坐標(biāo)原點(diǎn)，由一個(gè)橋吊承擔(dān)出入庫(kù)搬運(yùn)作業(yè)；

2)鋼板從左端緩沖堆入庫(kù)，進(jìn)入堆場(chǎng)后由起始坐標(biāo)搬運(yùn)至預(yù)分配垛位；

3)堆場(chǎng)每行(列)按照出庫(kù)日期及尺寸劃分，不考慮分段屬性。從坐標(biāo)原點(diǎn)開始，隨著橫(縱)坐標(biāo)增大均勻分布；

4)鋼板可以在不同行(列)之間進(jìn)行倒垛優(yōu)先選擇同列不同行，橋吊主體梁橫向(或起重小車縱向)移動(dòng)，且只考慮單張鋼板搬運(yùn)；

5)假設(shè)堆場(chǎng)起始狀態(tài)不為空，且以現(xiàn)有方式存儲(chǔ)了一定量的鋼板，并設(shè)垛位坐標(biāo)Pi(Ci,Ri),(i=1,2,…,Y)

圖1 堆場(chǎng)布局Fig.1 Layout of stack yard

混合存儲(chǔ)情況下，堆場(chǎng)垛位分割只考慮尺寸和出庫(kù)日期屬性，針對(duì)分段的特殊屬性再進(jìn)行后續(xù)出入庫(kù)方案優(yōu)化。因此從預(yù)分配的角度，按照全部鋼板的尺寸大小概率分布，以均衡各個(gè)垛位鋼板數(shù)量為主要目的進(jìn)行區(qū)域劃分。如圖2，堆場(chǎng)按尺寸界限值：下限(L,W)d=(Ld,Wd)，上限(L,W)u=(Lu,Wu)劃分為Ar塊區(qū)域，每個(gè)區(qū)域按照出庫(kù)日期D依次分配垛位。

圖2 堆場(chǎng)劃分Fig.2 Stack yard division

假設(shè)造船廠全部入庫(kù)鋼板尺寸分布服從概率函數(shù)f(l,w):

(1)

(2)

式中：l和w分別代表鋼板屬性長(zhǎng)和寬，Y為堆場(chǎng)垛位總數(shù)，μ為概率均值。式(1)為任意垛位i尺寸范圍概率，表示累計(jì)垛位i尺寸范圍內(nèi)出現(xiàn)的概率；堆場(chǎng)垛位布局預(yù)劃分時(shí)計(jì)算式(2)[8]，為保證堆場(chǎng)中各個(gè)垛位鋼板數(shù)量分布均衡，以概率方差Δf值為控制變量，不超過指定最大值時(shí)可保證分布均衡。根據(jù)式(1)計(jì)算的頻率，式(2)計(jì)算頻率方差，方差越小，各個(gè)垛位鋼板數(shù)量在概率上保證相近。從管理者角度來看式(1)、(2)，可以確定劃分界限，防止堆場(chǎng)劃分界限造成堆場(chǎng)運(yùn)行管理過程中，部分區(qū)域鋼板密集，垛位過高。同時(shí)按規(guī)則劃分存儲(chǔ)區(qū)域也便于出庫(kù)時(shí)可按照尺寸和出庫(kù)日期快速鎖定所在垛位范圍，能夠加快查找速度，降低搜索算法的運(yùn)行空間。

1.2出入庫(kù)作業(yè)流程

對(duì)于造船廠，入庫(kù)作業(yè)即為到貨鋼板安排合理垛位，出入庫(kù)日期確定的前提下，入庫(kù)鋼板應(yīng)盡量避免將出庫(kù)日期臨近的帶分段屬性板積壓在下層，引起大量不必要的倒垛。由于鋼板的分段屬性，無分段板只需滿足訂單數(shù)量規(guī)格要求，帶分段板須按分段先集齊段位后組合出庫(kù)。因出庫(kù)方式不同，所以出庫(kù)作業(yè)分兩種：1)取出符合出庫(kù)要求規(guī)格和數(shù)量的鋼板；2)從指定位置取出入庫(kù)前作特殊分段號(hào)標(biāo)記的鋼板集合。

根據(jù)在庫(kù)板存儲(chǔ)限制條件和本文研究問題的特殊性提出以下入庫(kù)規(guī)則：鋼板分段號(hào)、尺寸大小及材質(zhì)>出庫(kù)日期>垛位高度.按堆場(chǎng)放置原則逐個(gè)選擇，放置在垛位最上層，不進(jìn)行預(yù)倒垛。

出入庫(kù)作業(yè)和堆場(chǎng)狀態(tài)變化之間相互關(guān)系如圖3所示。

圖3 鋼板出入庫(kù)流程Fig.3 Logical flow of steel plate inbound and outbound

為解決本文混合存儲(chǔ)出入庫(kù)組合優(yōu)化問題，合理安排鋼板進(jìn)入堆場(chǎng)的次序，為鋼板預(yù)分配存儲(chǔ)空間，優(yōu)化出庫(kù)分配計(jì)劃，建立整數(shù)規(guī)劃模型。

2 數(shù)學(xué)模型

2.1堆垛及倒垛約束模型

設(shè)垛位t中鋼板的最大尺寸為L(zhǎng)max t，最小尺寸為L(zhǎng)min t，根據(jù)現(xiàn)有的船廠鋼板堆場(chǎng)管理信息系統(tǒng)，入庫(kù)鋼板在到達(dá)堆場(chǎng)前7、8 d就對(duì)堆場(chǎng)發(fā)出預(yù)約垛位信息，按分段號(hào)將訂單匯總分類整理。為防止同一垛位鋼板尺寸不同，會(huì)造成相互積壓變形，增加矯正工序，必須降低同一垛位鋼板尺寸差異，因此建立以下約束模型。全部鋼板包括指定分段和不指定分段屬性鋼板入庫(kù)選擇垛位時(shí)都需要滿足以下尺寸約束，降低同一垛位鋼板尺寸偏差。同理，倒垛即為出庫(kù)目標(biāo)板以上的鋼板集合重新選擇垛位[9]。z為初始設(shè)定值，同一個(gè)垛位鋼板的長(zhǎng)度寬度之差約束如下，j/k為垛位t中任意兩塊板。rij/cij為出庫(kù)板i對(duì)應(yīng)出庫(kù)集合中板j所在行/列，Xij=1表示鋼板j選為出庫(kù)Pij對(duì)應(yīng)板，Xij=0時(shí)則反之，i=1,2,…,M；Xijr：代表出庫(kù)板i對(duì)應(yīng)板j所在垛位第r層鋼板，存在時(shí)為1。限制垛位相鄰兩塊板寬度(長(zhǎng)度)差在一定范圍內(nèi)：

|Wj-Wk|≤Wm+(2-Xijr-Xikr-1)Z

(3)

|Wj-Wk|≤Wm+(2-Xijr-Xikr+1)Z

(4)

|Lj-Lk|≤Lm+(2-Xijr-Xikr-1)Z

(5)

|Lj-Lk|≤Lm+(2-Xijr-Xikr+1)Z

(6)

為保證垛位內(nèi)任意兩塊板與垛位內(nèi)最大板長(zhǎng)度差在一定范圍內(nèi),則

(7)

(8)

r=1,2,…,Hm

目前對(duì)于倒垛作業(yè)優(yōu)化的研究已經(jīng)較為成熟，倒垛模型假設(shè)選擇的垛位大部分都是在原垛位附近，以加快算法運(yùn)行速度降低問題復(fù)雜度，重新選擇的垛位滿足以上垛位尺寸約束同時(shí)還要滿足：

(9)

圖4 相鄰可倒垛位分布Fig.4 Distribution of neighbored shuffling stack

2.2目標(biāo)函數(shù)及約束

根據(jù)問題約束和優(yōu)化目標(biāo)建立數(shù)學(xué)模型，Dij為出庫(kù)板i對(duì)應(yīng)鋼板j翻板數(shù)量，優(yōu)化目標(biāo)為最小化橋吊翻板及運(yùn)輸所需鋼板行駛的時(shí)間為

(10)

完成板i出庫(kù)作業(yè)需要的操作時(shí)間為

(11)

式中：tc為橋吊橫向移動(dòng)單位距離時(shí)間，t0代表橋吊取板上下移動(dòng)時(shí)間，ts橋吊倒垛平移時(shí)間；tu橋吊倒垛上下移動(dòng)時(shí)間。

取出(i-1)塊板后，第i塊板預(yù)計(jì)倒垛量：

Dij=max{Dj-max{Xij,Dj+1|I′=

(12)

在出入庫(kù)作業(yè)全過程中，計(jì)算出橋吊行駛距離成本為

(13)

為取出出庫(kù)板i對(duì)應(yīng)符合條件的板j的付出的倒垛成本公式為

(14)

每一個(gè)垛位中鋼板堆放的總高度限制為

(15)

限制鋼板出庫(kù)時(shí)間在其上倒垛板完成倒垛之后作業(yè)時(shí)間為

(16)

保證對(duì)應(yīng)出庫(kù)序列中無分段板有符合要求數(shù)量的板、帶分段板有且只有一塊板被選作目標(biāo)板，則：

(17)

(18)

由以上描述及模型可知問題屬于多目標(biāo)組合優(yōu)化問題[10]。為求解該問題，本文將改進(jìn)現(xiàn)有方法，針對(duì)可行解空間大而難以找到最優(yōu)解的問題，提出基于模擬退火概率接受準(zhǔn)則的兩層嵌套遺傳算法，通過出庫(kù)作業(yè)內(nèi)層解對(duì)外層入庫(kù)作業(yè)計(jì)劃的動(dòng)態(tài)適應(yīng)，求解研究周期內(nèi)堆場(chǎng)物流周轉(zhuǎn)方案。這種算法具有特殊問題適應(yīng)性，從而更能找到本文提出的混合存儲(chǔ)優(yōu)化問題的較優(yōu)解。

3 模擬退火雙層遺傳算法

3.1編碼方式

本文提出基于模擬退火概率接收準(zhǔn)則的兩層遺傳算法來解決文中的問題，設(shè)Ei為入庫(kù)清單整合規(guī)格序列Ei{e1,e2,…,ei,…,eM}，M為出庫(kù)計(jì)劃中鋼板總數(shù)，鋼板出庫(kù)序列P=(P1,P2,…,PM)，Ωt堆場(chǎng)在研究周期T狀態(tài)，出庫(kù)計(jì)劃中的第i個(gè)鋼板Pi的規(guī)格參數(shù)為ei=(Li,Wi,Hi,Gi,Seg,Ni)，分別對(duì)應(yīng)長(zhǎng)、寬、厚、材質(zhì)、分段號(hào)、需求數(shù)量，不指定分段板Seg值為空，編碼方式如下所述：

圖5 入庫(kù)編碼Fig.5 Inbound coding mode

2)堆場(chǎng)狀態(tài)Ω編碼以及內(nèi)層選擇匹配組合出庫(kù)編碼，若堆場(chǎng)內(nèi)鋼板以數(shù)組堆棧存儲(chǔ)，E[i][k](i∈[1,Y],k∈[1,Hm])。將符合規(guī)格ei的板設(shè)為i×10+1，十位以上為外層染色體出庫(kù)次序編號(hào)。無板層設(shè)為0，有板層設(shè)為1，堆場(chǎng)可數(shù)字化為表1所示。

表1 堆場(chǎng)垛位數(shù)字化編碼

圖6 出庫(kù)組合編碼Fig.6 Outbound combining coding mode

4)倒垛按步驟3染色體中為1的基因位確定目標(biāo)板集合。倒垛集合也隨之確定，為每塊倒垛板建立可倒垛位集合。對(duì)于集合中每一個(gè)垛位，通過移動(dòng)堆場(chǎng)狀態(tài)編碼中原位置和新位置的值反映鋼板移動(dòng)。每次移動(dòng)令累積倒垛次數(shù)(shuffling number)SN=SN+1，最終在可倒垛集合中選擇為完成該板出庫(kù)作業(yè)預(yù)估倒垛量(SN值)最小的垛位組合。

另一方面，本文采用的對(duì)比算法為一般遺傳算法，編碼方式采用以上兩層染色體拼接為一條染色體的方式，如圖7所示。

圖7 GA染色體編碼Fig.7 GA chromosomecoding mode

3.2算法流程

本文采用的基于模擬退火兩層遺傳算法進(jìn)行優(yōu)化求解，其中選擇策略是基于模擬退火的概率接受準(zhǔn)則，可降低內(nèi)層算法對(duì)外層解的模糊化，采用概率接受準(zhǔn)則增加種群原始解的保存率，防止內(nèi)層算法對(duì)外層基因的破壞。具體算法流程如圖8所示。

圖8 模擬退火雙層遺傳算法流程Fig.8 SA-HGA algorithm flow

4 實(shí)例驗(yàn)證與數(shù)值分析

4.1參數(shù)設(shè)置

為證明上面提出的算法在該問題背景下的實(shí)用性和有效性，采用實(shí)例驗(yàn)證算法可行性并與一般遺傳算法性能作對(duì)比。算法是在Windows7系統(tǒng)下基于Matlab2011b實(shí)現(xiàn)，選取某大型造船廠實(shí)際數(shù)據(jù)驗(yàn)證，當(dāng)前研究的是在堆場(chǎng)狀態(tài)不為空的情況下一個(gè)調(diào)度周期內(nèi)出入庫(kù)作業(yè)計(jì)劃。表2是實(shí)例數(shù)據(jù)以及參數(shù)基準(zhǔn)單位設(shè)置。

表2 初始參數(shù)設(shè)置

遺傳算法的參數(shù)設(shè)置在文獻(xiàn)中有相關(guān)研究，根據(jù)文獻(xiàn)[10-12]，為保證種群多樣性增加變異概率，根據(jù)實(shí)驗(yàn)后的種群收斂性確定，基于模擬退火概率接受準(zhǔn)則的雙層遺傳算法參數(shù)選擇為：外層迭代次數(shù)NC1=100，種群大小N1=20，內(nèi)層迭代次數(shù)NC2=50次，種群大小N2=30，內(nèi)外層選擇比例GAP=0.8，交叉概率為XOVER=0.7，變異概率MUTR=0.2。

為了驗(yàn)證并與本文算法進(jìn)行對(duì)比，GA算法的參數(shù)選取為：迭代次數(shù)NC=100，種群大小N=50，選擇比例GAP=0.8，交叉概率XOVER=0.7，變異概率MUTR=0.2。

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

表3顯示混合存儲(chǔ)在出入庫(kù)規(guī)則約束下，對(duì)目標(biāo)函數(shù)無明顯影響。是由于堆場(chǎng)空間利用率的影響，因此表4數(shù)據(jù)證明了混合存儲(chǔ)方式在規(guī)則約束下的可行性。

表3不指定分段與混合存儲(chǔ)算例對(duì)比數(shù)據(jù)

Table3Datacomparisonbetweenmixedstorageandnon-segmentedstorage

算例SegY/N入庫(kù)數(shù)量SegY/N出庫(kù)數(shù)量SA-HGACost/元t/sSN920/2520020/302004620.52625.013959'0/302000/352004411.02519.513281025/4530020/503007223.54198.0216910'0/603000/603007094.54012.52056

注：Y、N分別是指定分段和不指定分段；Cost為完成出入庫(kù)倒垛作業(yè)所需的人工設(shè)備總成本；SN為倒垛量。

表4 混合存儲(chǔ)不同規(guī)模算例數(shù)據(jù)

表4分析了隨入庫(kù)鋼板數(shù)量，包括指定分段和不指定分段板同步增加時(shí)堆場(chǎng)運(yùn)行代價(jià)的變化趨勢(shì)。考慮到部分指定分段鋼板混合存儲(chǔ)在堆場(chǎng)中，出庫(kù)時(shí)不僅有出入庫(kù)鋼板相互堆疊[11]形成倒垛作業(yè)的增加，更有指定分段和不指定分段板之間相互堆疊，因此調(diào)度方案優(yōu)化方向?yàn)楸苊馊〕鲋付ǚ侄伟鍟r(shí)對(duì)積壓在其上的其他分段屬性鋼板大量移動(dòng)。表4中對(duì)比數(shù)據(jù)可以看到，對(duì)于算例1和2，在鋼板數(shù)量較少時(shí)兩個(gè)算法都能求得最優(yōu)解。當(dāng)鋼板出入庫(kù)的規(guī)格種類數(shù)較多，移動(dòng)總數(shù)量超過200時(shí)，比如算例10，運(yùn)輸成本和時(shí)間急劇增加，GA不能完成作業(yè)優(yōu)化，而SA-HGA算法則可以對(duì)兩層操作進(jìn)行動(dòng)態(tài)協(xié)調(diào)，找到令出庫(kù)組合最優(yōu)的入庫(kù)方式，同時(shí)得到與之相適應(yīng)的倒垛和出庫(kù)作業(yè)計(jì)劃，使得出庫(kù)作業(yè)高效且控制成本。本優(yōu)化算法得到的作業(yè)方案，明顯優(yōu)于GA得到的作業(yè)方案。以算例8為例，應(yīng)用本算法，倒板數(shù)量減少13.4%，橋吊作業(yè)成本減少14.1%，作業(yè)時(shí)間縮短10.1%。

為驗(yàn)證算法有效性，算法求解優(yōu)化模型需要的時(shí)間隨問題規(guī)模變化曲線如圖9所示。由于本文采用的雙層嵌套遺傳算法運(yùn)行時(shí)間比一般遺傳算法運(yùn)行時(shí)間稍慢，但也在實(shí)際堆場(chǎng)作業(yè)管理可接受范圍內(nèi)，因此算法是可行且有效的。

以算例9為例，進(jìn)一步將兩種優(yōu)化算法的收斂性[12]作對(duì)比。SA-HGA內(nèi)外層目標(biāo)函數(shù)變化曲線如圖10所示，可以看到算法運(yùn)行時(shí)表現(xiàn)出較好的收斂性。

圖9 算法運(yùn)行時(shí)間隨問題規(guī)模變化曲線圖Fig.9 Algorithm running time with variable problem scales

圖10 SA-HGA和GA 算法收斂性對(duì)比Fig.10 Convergence performance of SA-HGA comparison to GA

由于遺傳操作的局限性，一條同時(shí)攜帶出入庫(kù)計(jì)劃方案的染色體可能會(huì)同時(shí)在多個(gè)位置發(fā)生變化，容易破壞解的質(zhì)量甚至陷入早熟收斂。而與傳統(tǒng)的遺傳算法相比，采用模擬退火概率接受準(zhǔn)則的雙層遺傳算法對(duì)內(nèi)外層染色體協(xié)調(diào)優(yōu)化，出入庫(kù)作業(yè)方案相互配合，保證了外層較優(yōu)解的持久度，而遺傳操作同時(shí)不斷更新種群，防止早熟收斂。因此從表4及圖10可知，傳統(tǒng)遺傳算法收斂性較好，能較快尋得較優(yōu)解。

5 結(jié)論

1)提出了基于堆場(chǎng)當(dāng)前狀態(tài)，帶分段屬性和無分段屬性兩類鋼板混合存儲(chǔ)的方法，針對(duì)本文提出的多目標(biāo)組合優(yōu)化問題，建立了整數(shù)規(guī)劃模型，進(jìn)一步優(yōu)化出入庫(kù)作業(yè)成本和時(shí)間；

2)為適應(yīng)于該多約束組合優(yōu)化問題，提出運(yùn)用模擬退火雙層遺傳算法優(yōu)化作業(yè)計(jì)劃，通過算法實(shí)例演算結(jié)果表明，算法能在一定的迭代次數(shù)內(nèi)尋得較優(yōu)解；提供堆場(chǎng)管理作業(yè)方案，大幅度降低堆場(chǎng)作業(yè)成本和時(shí)間、減少倒垛量并且具有較高的規(guī)模適應(yīng)性。并與GA相比較，證明本文提出SA-HGA的可行性和有效性。

本文尚需完善堆場(chǎng)空間利用率的計(jì)算，同時(shí)也為兩類分段板的存儲(chǔ)方式研究提供了新的方向。

[1] 施敏, 徐端, 劉宇晶. 垛位自動(dòng)預(yù)約技術(shù)在寶鋼船板配送中心庫(kù)場(chǎng)管理系統(tǒng)中的應(yīng)用[J]. 冶金自動(dòng)化, 2011(6): 28-32.

SHI Min, XU Duan, LIU Yujing. Applications of pile automatic appointment in BaosteelShip distribution center[J]. Metallurgical industry automation, 2011(6): 28-32.

[2] 徐萍. 造船廠鋼板入庫(kù)作業(yè)優(yōu)化及鋼板管理信息系統(tǒng)開發(fā)[D]. 鎮(zhèn)江: 江蘇科技大學(xué), 2011.

XU Ping. Optimization on input operations and management information system development of a steel plate stacking yard in a shipyard[D]. Zhenjiang: Jiangsu University of Science and Technology, 2011.

[3] 蔣如宏, 鐘宏才, 譚家華. 船廠鋼板堆場(chǎng)管理的數(shù)字化仿真[J]. 上海交通大學(xué)學(xué)報(bào), 2003, 37(8): 1242-1245.

JIANG Ruhong, ZHONG Hongcai, TAN Jiahua. Simulation of digitized plate stockyard management in shipyards[J]. Journal of Shanghai Jiao Tong University, 2003, 37(8): 1242-1245.

[4] 劉建峰, 張小輝, 蔣志勇,等. 基于遺傳算法入庫(kù)鋼板分配策略研究[J]. 江蘇科技大學(xué)學(xué)報(bào):自然科學(xué)版, 2011(6): 524-529.

LIU Jianfeng, ZHANG Xiaohui, JIANG Zhiyong, et al. Allocation strategy of steel plate in store house based on genetic algorithm[J]. Journal of Jiangsu University of Science and Technology: natural science edition, 2011(6): 524-529.

[5] 唐立新, 楊自厚. 熱軋實(shí)施計(jì)劃中最優(yōu)倒垛問題的整數(shù)規(guī)劃模型及遺傳算法[J]. 自動(dòng)化學(xué)報(bào), 2000, 26(4): 461-469.

TANG Lixing, YANG Zihou. Integer programming model and modified genetic algorithm for optimalturned-out slab pile for hot rollinne schedule[J]. Acta automatic sinica, 2000, 26(4): 461-469.

[6] 李耀華, 王偉, 胡國(guó)奮, 等. 熱軋板坯庫(kù)出庫(kù)計(jì)劃編制模型與算法研究[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2006, 12(3): 377-381.

LI Yaohua, WANG Wei, HU Guofen, et al. Research on slab discharge planning model and algorithm for hot-rolling slab-yard[J]. Computer integrated manufacturing systems, 2006, 12(3): 377-381.

[7] ZHAO R, TANG L. Integer programming model and dynamic programming based heuristic algorithm for the heavy plate shuffling problem in the Iron and steel industry[C]// International Conference on Logistics Systems and Intelligent Management. 2010: 1381-1385.

[8] ZHANG Z, WANG P, WANG W. Optimization and operation scheduling for a steel plate yard based on greedy algorithm[J]. Journal of networks, 2013, 8(7):1654-1659.

[9] TANG L, REN H. Modelling and a segmented dynamic programming-based heuristic approach for the slab stack shuffling problem [J]. Computers & operations research, 2010, 37(2): 368-375.

[10] 王廣民. 造船廠鋼板堆場(chǎng)出庫(kù)作業(yè)計(jì)劃建模及優(yōu)化研究[D]. 大連: 大連理工大學(xué), 2009.

WANG Guangmin. Modeling and optimization on operation scheduling of a steel plate stacking yard in a shipyard[D]. Dalian: Dalian University of Technology, 2009.

[11] 張志英, 王維澤, 侯俊. 船廠鋼板堆場(chǎng)多時(shí)段作業(yè)計(jì)劃優(yōu)化[J]. 哈爾濱工程大學(xué)學(xué)報(bào), 2015(5): 638-643.

ZHANG Zhiying, WANG Weize, HOU Jun. Optimization of multistage operation scheduling for a steel plate stockyard in shipbuilding[J]. Journal of Harbin Engineering University, 2015(5): 638-643.

[12] WANG G, JIN C, DENG X. Modeling and optimization on steel plate pick-up operation scheduling on stack yard of shipyard[C]//IEEE International Conference on Automation and Logistics, 2008: 548-553.

本文引用格式：

侯俊，張志英. 船廠鋼板堆場(chǎng)混合存儲(chǔ)分配及出入庫(kù)調(diào)度研究[J]. 哈爾濱工程大學(xué)學(xué)報(bào)， 2017， 38(11): 1786-1793.

HOU Jun, ZHANG Zhiying. Location allocation for inbound and outbound scheduling of mixed storage steel plate in shipyard[J]. Journal of Harbin Engineering University， 2017， 38(11): 1786-1793.

Locationallocationforinboundandoutboundschedulingof
mixedstoragesteelplateinshipyard

HOU Jun, ZHANG Zhiying

(School of Mechanical Engineering, Tongji University, Shanghai 200092, China)

To meet with the principle of managing shipyard that the steel plate in the stack yard is partly characterized by the block numbers and hybrid storage, this paper firstly verified that the assumption of mixed storage of block-oriented plates is feasible, and at the same time, optimized the shuffling costs followed by the outbound and inbound operations, and realized the purpose of reducing the costs including logistics and operation time of the processes, thereby improving the utilization of the stockyard. An integer programming model was formulated, and the approximately optimal solution was obtained according to the hierarchic genetic algorithm based on the simulated annealing probability accepted criterion (SA-HGA), programming the operation of pre-allocating for the two kinds of inbounding plates based on the current storage state, making sure that the plates inbounding is equally distributed, providing shuffling and out bounding plans according to the demand which costs less budget and time. At last, it′s proved that the algorithm is of convergence and effectiveness by analyzing several cases, which are of different scales and make a contrast to the general genetic algorithm (GA). The results of the numerical experiments demonstrate the assumption and make an improvement to the operation plan of 4.9%～21.3% in cost and 7.6%～10.1% in operation time.

shipyard; stockyard; segment; steel plate operation scheduling; hierarchic genetic algorithm; simulated annealing

10.11990/jheu.201606059

http://www.cnki.net/kcms/detail/23.1390.u.20170427.1544.150.html

TP18，U673

A

1006-7043(2017)11-1786-08

2016-06-21.

網(wǎng)絡(luò)出版日期：2017-04-27.

國(guó)家自然科學(xué)基金項(xiàng)目(70872076);上海市科技創(chuàng)新行動(dòng)計(jì)劃項(xiàng)目 (11DZ1121803);江蘇省南通市2010AA科技創(chuàng)新計(jì)劃(工業(yè))基金項(xiàng)目(AA2010048).

張志英(1971-), 男, 副教授.

張志英, E-mail:zyzhang08@#edu.cn.