约束满足技术的研究及在生产调度中的应用

论文摘要

生产管理是提高现代生产企业生产效率和经济效益的重要手段。生产调度是生产管理系统关键的核心技术。单件车间调度问题是生产调度领域最为复杂的一类典型调度问题,由于其背景广泛存在于工业生产、医疗、交通、运输、通讯等领域中,同时也由于其调度模型可以看成是单机、并行机和流水车间调度等相对简单模型的一般化推广,因而对其建模和算法的研究,备受学术界和工业界的广泛关注,是公认的难题。由于一般的单间车间调度问题属于强NP-难问题,探讨问题的最优解极为困难。如果再考虑到生产环境的实时性和动态性等方面的特点,则大量问题成为NP-完全问题,即使是可行解有时也难以获得,因此探讨该类问题的可行的近似算法具有实际意义。本文针对一般单件车间调度问题、复杂单件车间调度问题、实时单件车间调度问题、动态反应单件车间调度问题,基于约束满足思想与理论,从增量构造式和重复修补式两大类方法,约束传播、搜索策略、启发式的集成与嵌入、学习机制四个方向研究约束满足技术,分别建立了相应问题的约束满足优化模型及约束网络结构模型,提出并设计了基于约束满足技术的求解算法。具体研究内容包括：1)基于增量构造式方法,通过分析传统运筹学方法与约束满足求解方法各自优缺点,提出集成约束传播技术和分支定界方法的混合求解策略,设计并构造带有时间窗口的分支定界搜索树,实现在每个树节点处的瞬时约束传播,并以最大完工时间最小化的单件车间调度问题为背景对提出的混合方法进行了应用研究。2)基于增量构造式方法,建立一种构造式的约束满足优化模型,提出并实现该问题模型的弧一致约束传播优化算法,并在搜索过程中的每个节点处,设计并嵌入多种动态加强约束传播技术,通过这些技术指导搜索节点的扩展方向的筛选,从而提高搜索效率。针对以最大完工时间最小化为目标的,带有公共释放期与交货期的单件车间调度问题,对所建立的模型和提出的算法进行应用研究。3)基于重复修补式方法,建立一种针对大规模优化问题的GENET网络结构约束满足优化模型,在GENET网络结构中,设计并构建记入新约束的约束传播框架,提出该模型的基于渐进式随机搜索模式的求解方法,并针对单件车间约束满足优化问题,进行应用研究,实现问题映射、约束网构造及修补式优化策略。4)基于重复修补式方法,针对问题中的研究对象,建立嵌入限定窗口约束的GENET网络结构约束满足优化模型,提出具有渐进式随机搜索模式、同时嵌入多种启发式的求解算法。针对以拖拉工件数最小化为目标的,工件带有不同释放期和交货期的单件车间调度问题,对提出的建模与优化方法进行应用研究。5)基于重复修补式方法,针对问题研究对象所需要的资源,建立嵌入多种形式不连续窗口约束的GENET网络结构约束满足优化模型,提出该模型的具有渐进式随机搜索模式、嵌入启发式的求解算法,并针对以平均拖拉量百分比最小化为目标的,具有单一停工和多次停工等三种机器无效约束情况下的单件车间调度问题,进行了应用研究。6)基于重复修补式方法,建立嵌入强制限定窗口约束（硬约束）的GENET网络结构约束满足优化模型,提出在此类网络模型中,实现多重优化目标的重复修补式搜索策略,以及嵌入启发式规则的学习方法。针对带有满足截止期和最大完工时间最小双重准则的单件车间在线实时调度问题,对所提出的方法进行应用研究,通过嵌入一个由最早截止期优先策略改良而来的启发式和一个优化机制,实现在满足截止期约束的前提下的调度目标最优化。7)基于重复修补式方法,建立具有对多重动态扰动调整与修复能力的GENET网络结构约束满足优化模型,提出一种可重复修补的局部搜索方法,实现使初始构造的原问题约束网络保持对外界多重动态扰动的调整与修复,并针对单件车间发生机器损坏和紧急工件双重扰动时,调度目标为在满足新调度的可行性的情况下,使新调度与原调度间的差别最小化的动态反应调度问题,进行了应用研究。8)针对现实中非二元约束满足问题的广泛存在,以及E-GENET在处理非二元约束满足问题上,既缺乏理论依据的支持,又缺少实际问题检验的情况,在对非二元约束满足问题和E-GENET网络模型能量函数进行新的数学定义基础上,将非二元约束满足问题转化为整数最小化问题,提出一类非二元变量约束关系的离散拉格朗日搜索模式与算法,建立E-GENET与离散拉格朗日乘子方法间的连接关系,对E-GENET进行重构与扩展,研究了E-GENET解决多元过约束问题求解原理,同时给出了相关的证明,并针对传统单件车间调度问题,进行应用研究。9)在上述研究的基础上,为了对提出的方法和进一步研究方法的有效性进行实验验证,探讨在工业应用的可能性,设计并使用VC++6.0开发了基于约束满足建模与技术的单件车间调度问题实验仿真软件平台。本文所提出的模型与算法均在该平台上进行了测试,验证了提出的模型和算法的有效性。

论文目录

