学位论文 > 优秀研究生学位论文题录展示

基于约束的调度系统的设计与实现

作　者: 礼欣
导　师: 孙吉贵
学　校: 吉林大学
专　业: 计算机应用技术
关键词: 基于约束调度系统约束程序调度问题设计与实现运筹学方法时态约束人工智能方法资源约束求解器
分类号: TP311.52
类　型: 硕士论文
年　份: 2004年
下　载: 159次
引　用: 2次
阅　读: 论文下载

内容摘要

调度问题起源于产品规划、人力规划、计算机设计、时间表等问题。随着时间的推移，对调度问题的理论及其应用研究已经成为一项重要的研究领域。粗略地讲，传统的调度研究方法有两个主要分支：一支是运筹学方法（OR：Operation Research）；另一支是人工智能方法（AI：Artificial Intelligence）。对于那些结构化调度问题，OR方法可以建立起较为严格的数学模型，对这些调度问题的数学模型的组合结构的透彻研究，使得OR方法在求解问题的过程中在算法上达到极高的效率。然而当用这些经典的数学模型建模一些实际的调度例子时，OR方法多少感到力不从心了。若强制建模，则不得不忽略实际调度问题中的很多自由度和副约束。抛弃自由度将会导致一些解的丢失，而通过抛弃副约束来简化问题和问题的求解将最终导致与原始问题解的偏离。相比之下AI方法关注的是更加广泛的调度模型，并且试图用通用的问题求解机制来解决问题，然而过多地关注通用性，必然导致在一些特殊问题的求解效率上逊色于运筹学方法。显然我们想要的是通用的模型以及能提供给模型的高效的求解算法，自然的我们想到将运筹学方法的效率与人工智能方法的通用性结合起来，而约束程序（CP：Constraint Programming)提供的通用建模和求解机制与运筹学算法的集成满足了这一要求。一般来说，约束程序关注的是求解一个约束满足问题（CSP）的实例,一个CSP的实例包括一组变量的集合，在每一个变量上规定指派的论域，以及在这些个变量之上的一组约束的集合。约束表示的是一个变量或多个变量之间的关系，例如：如果x是一个整型变量，x<10就是变量x上的一个约束。求解一个CSP的实例包含着为变量分配值来同时满足所有约束关系的过程。在约束程序中，约束的存在用来减少那些需要求解的问题的计算量。具体的讲就是使用约束来缩小问题的论域并且检测不相容，这个演绎的过程就叫做约束的传播。加、减、乘、大于、小于、等于、与和或构成了基于约束的通用求解器的主要约束，时态约束与资源约束则是基于约束的调度系统的两大约束。运用约束程序设计思想来求解组合优化问题，特别是各类调度问题,我们称之为基于约束的调度（CBS:Constraint-Based Scheduling）。约束程序的一个主要特征就是以自然，直观的方式描述问题，这样问题的描述也就同时为问题的声明定义所服务，这种问题的描述与问题的定义的符合也就保证了约束的解可以并且一定能够解决定义的问题，基于约束的调度系统也体现了CP建模与问题求解相分离的特点。CP使得调度系统具有精确性、高效性、灵活性和可扩充性。系统的精确性和灵活性体现在约束程序语言可表达任意约束；高效性是因为现在已经有适合调度问题要求的最优化的传播技术；可扩充性是在考虑一个新类型的约束时（特别是在面向对象框架中）只需要对约束系统进行扩展，或者在最坏情况下，只需实现额外的决策模块（不必修改已有的代码）。我们所研发的基于约束的调度求解器Scheduler是基于通用约束求解器Solver<WP=65>之上的面向对象的和约束程序的系统。它的类库框架通过把约束集成到面向对象的程序设计语言（C++）中，将约束、变量和求解器都作为实体，基于约束程序设计的思想，使用预定义的约束集合和通用的求解器来有效地解决组合优化和调度问题。使得开发基于约束的调度和资源分配的应用程序更加容易。它提供了一些特殊的机制来求解调度和资源分配问题。例如：一些类的建立是用来描述调度问题本身的一些方面如活动，资源，时态约束等等，同时它也可以使用Solver中提供的变量，约束等来表达特殊约束，实现特定的问题求解策略。我们设计的基于约束的调度系统的目标是简化工业调度应用程序的开发。通过对原有的约束求解器Solver的扩展，设计和实现了多种机制联合求解的一元资源约束处理算法，和一种通用离散资源约束传播算法，并实现了调度结果的图形化界面展示，从而建立起一个较为完善的调度问题求解系统。系统提供了描述现实调度中调度，活动和资源的类（例如：调度类，不可中断的活动类，一元资源类，多元资源类）还包括三种预定义约束：时态约束，容量约束，资源使用约束。为处理资源使用约束提供多种机制，时间表机制：依赖于析取约束来确保那些不相容的约束在时间上不能相互重叠（例如：那些需求容量为一的公共资源的活动）；edge-finding机制：它通过考虑有n个活动的活动集合{A1 …An}中的任意元组，来证明某个活动Ai是否必须在集合{A1 …An}中的第一个或最后一个执行.edge-finding机制的扩展是not-first,not-last机制用以判定某个活动Ai一定不在活动集合{A1 …An}中第一个或最后一个执行。edge-finding机制比前两种机制更耗费CPU时间，但是会导致为活动分配更加精确的最早（最晚）开始（结束）时间。以上的几种机制都很有效，析取机制可以表达更加更广泛的约束类，而edge-finding机制通常在搜索空间的剪枝上更为有效。此外还提供了一些简单的最优化调度的方法（例如：二分法）；用户还可以广泛选择决策变量，例如整型、布尔型等；用户也可通过扩展预定义类来增加新约束。系统采用问题表示与问题求解分离的设计原则，这样做的好处是用

