基于时间约束网络的动态规划调度算法.pdf

《基于时间约束网络的动态规划调度算法.pdf》由会员分享，可在线阅读，更多相关《基于时间约束网络的动态规划调度算法.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 10 卷第 1 期计算机集成制造系统)CIMSVol.10 No.22 0 0 4 年 2 月Computer Integrated Manufacturing SystemsFeb.2 004文章编号:1006-5911(2004)02-0188-07基于时间约束网络的动态规划调度算法徐 瑞1,2,徐晓飞1,崔平远2收稿日期:2003-01-13;修订日期:2003-06-16。基金项目:国防科工委民用航天资助项目。作者简介:徐 瑞(1975-),男,河南南阳人,哈尔滨工业大学计算机科学与技术学院博士研究生,主要从事规划与调度、智能优化算法、分布式人工智能、系统建模与仿真等方面的研究。E

2、-mail:xurui 。(1.哈尔滨工业大学计算机科学与技术学院,黑龙江 哈尔滨 150001;2.哈尔滨工业大学航天学院,黑龙江 哈尔滨 150001)摘 要:为解决与时间有关的规划调度问题,提出了一种基于时间约束网络的动态算法。该算法与传统的计算最短路径方法不同,它只需计算受到新增约束影响的局部网络。同时,给出了算法的最坏时间复杂性,并进行了证明。最后,以 Job-Shop 调度系统为例进行了仿真验证,结果表明,该算法可快速地判断约束网络的一致性,并计算每个工序的最早可能开始时间。关键词:时间约束网络;规划调度;动态算法;最短路径中图分类号:TP18 文献标识码:A0 引言从 1983年

3、 Allen开创性地提出时间区间知识表示方法1之后,时间约束处理技术便在人工智能领域中日益受到关注。近十年来,该方面的研究取得了引人注目的成绩,并在计算机许多相关领域中得到了广泛应用,例如,计算机集成制造系统(CIMS)、计算机辅助设计系统(CAD)、规划调度系统 2,3、时态数据库系统4、自然语言处理、常识推理和探测器任务规划5等。并且提出了许多形式化描述和推理时间约束的方法 6 8,主要有时间区间代数方法1、时间点代数方法、线性不等式组方法、时间图方法以及和时间约束网络方法等。每一种不同的描述方法都有相应的一些约束传播方法来支持。时间约束网络是对具有时间知识和时间约束系统进行描述和推理的有

4、效方式和手段,它将图论中处理问题的思想引入到约束满足问题的求解中。时间约束网络中的顶点表示所要计算的时间变量,顶点之间的连接弧表示时间变量之间的约束关系。Dechter 等给出了时间约束网络的基本概念和常用的 Floyd-Warshall 算法 5。该方法是在时间约束网络为静态情况下的算法,但是对于规划调度系统,活动和约束的改变导致了约束网络的动态变化,若仍然采用 Floyd-Warshall 算法,必然导致计算量的大量增加。本文根据规划调度系统动态变化的特点,分析规划调度过程中约束出现的形式,在图论中最短路径理论的基础上,给出一种动态时间约束网络算法,该算法的时间复杂性在最坏的情况下是 O(

5、2ne)。仿真结果表明,该算法可以快速地判断时间约束网络的一致性,并计算出各个活动(工序)的最早可能开始时间和它们之间的时间关系。1 问题描述及时间约束网络在人工智能领域中,许多问题可以转化为约束满足问题来解决。时间约束满足问题是约束满足问题中的一个特例,它主要处理和时间知识密切相关的一类问题,例如规划调度等。时间约束网络是描述和求解这类问题的有效方法。111 问题描述我们所讨论的规划调度问题是在不违反多种时间约束的条件下选取活动,并调度各自的开始时间和结束时间,使其在执行后能够达到所要求的目标。这里,活动是系统能够执行的一个基本动作,它占用一定的时间和资源;时间约束是多个活动之间的时间关系,

