详情

原文传递面向集装箱码头岸桥调度的可重叠流水作业优化

论文题名：	面向集装箱码头岸桥调度的可重叠流水作业优化
关键词：	可重叠工序;岸桥调度;流水作业;双周期策略;启发式算法;集装箱码头
摘要：	可重叠工序是提高柔性和调度性能的有效技术手段，广泛存在于新型调度资源及其组成的应用系统中。考虑集装箱运输、分布式计算等系统中具有可重叠工序的组合优化问题，以大幅度提高实际应用系统的调度质量和效率为目的，探讨相应的可重叠流水作业调度优化理论和方法，具有重要的理论和实际应用价值。　　论文以最小化最大完工时间为优化目标，以可重叠流水作业调度为核心和基础，分析可重叠操作的相关性质，提出基于空隙消除的贪心启发式算法;将相应理论和方法分别拓展到双周期集装箱岸边起重机（岸桥）调度和双贝位双周期岸桥调度等具体离散优化问题。论文的主要创新性工作如下: 　　(1)可重叠流水作业调度优化。通过分析应用系统的实际业务流程，发现其中的可重叠工序现象，提出可重叠流水作业调度这一新的组合优化问题;以最小化最大完工时间为优化目标建立整数规划模型，并证明该问题是NP完全的;原问题目标函数最大完工时间的求解分为不依赖于调度的重叠量和非重叠流水作业调度两块部分，该目标函数计算方法推广到泛化的可重叠流水作业调度;设计贪心策略消除可重叠工序的内部空隙，提出可重叠工序任务量的合理分配，推导最优排序规则;提出六个贪心搜索算法，从构造初始解出发，以迭代方式逐步改进解的质量。通过不同规模实例组的测试，验证了所提算法的有效性和重叠以及重叠量对流水调度性能带来的重要影响。　　(2)集装箱码头双周期岸桥调度。将可重叠流水作业调度优化拓展到集装箱码头岸桥调度;提出带舱门约束的岸桥调度采用新的双周期调度策略，实现卸载和装载协同操作，以降低岸桥的操作周期数;将双周期岸桥调度问题划分为组内调度和组间调度两个子问题;组内调度子问题建模成两机非置换的流水作业调度，提出新的集装箱堆排序算法，用于获得最优的组内操作调度;组间调度子问题建模为两机成组流水作业调度，每个组内调度构成一个含有可重叠工序组任务;设计空隙移动机制，调整每个组任务的重叠量，用以构造单贝位的岸桥舱门调度方案。通过测试大量不同参数配置的实例，表明所提算法优于已有算法;相比于传统的单周期调度方式，双周期调度策略能够显著降低岸桥操作周期数。　　(3)双贝位双周期岸桥调度。设计新型岸桥架构——双大梁轨道式起重机(DGBC)。DGBC仅需一位操作员采用双周期策略同时操控两个贝位，节省岸桥自身移动成本和对集装箱船的服务时间。两个贝位调度间、同周期的卸载和装载间都具有重叠操作。以最小化双贝位最大完工时间为优化目标，建立有资源约束的项目调度模型;基于可重叠流水作业调度算法，设计两阶段启发式方法:第Ⅰ阶段使用双周期调度策略生成单贝位操作序列;第Ⅱ阶段在满足操作员工作约束的前提下，通过贪心策略消除资源冲突，构造统一的双贝位协同时间表。针对双贝位双周期岸桥调度的特性，定义三种边界情况，并依次与传统岸桥操作比较;结果表明:DGBC可显著优化岸桥最大完工时间和操作员的有效工作效率;双周期调度策略的改进效果不仅对传统岸桥非常明显，对新型岸桥同样有效。
作者：	王丹丹
专业：	计算机应用技术
导师：	李小平
授予学位：	博士
授予学位单位：	东南大学
学位年度：	2015
正文语种：	中文