• 摘要
• Abstract
• 目录
• 第一章 绪论
• 1.1 问题研究的目的和意义
• 1.1.1 问题的来源及研究目的
• 1.1.2 问题研究的背景与意义
• 1.2 约束满足问题及约束满足技术研究现状
• 1.2.1 约束满足思想来源
• 1.2.2 约束满足问题描述
• 1.2.3 约束满足求解原理
• 1.2.4 约束满足求解特点
• 1.2.5 约束满足技术及其研究现状
• 1.2.5.1 约束满足技术的分类
• 1.2.5.2 约束满足技术的综合运用
• 1.2.5.3 约束满足技术在调度问题中的应用
• 1.2.5.4 约束满足技术的应用分析
• 1.3 单间车间调度问题及其研究现状
• 1.3.1 问题的背景
• 1.3.2 问题的定义
• 1.3.3 问题的特点
• 1.3.4 问题的分类
• 1.3.5 问题的研究现状
• 1.3.5.1 一般单件车间调度问题研究现状
• 1.3.5.2 复杂单件车间调度问题研究现状
• 1.3.5.3 实时单件车间调度问题研究现状
• 1.3.5.4 动态反应单件车间调度问题研究现状
• 1.4 本文的研究路线及主要工作
• 1.4.1 本文的研究线路
• 1.4.2 本文的主要工作
• 第二章 构造式混合搜索CST及在传统JSSP的应用
• 2.1 引言
• 2.2 问题的描述与模型
• 2.2.1 问题的描述
• 2.2.2 线性规划模型
• 2.2.3 图模型
• 2.3 分支定界方法与CPT的基本思想
• 2.3.1 活动调度
• 2.3.1.1 优先分派启发式方法生成活动调度
• 2.3.1.2 随机分派启发式方法生产活动调度
• 2.3.2 分支定界方法
• 2.3.3 CPT策略
• 2.4 在分支定界方法中集成CPT的算法
• 2.4.1 带有时间窗口搜索树的构造
• 2.4.2 搜索树中的瞬时约束传播及死端学习
• 2.4.3 瞬时约束传播的削支过程
• 2.4.4 方法步骤与流程
• 2.5 实验结果与分析
• 2.6 本章小结
• 第三章 构造式约束满足优化CST及在JSCSOP的应用
• 3.1 引言
• 3.2 问题描述与模型
• 3.3 弧一致约束传播优化算法
• 3.3.1 约束传播与弧一致
• 3.3.2 初始化
• 3.3.3 搜索过程与活动调度构造
• 3.3.4 优化过程的实现
• 3.3.5 算法流程与应用举例
• 3.4 动态加强CPT方法
• 3.4.1 瞬时下界CPT（B-CPT）
• 3.4.2 可调度工序集同机工序CPT（C-CPT）
• 3.4.3 未调度工序集同机工序CPT（A-CPT）
• 3.5 实验结果与分析
• 3.6 本章小结
• 第四章 修补式约束满足优化CST及在JSCSOP的应用
• 4.1 引言
• 4.2 问题描述
• 4.3 GENET网络
• 4.3.1 网络结构
• 4.3.2 收敛方式
• 4.3.3 学习
• 4.3.4 渐进式随机搜索模式
• 4.4 求解方法
• 4.4.1 初始化
• 4.4.2 网络构造
• 4.4.3 搜索策略
• 4.4.4 实现优化
• 4.5 实验结果与分析
• 4.6 本章小结
• 第五章 修补式限定窗口约束CST及在带有不同释放期与交货期JSSP的应用
• 5.1 引言
• 5.2 公式化问题
• 5.3 GENET模型
• 5.3.1 连接结构
• 5.3.2 运行机制与PSS方式
• 5.4 方法描述
• 5.4.1 网络构造
• 5.4.2 启发式与嵌入方法
• 5.5 实验研究
• 5.6 本章小结
• 第六章 修补式不连续窗口约束CST及在带有机器无效约束JSSP的应用
• 6.1 引言
• 6.2 问题的描述与模型
• 6.3 问题求解
• 6.3.1 网络模型
• 6.3.2 搜索策略
• 6.4 实验研究
• 6.4.1 实验设计
• 6.4.2 实验结果
• 6.5 本章小结
• 第七章 修补式硬约束多目标CST及在在线实时JSSP的应用
• 7.1 引言
• 7.2 问题描述与模型
• 7.3 网络调度方法
• 7.3.1 网络模型
• 7.3.2 能量函数与收敛
• 7.3.2.1 排序约束和重叠约束
• 7.3.2.2 截止期约束
• 7.3.2.3 可调整的辅助准则约束
• 7.4 实验研究
• 7.4.1 实验设计
• 7.4.2 结果与分析
• 7.5 本章小结
• 第八章 修补式抗多重扰动CST及在动态反应JSSP的应用
• 8.1 引言
• 8.2 问题描述
• 8.3 问题求解
• 8.3.1 构造预调度网络
• 8.3.2 扰动与网络修正
• 8.3.3 优化修补调度
• 8.4 实验研究
• 8.5 本章小结
• 第九章 非二元约束CST原理及在JSCSOP的应用
• 9.1 引言
• 9.2 预备知识
• 9.2.1 NB-CSPs定义
• 9.2.2 E-GENET方法
• 9.3 NB-CSPs的离散拉格朗日函数
• 9.3.1 能量函数重定义
• 9.3.2 将NB-CSPs转化为整数最小化问题
• 9.3.3 NB-CSPs的离散拉格朗日乘子方法（NB-LSDL）
• 9.4 E-GENET重构
• （E-GENET）'>9.4.1 NB-LSDL_{（E-GENET）}
• 9.4.2 基于NB-LSDL的E-GENET再扩展
• 9.5 求解单件车间约束满足优化问题
• 9.6 本章小结
• 第十章 基于约束满足调度问题研究平台开发
• 10.1 引言
• 10.2 开发背景和目标
• 10.3 平台设计思想
• 10.4 平台设计方案
• 10.4.1 问题库管理
• 10.4.2 算法函数库
• 10.4.3 计算结果处理
• 10.5 开发环境
• 10.6 平台设计成果
• 10.7 本章小结
• 第十一章 结束语
• 参考文献
• 致谢
• 作者攻博期间撰写的论文
• 作者攻博期间参与科研情况
• 作者简介