6、例如,活动 A 必须在活动 B 开始之前的 10个时间单位内结束,活动 D 必须在活动 A 结束后20个时间单位内开始等。为了更加清楚地描述与时间有关的规划调度问题,首先给出一般时间约束问题的定义。定义 1 时间约束问题定义为一组有限变量集合 X=X1,X2,Xn 和一组变量上的约束 C1,C2,Cn。每个变量代表一个时间点,变量之间的约束代表时间点之间的时间关系。每个约束根据 Allen 提出的时间区间理论1,可以描述为区间的形式:I1,I2,In=a1,b1,a2,b2,an,bn(1)对于实际问题,变量可以代表各个活动的开始时间点和结束时间点。例如,活动 A 的开始和结束时间点分别为A-

7、和 A+,活动 B 的开始和结束时间点分别为B-和 B+,则前面的约束可以表示为 0 A+-B-10,即约束 Ci可表示为区间 0,10的形式。定义 2 时间约束问题的解。当赋值X1=a1,X2=a2,Xn=an满足所有的约束时,元组 X=(a1,a2,an)为时间约束问题的解。对于一般的时间约束问题,如果每一对变量的约束区间很多,而且约束区间是连续时,计算一致性后的总的区间的个数与每对变量的区间数呈指数关系增加,即所谓的区间碎裂化,给求解带来很大困难。而简单时间约束问题不会产生这个问题,因此,在求解一般时间约束问题一致性时,往往将其转化为简单时间约束问题来求解。而且实际中的许多问题也可以直接

8、用简单时间约束问题来描述和求解,例如规划问题和车间调度问题等。本文就是在简单时间约束问题的基础上来对相关的问题进行讨论。112 简单时间约束问题对于存在二元时间约束关系的问题,通常采用简单时间约束问题来描述和计算。下面首先给出简单时间约束问题的定义以及相关理论。定义 3 当一个时间约束满足问题的所有两个时间点之间的约束都仅是一个区间时,就称为简单时间约束问题。简单时间约束问题同样包括一组具有一定连续域的时间点变量 X1,Xn 和一组约束 aij Xj-Xi bij,其中,0 aij bij。对于这样的问题,可以用有向约束图 G(V,E)来表示,其中,V 为顶点的集合,每个顶点表示时间点变量;E

9、 为边的集合,边 i y j 表示约束 Cij,其每一边 i yj 仅标注了一个区间 aij,bij,它表示约束为 aij Xj-Xi bij。该约束还可以表示为一对不等式的形式:Xj-XibijXi-Xj-aij(2)这样,求解简单时间约束问题可归结为求解一组关于 Xi的线性不等式。求解线性不等式组的方法在运筹学中已经进行了非常深入地研究,给出了许多求解方法,例如,椭球算法及其系列改进、单纯形方法和内点方法等。这些方法在实际数值计算中都获得了很好的效果。这里,采用一种图形式来表示这组线性不等式,称之为时间网络图。这个概念是 Dean 和 Mcdermott 首次提出的。时间图采用一个有向加权

10、图 Gd=(Vd,Ed)来描述简单时间问题。为了区别,Gd称为距离图。图中的顶点仍是时间点的集合,边 i yj 标注权值bij,表示线性不等式 Xj-Xi bij;边 j y i 标注权值-aij,表示线性不等式 Xi-Xj-aij,如图 1 所示。Gd图中从i 到j 的每一个路径 i0=i,i1,ik=j,导致在 Xj-Xi上存在约束公式:Xj-XiEkj=1aij-1,ij(3)如果从 i 到j 存在多条路径,则:Xj-Xidij(4)这里,dij是从 i 到 j 的路径中最短的一条路径的长度。在给定约束网络之后,我们希望获得构成的网络是否一致的信息,即对应的时间约束问题是否存在解。如果网

11、络是一致的,希望得到问题的可能解。根据解可以回答以下关心的问题:时间点 xi可能在什么时间出现?时间点 xi和时间点 xj之间存在什189第 2期徐 瑞 等:基于时间约束网络的动态规划调度算法么样的关系?转化为规划调度中的问题即为:活动ai什么时候可以开始执行?活动 ai和活动aj之间存在什么样的关系?文献 5 中给出了以下几个简单时间约束网络的相关定理和推论。引理 1 给定简单时间约束网络是一致的,当且仅当它的距离图 Gd没有负环存在。该定理给出了判断简单时间问题是否有解的一种方法,时间约束网络算法就是根据这个定理设计的。引理 2 假设 Gd是一致的简单时间约束网络,可给定两种一致情况:S1

