基于约束的现代调度系统研究

论文摘要

现代调度问题往往都是NP完全问题,具有高复杂、动态随机等特性。本文主要研究内容为基于约束的现代调度,即运用约束程序设计方法来求解现代调度问题,从而拓展了约束程序设计在求解组合优化问题方面的应用领域。主要工作包括:通过对一般工业调度问题的深入研究,建立起基于多值逻辑的调度约束模型和模型库;设计了三种完备约束优化调度算法和三种启发式调度规则,设计了一种新的通用离散资源约束处理策略,从而完善了一般调度问题求解的通用方法库;首次运用约束程序方法对在线/半在线调度问题求解进行了研究;实现了基于约束求解的调度算法,构架出基于约束的调度建模和求解类库框架,并调用此类库对一些典型问题进行了实验测试,运行结果良好。

论文目录

• 第一章 绪论
• 1.1 约束满足与约束优化
• 1.1.1 约束问题
• 1.1.2 约束满足问题求解
• 1.1.3 动态约束满足问题求解
• 1.1.4 约束优化问题求解
• 1.1.5 软约束满足问题
• 1.2 约束程序
• 1.2.1 CP 组成
• 1.2.2 CP 实现
• 1.2.3 CP 应用
• 1.3 调度及其方法
• 1.3.1 车间调度问题
• 1.3.2 现代调度问题
• 1.3.3 基于约束的调度
• 1.4 本文工作
• 第二章 调度中的约束建模
• 2.1 基于约束的调度模型
• 2.1.1 任务和作业
• 2.1.2 资源
• 2.1.3 目标函数和优化指标
• 2.2 约束模型
• 2.2.1 约束类别
• 2.2.2 基于离散逻辑的约束建模
• 2.3 优化指标约束建模
• 2.4 基于离散时间的时间建模
• 2.5 小结
• 第三章 完备优化调度算法
• 3.1 直接使用CSP 求解器的二分调度算法
• 3.2 基于目标约束优化的调度算法
• 3.3 分支界限整型优化算法
• 3.4 小结
• 第四章 通用资源约束处理
• 4.1 基于调度规则的方法
• 4.2 EDGE-FINDING 约束消解规则
• 4.3 三个启发式调度规则
• 4.3.1 基于争用度和依赖度的调度规则
• 4.3.2 基于Bslack 的调度规则
• 4.3.3 基于基本工件组的调度规则
• 4.4 基于E-FC 的通用资源处理方法
• 4.4.1 资源约束传播事件
• 4.4.2 资源约束传播算法e-FC
• 4.4.3 算例测试
• 4.5 小结
• 第五章 在线/半在线调度约束求解
• 5.1 基于动态约束满足的在线调度
• 5.1.1 在线调度
• 5.1.2 在线调度动态信息分析
• 5.2 基于单调约束的半在线调度
• 5.2.1 半在线调度
• 5.2.2 动态约束建模和单调性
• 5.2.3 通用动态约束求解算法
• 5.3 小结
• 第六章 系统实现与实验结果
• 6.1 总体设计
• 6.2 SCHEDULER 设计说明
• 6.3 实验结果
• 6.3.1 一元资源约束调度问题
• 6.3.2 车间作业调度问题
• 6.3.3 基于订单任务的生产排程问题
• 6.3.4 资源约束项目调度问题
• 6.3.5 半在线Ship-loading 问题
• 6.4 小结
• 第七章 总结与展望
• 参考文献
• 作者读博士期间完成的论文与参加的科研项目
• 致谢
• 附录
• 摘要
• ABSTRACT