集裝箱作業系統一體化調度研究綜述＊

張 煜 李文鋒 嚴新平

(武漢理工大學物流工程學院1) 武漢 430063)

(武漢理工大學智能運輸系統研究中心2) 武漢 430063)

集裝箱作業系統,尤其是岸邊采用新型雙40 ft岸橋的集裝箱復雜作業系統,資源(例如岸橋、場橋、集卡)是同步和交互式的合作和協調,運作的管理模式是自主和分散的,作業環節間的資源協同和調度是相互耦合和制約的.以上決定了集裝箱作業系統的生產組織和調度是十分困難和復雜的.本文從集裝箱作業系統一體化調度的國內外研究綜述層面出發,探討相關技術方法的優劣,為集裝箱作業系統一體化調度的研究提供支持.考慮到一體化調度的核心是設備之間的協同和有效銜接,即多資源的協同分配問題,結合多資源協同分配,給出了一體化調度問題建模和求解的解決方案.

1 集裝箱作業系統一體化調度

集裝箱作業系統是由岸邊裝卸設備(常規岸橋QC、雙40 ft岸橋D40′QC)、水平輸送設備(集卡CT、自動導引小車AGV、跨運車SC)和堆場裝卸設備(軌道式龍門起重機RMC、輪胎式龍門起重機RTG)組成的復雜系統,以實現集裝箱(進口Import、出口 Export、中轉 Transshipment)的裝卸、運輸和堆存[1-2].針對亞太國家常用的 QCCT-RTG裝卸工藝,集裝箱作業系統的調度問題主要涉及：泊位分配(berth allocation problem, BAP)、前沿起重機調度(quay crane scheduling problem,QCSP)、集卡調度(container truck scheduling problem,CTSP)、堆場起重機調度(yard crane scheduling problem,YCSP)和堆場空間分配(yard storage allocation problem, YSAP).此外,QCSP需要考慮船舶配載(stowage planning,SP)、發箱和裝船順序等問題的決策, YSAP需要考慮堆場箱位分配(slot assignment, SA)、集裝箱翻箱和轉堆等問題決策.

目前,一體化調度的問題描述、建模和算法研究正成為港口調度的熱點和難點,是提高集裝箱港口整體性能的關鍵,但相關研究不多,且多集中在 QCSP-CTSP-YCSP,BAP-QCSP,QCSPCTSP,CTSP-YSAP等問題的組合.

1)BAP-QCSP Christian[3]對BAP,QCSP和BAP-QCSP進行了文獻綜述,提供的83篇文獻僅有19篇是關于BAP-QCSP的研究,指出一體化調度是港口調度的難點和方向.Giovanni Giallombardo[4]采用混合整數二次規劃(MIQP)對BAP-QCSP問題進行數學描述,結合禁忌搜索啟發式算法,構建了Bi-level的啟發式算法,目標是最大化每個時間段內前沿起重機的使用數目和最小化堆場內轉堆的成本,采用加權的單目標函數,對多泊位的靜態調度案例進行了驗證和分析.周鵬飛[5]建立了面向隨機環境的集裝箱碼頭泊位2岸橋分配模型,設計了一種改進的遺傳算法,其優化目標是最小化船舶的平均等待時間.

2)QCSP-CTSP 計明軍[6]針對同時裝卸集裝箱作業的情況,考慮集裝箱卡車的運輸時間和岸橋的作業時間,建立了QCSP-CTSP問題的基于時間最少的優化模型,設計了求解此優化模型的進化算法.

3)CTSP-YSAP Han等[7]提供了整合集卡調度和堆場資源分配兩個決策問題的途徑,核心思路是平衡每個堆區的工作量,減少集卡引起的交通擁堵.Lee Derhorng[8]考慮了進口箱在堆場的堆存資源分配和集卡調度問題,采用混合整數規劃對問題進行數學描述,優化的目標是使所有進口箱對應的運輸成本最小.

4)QCSP-CTSP-YCSP 陳璐[9]提出了基于柔性化flow shop的集成化控制模型,提出禁忌搜索算法進行求解,案例沒有考慮混合裝卸的情況.張海霖[10]針對集裝箱港口集疏運系統多階段動態調度的問題,借鑒柔性制造系統(FMS)生產調度問題的研究方法,提出了基于規則的方法實現集裝箱集疏運系統的實時動態調度.陸志強[11]基于析取圖建立了碼頭裝卸設備集成調度問題的析取圖模型.曾慶成[12]采用仿真優化方法進行系統的一體化調度,優化算法為NN和GA的混合算法,NN主要是用于對個體適應度函數的預測.

