集装箱作业系统一体化调度研究综述＊

张 煜 李文锋 严新平

(武汉理工大学物流工程学院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.