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

发布时间：2017-03-23 09:06

  本文关键词：面向集装箱码头岸桥调度的可重叠流水作业优化，由笔耕文化传播整理发布。

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

• 摘要4-6
• Abstract6-14
• 第1章 绪论14-26
• 1.1 研究依据14-15
• 1.2 研究现状15-20
• 1.2.1 流水作业调度研究现状16-18
• 1.2.2 传统岸桥调度问题的研究现状18-19
• 1.2.3 新型岸桥的架构和调度方式研究现状19-20
• 1.3 研究动机和主要研究内容20-23
• 1.3.1 研究动机20-22
• 1.3.2 主要研究内容22-23
• 1.4 论文结构23-26
• 第2章 可重叠流水作业调度优化26-48
• 2.1 重叠工序对优化目标的影响26-28
• 2.2 问题描述与模型28-31
• 2.2.1 问题描述28-29
• 2.2.2 数学模型29-30
• 2.2.3 问题的复杂性30-31
• 2.3 可重叠工序的性质31-36
• 2.3.1 目标函数推广31-32
• 2.3.2 任务量分配32-34
• 2.3.3 最优排序规则34-35
• 2.3.4 下界证明35-36
• 2.4 贪心搜索算法36-40
• 2.4.1 过滤机制36-37
• 2.4.2 初始解生成37
• 2.4.3 改进启发式方法37-38
• 2.4.4 扰动和终止条件38-40
• 2.5 实验结果及讨论40-45
• 2.5.1 算法和CPLEX的性能比较40-41
• 2.5.2 重叠性对算法的影响41-43
• 2.5.3 算法性能评估43-45
• 2.5.4 算法步骤的测评45
• 2.6 本章小结45-48
• 第3章 集装箱码头双周期岸桥调度48-64
• 3.1 问题描述和特性48-50
• 3.1.1 问题描述48-49
• 3.1.2 内部空隙对调度性能影响49-50
• 3.2 问题模型50-55
• 3.2.1 集装箱堆排序模型51-53
• 3.2.2 左移内部空隙的作用53-54
• 3.2.3 改进的舱门调度模型54-55
• 3.3 复合启发式算法55-58
• 3.3.1 集装箱堆排序方法55-56
• 3.3.2 复合启发式算法56-57
• 3.3.3 算法性质分析57-58
• 3.4 实验结果及讨论58-62
• 3.4.1 测试实例58-59
• 3.4.2 算法性能比较59-62
• 3.4.3 双周期调度策略性能分析62
• 3.5 本章小结62-64
• 第4章 双贝位双周期岸桥调度64-82
• 4.1 新型岸桥DGBC64-65
• 4.2 问题描述65-67
• 4.2.1 问题描述及定义65-66
• 4.2.2 双周期DGBC调度66-67
• 4.3 问题模型67-70
• 4.3.1 问题假设67
• 4.3.2 数学模型67-70
• 4.4 两阶段启发式算法70-75
• 4.4.1 单贝位双周期调度70
• 4.4.2 双贝位时间表70-73
• 4.4.3 两阶段启发式算法73-74
• 4.4.4 DGBC及其算法实例74-75
• 4.5 DGBC性能评估和分析75-81
• 4.5.1 参数配置75-76
• 4.5.2 三种边界情况76-77
• 4.5.3 架构性能比较77-80
• 4.5.4 调度策略对岸桥架构的影响80-81
• 4.6 本章小结81-82
• 第5章 总结与展望82-86
• 5.1 全文总结82-83
• 5.2 未来工作展望83-86
• 致谢86-88
• 参考文献88-96
• 攻读博士期间论文发表情况96-98
• 攻读博士期间参与的科研项目98

【相似文献】

中国期刊全文数据库 前10条

1 惠永涛;;作业调度的原理及算法[J];计算机研究与发展;1989年03期

2 陈曦,柳林;基于仿真方法的流通加工作业调度研究[J];信息技术;2001年11期

3 潘全科,罗翔,朱剑英;基于准时制的时间成本双目标作业调度优化[J];东南大学学报(自然科学版);2003年01期

4 刘繁茂;陈新;;中小型半流程制造业的生产作业调度系统研究与应用[J];制造技术与机床;2006年09期

5 颜斯泰;熊萌立;赵淑光;曾志华;;高性能计算与作业调度技术在核电工程领域的应用[J];互联网天地;2013年10期

6 蔡龙飞;;田间作业调度的优化研究与应用[J];现代计算机(专业版);2009年02期

7 刘新闯;邱洪泽;魏二有;苏兆锋;;利用优势元素改进进化算法求解柔性作业调度[J];计算机工程与应用;2010年17期

8 梁迪;陶泽;;多目标柔性作业调度的优化研究[J];计算机工程与应用;2009年15期

9 胡中华;赵敏;;一种求解机器人作业调度的智能优化算法[J];电焊机;2009年11期

10 苏开根;毋国庆;石晓红;;785计算机操作系统作业调度策略[J];计算机工程与科学;1981年01期

中国重要会议论文全文数据库 前3条

1 裴尔明;Karim Bernardet;于传松;孙功星;;基于Agent技术“推拉”结合的网格作业调度系统[A];第十四届全国核电子学与核探测技术学术年会论文集（2）[C];2008年

2 刘礼;杨裔;火久元;刘海迪;李振芳;李廉;;数学网络集成环境作业调度系统模型[A];2006年全国理论计算机科学学术年会论文集[C];2006年

3 裴尔明;Karim Bernardet;于传松;孙功星;;基于Agent技术“推拉”结合的网格作业调度系统[A];第十四届全国核电子学与核探测技术学术年会论文集（下册）[C];2008年

中国重要报纸全文数据库 前1条

1 陈超;有效作业调度实现高效生产[N];中国计算机报;2004年

中国博士学位论文全文数据库 前6条

1 王丹丹;面向集装箱码头岸桥调度的可重叠流水作业优化[D];东南大学;2015年

2 邹敢;柔性搬运系统的智能作业调度方法研究[D];昆明理工大学;2014年

3 顾学民;分布式制造环境下的作业调度研究[D];西北工业大学;2006年

4 梁毅;面向网络计算的作业调度系统关键技术研究[D];中国科学院研究生院（计算技术研究所）;2005年

5 顾涛;集群MapReduce环境中任务和作业调度若干关键问题的研究[D];南开大学;2014年

6 高昊江;板料加工车间物流智能控制及仓储管理系统研究[D];华中科技大学;2007年

中国硕士学位论文全文数据库 前10条

1 罗惠星;基于批量作业调度的算法研究[D];上海师范大学;2015年

2 林薇;多目标多约束环境下的生产计划与作业调度方法研究[D];东华大学;2008年

3 徐磊;云环境下资源管理与作业调度关键问题研究及应用[D];清华大学;2014年

4 侯明霞;云计算环境下作业调度策略研究[D];电子科技大学;2014年

5 薛帆;结合组织模型的多Agent分布式调度研究[D];中国民航大学;2007年

6 谢杨;自动化立体仓库拣选作业调度优化研究[D];重庆大学;2015年

7 葛新;基于云计算集群扩展中的调度问题研究[D];中国科学技术大学;2011年

8 黄游槟;面向c-MES的资源重构与作业调度优化技术研究[D];南京航空航天大学;2006年

9 谭伟良;集群作业调度优化技术研究[D];昆明理工大学;2009年

10 惠新华;云环境下作业调度优化的方法研究[D];辽宁大学;2011年

  本文关键词：面向集装箱码头岸桥调度的可重叠流水作业优化，由笔耕文化传播整理发布。

，

本文编号：263374