12、=(d01,d0n)S2=(-d10,-dn0)(5)它们分别将变量赋值为最迟和最早可能时间。引理 3 任何一致的简单时间约束问题,相对于它最短距离图中的约束是可分解的(可分解性)。该定理给出了一种构造简单时间问题解的有效方法。引理 4 令 Gd是一致的简单时间约束问题的距离图,变量 Xi的可能值的集合是-di0,d0i。由这个推论可以求得时间点可能的时间范围,即-di0 Xi d0i。根据最小时间网络图,可以很方便地得到时间点的最小范围,即约束区间的最小范围。113 规划调度过程中的时间约束网络如前所述,将规划调度问题每个可能执行活动的开始时间和结束时间看作时间点,从而建立起规划调度问题中活

13、动之间的时间约束。例如,有一时间约束规则为/活动 A 在活动B 执行之前 3,10秒内执行结 束0,假定活动 A 的开始时间 点是start A,结束时间点是 endA,活动 B 的开始时间点是startB,结束时间点是 endB,活动 A 的持续时间为 10,20 秒,活动 B 的持续时间是 5,15 秒,则这四个时间点之间存在如下关系:10 endA-startA 205 endB-start B 203 startB-endA 10 规划调度中就是根据这样的时间关系,建立起系统的简单时间约束网络。当一个新的活动加入时,通过简单时间约束网络来判断新加入的活动与已存在的活动在时间上是否一致,

14、如果一致,便可以求得各个时间点的取值范围。但是,规划调度过程中的简单时间约束网络是动态变化的,随着活动的增加或时间约束的增加,时间约束网络也不断变化。以前求解这种动态变化时间约束网络的方法是,当系统中网络的某一部分发生变化时,便重新对网络中的所有约束进行处理,得到各个时间点的可能的取值区间,例如,Floyd-Warshall 算法。但是网络的局部变化不一定影响到整个网络,对网络中的每个点求解是没有必要的。我们只需在前一次求解的基础上,将受到影响的点重新进行计算,便可以得到新的解,这也正是本文的出发点。下面对规划调度过程中可能出现的情况进行分析。假设距离图 Gd(Vd,Ed)是已经求解的距离图,

15、Cij是新增加的一个时间约束,表示为 aij Xj-Xi bij(0 aij bij),即Xj-XibijXi-Xj-aij(6)这时新加入的约束有以下三种情况:(1)Xi,Xj两个端点都不属于图Gd中的端点,即Xi,Xj|Vd(如图 2a)。(2)Xi,Xj两个端点有一个属于图Gd中的端点,即 XiI Vd或XjI Vd(如图 2b)。(3)Xi,Xj两个端点都属于图 Gd中的端点,即Xi,XjI Vd(如图 2c)。以上三种情况实际上是对应增加两个顶点、增加一个顶点和不增加顶点而只改变约束的情况。在上述三种情况中,加入新的约束时,第一种和第二种情况对前一步所求出的最短距离图不产生影响。当第

16、三种情况的约束加入后,前一步所求出的最短距离图将发生改变。下面分别对这三种情况进行说明:第一种情况下,新加入的两个点与前面求得的距离图是分离的,显然,对已经求出的距离图不产生影响,Xi和Xj与其他任何属于 Gd中的顶点之间的距离都是无穷大,即 d0i=di0=d0j=dj 0=。第二种情况下,在新加入的约束中,有一个顶点(假定是顶点 Xi)是属于前一步求得的距离图 Gd,而且已知新加入的约束条件 aij Xj-Xi bij(0190计算机集成制造系统)CIMS第 10 卷aij 0,因此,前一步 Gd中所有 dk0和 d0k(XkIVd)均不改变,且:d0j=d0i+bijdj 0=-aij+

