張志英,曾建智

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

?

基于啟發(fā)式規(guī)則的臨時(shí)分段調(diào)度計(jì)劃與優(yōu)化

張志英,曾建智

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

船舶堆場(chǎng)中臨時(shí)分段調(diào)度方案的優(yōu)劣影響著調(diào)度的效率和成本。本文以臨時(shí)分段的調(diào)度過(guò)程為優(yōu)化對(duì)象，以平板車的移動(dòng)距離為優(yōu)化目標(biāo)建立數(shù)學(xué)模型。通過(guò)制定動(dòng)態(tài)的臨時(shí)分段調(diào)度規(guī)則和超長(zhǎng)分段調(diào)度規(guī)則，充分利用堆場(chǎng)中的空存儲(chǔ)單元，最終確定一個(gè)較優(yōu)的臨時(shí)分段調(diào)度方案。同時(shí)利用任務(wù)合并對(duì)堆場(chǎng)調(diào)度的任務(wù)序列進(jìn)行優(yōu)化，從而減少調(diào)度過(guò)程中臨時(shí)分段的數(shù)量。最后，利用某船廠的實(shí)際數(shù)據(jù)對(duì)模型和調(diào)度規(guī)則進(jìn)行實(shí)例驗(yàn)證和數(shù)值分析，結(jié)果表明，所制定的調(diào)度規(guī)則可以優(yōu)化堆場(chǎng)調(diào)度方案，提高堆場(chǎng)空間資源利用率和調(diào)度效率。

堆場(chǎng)；調(diào)度規(guī)則；超長(zhǎng)分段；任務(wù)合并；啟發(fā)式規(guī)則

在大中型船舶的設(shè)計(jì)階段，因?yàn)樯a(chǎn)資源和工藝的約束，一艘船通常被分割為200個(gè)左右的分段，這些分段分別進(jìn)行獨(dú)立的生產(chǎn)建造，最后在船塢進(jìn)行搭載。由于船舶企業(yè)生產(chǎn)和管理的原因，各個(gè)分段在不同加工工序之間無(wú)法即時(shí)周轉(zhuǎn)，堆場(chǎng)便作為暫存或者預(yù)處理(預(yù)舾裝、檢驗(yàn)和修補(bǔ)等)分段的場(chǎng)所。作為中間產(chǎn)品的分段規(guī)格約為15 m×15 m×5 m，重量為100～300 t，有些特殊規(guī)格的分段甚至超過(guò)500 t。因此需要專門的搬運(yùn)設(shè)備(平板車)對(duì)分段進(jìn)行運(yùn)輸和調(diào)度。平板車只能進(jìn)行平面方向上的運(yùn)輸，且一次只能搬運(yùn)一個(gè)分段，它利用液壓裝置將分段提升，通過(guò)堆場(chǎng)中的可行路徑，將分段移動(dòng)至目標(biāo)位置并放置支撐桿上。在船舶堆場(chǎng)調(diào)度過(guò)程中，根據(jù)作業(yè)流程可分為三種分段：進(jìn)場(chǎng)分段、出場(chǎng)分段和臨時(shí)分段。對(duì)于臨時(shí)分段的處理是無(wú)增值的操作，且對(duì)其采用不同的調(diào)度規(guī)則會(huì)直接影響平板車的調(diào)度效率以及整個(gè)堆場(chǎng)的調(diào)度計(jì)劃，因此對(duì)于臨時(shí)分段如何制定一個(gè)科學(xué)、合理的調(diào)度規(guī)則尤為重要。