5)QCSP-CTSP-YSAP Bish[13]將水平輸送車輛調度和堆場資源分配2個決策問題整合成一個問題進行研究,構建了啟發式算法,并分析了下界值.

以上研究普遍缺乏對多資源協同分配的思考,而資源的協同和分配是一體化調度的關鍵,缺失資源/設備的協同和分配,將導致構建的模型和算法無法滿足生產連續、組織協作、任務平衡的需要,也無法從整體把握和評價系統性能.

2 多資源協同分配

集裝箱復雜作業系統一體化調度的核心在于復雜系統內分散和自主的多資源協同及其分配. QC&D40′QC-CT-RTG工藝下的多資源協同分配,是針對大規模串并行作業任務的執行,在港口分散和自主管理模式環境中對QC,D40′QC,CT, RTG等可得資源進行協同分配,目的是實現有限資源的任務均衡、生產連續和系統整體性能的提高.由于D40′QC的引入,帶來了批處理能力,使多資源協同分配問題(Multi-resources co-allocation)更加復雜.

多資源協同分配最初針對的是單個應用程序的執行,主要是在分布式環境中對CPU、網絡、內存、數據倉庫等可得資源進行協同分配.一些著名的網格計算系統,例如 MSHN,Globus,Legion等,均在其資源管理中提供了協同分配機制.目前,多資源協同分配問題的研究主要集中在多個應用程序競爭資源,并從分布式環境擴展到工作站網絡、多機群的環境中.

Wang Lizhe[14]將網格計算環境下的并行任務在多資源的分配問題描述為任務集合到資源協同分配矩陣的映射,調度的目的是找到一個使并行任務執行時間最小的調度.Li Jiadao[15]指出資源協同分配問題是網格計算資源管理方面最具有挑戰性的研究內容之一,并構建了具有協商(Negotiation)機制的資源協同分配模型及其調度策略.Joerg Decker[16]針對網格計算環境下的工作流,基于表調度提出了2種啟發式算法：(1)使用Greedy list scheduler貪心表調度;(2)加入了搜索技術,以實現資源的協同分配和預置.Andrea Pugliese[17]指出網格計算環境下的網格資源管理系統(GRM)涉及的主要需求是多資源協同分配下的資源預置和服務質量(QoS),由于網格環境具有自治、異構、分布、動態等特性,導致網格環境下的資源調度十分困難.

李慧賢[18]利用DAG理論,將網格資源的協同分配問題視為應用任務到資源的映射問題,目標是使應用集合的整體調度時間最小.張偉哲[19]采用最大空閑節點優先、最小網絡擁塞優先、最小異構因子優先和最小異構空閑節點優先等啟發式策略,對多機群協同調度算法進行研究,允許并行任務的不同部分并發運行于分布在多個管理域的異構機群.

以上文獻主要從分布式計算和多機群計算方面,采用資源預置、DAG、Backbilling、協商、啟發式策略、鄰域搜索法等方法對多資源協同分配問題展開研究,在其他領域尤其是集裝箱復雜作業系統下的研究和應用尚沒有相關文獻.

3 一體化調度問題解決方案

集裝箱作業系統,尤其是采用雙40 ft岸橋的集裝箱復雜作業系統,生產作業中同時存在進口、出口、中轉等3種流向的集裝箱,其工藝路線不同.中轉箱在當前碼頭中轉時,可能會出現在同一設備處理兩次的情況.對于任意流向的集裝箱,都要被岸橋、場橋、集卡等類型的設備處理.每種類型的設備都是一個并行機集合.岸橋集合中存在具有批處理能力的雙40 ft岸橋和其他沒有批處理能力的岸橋,即多同類機集合,以上帶有復雜作業車間的特征.因此,將集裝箱復雜作業系統抽象為復雜作業車間(complex jop shop)進行數學描述,便于從整體對系統各環節的指標進行整體考慮,從而實現一體化調度.相關映射關系如圖1所示,左邊為港口集裝箱物流系統中的作業系統,右邊為復雜作業車間.

圖1 集裝箱復雜作業系統原型