17、di0(7)第三种情况下,新加入的约束的两个顶点均是前一步求得的距离图 Gd中的两个点,即没有新加入顶点,只是改变了相应两个顶点之间的约束关系,这样,它必然影响所有经过这两个点的最短路径。因而需要重新计算相关的点。对于规划调度系统中时间约束网络的上述三种情况,我们没有必要对第一和第二种情况进行过多地处理,仅需考虑第三种情况,并考虑其中相应受到影响的顶点,从而减少了计算量。根据有关改进的最短路径算法 9,本文提出了动态时间约束网络算法。2 基于时间约束网络的规划调度算法对于规划调度系统,给定时间约束问题的网络描述,最常用的算法是 Floyd-Warshall 的每对顶点间的最短路径算法 10,该

18、算法如图 3 所示。最短路径算法 for i=1Bn dij=0 for i,j=1Bn dij=aij for k=1Bn for i=1Bn for j=1Bn dij=min(dij,dik+dkj)图 3 每对顶点间的最短路径算法 这种算法结构简单、定义明确,可以很方便地对时间约束网络进行计算,从而由引理 4 确定网络中各个时间点的范围,以及时间点之间的可能关系。根据引理 1,可以通过检查对角线元素 dii的情况来确定网络的一致性。从图 3 中可以看出,这种算法的时间复杂性是 O(n3),其中,n 是顶点的个数。上述算法对于静态的时间约束问题可以得到满意的解,但是,对于规划调度系统而言

19、,随着规划的进行,需要不断地加入活动或改变一些约束条件,从而导致时间约束网络的不断变化,每次改变都需要重新检查一遍网络的一致性,即重复一遍上述的算法,这样,会大大增加算法的计算量。当规划调度系统中的活动很多时(即约束网络中的顶点和边很多时),上述算法必将降低规划调度算法效率。为了能快速地得到问题的解,根据对时间约束网络和规划调度过程中约束网络变化情况的分析,可以采用递推的方法来计算时间约束问题的解,即当有新的活动加入时,仅仅计算与新增活动相关的一些时间变量的范围。该算法的输入是图 Gd和新的约束 Cij(Cij为aij Xj-Xi bij),输出是网络是否一致和每个时间点的新的可能值区间。其算

20、法如图 4 所示。动态递推算法(Gd(Vd,Ed),Cij)判断新加入约束 Cij的两个顶点(Xi,Xj)是否属于上一步已经计算的距离图 Gd(Vd,Ed)中的顶点:(1)如果两个顶点中都不属于距离图 Gd(Vd,Ed)中的顶点,即Xi,Xj|Vd,则:d0i=di0=d0j=dj0=(2)如果两个顶点中有一个顶点(假设为 Xi)属于距离图 Gd(Vd,Ed)中的顶点,即 XiI Vd或Xj|Vd,则:d0j=d0i+bij,if d0j+dj0 0 then exit(fail)dj0=-aij+di0,if dj0+d0j 0 then exit(fail)(3)如果两个顶点都属于距离图

21、Gd(Vd,Ed)中的顶点,即 Xi,XjIVd,则:调用递推算法(Gd(Vd,Ed),Cij)图 4 时间约束网络动态递推算法主程序 该算法根据上节分析中给出的三种情况分别进行处理,前两种情况很容易得到,第三种情况是由图5 中所示的动态递推算法子程序来实现的。该动态算法的输入 Gd(Vd,Ed)为上一步已经计算出的时间约束网络距离图(此时源点 X0到每一个顶点 Xk的最短距离d0k和dk0已求出),Cij为新增约束。算法的输出是最短距离数组 D 和 D-,(D用来记录源点到每个顶点的最短距离值 d0i,D-用来记录每个顶点到源点的最短距离值 di0)。我们用一个队列 Queue 来记录受到影

22、响的顶点,用矩阵 L来记录时间约束网络的边的权值,其中 lij表示连接i,j 两个顶点的边的权值。对于 Gd中的一个顶点Xi,EOut(i)定义为离开顶点 Xi的边,其离开该顶点边的总数称为出度;EIn(i)定义为到达顶点 Xi的边,到达该顶点的边的总数称为入度。X0是 Gd的参考顶点,每一个顶点 u IVd,有 Forward(u)和Backward(u)两个标示,用于区分图中计算的方向。191第 2期徐 瑞 等:基于时间约束网络的动态规划调度算法具体算法如下:动态递推算法子程序(Gd,Cij)(1)Queuez i,j /将新加入约束的两个顶点放入队列(2)Forward(i)=Backw

