非標準HFS－B問題的設備協同調度研究＊

張 煜 匡家喜 李文鋒 容芷君

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

0 引 言

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

圖1 采用邊裝邊卸工藝的集裝箱作業系統

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

非標準HFS－B環境內的港口設備調度問題研究，需要綜合考慮設備之間的工作量均衡、箱流的平穩流暢，以上都離不開非標準HFS－B環境內不同階段之間設備協同能力的研究，即非標準HFS－B問題的設備協同研究.由于標準的HFS－B問題屬于NP－hard，精確算法難于求解大規模實際案例，因而啟發式算法、元啟發式算法被廣泛用于實際生產環境中HFS－B問題的求解.本文的研究內容是構建快速高效的3階段決策的啟發式算法，求解這類非標準HFS－B環境下的實際大規模案例，以提高設備之間的協同能力.

1 啟發式算法

1.1 堆場空間決策

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

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

1.2 任務分配決策

任務分配決策可以描述為：有n個集裝箱作業任務（主要涉及前沿操作、水平輸送、堆場操作等環節的作業任務）和m個設備（主要涉及岸橋、集卡、場橋）；任意設備i的最大加工能力，即設備i最多可處理的裝卸任務數，記為bi，TEU；如果將任務j分配給設備i，記xij＝1，同時產生費用或成本cij；當裝卸任務j對應的集裝箱為20或40英尺箱，rij分別取值1或2TEU；決策的目標是如何分配任務給設備，使總成本最小（成本可以是時間、距離、費用等）.該類問題的數學模型可以表示為

目標函數（4）要求總的成本最小；約束（5）保證任意設備加工的工件數不能超過其加工能力；約束（6）保證任意任務都能被唯一分配給某臺設備；約束（7）保證xij為0－1變量.對于此類任務分配問題，Robert M.Nauss指出其為NP－hard問題［9］，很難在多次項時間內獲得其最優解.

1.3 設備調度決策

通過分析設備的順序約束和協同關系（見圖2），利用仿真時間的變化和事件的觸發，對設備的狀態空間進行更新.基于以上狀態的轉移和當前時刻，確定設備處理當前任務的開始和結束時間，以及當前工件離開該設備的時間.

圖2 設備的順序約束和協同關系

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

1.4 3階段啟發式算法

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

圖3 三階段決策的啟發式算法

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

任務分配決策采用基于庫存和配額的表調度理論，核心思想是：將當前可得任務按FIFO策略排序和構建任務表單Ltask，將當前空閑設備按庫存非減和配額非增進行排序和構建設備表單Le，實現兩個表單元素的一一配對，當任意表單為空，算法結束.

2 仿真實驗

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

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

表1 案例

圖4 仿真結果

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

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

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

3 結束語

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

［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.