分段堆場(chǎng)一般為若干個(gè)大小相等的正方形場(chǎng)地組成的一個(gè)矩形區(qū)域，每一個(gè)場(chǎng)地為一個(gè)存儲(chǔ)單元。一個(gè)存儲(chǔ)單元一般存放一個(gè)分段(常規(guī)分段)，但是船舶分段的尺寸不盡相同，對(duì)于一些超長(zhǎng)規(guī)格的分段，將占用一個(gè)以上的存儲(chǔ)單元。這些分段成為臨時(shí)分段時(shí)，其調(diào)度復(fù)雜程度將遠(yuǎn)遠(yuǎn)大于常規(guī)分段，堆場(chǎng)需要為其制定相應(yīng)的調(diào)度方法。Changkyu等[1-2]以臨時(shí)分段移動(dòng)數(shù)量為優(yōu)化目標(biāo)建立模型，并運(yùn)用遺傳算法和改進(jìn)動(dòng)態(tài)啟發(fā)式算法對(duì)模型進(jìn)行求解。Tao等[3]在此基礎(chǔ)上考慮分段進(jìn)出堆場(chǎng)任務(wù)順序?qū)φ{(diào)度方案的影響，并運(yùn)用啟發(fā)式算法和禁忌搜索對(duì)結(jié)果進(jìn)行優(yōu)化。以上研究通過(guò)制定相應(yīng)的規(guī)則對(duì)臨時(shí)分段的位置進(jìn)行重新選擇，雖然提高堆場(chǎng)的空間利用率，但是臨時(shí)分段可能阻礙其他分段的移動(dòng)，增加了調(diào)度難度且效率不高。申鋼等[4]以最小化臨時(shí)分段移動(dòng)量和平板車在堆場(chǎng)中的行駛距離為優(yōu)化目標(biāo)建立優(yōu)化模型，并運(yùn)用分支定界法和啟發(fā)式規(guī)則來(lái)確定分段的移動(dòng)路徑和停放位置。平板車移動(dòng)路徑中的臨時(shí)分段先移至堆場(chǎng)外暫存，待分段調(diào)度完成后再移回原來(lái)位置。徐建祥等[5]提出利用臨時(shí)場(chǎng)地用于暫時(shí)存放臨時(shí)分段并在任務(wù)結(jié)束后移回原來(lái)位置。以上研究對(duì)臨時(shí)分段都采用了重回原位的調(diào)度策略，對(duì)堆場(chǎng)空存儲(chǔ)單元并沒有充分的利用，堆場(chǎng)調(diào)度過(guò)程是一個(gè)靜態(tài)的過(guò)程，堆場(chǎng)的空間資源利用率不高。而且每一個(gè)調(diào)度任務(wù)結(jié)束后都需將暫存在堆場(chǎng)外的臨時(shí)分段移回，可能再次影響后續(xù)的調(diào)度任務(wù)。對(duì)于特殊規(guī)格分段的研究，Tao[6]考慮了超重分段的調(diào)度，當(dāng)分段重量大于平板車的額定載重時(shí)，采用兩輛平板車協(xié)同調(diào)度的方法并制定了相應(yīng)的平板車指派規(guī)則，但其研究的是船廠中車間與車間和車間與堆場(chǎng)之間的調(diào)度流程優(yōu)化，并沒有對(duì)堆場(chǎng)內(nèi)部的調(diào)度進(jìn)行細(xì)化的研究。

本文通過(guò)對(duì)臨時(shí)分段的調(diào)度過(guò)程進(jìn)行研究，提出動(dòng)態(tài)的臨時(shí)分段調(diào)度規(guī)則，并針對(duì)超長(zhǎng)分段，研究相應(yīng)的調(diào)度方法。同時(shí)還對(duì)調(diào)度時(shí)間差在規(guī)定可接受時(shí)間范圍內(nèi)的任務(wù)進(jìn)行任務(wù)合并，最終得到一個(gè)科學(xué)、合理的堆場(chǎng)調(diào)度方案，并用某船廠的實(shí)際數(shù)據(jù)對(duì)以上調(diào)度規(guī)則的合理性進(jìn)行驗(yàn)證。

1 問題描述與解決方法

1.1 問題描述

船舶分段堆場(chǎng)的調(diào)度與集裝箱堆場(chǎng)的調(diào)度[7]相似，但其屬于平面調(diào)度[8]。分段堆場(chǎng)的調(diào)度操作包括分段的存放和取回，由于平板車運(yùn)輸?shù)木窒扌訹9]，在存放和取回分段的路徑中會(huì)遇到阻擋其前進(jìn)的分段(臨時(shí)分段)，必須將這些分段移動(dòng)至平板車調(diào)度路徑之外，才能完成后續(xù)的調(diào)度工作。對(duì)于臨時(shí)分段的處理一般有移至?xí)捍鎴?chǎng)所待分段調(diào)度完成后移回原位和移至堆場(chǎng)的其他空存儲(chǔ)單元進(jìn)行存放。但這兩種方法都需要將臨時(shí)分段移出堆場(chǎng)，使得平板車的移動(dòng)距離較遠(yuǎn)、調(diào)度時(shí)間較長(zhǎng)，從而導(dǎo)致堆場(chǎng)的調(diào)度效率不高。因此需要對(duì)臨時(shí)分段的調(diào)度方法進(jìn)行優(yōu)化。