23、ard(i)=Forward(j)=Backward(j)=True/将两个顶点的前向计算和后向计算的标志置为真(3)While Queue 不为空 w z Queue/取出队列的第一个元素(4)if Forward(w)then/进行前向计算(5)for each(w,v)in EOut(w)do/对该顶点的每一条出边进行计算(6)if dow+lwv dov/判断 dov 是否受影响(7)dov=dow+lwv/改变 dov 的值(8)if dov+dvo 0 then ex it(fail)/判断是否存在负环路 Forward(v)=True/将受影响的顶点的前向计算标志置为真(9)If

24、 v|Queue then Queue z v /如果受影响的顶点不在队列中,将其加入队列 (10)if Backward(w)then/进行后向计算(11)for each(w,v)in EIn(w)do/对顶点的每一条入边计算(12)if dwo+lvw dvo /判断 dvo 是否受影响(13)dvo=dwo+lvw/改变 dvo 的值(14)if dov+dvo 0 then ex it(fail)/判断是否存在负环路 Backward(v)=T rue /将受影响的顶点的后向计算标志置为真(15)if v|Queue then Queue zv /如果受影响的顶点不在队列中,将其加入

25、队列 (16)Backward(w)=False Forward(w)=False /将该顶点的前向和后向计算标志全置为假(17)Out(D,D-)/输出结果图 5 时间约束网络动态递推算法子程序(新加入约束的顶点均在原来图中的情况)图 5 中(1)(9)部分计算的是距离数组 D,(10)(17)部分计算的是距离数组 D-。其中,步骤(8)和(14)判断 dov+dv o 0,是根据引理 1 检测Gd中是否包括负环路,即检查新加入的约束是否与以前的时间约束网络相一致。动态递推算法与Floyd-Warshall 算法结果是等价的,通过图 4 和图5 给出的算法,可以快速地获得时间约束网络是否一致

26、,以及各个时间点的范围 d0i,di0,从而可以得到规划调度系统中各个活动是否与系统中已有的活动相容,以及各个活动的开始时间和结束时间的范围。3 时间复杂性分析下面首先给出基于时间约束网络动态规划调度算法的时间复杂性定理。定理 1 动态规划调度算法的时间复杂性在最坏情况下是 O(2ne),其中,e 是图 Gd中的边的数目,n 是图 Gd中顶点的数目。证明:动态算法是在前一步求解最短距离图 Gd的基础上,对加入的约束进行计算。如果加入的约束相关的顶点中没有或有一个顶点是原 Gd图中的,则可以直接给出相应的最短距离,如算法中的步骤(1)和步骤(2)。算法的复杂性主要体现在步骤(3),即新加入约束中

27、的两个顶点均是原 Gd图中的顶点。该算法采用一个队列存储受影响的顶点,并对其一一进行处理。步骤(3)调用的子程序(如图 5)主要分两部分:第一部分对顶点发出的各个边进行计算;第二部分是对顶点进入的各个边进行计算。其中第一部分的计算量与顶点的出度有关,第二部分的计算量与顶点的入度有关。假定在最坏的情况下,新加入的约束改变了所有顶点的最短距离,即队列Queue 中将存储 n 个顶点。另外,对于一个图,所有顶点的出度之和是图的边数 e,所有的入度之和也等于图的边数 e,因此,这一部分的时间复杂性在最坏的情况下是 O(2ne)。在一般的应用中,所构造的时间约束图并不是每对时间点之间都存在约束,所以有

28、2e n2,即时间约束网络的动态算法优于 Floyd-Warshall 的每对顶点间的最短路径算法。在实际应用中,新加入的约束并不会都影响所有顶点的最短距离,只有少部分与加入顶点紧密相连的顶点才会受到影响,因此,实际计算速度比理论上还要快。针对某一与时间相关的规划调度系统,考虑其中活动之间的时间约束关系,将其描述为时间约束网络,并求解网络的一致性和各个时间点的可能范围,分别对具有 20 个时间点、50 个时间点和 100 个时间点的情况用 Floyd-Warshall 算法和本文的动态算法进行计算,其结果如图 6 所示。从计算结果可以发现,在时间约束网络顶点比较少的情况下,动态算法计算所用时间

