張 煜 匡家喜 李文鋒 容芷君

（武漢理工大學(xué)物流工程學(xué)院1） 武漢 430063） （武漢科技大學(xué)汽車與交通工程學(xué)院2） 武漢 430081）

0 引 言

傳統(tǒng)集裝箱裝卸系統(tǒng)中的設(shè)備調(diào)度問題，可以描述為帶阻塞的混合流水車間（hybrid flow shop problem with blocking，HFS－B）問題［1－2］：在任意時空，系統(tǒng)中僅存在一種箱流，箱流中的任意集裝箱都經(jīng)歷相同的3個階段；各個階段都對應(yīng)一個并行機(jī)集合；相鄰階段之間無緩沖區(qū)；集裝箱在每個階段的操作，都對應(yīng)一個處理時間.這種標(biāo)準(zhǔn)的 HFS－B 問題，廣泛存在于電子制造［3］、鋼鐵［4］、紡織［5］、港口［6］等流程工業(yè)中.

圖1 采用邊裝邊卸工藝的集裝箱作業(yè)系統(tǒng)

目前，采用同貝位邊裝邊卸（dual－cycle或double－cycling）工藝的港口集裝箱裝卸系統(tǒng)［7］，如圖1所示，有別于傳統(tǒng)的集裝箱裝卸系統(tǒng)，體現(xiàn)為2種流程互逆的箱流（進(jìn)口和出口箱流）同時存在，這類系統(tǒng)內(nèi)的設(shè)備調(diào)度問題可以被描述為非標(biāo)準(zhǔn)的 HFS－B問題或Bidirectional FSP（BiFSP）問題［8］，其主要特征為：系統(tǒng)中同時存在2種流向互逆的工件流；同流向的工件，都經(jīng)歷3個相同的階段，相鄰階段無緩沖區(qū)；第2階段設(shè)備的準(zhǔn)備和處理時間不是預(yù)先可知的，與設(shè)備當(dāng)前工件的緊前和緊后操作的機(jī)器位置相關(guān).

非標(biāo)準(zhǔn)HFS－B環(huán)境內(nèi)的港口設(shè)備調(diào)度問題研究，需要綜合考慮設(shè)備之間的工作量均衡、箱流的平穩(wěn)流暢，以上都離不開非標(biāo)準(zhǔn)HFS－B環(huán)境內(nèi)不同階段之間設(shè)備協(xié)同能力的研究，即非標(biāo)準(zhǔn)HFS－B問題的設(shè)備協(xié)同研究.由于標(biāo)準(zhǔn)的HFS－B問題屬于NP－h(huán)ard，精確算法難于求解大規(guī)模實際案例，因而啟發(fā)式算法、元啟發(fā)式算法被廣泛用于實際生產(chǎn)環(huán)境中HFS－B問題的求解.本文的研究內(nèi)容是構(gòu)建快速高效的3階段決策的啟發(fā)式算法，求解這類非標(biāo)準(zhǔn)HFS－B環(huán)境下的實際大規(guī)模案例，以提高設(shè)備之間的協(xié)同能力.

1 啟發(fā)式算法

1.1 堆場空間決策

該決策子問題可以描述為不平衡運輸和分配問題.以進(jìn)口箱為例，已知有m個岸橋，進(jìn)口箱堆區(qū)有n個區(qū)塊，第i個岸橋需要執(zhí)行的進(jìn)口箱任務(wù)為ai（i＝1，2，…，m），第j個區(qū)塊能夠接收的箱量為bj（j＝1，2，…，n），從第i個 QC到第j個區(qū)塊的最短水平輸送時間為tij，則如何確定任意區(qū)塊j從任意岸橋i接收的進(jìn)口箱量xij，使總水平輸送時間最短.該類問題的數(shù)學(xué)模型為

目標(biāo)函數(shù)（1）要求總的水平運輸時間最短；約束（2）對應(yīng)流平衡約束，保證任意岸橋需要執(zhí)行的進(jìn)口箱任務(wù)都能被分配給集卡，執(zhí)行運輸任務(wù)；約束（3）對應(yīng)能力約束，保證任意區(qū)塊或區(qū)段（block）接收的進(jìn)口箱量不能溢出.該數(shù)學(xué)模型為線性方程，變量數(shù)為m×n個，當(dāng)碼頭規(guī)模較大時（例如：4個泊位，24個QC，48個進(jìn)口區(qū)塊），變量數(shù)通常上千，很難在較短時間實現(xiàn)問題的精確求解.

1.2 任務(wù)分配決策

