资源描述：
《基于时间约束网络的动态规划调度算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第10卷第1期计算机集成制造系统)CIMSVol.10No.22004年2月ComputerIntegratedManufacturingSystemsFeb.2004文章编号:1006-5911(2004)02-0188-07基于时间约束网络的动态规划调度算法1,212徐瑞,徐晓飞,崔平远(1.哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨150001;2.哈尔滨工业大学航天学院,黑龙江哈尔滨150001)摘要:为解决与时间有关的规划调度问题,提出了一种基于时间约束网络的动态算法。该算法与传统的计算最短路径方法不
2、同,它只需计算受到新增约束影响的局部网络。同时,给出了算法的最坏时间复杂性,并进行了证明。最后,以Job-Shop调度系统为例进行了仿真验证,结果表明,该算法可快速地判断约束网络的一致性,并计算每个工序的最早可能开始时间。关键词:时间约束网络;规划调度;动态算法;最短路径中图分类号:TP18文献标识码:A[5]的Floyd-Warshall算法。该方法是在时间约束0引言网络为静态情况下的算法,但是对于规划调度系统,从1983年Allen开创性地提出时间区间知识表活动和约束的改变导致了约束网络的动态变化,若[1]示方法
3、之后,时间约束处理技术便在人工智能领域仍然采用Floyd-Warshall算法,必然导致计算量的中日益受到关注。近十年来,该方面的研究取得了引大量增加。本文根据规划调度系统动态变化的特人注目的成绩,并在计算机许多相关领域中得到了广点,分析规划调度过程中约束出现的形式,在图论中泛应用,例如,计算机集成制造系统(CIMS)、计算机最短路径理论的基础上,给出一种动态时间约束网[2,3]辅助设计系统(CAD)、规划调度系统、时态数据库络算法,该算法的时间复杂性在最坏的情况下是O[4]系统、自然语言处理、常识推理和探测器任务规
4、(2ne)。仿真结果表明,该算法可以快速地判断时[5]划等。并且提出了许多形式化描述和推理时间约间约束网络的一致性,并计算出各个活动(工序)的[6~8][1]束的方法,主要有时间区间代数方法、时间点最早可能开始时间和它们之间的时间关系。代数方法、线性不等式组方法、时间图方法以及和时1问题描述及时间约束网络间约束网络方法等。每一种不同的描述方法都有相应的一些约束传播方法来支持。在人工智能领域中,许多问题可以转化为约束时间约束网络是对具有时间知识和时间约束系满足问题来解决。时间约束满足问题是约束满足问统进行描述和推理的有
5、效方式和手段,它将图论中题中的一个特例,它主要处理和时间知识密切相关处理问题的思想引入到约束满足问题的求解中。时的一类问题,例如规划调度等。时间约束网络是描间约束网络中的顶点表示所要计算的时间变量,顶述和求解这类问题的有效方法。点之间的连接弧表示时间变量之间的约束关系。111问题描述Dechter等给出了时间约束网络的基本概念和常用我们所讨论的规划调度问题是在不违反多种时收稿日期:2003-01-13;修订日期:2003-06-16。基金项目:国防科工委民用航天资助项目。作者简介:徐瑞(1975-),男,河南南阳人,
6、哈尔滨工业大学计算机科学与技术学院博士研究生,主要从事规划与调度、智能优化算法、分布式人工智能、系统建模与仿真等方面的研究。E-mail:xurui@hit.edu.cn。第2期徐瑞等:基于时间约束网络的动态规划调度算法189间约束的条件下选取活动,并调度各自的开始时间束{aij[Xj-Xi[bij},其中,0[aij[bij。和结束时间,使其在执行后能够达到所要求的目标。对于这样的问题,可以用有向约束图G(V,E)这里,活动是系统能够执行的一个基本动作,它占用来表示,其中,V为顶点的集合,每个顶点表示时间一定的时间
7、和资源;时间约束是多个活动之间的时点变量;E为边的集合,边iyj表示约束Cij,其每间关系,例如,活动A必须在活动B开始之前的10一边iyj仅标注了一个区间[aij,bij],它表示约束个时间单位内结束,活动D必须在活动A结束后为aij[Xj-Xi[bij。该约束还可以表示为一对不20个时间单位内开始等。为了更加清楚地描述与等式的形式:时间有关的规划调度问题,首先给出一般时间约束Xj-Xi[bij(2)问题的定义。Xi-Xj[-aij定义1时间约束问题定义为一组有限变量集这样,求解简单时间约束问题可归结为求解一组关合
8、X={X1,X2,,,Xn}和一组变量上的约束{C1,于Xi的线性不等式。C2,,,Cn}。每个变量代表一个时间点,变量之间求解线性不等式组的方法在运筹学中已经进行的约束代表时间点之间的时间关系。了非常深入地研究,给出了许多求解方法,例如,椭[1]每个约束根据Allen提出的时间区间理论,球算法及其系列改进、单纯形方法和内点方法等。可以描述为区