29、与 Floyd-Warshall 算法差不多,这是因为动态算法记录了许多相关数据,并在算法中进行了对应的处理,而192计算机集成制造系统)CIMS第 10 卷Floyd-Warshall 算法简单明了,没有额外的信息需要处理,所以在时间约束图中顶点比较少的情况下并不能够显示动态算法的优点。但随着顶点数的增加,动态算法的优势越来越明显。另外,在实际情况中,动态算法还与边的数量有关,而且新加入的约束并不一定影响前一步计算的所有的最短距离,因此,实际应用中,动态算法比理论上的计算速度还要快很多。4 Job-Shop调度问题实例Job-Shop 调度是规划调度问题研究中的一类重要问题 11,12,它要

30、求在一定的时间范围内和一定的资源集上完成一组作业的调度。如何安排工序(操作)到具体设备上,使得目标函数达到最优或较优的问题为多机调度问题。尽管设备加工性质基本相同,但加工速度可能不同,而且任务还有交货期的约束,所以工序多机调度较为复杂,其模型可以构造为给定资源集 RES=1,v 和作业集 JOB=J1,Jw。其中作业 Ji的提交时间和截止时间分别是 Bi和 Ei,并且 Ji是由 qi个不重叠的工序组成,即 Ji=oi1,oiqi,而每个工序 oim又有一定的执行时间dim和资源需求 RimI RES。求解工序 oim的开始时间sim,要求满足以下约束:(1)作业的时间约束 任何工序 oim有s

31、imBiCsim+dim Ei;(2)工序的顺序约束 作业Ji的两个工序oim和oin,若 m n,则 sim+dim sin;(3)资源的相容约束 任两个工序 oim和 okn,RimX RknD sim+dim sknD skn+dkn sim。下面是一个标准的 6 6 的 Job-Shop 调度问题(如表 1),这里,我们给出了每个作业集的提交时间和截止时间,并根据上面的时间约束关系和本文提到的简单时间约束网理论,以各个工序的开始时间为时间点,以工序之间的约束为时间点之间的连接权值,构建 Job-Shop 问题求解的时间约束网。采用本文设计的动态算法,可以快速地求解出各个作业集中每个工序

32、的最早开始时间,并以此时间为每个工序的开始时间在各个机器上进行排列,最终结果如图 7 所示,该结果满足总的作业时间最短的目标。这种方法的优点是,可以对工序之间的时间约束关系进行详细的描述,它不仅可以处理定性约束关系(如作业之间的顺序约束等),也可以处理定量的时间关系(如考虑工件在机器之间的传输时间,某工序完成 10 个单位时间之后才能进行下一工序等)。另外,该方法是动态进行处理的,所以在调度过程中,可以对工序进行灵活的调整,例如加入新的工序,删除某些多余的工序等,这给车间生产带来了很大的灵活性。表 1 一个 6 6 的 Job-Shop 调度问题例子BiEi(m,t)(m,t)(m,t)(m,

33、t)(m,t)(m,t)Job10653,11,32,64,76,35,6Job20652,83,55,106,101,104,4Job30503,54,46,81,92,15,7Job46652,51,53,54,35,86,9Job53603,92,35,56,41,34,1Job62602,34,36,91,105,43,15 结束语与时间有关的知识表示和推理是人工智能相关领域中经常要涉及到的一个问题,针对具体的系统有多种不同的解决办法。本文针对规划调度系统中的各个活动之间的时间关系,利用时间约束网络(Temporal Constraint Network,T CN)来表达活动的时间信息

34、及活动间的相互关系,并针对 Floyd-Warshall 算法在动态系统中的缺点,参考图论中求193第 2期徐 瑞 等:基于时间约束网络的动态规划调度算法解最短路径的方法,提出一种动态时间约束网络算法。该 算法在 最坏情 况下的时 间复杂 性为 O(2ne),在实际应用中,比常用的 Floyd-Warshall 算法计算速度明显提高。最后,以典型的 Job-Shop调度问题为例,进行了数值计算,仿真结果表明,动态算法可以快速地判断时间约束网络的一致性,给出各个工序的最早可行执行时间,并计算出满足最短作业时间的解。参考文献:1 ALLEN J F.Maintaining knowledge ab

