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

《约束满足技术的研究及在生产调度中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、博士学位论文1934808约束满足技术的研究及在生产调度中的应用冯欣二00七年十二月／；蝎子◎姒球，≯j‘≯●p7’!．-_、‘＼分类号UDC密级学位论文约束满足技术的研究及在生产调度中的应用作者姓名冯欣-盘三垦盘堂堑速丝垡鱼撞剑堑寇堑申请学位级别谴±学科类别三堂学科专业名称系统工程论文提交日期上迦2生12月论文答辩日期2QQ墨生童旦学位授予日期，答辩委员会主席j遮越曼评阅人—弛j：笙生歪华东北大学2007年12月●·I＼'lj1●■■■■，瀣糯雩一‘。上ADissertationfortheDegreeofDoctorin．Syste

2、msEngineeringStudyontheConstraintSatisfactionTechniqueandItsApplicationforProductionSchedulingByFengXinSupervisor：ProfessorTangLixinNortheasternUniversityDecember2007▲rf一．F^声明尸明本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作

3、的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：呕彼日期：2印留．弓．，o学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。学位论文作者签名：日期：另外，如作者和导师不同意网上交流，请在下方签名；否则视为罔j匕l口J思。学位论文作者签名：导师签名：签字日期：、1；≯’●◆?奄～_'f_、东北大学博士学位论

4、文摘要约束满足技术的研究及在生产调度中的应用摘要生产管理是提高现代生产企业生产效率和经济效益的重要手段。生产调度是生产管理系统关键的核心技术。单件车间调度问题是生产调度领域最为复杂的一类典型调度问题，由于其背景广泛存在于工业生产、医疗、交通、运输、通讯等领域中，同时也由于其调度模型可以看成是单机、并行机和流水车间调度等相对简单模型的一般化推广，因而对其建模和算法的研究，备受学术界和工业界的广泛关注，是公认的难题。由于～般的单间车间调度问题属于强NP．难问题，探讨问题的最优解极为困难。如果再考虑到生产环境的实时性和动态性等方面的特点，则大

5、量问题成为NP．完全问题，即使是可行解有时也难以获得，因此探讨该类问题的可行的近似算法具有实际意义。本文针对一般单件车间调度问题、复杂单件车间调度问题、实时单件车间调度问题、动态反应单件车间调度问题，基于约束满足思想与理论，从增量构造式和重复修补式两大类方法，约束传播、搜索策略、启发式的集成与嵌入、学习机制四个方向研究约束满足技术，分别建立了相应问题的约束满足优化模型及约束网络结构模型，提出并设计了基于约束满足技术的求解算法。具体研究内容包括：1)基于增量构造式方法，通过分析传统运筹学方法与约束满足求解方法各自优缺点，提出集成约束传播技

6、术和分支定界方法的混合求解策略，设计并构造带有时间窗口的分支定界搜索树，实现在每个树节点处的瞬时约束传播，并以最大完工时间最小化的单件车间调度问题为背景对提出的混合方法进行了应用研究。2)基于增量构造式方法，建立一种构造式的约束满足优化模型，提出并实现该问题模型的弧一致约束传播优化算法，并在搜索过程中的每个节点处，设计并嵌入多种动态加强约束传播技术，通过这些技术指导搜索节点的扩展方向的筛选，从而提高搜索效率。针对以最大完工时间最小化为目标的，带有公共释放期与交货期的单件车间调度问题，对所建立的模型和提出的算法进行应用研究。．II—jr东

7、北大学博士学位论文摘要3)基于重复修补式方法，建立一种针对大规模优化问题的GENET网络结构约束满足优化模型，在GENET网络结构中，设计并构建记入新约束的约束传播框架，提出该模型的基于渐进式随机搜索模式的求解方法，并针对单件车间约束满足优化问题，进行应用研究，实现问题映射、约束网构造及修补式优化策略。4)基于重复修补式方法，针对问题中的研究对象，建立嵌入限定窗口约束的GENET网络结构约束满足优化模型，提出具有渐进式随机搜索模式、同时嵌入多种启发式的求解算法。针对以拖拉工件数最小化为目标的，工件带有不同释放期和交货期的单件车间调度问题

8、，对提出的建模与优化方法进行应用研究。5)基于重复修补式方法，针对问题研究对象所需要的资源，建立嵌入多种形式不连续窗口约束的GENET网络结构约束满足优化模型，提出该模型的具有渐进式随机搜索模式、嵌入启发式