任務(wù)分配決策可以描述為：有n個集裝箱作業(yè)任務(wù)（主要涉及前沿操作、水平輸送、堆場操作等環(huán)節(jié)的作業(yè)任務(wù)）和m個設(shè)備（主要涉及岸橋、集卡、場橋）；任意設(shè)備i的最大加工能力，即設(shè)備i最多可處理的裝卸任務(wù)數(shù)，記為bi，TEU；如果將任務(wù)j分配給設(shè)備i，記xij＝1，同時產(chǎn)生費用或成本cij；當(dāng)裝卸任務(wù)j對應(yīng)的集裝箱為20或40英尺箱，rij分別取值1或2TEU；決策的目標(biāo)是如何分配任務(wù)給設(shè)備，使總成本最?。ǔ杀究梢允菚r間、距離、費用等）.該類問題的數(shù)學(xué)模型可以表示為

目標(biāo)函數(shù)（4）要求總的成本最??；約束（5）保證任意設(shè)備加工的工件數(shù)不能超過其加工能力；約束（6）保證任意任務(wù)都能被唯一分配給某臺設(shè)備；約束（7）保證xij為0－1變量.對于此類任務(wù)分配問題，Robert M.Nauss指出其為NP－h(huán)ard問題［9］，很難在多次項時間內(nèi)獲得其最優(yōu)解.

1.3 設(shè)備調(diào)度決策

通過分析設(shè)備的順序約束和協(xié)同關(guān)系（見圖2），利用仿真時間的變化和事件的觸發(fā)，對設(shè)備的狀態(tài)空間進(jìn)行更新.基于以上狀態(tài)的轉(zhuǎn)移和當(dāng)前時刻，確定設(shè)備處理當(dāng)前任務(wù)的開始和結(jié)束時間，以及當(dāng)前工件離開該設(shè)備的時間.

圖2 設(shè)備的順序約束和協(xié)同關(guān)系

圖2 中，YT1，YC1，QC分別表示集卡、場橋、岸橋等設(shè)備；括號中的內(nèi)容表示設(shè)備的狀態(tài)；箭頭表示順序約束和協(xié)同關(guān)系；集卡的S1、S3，S4，S5，S7，S8，S9分別表示空閑、前沿空車排隊、重車前往堆場、堆場重車排隊、空車前往堆場、堆場空車排隊、重車前往前沿、前沿重車排隊等狀態(tài)；場橋的S1，S4，S6，S8，S9分別表示空閑、提取集裝箱、裝車、卸車、堆碼集裝箱等狀態(tài)；岸橋的S1，S3，S5，S7，S8分別表示空閑、卸船、裝車、卸車、裝船等狀態(tài).

1.4 3階段啟發(fā)式算法

結(jié)合以上決策子問題描述和策略，圖3給出了3階段決策的啟發(fā)式算法.圖中，集合D表示空閑和即將空閑的集卡集合，通過集卡的工作狀態(tài)進(jìn)行判別；Si＝S0表示當(dāng)前工班的集卡是否全部都為非激活狀態(tài)的集卡，用于判別算法是否結(jié)束；算法主要有堆場空間決策、任務(wù)分配決策和設(shè)備調(diào)度決策等內(nèi)容組成，詳細(xì)描述如下.

圖3 三階段決策的啟發(fā)式算法

堆場空間決策采用基于Fill ratio的啟發(fā)式算法，核心思想是：堆場各區(qū)塊（block）的fill ratio大致均衡，這意味著可以均衡分配工作量，從而避免局部的交通堵塞，因此就可以將港口路網(wǎng)的不平衡運輸和分配問題轉(zhuǎn)化為Fill ratio的均衡問題，從而大大降低了變量數(shù)和運算的復(fù)雜度.此處，任意區(qū)塊i的Fill ratio用fi表示，＝（ai＋xi）／A.式中：ai，xi，A分別為區(qū)塊i的初始箱量、區(qū)塊i的配額、區(qū)塊的最大容量；xi為決策變量，其他為已知量.

任務(wù)分配決策采用基于庫存和配額的表調(diào)度理論，核心思想是：將當(dāng)前可得任務(wù)按FIFO策略排序和構(gòu)建任務(wù)表單Ltask，將當(dāng)前空閑設(shè)備按庫存非減和配額非增進(jìn)行排序和構(gòu)建設(shè)備表單Le，實現(xiàn)兩個表單元素的一一配對，當(dāng)任意表單為空，算法結(jié)束.

2 仿真實驗

假設(shè)：某集裝箱碼頭分為進(jìn)、出口堆場；前沿、陸域長度皆為1 000m；岸橋、場橋、集卡等設(shè)備的基本參數(shù)分別設(shè)置為48moves／h，20moves／h，30 km／h（空車）或20km／h（重車）；岸橋和場橋的處理時間服從正態(tài)分布，均值采用以上基本參數(shù).

構(gòu)建4個案例，見表1.每個案例仿真20次，置信區(qū)間為90%，主要實驗結(jié)果見圖4.以上案例的CPU時間都小于2s.