船舶設(shè)計(jì)過(guò)程中由于建造工藝要求特殊[10]，船舶艏、艉部的分段其規(guī)格與大部分常規(guī)分段有所不同，其中有部分超長(zhǎng)分段，這些分段需要占用的存儲(chǔ)單元數(shù)較多且連續(xù)，更容易成為臨時(shí)分段。因此需要根據(jù)分段的形狀特性來(lái)進(jìn)行相應(yīng)的調(diào)度。

分段堆場(chǎng)調(diào)度中每一個(gè)分段都有其相應(yīng)的調(diào)度時(shí)間，而由于堆場(chǎng)空間資源的有限性，一些調(diào)度時(shí)間較晚的分段不可避免的會(huì)存放于調(diào)度時(shí)間較早分段的移動(dòng)路徑上，成為了臨時(shí)分段。這樣在調(diào)度過(guò)程中會(huì)產(chǎn)生大量不必要的臨時(shí)分段，從而增加了堆場(chǎng)的運(yùn)作成本。

考慮到堆場(chǎng)運(yùn)作的實(shí)際情況和研究問題的方便，作了以下假設(shè)：1)船舶分段堆場(chǎng)由若干個(gè)面積相等的正方形場(chǎng)地組成，每個(gè)正方形場(chǎng)地為一個(gè)存儲(chǔ)單元；2)分段用最小包絡(luò)矩形近似；3)一個(gè)存儲(chǔ)單元只能存放一個(gè)分段；4)每個(gè)存儲(chǔ)單元能容下各種常規(guī)分段；5)超長(zhǎng)分段需要兩個(gè)相鄰的存儲(chǔ)單元進(jìn)行存放；6)調(diào)度時(shí)間差在可接受范圍內(nèi)的調(diào)度任務(wù)可以進(jìn)行任務(wù)合并；7)所有分段按“筆直型”路徑進(jìn)出堆場(chǎng)。

根據(jù)以上假設(shè)，本文擬解決的問題有：1)確定堆場(chǎng)調(diào)度計(jì)劃中所產(chǎn)生臨時(shí)分段的具體調(diào)度過(guò)程；2)調(diào)度過(guò)程中超長(zhǎng)分段的調(diào)度方案；3)對(duì)計(jì)劃調(diào)度周期內(nèi)分段的調(diào)度任務(wù)序列進(jìn)行優(yōu)化。

1.2 解決方法

本文針對(duì)以上問題，首先研究了臨時(shí)分段動(dòng)態(tài)的調(diào)度規(guī)則，對(duì)臨時(shí)分段采取移動(dòng)至相鄰的空存儲(chǔ)單元的調(diào)度方法；其次對(duì)于超長(zhǎng)分段也提出了相應(yīng)的調(diào)度規(guī)則，通過(guò)平板車的旋轉(zhuǎn)、平移等操作對(duì)超長(zhǎng)分段進(jìn)行調(diào)度；最后以臨時(shí)分段移動(dòng)距離為優(yōu)化目標(biāo)，利用以上調(diào)度規(guī)則優(yōu)化堆場(chǎng)一段調(diào)度時(shí)間內(nèi)的調(diào)度過(guò)程。本文還根據(jù)堆場(chǎng)的實(shí)際情況，對(duì)調(diào)度時(shí)間相近的任務(wù)進(jìn)行任務(wù)合并，優(yōu)化堆場(chǎng)分段調(diào)度計(jì)劃的任務(wù)序列。分段調(diào)度流程如圖1所示。

圖1 分段調(diào)度流程圖Fig.1 Block scheduling flow chart

2 建立船舶分段堆場(chǎng)調(diào)度模型

2.1 分段堆場(chǎng)存儲(chǔ)單元位置編碼

船舶分段堆場(chǎng)由若干個(gè)大小相同的正方形場(chǎng)地組成，每一個(gè)場(chǎng)地為一個(gè)存儲(chǔ)單元。存儲(chǔ)單元的位置編碼方式為臨近道路的位置開始從左至右，從上至下依次編碼，如圖2所示，堆場(chǎng)被劃分成M行N列，即堆場(chǎng)有M×N個(gè)存儲(chǔ)單元，存儲(chǔ)單元位置編碼從1至M×N。

圖2 存儲(chǔ)單元位置編碼Fig.2 Position coding of storage unit

