自动化码头调度平台 作 品 综 述 2009 年 9 月中国科学院软件研究所 2009 年 9 月中国科学院软件研究所 http:/cscup.iscas.ac.cn 1 自动化码头调度平台的意义自动化码头调度平台的意义 随着世界码头的发展和需求，传统的码头模型将会被自动化模型所代替，这个是毫 无争议的。 现在世界上已经有很多码头专家提出了很多不同类型的， 基于不同设备解决 方案的自动化码头模型。 但是并没有一个模型是已经成熟， 自动化码头还处于一个发展 阶段，还有许多问题需要去研究。然而研究这样的调度系统，只从数学的计算推理的方 向进行研究是不完善的，也是不现实的。问题的本身也是非常复杂的，所以我们认为如 果能研究出这样的一个调度平台： 它不仅能够模拟设备正常运行情况， 而且能够支持多 种不同调度策略， 并可以根据不同的设备性能和配置设置不同的参数， 以达到真实而稳 定的效果，那么这个调度平台对我们以后码头的智能调度系统和调度算法有极大的帮 助，相比纯数学层面上的研究将更直接更准确更可靠。 其次，智能调度是一个 NP-HARD 问题。问题规模是比较庞大的，开发这样一个平 台有利于我们把调度问题具体化，可视化。在未来的发展过程中，这样的一个调度平台 将有两个作用，一是提供调度算法的研究平台，二是应用到实际自动化码头中，成为码 头的自动化调度核心。 2 该系统所采用的硬件布局（该模型来自振华重工集团提供的自动化码头方案）该系统所采用的硬件布局（该模型来自振华重工集团提供的自动化码头方案） u 设备介绍 该自动化码头方案包括以下基本运输设备：岸桥（QC） 、低架桥轨道电动起重小车 （OBC） 、 低架桥轨道电动平板小车 （TC） 、 地面轨道电动平板小车 （GC） 、 场桥 （RMG） 。 （1）岸桥（QC）岸边集装箱起重机。它的作用在能从船上吊起集装箱往岸上传输， 或者往船上堆放箱子。在本系统中，每个码头默认有四个 QC 参与装卸调度。 （2）在 QC 的陆侧，有五个低架桥轨道，每个轨道上有两对电动起重小车（OBC） 和电动平板小车（TC） 。每对小车之间的位置不可逾越。TC 用于沿海岸线水平运输集 装箱。而 OBC 则用于箱子的垂直转移，它把 TC 的箱子垂直提起然后放到 GC 上，或 者把 GC 上的箱子垂直提起然后放到 TC 上。每个码头有五条低架桥轨道线，但是使用 其中的四条轨道，共八个 OBC 八个 TC 参与装卸调度，另外一条轨道线则用于预备。 （3）在陆侧的堆场中，每个堆场被平均分割为七个堆场区（术语为垛） 。每个垛配 备了一个长的场桥（RMG）和一个短的场桥（RMG） 。还有两个地面轨道电动平板小 车（GC） ，具体布局如图。 （4）在陆侧与海测的中间一段空旷地带，那是集装箱卡车的运行轨道，这部分有 人参与运输。由于某些箱子由于特殊的要求，他们并不进入当前堆场，这时候就必须调 度集卡运走，我们把这部分箱子统称为特殊箱。 （5）为了提高码头的吞吐率，所有的设备都支持双箱操作。 u 流程介绍 卸箱流程：卸箱流程：岸桥起重机（QC）从货船上同时吊起两个集装箱至低架桥轨道的上方， 被分配的电动平板小车（TC）接到箱子后自动运行至指定位置，同时低架桥轨道电动 起重小车（OBC）也运行到相同的目的地，然后 OBC 从 TC 上提起箱子，待到 TC 避 开一定的距离后将集装箱下移到轨道以下旋转九十度然后放到地面轨道电动平板小车 （GC） 平台上， GC 负载箱后向堆场区运行， 来到箱子的目的地后由堆场起重机 （RMG） 将集装箱分别吊至指定的堆场箱位。 卸箱流程：卸箱流程：堆场起重机（RMG）将集装箱分别从堆场吊至地面轨道电动平板小车 （GC）上，GC 负载箱后向低架桥方向运行，待到 OBC 到位后由 OBC 提起箱子，旋 转九十度然后直接吊至轨道上空某高度，接着 TC 进入 OBC 的正下方，OBC 将集装箱 箱卸到 TC 上，TC 负载箱后自动运行至指定的岸桥 QC 所在的位置，然后 QC 将集装2009 年 9 月中国科学院软件研究所 2009 年 9 月中国科学院软件研究所 http:/cscup.iscas.ac.cn 箱从 TC 吊起，放至货船的指定目的地。 对于每一个 QC 设备，它的工作流程是先卸载它当前工作的船贝，然后再装载它当 前工作的船贝。但是对于整个系统运行的时候，装卸是同时运行的。 u 系统布置平面图： （平台二维界面） u 系统布置三维图： （平台三维界面） 2009 年 9 月中国科学院软件研究所 2009 年 9 月中国科学院软件研究所 http:/cscup.iscas.ac.cn 3 该平台的软件架构和开发环境该平台的软件架构和开发环境 用 vs2005 + sql20005 开发的 WINDOWS 程序，C+开发，MFC 做二维界面,OPENGL 做 三维显示。多线程并发（多达 64 线程） ，实时调度算法。平台规模相对是比较大的。 模块划分清晰，包括数据库模块，系统参数配置模块，显示模块（包括二维显示模块和 三维显示模块） ，任务调度模块，PLC 模拟模块，设备运行模拟模块，调度算法模块（包括 集中调度方式和集中式调度方式） ，和信息收集模块。 数据中心：数据中心：整个平台的所有数据信息都放在这里，包括设备的数量，设备的性能参数， 堆场布局，当前工作船只的信息，平台模拟的加速比，还有模拟外界环境对设备运行的影响 参数。 参数配置：参数配置：这个模块主要是用于配置平台参数。可配置部分包括以下：1.设备配置参数 （QC 的参与执行的数目，参与运行的 TC 轨道数，每个堆场垛的所参与工作的 RMG-GC 小 车对数等） ，2.设备性能参数（QC 整车移动的速度，QC 内部小车水平运行的速度，QC 吊 钩空载时候的垂直速度， QC 吊钩满载时候的垂直速度， QC 的高度， TC 空载水平运动速度， TC 满载水平运动速度，OBC 水平运动速度，OBC 吊钩空载的垂直速度，OBC 吊钩满载的 垂直速度，OBC 旋转吊钩速度，RMG 整车移动速度，RMG 内部小车水平运动速度，RMG 吊钩空载垂直速度，RMG 吊钩满载垂直速度，GC 小车的空载水平移动速度，GC 小车的满 载水平移动速度） ，3.模拟运行的加速参数，4.调度算法配置，5.外部因素对设备运行影响系 数（10.1） 。 显示模块：显示模块：在整个系统的模拟运行中，都是使用了实际的位置坐标。显示模块把实际坐 标系转化为屏幕显示坐标系， 并根据屏幕的大小比例进行放大缩小。 为了实现设备的不同时 刷屏而屏幕不闪烁效果， 其中使用了局部刷新和双缓冲技术。 目前只实现了堆场的俯视图二 维显示，通过不同颜色的现实表到不同的设备状态和箱位的高低。 任务调度器：任务调度器： 整个系统的输入是任务队列， 但是任务队列并不直接暴露给调度算法模块，2009 年 9 月中国科学院软件研究所 2009 年 9 月中国科学院软件研究所 http:/cscup.iscas.ac.cn 而是由任务调度器统筹管理， 该调度器对任务队列的合理性进行初步分析， 在不改变堆场计 划下，对任务次序进行局部修改，达到提高双箱率的效果。任务调度通过观测每个设备的运 行状态和当前任务队列的情况，适时的给 QC 或者堆场的 RMG 发送装卸箱任务，设备到接 到任务消息后， 激发新的装卸操作。 任务调度器直接决定着每个 QC 设备当前工作的状态 （处 于装状态，或者卸状态） ，以及当初工作的船贝。 在整个装卸模拟开始的时候， 所有任务队列装载进入调度器， 当调度器把队列内的所有 任务项发送执行完成，标志着该任务模拟执行结束。 PLC 模拟：模拟：这个模块是和调度器交互的主要模块，由于整个平台架构是消息驱动的， 所以他们之间的主要交互方式也是消息。调度模块向 PLC 模块发送设备的运行命令，调度 命令其中可以包括了一些宏命令，PLC 对每个命令进行解析，根据命令的参数，发送到所 对应的设备，进行运行模拟。并跟踪每个设备的运行情况和命令的完成情况，最后在命令完 成时想调度算法模块回复命令完成消息和和设备所处的状态。 设备运行模拟：设备运行模拟：在这模块中，将模拟每个设备的运行。我们对每个设备分配一个消息队 列和一个模拟执行的线程，线程一直监视着消息队列，当消息队列中有任务进入的时候，线 程就会获取该任务并解析执行，任务完成会回馈任务完成信息。在这个模块中，平台将为它 分别分配 56 个线程，分别模拟 56 个设备。设别运行的参数都读取自数据中心模块。 调度算法模块：调度算法模块：这个模块将根据用户的不同算法需求，做不同的设置，它主要需要实现 平台的两个接口，一个是和任务调度器的任务交互，一个是对设备的命令交互等。 信息收集模块：信息收集模块：作为一个研究性平台，数据的收集很重要。利用收集起来的数据我们可 以对计算出设备的利用率，系统的流量进而对算法性能进行分析评估。而这其中，我们收集 的数据包括了设备的运行日志(按时间的顺序记录所有设备的运行轨迹)，平台交互消息（按 时间顺序记录整个任务完成过程中的消息） ，箱子的运行轨迹（什么时间由什么设备进行什 么操作） ，设备的运行时间（完成每一个任务包括的时间：空闲时间，空载等待时间，装载 等待时间，空载运行时间，装载运行时间） 。平台分析人员可以通过这样数据的不同组合得 到的需要的不同分析数据。 整个系统使用消息驱动的方式，即每个调度的触发点都是收到新的操作消息。其中的这 个消息机制由我们自主开发的，相对简单的，但是容易管理，调试，比较安全。下图展示我 们平台中的部分消息交互情况： 2009 年 9 月中国科学院软件研究所 2009 年 9 月中国科学院软件研究所 http:/cscup.iscas.ac.cn 4 调度算法的描述调度算法的描述 基于这个模拟平台，我们研发了两种智能调度算法，一种是集中式调度方式，一种是分 级分布式调度方式，以下我们分别介绍下发这两种调度算法的架构和优缺点比较。 4.1 集中式调度算法 思路：思路：所有设备的运行都由一个核心逻辑控制。从任务出发逐步调度每一种设备， 直到把集装箱放入目的地。我们把每个任务的控制逻辑块，叫做一个执行体。整个系统 的执行过程就是不同执行体抢占资源， 使用资源， 释放资源的过程 （这里的资源是设备） 。 由于这其中使用了多线程在进行资源竞争，所以我们必须实现一个资源的锁定，分配和 释放，以防死锁的情况。 任务消息接收器在接收到任务的消息后，把任务包装成一个执行体（executor）并 放入执行体容器中，每个执行体有自身的一个执行逻辑。每个执行都有一个标识，唯一 标志本身，他们向设备管理器申请设备，并不断通过消息收发中向设备发送运行命令， 消息发送中心得到设备的反馈消息后会通过执行体的标志，把消息传递给所对应的执行 体，当执行体自身的任务完成后，会自行销毁。 4.2 分级分布式调度算法 思路：思路：和集中式调度算法相对的概念就是分级分布式。重新思考整个自动化码头的 运行流程，其实我们很快就可以发现，集装箱在运送过程中是一个流水线的过程。在卸 箱的过程中经历过了三个运输的阶段，而在装箱的过 程中，则经历了反过程。每个阶段可以同时运行多个 箱，而在两个阶段的运输过程中只有箱子交互，没有多余的资源依赖，所以我们可以把 整个装卸设备分成以下三个级别,并装卸调度的控制逻辑 分别分布到每个级别上，每个级别的调度逻辑只管理调度本级别的设备，对其他级别而 言是不可见的。集装箱的装卸过程也就是箱子在不同级别设备上转移的过程。 关于 QC 调度级别，由于 QC 间没有任何的交互操作都是独立工作，所以我们为每 个 QC 设计了一个调度器，每个调度器有装和卸两套逻辑。卸调度器从任务控制器拿到 卸箱任务后开始调度设备从船取箱， 运输并向 TC 调度申