如圖1所示,集裝箱作業系統存在前沿操作、水平運輸、場橋操作等3個操作,每個操作對應的機器或設備分別為岸橋、集卡、場橋,有別于化工、半導體制造領域的復雜作業車間描述,集裝箱作業系統各操作環節間通常不存在緩沖區.作為工件的集裝箱其任意操作的完成都離不開相鄰操作對應設備的協同配合,需要為工件指派或分配設備集合;對于任意設備,都存在大量集裝箱作業任務,需要對工件進行排序;任意工件的任意操作也面臨在并行機集合或多同類機集合中選擇設備的決策.其中,機器的作業時間取決于設備的生產作業效率,機器的阻塞時間取決于多資源協同分配下多個資源最后到達時間與請求發出時間之差.問題的求解目標是系統整體系能的最優,通常是多目標優化.例如：滿足客戶要求最大化(兼顧一程船和二程船的客戶滿意度)、系統性能最好(通常以min(max(TurnaroundTime))進行衡量)、設備生產效率高(尤其是瓶頸設備QC和D40′QC的GCR：Gross Crane Rate)等.

在圖1描述的基礎上,采用基于迭代式分解調度方法,構建解決方案,如圖2所示.一體化調度問題抽象為復雜作業車間調度問題Q,根據工件流向i,分解為混合流水車間調度問題HFi;相應地,HFi可繼續分解為多同類機調度問題,如果還存在多資源協同分配請求,則該問題還嵌套有多資源協同分配問題.其他,依此類推.

圖2 解決方案

4 結束語

考慮到集裝箱作業系統的復雜性、動態隨機性,一體化調度的方法體系研究、模型的有效描述、算法的自適應和快速、方案的重調度能力和魯棒性、基于Agent的仿真建模、仿真優化技術等,都將是一體化調度研究的重點和方向.

[1]張艷偉.集裝箱碼頭混合裝卸系統生產組織關鍵技術研究[D].上海：同濟大學機械工程學院,2008.

[2]Gǜnther H O.Kim K H.Container terminals and terminal operations[J].OR Spectrum,2006,(28)：437-445.

[3]Bierwirth C,Meisel F.A survey of berth allocation and quay crane scheduling problems in container terminals[J].European Journal ofOperational Research,2010(202)：615-627.

[4]Giallombardo G,Moccia L,Salani M.Modeling and solving the tactical berth allocation problem[J]. T ransportation Research Part B,2010(44)：232-245.

[5]周鵬飛,康海貴.面向隨機環境的集裝箱碼頭泊位2岸橋分配方法[J].系統工程理論與實踐,2008(1)：161-169.

[6]計明軍,靳旨宏.集裝箱碼頭集卡與岸橋協調調度優化[J].復旦學報：自然科學版,2007,46(4)：476-481.

[7]Han Y.A yard storage strategy for minimizing traffic congestion in a marine container transshipment hub[J].OR Spectrum,2008,(30)：697-720.

[8]Lee Derhorng Lee,Cao Jinxin,Shi Qixin.A heuristic algorithm for yard truck scheduling and storage allocation problems[J].Transportation Research Part E, 2009,(45)：810-820.

[9]陳 璐,奚立峰,蔡建國.一種求解帶有阻塞限制的混合流水車間的禁忌搜索算法[J].上海交通大學學報,2006,40(5)：856-859.

[10]張海霖,江志斌,許 泓.集裝箱港口集疏運調度系統作業模式的仿真分析[J].上海交通大學學報, 2006,40(6)：1 024-1 030.

[11]陸志強,梁 亮.集裝箱碼頭作業調度問題建模和性質分析[J].交通運輸工程學報,2009,9(4)：98-102;107.

[12]Zeng Qingcheng,Yang Zhongzhen.Integrating simulation and optimization to schedule loading operations in container terminals[J].Computers&Operations Research,2009(36)：1 935-1 944.

[13]Bish E K,Chen F Y.Dispatching vehicles in a mega container terminal[J].OR Spectrum,2005,27：491-506.

[14]Wang Lizhe,Cai Wentong,Lee Busung.Resource co-allocation forparallel tasks in computational grids[C]//Proceedings of the International Workshop on Challenges of Large Applications in Distributed Environment(CLADE′03),21 June 2003：88-95.

[15] Li Jiadao,Yahyapour R.Negotiation model supporting co-allocation for grid scheduling[C]//Grid Computing Conference 2006：254-261.

[16]Decker J,Schneider J.Heuristic scheduling of grid workflowssupportingco-Allocation and advance reservation[C]//Seventh IEEE International Symposium on Cluster Computing and the Grid(CCGrid' 07),14-17,May,2007,：335-342.

[17]Pugliese A,Talia D,Yahyapour R.M odeling and supporting grid scheduling[J].J Grid Computing, 2008(6)：195-213.

[18]李慧賢,程春田.一種并行的網格資源協同分配方法[J].大連理工大學學報,2005,45(2)：272-277.

[19]張偉哲,田志宏,張宏莉,何 慧,劉文懋.虛擬計算環境中的多機群協同調度算法[J].軟件學報,2007, 18(8)：2 027-2 037.