2.2 堆場(chǎng)狀態(tài)二進(jìn)制矩陣

為了表示分段在堆場(chǎng)中的停放位置及堆場(chǎng)存儲(chǔ)單元的狀態(tài)，建立堆場(chǎng)狀態(tài)二進(jìn)制矩陣。矩陣Ht的每個(gè)元素bVi表示調(diào)度時(shí)刻t堆場(chǎng)中存儲(chǔ)單元位置為Vi的狀態(tài)，bVi=1表示存儲(chǔ)單元內(nèi)已有分段存放，bVi=0表示該時(shí)刻存儲(chǔ)單元狀態(tài)為空。

2.3 堆場(chǎng)狀態(tài)的更新

2.4 堆場(chǎng)調(diào)度模型

模型中的符號(hào)如下：

M、N分別表示堆場(chǎng)在寬度和長(zhǎng)度上被劃分的存儲(chǔ)單元數(shù)量，堆場(chǎng)中存儲(chǔ)單元的總數(shù)為M×N；

D：堆場(chǎng)存儲(chǔ)單元的規(guī)格D×D；

W：堆場(chǎng)至?xí)捍娑褕?chǎng)的距離；

(Lg，Wg)：分段g的幾何投影參數(shù)，其中g(shù)∈R；

T：堆場(chǎng)的調(diào)度周期；

ts：調(diào)度周期T的開始時(shí)間；

te：調(diào)度周期T的結(jié)束時(shí)間；

Vi：分段i在堆場(chǎng)中的位置；

tRi：分段Ri的調(diào)度時(shí)間；

決策變量：

目標(biāo)函數(shù)：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

目標(biāo)函數(shù)(1)根據(jù)不同規(guī)格的分段計(jì)算出堆場(chǎng)每次調(diào)度時(shí)臨時(shí)分段的移動(dòng)距離，并利用所對(duì)應(yīng)的調(diào)度規(guī)則選擇每個(gè)臨時(shí)分段的最優(yōu)調(diào)度方法，使整個(gè)調(diào)度周期內(nèi)，對(duì)于臨時(shí)分段平板車的移動(dòng)距離最小。同時(shí)，根據(jù)任務(wù)合并的規(guī)則，對(duì)整個(gè)調(diào)度計(jì)劃內(nèi)的任務(wù)調(diào)度序列進(jìn)行優(yōu)化。

約束(2)限制堆場(chǎng)每次只能執(zhí)行一個(gè)調(diào)度任務(wù)；約束(3)限定臨時(shí)分段與調(diào)度分段之間的相互位置關(guān)系；約束(4)表示超長(zhǎng)分段的尺寸與存儲(chǔ)單元大小的關(guān)系；約束(5)、(6)規(guī)定了不同規(guī)格類型的分段所分配的存儲(chǔ)單元個(gè)數(shù)，即常規(guī)分段分配一個(gè)確定的存儲(chǔ)單元，超長(zhǎng)分段需要兩個(gè)相鄰的存儲(chǔ)單元才能滿足其存放空間需求。約束(7)確保分段的調(diào)度時(shí)間在規(guī)定的調(diào)度周期內(nèi)。

3 基于啟發(fā)式規(guī)則的堆場(chǎng)調(diào)度模型求解

3.1 臨時(shí)分段動(dòng)態(tài)調(diào)度規(guī)則

現(xiàn)有堆場(chǎng)調(diào)度對(duì)于臨時(shí)分段的處理一般將其移至堆場(chǎng)外的暫存堆場(chǎng)，等調(diào)度結(jié)束后再將分段移回原位。這樣的調(diào)度方法不僅平板車移動(dòng)距離遠(yuǎn)，而且占用堆場(chǎng)以外的其他資源。將臨時(shí)分段重新選位能有效的提高對(duì)堆場(chǎng)資源的利用率，但是該調(diào)度方法較為繁雜。因此，本文對(duì)臨時(shí)分段采取動(dòng)態(tài)的調(diào)度規(guī)則，即利用臨時(shí)分段相鄰的空存儲(chǔ)單元進(jìn)行合理調(diào)度。

圖3 臨時(shí)分段調(diào)度規(guī)則Fig.3 Scheduling rule of the obstructive blocks

3.2 超長(zhǎng)分段調(diào)度規(guī)則