全文目录

第一章绪论  7-9
  1.1 研究背景及意义  7
  1.2 研究现状  7-8
  1.3 本文主要工作  8-9
第二章约束求解及约束程序  9-16
  2.1 约束  9
  2.2 约束满足问题及其求解方法  9-14
    2.2.1 约束满足问题  9-10
    2.2.2 CSP求解技术  10-14
      2.2.2.1 系统搜索方法  10-11
      2.2.2.2 相容性技术  11-12
      2.2.2.3 约束传播方法  12-13
      2.2.2.4 约束满足优化问题  13-14
  2.3 约束程序设计  14-16
    2.3.1 概念  14-15
    2.3.2 实现方式  15-16
第三章基于约束的调度  16-19
  3.1 调度问题  16-17
  3.2 基于约束的调度  17-19
第四章基于约束调度系统的详细描述与实现  19-32
  4.1 设计思想  19
  4.2 系统体系结构  19
  4.3 Solver设计说明  19-21
  4.4 Scheduler设计说明  21-27
  4.5 系统中使用的相容性技术  27-30
  4.6 求解方法  30-32
第五章调度中的约束及约束传播  32-47
  5.1 时态约束及时态约束传播  32-33
    5.1.1 时态约束  32
    5.1.2 时态约束传播  32-33
  5.2 资源约束及资源约束的传播  33-47
    5.2.1 资源容量约束及其传播  33-35
      5.2.1.1 资源容量约束  33
      5.2.1.2 资源容量约束传播  33-35
    5.2.2 资源使用约束及其传播  35-47
      5.2.2.1 资源使用约束  35
      5.2.2.2 资源使用约束传播  35-47
        5.2.2.2.1 一元资源上的时间表机制  35-37
        5.2.2.2.2 一元资源上的析取约束机制  37-38
        5.2.2.2.3 一元资源上的Edge-Finding机制  38-41
        5.2.2.2.4 一元资源上的Not-First/Not-Last机制  41-43
        5.2.2.2.5 一元资源上的Energetic Reasoning机制  43-45
        5.2.2.2.6 多元资源上的Edge-Finding机制  45-47
第六章基于约束的调度优化  47-50
第七章测试实例及实验结果  50-61
第八章结语  61-62
  8.1 系统评价  61
  8.2 今后的工作  61-62
参考文献  62-64
摘要  64-66
ABSTRACT  66-68

基于约束的调度系统的设计与实现

内容摘要

全文目录

相似论文