表1 案例

圖4 仿真結(jié)果

圖4 中，橫坐標(biāo)對應(yīng)當(dāng)前工班的集卡數(shù)量，左邊的縱坐標(biāo)對應(yīng)makespan時間，右邊縱坐標(biāo)對應(yīng)Gap；C，L，Gap分別為啟發(fā)式算法獲得的makespan時間、makespan時間的理論下界、（CL）／L；理論下界L采用了基于階段的下界理論［10］和基于 makespan的下界理論［11］，取兩者的最大值.

圖4中，每個案例下的C和L曲線都對應(yīng)一個折點（knee point－KP），說明：（1）在 KP左側(cè)，提高集卡數(shù)量能夠顯著降低makespan時間；（2）在KP右側(cè)，提高集卡數(shù)量不能顯著降低makespan時間.以上揭示了合理的當(dāng)前工班集卡數(shù)量在KP附近，也反映了當(dāng)前工班的集卡數(shù)量與系統(tǒng)的makespan之間的關(guān)系.

基于以上結(jié)論，可知KP附近的最大Gap是小于4%.因而，根據(jù)Gap特性的分析，能夠揭示：（1）本文開發(fā)的算法具有較好的特性；（2）通過合理選擇當(dāng)前工班的集卡數(shù)量，能夠避開最差的情形.

3 結(jié)束語

從采用dual－cycle工藝的集裝箱裝卸系統(tǒng)中提煉了一種非標(biāo)準(zhǔn)的HFS－B問題，該問題具有以下特點：具有互逆的2種工件流，某些階段機(jī)器的處理時間和準(zhǔn)備時間不預(yù)先可知，無緩沖區(qū)等.該問題的NP－h(huán)ard特性，促使我們開發(fā)了3階段決策的啟發(fā)式算法，對這類實際背景下的HFS－B問題進(jìn)行求解.大量實驗仿真數(shù)據(jù)表明：（1）開發(fā)的算法能夠在2s內(nèi)求解本文所提供的大規(guī)模場景案例；（2）算法的最大Gap不大于7%；（3）仿真結(jié)果表明合理的工班集卡數(shù)量處于knee point附近；（4）當(dāng)取knee point附近的集卡數(shù)量作為當(dāng)前工班的集卡數(shù)，最大Gap不大于4%.綜上，本文所開發(fā)的3階段啟發(fā)式算法具有快速高效的性能，特別適合百萬噸海港設(shè)備的協(xié)同調(diào)度.

［1］Ruiz R，JoséAntonio Vázquez－Rodríguez.The hybrid flow shop scheduling problem［J］.European Journal of Operational Research，2010，205 （1）：1－18.

［2］Chen L，Bostel N，Dejax P，et al.A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal［J］.European Journal of Operational Research，2007，181（1）：40－58.

［3］Choi Hyunseon，Kim Hyungwon，Lee Dongho，et al.Scheduling algorithms for two－stage reentrant hybrid flow shops：minimizing makespan under the maximum allowable due dates［J］.The International Journal of Advanced Manufacturing Technology，2009，42（9－10）：963－973.

［4］Atighehchian A，Bijari M，Tarkesh H.A novel hybrid algorithm for scheduling steel－making continuous casting production［J］.Computers ＆ Operations Research，2009，36（8）：2 450－2 461.

［5］Montoya－Torres J R，Vargas N F.Solving a bi－crite－ria hybrid flowshop scheduling problem occurring in apparel manufacturing［J］.International Journal of Information Systems and Supply Chain Management，2011，4（2）：42－60.

［6］Zeng Qingcheng，Yang Zhongzhen.Integrating simulation and optimization to schedule loading operations in container terminals［J］.Computers ＆Operations Research，2009，36（6）：1 935－1 944.

［7］Goodchild A V，Daganzo C F.Double－cycling strategies for container ships and their effect on ship loading and unloading operations［J］.Transportation Science，2006，40（4），473－483.

［8］ZhengYi，John Zhao，Hoong Chuinlau，et al.Integrated resource allocation and scheduling in a bidirectional flowshop with multimachine and COS constraints［J］.IEEE Transactions on Systems，Man，and Cybernetics－Part C，2009，39（2）：190－200.

［9］Nauss R M.Solving the generalized assignment problem：an optimizing and heuristic approach［J］.INFORMS Journal on Computing，2003，15（3）：249－266.

［10］Santos D L，Hunsucker J L，Deal D E.Global lower bounds for flow shops with multiple processors［J］.European Journal of Operational Research，1995，80（1）：112－120.

［11］Bish E K.A multiple－crane－constrained scheduling problem in a container terminal［J］.European Journal of Operational Research，2003，144（1）：83－107.