對(duì)于超長(zhǎng)分段的存放位置VSi作以下規(guī)定：若超長(zhǎng)分段Si平行于道路存放(pSi=1)，那么該分段的存放位置用分段左端所占的存儲(chǔ)單元位置表示；若超長(zhǎng)分段Si垂直于道路存放(pSi=0)，則該分段的存放位置用分段上端所占的存儲(chǔ)單元位置表示。

平板車在堆場(chǎng)中除了平移，還可以通過(guò)旋轉(zhuǎn)操作將超長(zhǎng)分段以O(shè)Si為中心進(jìn)行旋轉(zhuǎn)，從而完成后面存儲(chǔ)單元上存放分段的調(diào)度任務(wù)。若分段調(diào)度路徑中存在超長(zhǎng)分段，即臨時(shí)分段為超長(zhǎng)分段的情況，為此提出以下調(diào)度規(guī)則：

5)超長(zhǎng)分段垂直于道路存放，即pSi=0，則按照常規(guī)分段的調(diào)度規(guī)則對(duì)其進(jìn)行調(diào)度。

圖4 超長(zhǎng)分段調(diào)度方法Fig.4 Scheduling method of the ultra-long blocks

3.3 任務(wù)合并規(guī)則

在堆場(chǎng)中兩分段Ri與Rj，若在調(diào)度中存在以下關(guān)系：分段Rj在分段Ri的移動(dòng)路徑上，且分段Ri的調(diào)度時(shí)間早于分段Rj。這樣分段Rj便成為了臨時(shí)分段，需要利用平板車將其移動(dòng)至其他位置來(lái)完成對(duì)分段Ri的調(diào)度。但若這兩個(gè)調(diào)度分段的調(diào)度時(shí)間差在一個(gè)可以接受的時(shí)間范圍δ內(nèi)，便可以將這兩個(gè)調(diào)度任務(wù)合并，即忽略兩者的調(diào)度時(shí)間順序，根據(jù)它們的存放位置關(guān)系依次進(jìn)行調(diào)度。如圖5所示。

圖5 任務(wù)合并示例Fig.5 Task merging sample

(8)

(9)

(10)

(11)

式(8)表示兩調(diào)度分段之間的時(shí)間約束關(guān)系；式(9)、(10)說(shuō)明了兩調(diào)度分段之間的位置關(guān)系；式(11)限定兩個(gè)任務(wù)合并的分段的調(diào)度時(shí)間差必須在δ內(nèi)，否則兩個(gè)任務(wù)不能合并。滿足以上條件的任務(wù)可以進(jìn)行合并，即taski=taskj。

4 實(shí)例驗(yàn)證與結(jié)果分析

4.1 實(shí)驗(yàn)驗(yàn)證與結(jié)果

為了驗(yàn)證本文調(diào)度模型以及規(guī)則的可行性與正確性，以上海某大型船廠調(diào)度周期內(nèi)一段時(shí)間的分段調(diào)度為例，利用MicrosoftVisualStudio2010軟件，在處理器為2.40GHz，內(nèi)存為4GB的計(jì)算機(jī)上進(jìn)行求解。實(shí)驗(yàn)包括以下輸入?yún)?shù)：1)堆場(chǎng)調(diào)度前的二進(jìn)制狀態(tài)矩陣；2)60h內(nèi)所需調(diào)度的分段及其具體調(diào)度時(shí)間(表1)；3)堆場(chǎng)調(diào)度允許任務(wù)合并的最大時(shí)間差δ=3h。某堆場(chǎng)調(diào)度前的狀態(tài)如圖6所示，堆場(chǎng)的參數(shù)為M=6，N=10，即堆場(chǎng)由60個(gè)存儲(chǔ)單元構(gòu)成，初始負(fù)載率為65%，Bx是已存放在堆場(chǎng)存儲(chǔ)單元上分段的編號(hào)。

按照調(diào)度時(shí)間順序排列的調(diào)度計(jì)劃如表1所示，調(diào)度分段的數(shù)量為30個(gè)，其中進(jìn)場(chǎng)分段13個(gè)(常規(guī)分段用A1至A10依次編號(hào)，超長(zhǎng)分段用S1至S3編號(hào))，出場(chǎng)分段17個(gè)(用Bx表示)，為了便于區(qū)分，調(diào)度過(guò)程中遇到的臨時(shí)分段用Bx表示。