35、out temporal intervals J.Communications of the ACM,1983,26(11):832-843.2 ALLEN J.Planning as temporal reasoning A.KR.91:Princ-iples of Knowledge Representation and Reasoning C.Cam-bridge,MA,USA:Morgan Kaufmann Publishers,1991.3-14.3 BADALONI S,BERAT I M.Hybrid temporal reasoning for plan-ning and sc

36、heduling A.Proceedings of 3rd Workshop on T em-poral Representation and Reasoning(TIME.96)C .LosAlamitos,CA:IEEE,1996.39-44.4 VRBSKY S V,T OMIC S.Satisfying temporal consistency con-straints of real-time databases J.The Journal of Systems andSoftware,1999,45(1):45-60.5 MUSCETTOLA N,NAYAK P P,PELL B,

37、WILLIAMS B.Re-mote agent:to boldly go where no AI system has gone before J.Artificial Intelligence,1998,103(1-2):5-47.6 DECHT ER R,MEIRI I,PEARL J.Temporal constraint net-work J.Artificial Intelligence,1991,49(1-3):61-95.7 SCHWALB E,VILA L.T emporal constraints:a survey J.Con-straints:An Internation

38、al Journal,1998,3(2-3):129-149.8 SCHWAL B E,DECHTER R.Processing disjunctions in tempo-ral constraint networks J.Artificial Intelligence,1997,93(1-2):29-61.9 DUAN Fanding.A fast algorithm for shortest-path-SPFAJ.Journal of Southwest Jiaotong University,1994,29(2):207-212(in Chinese).段凡丁.关于最短路径的 SPFA

39、 快速算法 J.西南交通大学学报,1994,29(2):207-212.10 ZWICK U.All pairs shortest paths in weighted directed graphs-exact and almost exact algorithms A.Proceedings of the39th IEEE Annual Symposium on Foundations of Computer Sc-ience(FOCS.98)C.Los Alamitos,CA:IEEE,1998.310-319.11 CHEN Enhong,XUE Hanhong.On solving c

40、onstraint satisfac-tion based job-shop scheduling problems J.Journal of Soft-ware,1998,9(2):946-948(in Chinese).陈恩红,薛瀚宏.基于约束满足的 Job-Shop 调度问题求解方法研究 J.软件学报,1998,9(2):946-948.12 WEISSER P,COCHRAN S,LANE S,et al.Modeling temporalrelations in task hierarchies for job shop scheduling A.Proceed-ings of th

41、e Second International Conference on Computer Inte-grated Manufacturing C.T roy,New York:Rensselaer Poly-technic Institute,1990.39-46.Dynamic Planning and Scheduling Algorithm Based on Temporal Constraint NetworkX U Rui1,2,X U Xiao-f ei1,CUI Ping-yuan2(1.Sch.of Computer Sci.&Tech.,Harbin Inst.of T e

42、ch.,Harbin 150001,China;2.Sch.of Astronautics,Harbin Inst.of Tech.,Harbin 150001,China)Received 13 Jan.2003;accepted 16 Jun.2003.Foundation item:Project supported by theCivil Aerospace Program of Commission of Sci.Tech.&Industry for National Defense.Abstract:For solving the temporal-relating plannin

43、g and scheduling problem,a dynamic algorithm is proposedbased on temporal constraints network(TCN).Unlike the traditional work in all shortest path algorithm,thisalgorithm only computes the partial network influenced by the new introduced constraint rather than the wholenetwork.T he worst time compl

44、exity of the algorithm(O(2ne)is given and proved.Taken the typical Job-Shop scheduling problem as an example,the simulation system is designed to verify the proposed algorithm,andthe result has shown that it can quickly judge the consistence of the constraints and work out the earliest starttime of the operator.Key words:temporal constraint network;planning and scheduling;dynamic algorithm;shortest path194计算机集成制造系统)CIMS第 10 卷