通過(guò)算法程序確定調(diào)度分段進(jìn)出堆場(chǎng)時(shí)所產(chǎn)生的臨時(shí)分段，用本文研究的調(diào)度規(guī)則對(duì)臨時(shí)分段、超長(zhǎng)分段的具體調(diào)度過(guò)程進(jìn)行優(yōu)化，同時(shí)將任務(wù)合并的規(guī)則運(yùn)用到調(diào)度中，得到一種較優(yōu)的堆場(chǎng)臨時(shí)分段調(diào)度方案，如表2所示，其中陰影部分表示任務(wù)進(jìn)行了合并，任務(wù)合并減少的臨時(shí)分段由△表示。若取D=15m、W=10m，該調(diào)度方案的臨時(shí)分段移動(dòng)距離為656.3m，其中平板車對(duì)超長(zhǎng)臨時(shí)分段進(jìn)行了3次旋轉(zhuǎn)調(diào)度操作，采用任務(wù)合并后臨時(shí)分段數(shù)量減少了9個(gè)。

圖6 堆場(chǎng)初始狀態(tài)Fig.6 Stockyard initial state

表1 堆場(chǎng)調(diào)度計(jì)劃

表2 堆場(chǎng)調(diào)度方案

4.2 數(shù)值分析

4.2.1 任務(wù)合并對(duì)減少臨時(shí)分段的影響

任務(wù)合并可以有效的減少調(diào)度過(guò)程中臨時(shí)分段的數(shù)量，而且任務(wù)允許任務(wù)合并的最大時(shí)間差δ和調(diào)度分段的數(shù)量都會(huì)影響最終的優(yōu)化效果。為了比較不同參數(shù)下任務(wù)合并對(duì)減少臨時(shí)分段的影響，在δ為2、3、4、5 h，調(diào)度規(guī)模分別為60、80、100個(gè)分段的參數(shù)下共進(jìn)行了12組試驗(yàn)，其中各個(gè)分段的調(diào)度時(shí)間由[0,60 h]隨機(jī)生成。為了保證更好的試驗(yàn)效果，對(duì)每組試驗(yàn)進(jìn)行5次，并取平均值。

圖7 任務(wù)合并試驗(yàn)結(jié)果Fig.7 Test results of task-merging

試驗(yàn)結(jié)果如圖7所示，通過(guò)對(duì)堆場(chǎng)調(diào)度過(guò)程進(jìn)行合理的任務(wù)合并，可以有效的減少調(diào)度過(guò)程中臨時(shí)分段的調(diào)度數(shù)量。隨著可接受任務(wù)合并時(shí)間差δ從2 h逐漸增加至5 h，臨時(shí)分段的減少百分比也相應(yīng)的增加，而且相同的調(diào)度周期內(nèi)，任務(wù)數(shù)量越多，任務(wù)合并的效果也約為明顯。但任務(wù)合并使一段時(shí)間內(nèi)同時(shí)出場(chǎng)的分段數(shù)量增多，受后續(xù)工序的空間資源的制約，若δ值過(guò)大，例如δ=8 h時(shí)，一段時(shí)間內(nèi)由于任務(wù)合并造成的同時(shí)出場(chǎng)分段的最大數(shù)量為5個(gè)，因此會(huì)引發(fā)場(chǎng)地堵塞等問題。

4.2.2 堆場(chǎng)存儲(chǔ)單元空置率e

在一定的調(diào)度周期內(nèi)，堆場(chǎng)中一些存儲(chǔ)單元始終處于空置狀態(tài)，使得堆場(chǎng)的空間資源利用率不高，因此通過(guò)堆場(chǎng)存儲(chǔ)單元空置率可以反映出調(diào)度規(guī)則對(duì)堆場(chǎng)空間資源的利用情況，一個(gè)合理、高效的調(diào)度計(jì)劃會(huì)對(duì)堆場(chǎng)的存儲(chǔ)空間充分的利用。給出空置率的定義為

式中：Nume表示調(diào)度周期內(nèi)堆場(chǎng)中始終沒有被用于存儲(chǔ)分段的存儲(chǔ)單元個(gè)數(shù)，M、N分別表示堆場(chǎng)的行數(shù)和列數(shù)。

為了比較不同調(diào)度規(guī)則和不同規(guī)模(40、50、60個(gè)分段)對(duì)存儲(chǔ)單元空置率影響，在堆場(chǎng)規(guī)格為6×10，初始負(fù)載率為65%的堆場(chǎng)中，分別運(yùn)用不同的調(diào)度規(guī)則進(jìn)行試驗(yàn)，得到結(jié)果如圖8所示，可以看出制定的動(dòng)態(tài)調(diào)度規(guī)則對(duì)于降低堆場(chǎng)空置率有一定的效果，且隨著調(diào)度規(guī)模的增加，效果更佳。雖然采用該調(diào)度規(guī)則空置率高于重新選位調(diào)度規(guī)則(位置隨機(jī)選擇)時(shí)的空置率，但是臨時(shí)分段采用重新選位的調(diào)度規(guī)則，會(huì)增加平板車的運(yùn)輸距離，增加了調(diào)度計(jì)劃的復(fù)雜度。因此該調(diào)度規(guī)則對(duì)于降低堆場(chǎng)存儲(chǔ)單元空置率，提高堆場(chǎng)空間資源利用率有一定的效果。

臨時(shí)分段動(dòng)態(tài)調(diào)度規(guī)則在不同堆場(chǎng)初始負(fù)載率時(shí)的調(diào)度效果也有所不同，因此試驗(yàn)比較了不同初始負(fù)載率下(60%、70%、80%、90%)采用動(dòng)態(tài)調(diào)度規(guī)則相比于移出暫存規(guī)則堆場(chǎng)空置率e的優(yōu)化幅度。試驗(yàn)的其他輸入?yún)?shù)為：1)調(diào)度規(guī)模：50個(gè)分段；2)M=6，N=10。

圖8 堆場(chǎng)空置率試驗(yàn)結(jié)果Fig.8 Test results of Nume

對(duì)比結(jié)果如圖9所示，在堆場(chǎng)初始負(fù)載率較低時(shí)(60%、70%、80%)動(dòng)態(tài)調(diào)度規(guī)則相比于將臨時(shí)分段移出堆場(chǎng)暫存待分段調(diào)度完成后移回堆場(chǎng)的調(diào)度方式對(duì)堆場(chǎng)存儲(chǔ)單元空置率的優(yōu)化效果較為明顯。但堆場(chǎng)負(fù)載率較高時(shí)(90%)，本文的調(diào)度規(guī)則優(yōu)化效果則不明顯，原因是該調(diào)度規(guī)則需要利用堆場(chǎng)中閑置的存儲(chǔ)單元，一旦堆場(chǎng)的負(fù)載率過(guò)高，堆場(chǎng)中空存儲(chǔ)單元數(shù)量也相應(yīng)減少，這樣也就無(wú)法發(fā)揮動(dòng)態(tài)調(diào)度的優(yōu)勢(shì)。

圖9 空置率優(yōu)化幅度Fig.9 Optimization effect of Nume

4.2.3 調(diào)度規(guī)則對(duì)比

臨時(shí)分段的移動(dòng)量是評(píng)價(jià)堆場(chǎng)調(diào)度方案優(yōu)劣的標(biāo)準(zhǔn)，對(duì)于臨時(shí)分段的處理一般有：1)移出堆場(chǎng)暫存；2)重新選位。本文采用動(dòng)態(tài)的調(diào)度規(guī)則，將臨時(shí)分段移動(dòng)至相鄰的存儲(chǔ)單元進(jìn)行存儲(chǔ)。如圖10所示，臨時(shí)分段的移動(dòng)距離相比于其他調(diào)度規(guī)則有所下降，而且隨著調(diào)度分段數(shù)量的增加，該調(diào)度規(guī)則的優(yōu)勢(shì)也更加的明顯。

圖10 不同調(diào)度規(guī)則對(duì)比Fig.10 Comparison of different scheduling rule

4 結(jié)論

本文通過(guò)對(duì)船舶分段堆場(chǎng)的調(diào)度過(guò)程進(jìn)行研究，得出以下結(jié)論：

1)通過(guò)對(duì)堆場(chǎng)調(diào)度過(guò)程進(jìn)行合理的任務(wù)合并，可以有效地減少調(diào)度過(guò)程中臨時(shí)分段的調(diào)度數(shù)量；

2)在較低的堆場(chǎng)初始負(fù)載率時(shí)本文的調(diào)度規(guī)則對(duì)堆場(chǎng)存儲(chǔ)單元空置率的優(yōu)化效果較為明顯；

3)本文將臨時(shí)分段移動(dòng)至相鄰的存儲(chǔ)單元進(jìn)行存儲(chǔ)，在調(diào)度規(guī)模較大時(shí)，優(yōu)勢(shì)更為明顯。

[1]PARK C, SEO J. Comparing heuristic algorithms of the planar storage location assignment problem[J]. Transportation research part E: logistics and transportation review, 2010, 46(1): 171-185.

[2]PARK C, SEO J. Mathematical modeling and solving procedure

of the planar storage location assignment problem[J]. Computers & industrial engineering, 2009, 57(3): 1062-1071.

[3]TAO Ningrong, JIANG Zuhua, QU Shipeng. Assembly block location and sequencing for flat transporters in a planar sto-rage yard of shipyards[J]. International journal of production research, 2013, 51(14): 4289-4301.

[4]張志英, 申鋼, 劉祥瑞. 基于最短路算法的船舶分段堆場(chǎng)調(diào)度[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2012, 18(9): 1982-1990.

ZHANG Zhiying, SHEN Gang, LIU Xiangrui. Block storage yard scheduling of shipbuilding based on shortest-path algorithm[J]. Computer integrated manufacturing systems, 2012, 18(9): 1982-1990.

[5]張志英, 徐建祥, 計(jì)峰. 基于遺傳算法的船舶分段堆場(chǎng)調(diào)度研究[J]. 上海交通大學(xué)學(xué)報(bào), 2013, 47(7): 1036-1042.

ZHANG Zhiying, XU Jianxiang, JI Feng. Shipbuilding yard scheduling approach based on genetic algorithm[J]. Journal of Shanghai Jiao Tong University, 2013, 47(7): 1036-1042.

[6]陶寧蓉. 船舶分段建造過(guò)程中的資源調(diào)度優(yōu)化研究[D]. 上海: 上海交通大學(xué), 2013.

TAO Ningrong. Research on resouce scheduling problems during ship block assembly process[D]. Shanghai: Shanghai Jiaotong University, 2013.

[7]BAZZAZI M, SAFAEI N, JAVADIAN N. A genetic algorithm to solve the storage space allocation problem in a container terminal[J]. Computers & industrial engineering, 2009, 56(1): 44-52.

[8]PARK C, SEO J. Genetic algorithm of the planar storage location assignment problem[J]. Journal of the Korean institute of industrial engineers, 2009, 35(2): 129-140.

[9]ROH M I, CHA J H. A block transportation scheduling system considering a minimisation of travel distance without loading of and interference between multiple transporters[J]. International journal of production research, 2011, 49(11): 3231-3250.

[10]BANERJEE S K. Shipyard production systems design: a statistical approach[J]. International journal of production research, 1979, 17(6): 541-555.

Obstructive block stockyard scheduling and optimization based on heuristic rules

ZHANG Zhiying，ZENG Jianzhi

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

The scheduling scheme of the obstructive blocks in the shipyard determined the efficiency and the cost of the stockyard scheduling operations. This paper took the scheduling process of the obstructive blocks as an optimization object. A mathematical model was established with the aim of minimizing the moving distance of the flat transporter. A dynamic scheduling rule for the obstructive blocks and the ultra-long blocks were proposed to make full use of the empty storage units, and which can ultimately obtain an optimal scheduling of the obstructive blocks. Meanwhile task-merging was used to optimize the sequence of the stockyard scheduling, thereby reducing the number of obstructive blocks during the scheduling process. Application data were acquired from a shipyard to validate the model and the scheduling rules, and the results showed that the proposed rules were effective to obtain a better stockyard scheduling scheme, and also improved the utilization of the space resource and scheduling efficiency.

stockyard; scheduling rules; ultra-long blocks; task-merging; heuristic rules

2015-08-06.

日期：2016-08-29.

國(guó)家自然科學(xué)基金項(xiàng)目(70872076)；上海市科技創(chuàng)新行動(dòng)計(jì)劃項(xiàng)目(11dz1121803).

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

張志英，E-mail：zyzhang08@#edu.cn.

10.11990/jheu.201508010

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20160829.1421.032.html

O224；U673

A

1006-7043(2016)10-1416-08

張志英,曾建智. 基于啟發(fā)式規(guī)則的臨時(shí)分段調(diào)度計(jì)劃與優(yōu)化[J]. 哈爾濱工程大學(xué)學(xué)報(bào)， 2016, 37(10): 1416-1423.

ZHANG Zhiying，ZENG Jianzhi. Obstructive block stockyard scheduling and optimization based on heuristic rules[J]. Journal of Harbin Engineering University, 2016, 37(10): 1416-1423.