（计算机应用技术专业论文）时间规划中d_时刻表的设计及应用.pdf

摘要 摘要 在时间规划中，时间模型是一个童要的概念。时间规划的算法均要建立在， 定的模型之上。时间模型多种多样，各有特色，本文中的时间规划运算使用了时 间矩阵模型，时间规划可以用矩阵的运算完成，这种运算是简洁而高效的。 d 一时刻表是时间规划算法的一种，它可以在若干存在关系约束和宽度约束 的时间区间中找到同时满足两种约束的规划方案。 在d 一时刻表规划算法的实际应用中，我们发现它的一些局限性和不完善的 地方，如： 算法中输入的矩阵是化简后的矩阵，它的行列数目不一定是偶数；而且 行列与原时间区间端点的对应关系也不再一一对应。 算法中没考虑区间关系约束的一些附加条件，而这些条件在实际应用中 往往是不能忽略的。 算法中时间点的赋值由关系约束和宽度约束决定，而实际应用中某些特 殊时间点的赋值需要我们特别指定。 通过实践，我们不断的对其改进和完善，加入了一些新的特性和运算，使其 更适应于真实的环境。 在矩阵化简中加入合并链，记录和查找简化时间矩阵和原时间关系矩阵 的行列对应关系。 加入空事件，调整时间区间的滞后值。 加入重定位算法，调整特殊时间点的赋值。 以此为基础，编写了一个通用的时间规划程序。通过输入的几个实例，说明 了算法的改进是可行有效，通用时间规划程序可以很好的完成时间矩阵的简化、 r 时刻表和d 时刻表的求解。 关键词：时间关系，时间规划，d 时刻表，时间矩阵，时间模型， a b s t r a c t a b s t r a c t i nt e m p o r a j p i a n n i n g ，t e m p o r a i - m o d e j i sav e r yi m p o r t a t l tr u n d a t j o nt h e a l g o r i t h mo ft e r n p o r a l - p l a n n i n gs h o u l dr m no nt h er n o d e l e a c ht e m p o r a l m o d e lh a s i t so w nc h a r a c t e r i s t i c si nt h i s a r t i c l ew eu s et h e t e m p o m l m a t r i xm o d e l ， r 蛳p o r a l 一p i a n n i n gc a nb ed o n ew i t ht h eo p e r a t i o no f t h em a t 血，a n dt h eo p e r a t i o ni s s u c c i n c ta n di l i 曲一e m c i e n l d m m e t a b l ei so n el ( i n do fp l a n n i n ga l g o r i t h 皿i tc a ng e tas c h e m em e e “n g r e s t c t i o n s ：r e i a t i o n r e s t r i c t i o na n dw i d t h r e s t r i c t i o n i nt h eu s i l l go fd n m e t a b l ep j a n i l i n ga l g o r i t h m ，w ef i n ds o m el i m i t a t i o na n d f a u l t i r l e s sp l a c eo f i t t h en u m b e ro f 删 1 i 【so ft h er e d u c e dt e m p o r a l m a t 血f n i g h tn o tb ea 1 1e v e n n u m b e r ；a n dt h er a n k si sn o tc o f r e s p o n d e dt ot h eo 堍i n a lm a t 血 s o m ea p p e n d e dr e s t r a i n sa r en o tc o n s i d e r i n gi nt h ea l g o r i t h m ，b u tt h e s e r e s t r a j n so f t e nc a n tb en 号g l e c t e di nt h ep r a c t i c a la p p l i c a t i o n t h ea s s i g 砌e n to fs o m et e m p o r a l - p o i n t e r si sd e c i d e do n l yb yr e l 砒i o n r e s t r a i l l i n g ，b u ti np r a c t i c a la p p i i c a t i o ns o m ea s s 埝n m e n t 删s tb es p e c 洒e d a d dt oi ts o m en e wc h 删“s t i c sa n d o p e r a t i o n s ， i t a d a p t t ot h e r e a l - e n 啊r o 砌e 1 1 te v e nm o r e a d dt oi t c o a l “i o n c h a i n s ，f e c o f dt h ec o f t e s p o n d i n gr e l a t i o n sb e t w e e n r e d u c e dt 锄p o r a l m a t r i xa n do r i 萄n a lt e m p o r a l - m a t d x a d dt oi te m p t yi n c i d e n t ，a d j u s tt h el a g g i n gv a l u eo f t h et e m p o r a li n t e r v a l a d dt oi tr e l o c a t i o na l g o r i t h m ，a d j u s tt h ea s s i g n m e mo ft h es p e c i a lt e m p o r a l p o i n t e r s b a s e do nt l l i s ，w ew r i n 饥ag e n e m lc o m p u t e rp r o 铲a m i n p u t t i n gs e v e r a l i n s t a n c e s ，i ti sp r o v e dt h a tt h ei m p r o v e m e n to ft h ea l g o t h ma n dt h eg e n e r a l c o m p u t 盯p r o g f a m a r ef e a s i b l ea n d 出c t u a l k e y w o r d ：t e m p o r a l r e l a t i o n ，t e m p o r a l - p l a n n 吨，d - t i m c t a b l e ， t e m p o r a l m a t r i x ，t e m p o r a l - m o d e l ， 目录 表索弓 表l 一】两区间的1 3 种关系 表2 1 两区间1 3 种关系的矩阵表示 表6 1 计算机专业课程关系一览 表6 2 各课程的关系 表6 3 比赛项目一览表 表6 4 比赛项目之间的关系 表6 5 比赛时间安排表 v 2 9 s 拍 卯 印 a b s 缸a c t 图索引 2 1 时间点与区间的关系 2 2 时间关系的平面表示( 一) 2 3 时间关系的平面表示( 二) 2 4 用x l x 2 积空间表示x 3 1 赋值有向图的联结运算 ， 3 2 宽度约束右移运算 3 3 关系约束右移传播 3 4 求基本赋值流程图 3 5 赋值修正算法流程图 4 1 合并链 4 2 矩阵化简后与原事件区问的对应关系表示 4 3 空事件和前后事件的关系 4 4 重定位的算法流程图 5 1 时间规划通用程序的数据流图 5 2 时间规划通用程序的模块图 5 3 输入向导一信息和宽度约束 5 4 输入向导一关系约束 5 5 多成分提示 5 6 字符显示结果 5 7 显示事件的关系 5 8 赋值图 一 6 1 选修课程的安排的赋值图 6 2 运动会比赛项目安排的赋值图 石 0 石 m 博 饽 盟 抖 拼 筋 砣 弛 孙 弭 鲥 卯 钙 铝 舛 图图图图图图图图图图图图图图图图图图图图图图图 独创性声明 y7 6 5 6 4 0 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得塞徵盘堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：场惑彳龟了签字日期：驴夕年夕月石日 学位论文版权使用授权书 本学位论文作者完全了解塞堂杰堂 有关保留、使用学位论文的规定 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权 塞堂太堂 可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者鲐f 褥智 签字日期：? 瑚歹年f 月多日 学位论文作者毕业去向： 工作单位： 通讯地址： 翩鲐程衫 芦字日期：以叮年厂月f 日 电话 邮编 第一章引言 第1 章引言 1 1 时间规划方法的发展回顾 7 0 年代初，re f i k e s 1 m s t e f i k 【2 l ，e d s a c e r d o t j l 3 】等都先后讨论过 时间规划问题，不过他们的理论都有一个共同的不足之处，即没有一个明确的时 间模型，并且对两个事件之间的时间关系只假设“在前”和“在后”两个简单情况。 正因为对事件之间的时间关系的假设过于简单，所以他们的方法能够处理的问题 的范围也就受到限制。 1 9 8 3 年s a v c r e 【4 】针对上述方法的缺陷，提出一个时间规划的新模型， 一个关于包a c k a g e ) 的概念，所谓包是由两个元素“窗口”( w i n d o w ) 和“宽 度”( d 吣r a t i o n ) 组成。 窗口用个二元组( e ，l ) 表示，其中e 表示包中事件最早可能发生的时间，l 表示包中事件最迟可能发生的时间。 “宽度”用一个实数表示，表示在包中事件保持的时间长度( 即从事件发生到停 止之间的时间长度) 。 这个模型比上面只有“前”和“后”关系的模型前进了一步，它可以描述两个事 件之间的各种相互关系，但仍有两个不足之处，一是每个事件发生的事件要求落 在给定的窗口上，即其发生的时间“基本”上确定了。 在处理具体问题时这个限制还嫌太强。如制定一个田运动会的比赛时刻表， 在制定之前我们并不能指定男子百米决赛一定要在指定的“窗口”开始进行。除非 你把“窗口”定义得很大，如e 在第一天八点，l 在最后一天下午五点，这样定义 的“窗口”就毫无意义。故“窗口”的概念对实际问题还不是很好用。 其次，模型中用一个固定的正实数描述事件的时间宽度，这在实际上也嫌要 求过严。因为实际中，事件的时间宽度往往只是给出一个范围，而不是一个准确 的数字。如百米决赛若进行得很顺利，从参赛选手的点名至结束也许只要十分钟， 若不顺利可能要二十分钟才能结束。即实际宽度应是在1 0 2 0 分钟的之间。 同年j f a l l e n 和，a k o o r n e n 提出时间世界模型( t e m p o m lw j r l dm o d e l ) 作为 时间规划的描述跚6 l 【7 】。舢l e n 的时间世界模型是当前关于时间规划问题的比较好 时问规划中d l 时刻表的设计及应用 的模型之一，他克服了v e r e 模型中的两个不足，这个模型能比较全面地反映各 事件之间的时间关系。但a 1 1 e n 利用这个模型提出的求解时间规划的“时间逻辑” 方法并不理想。最近t s a n g ，ep k 对a j l e n 的一套方法做了推广，提出“部分世 界描述方法( a p a n i a lw b r l dd e s c r i p t i d na p p r o a c h ) 8 1 ，这个推广扩大了a 1 i e n 模型 的描述能力，但是对求解时间规划的方法仍未能克服其计算量大，计算方法复杂 的缺点。 在越l e n 的时间世界模型中，a l l e n 规定了两区间之间的1 3 种不同的关系( 表 1 n ，为了进行区间之间的时间关系的推理，他引入了所谓“时间逻辑”的概念， 并证明1 3 种不同关系均可用“遇”( m e e t ) 来定义。还引入关于“m ”运算的五条公理， 又给出三个区间i ，j ，k 之间的约束传播规律，如，i ( ) j ，且j ( ) k 得i ( ) k 。 于是三区问之间的可能的关系共有1 3 1 3 = 1 6 9 种情况。 表1 - 1 两区间的1 3 种关系 x 和y 的符号基于区间基于点的逻辑图形示意 关系表示的逻辑 口i l ，。1 2 lb e f o r e x ( ) y a l a 2 ，b l a 2e j = = = 2m e e tmx ( m ) yb l = a 2 = = = 2 = = = 3 o v e r l a p o x ( o ) y a l a 2 b l b 2c = = 2 i | = = 4f i i l i s h e db y矗 x ( f i ) y a 1 a 2 bl = - b 2 t = = 2 2 i ；j i 5c o n t a i n sd i x ( d i ) y a 1 a 2 b 2 b 1= = 毛兰兰兰j 一 6s t a ns x ( s ) y a 1 = a 2 b 1 b 2 e 兰善三三= = 一 7 e q u a lx ( ；) y a l = a 2 且b l _ b 2 e 兰旨三三三三j 8s t a r t b vs l x ( s i ) y a 1 = a 2 b 2 b 1e 兰三三三f = = 一 9 d u n g dx ( d ) ya 2 a 1 b 1 b 2 = = 兰兰三三兰：罩 1 0 f i i l i s h f x ( f ) y a 2 a l b l = b 2 c = = = = 5 i i 目 1 10 v e r l a p p e db y 0 l x ( o i ) y a 2 a 1 b 2 b 1 = = = = 兰兰；一 1 2 m e e tb v肌 x ( 面) y a 2 ) y a 2 b 2 a l b 1 c j = = = j 第一章引言 a l l e n 主张在给定各事件之间( 两两之间) 的时间关系之后，利用三区间的传 递律来求解对各事件均一致满足的时刻表。 可惜，如前所述，对一组事件来说，即使任意三个都是一致的，仍未能保证 所有事件的时间关系都是一致的时刻表存在。 进一步，即使求到一个一致满足所有时间关系约束都是的时刻表，也不能保 证这个时刻表能满足时间宽度的约束。 t s a n g ，ep _ k 虽然对灿1 e n 的方法进行了推广，加强了i e n 方法的描述能 力，但是对舢l e n 的方法在求解时间规划问题中计算量过大的问题一直未能解决。 t s a n g 为能求到满足约束的时刻表，使用搜索方法，其计算量从理论上来说就是 ( e “) ，其中n 是事件的个数。所以从这个意义上来说，m l e n 的方法也未能完全 解决时间规划问题。但是他们提供的用区间及区间之间的1 3 种不同关系的形式 来描述时间规划问题却是一个很好的方法，它的优点在于可以描述很广泛一类的 时间规划问题，克服了过去一些时间规划模型的局限性。 1 2 时间规划的关系矩阵方法 本文中求解时间规划的时刻表的方法，是一种基于矩阵运算的方法，可称为 “关系矩阵方法”，它克服了以上方法的局限性，提供了一个很有效的求时刻表的 方法【1 2 j 。 在关系矩阵方法中，时间的区间用其两个端点表示，n 个事件之间的关系转 变为2 n 个端点之间的关系问题，问题的规模变为原来的两倍，但两个端点之间 的关系只有3 种，比区间之间的1 3 种关系简单的多，算法的复杂性反而有所下 降。 由于端点之间的关系用“关系矩阵”来表示，求时间规划的时刻表就是对该矩 阵的一系列操作。矩阵的特性决定了这种操作的规整形，关系矩阵方法具有很强 的可操作性、可应用性。 算法本身是种通用的数学描述，在实际应用中表现出了一定的局限性，在 实际应用中，我们根据实际情况，在原有的算法中添加了一些必要的元素，增加 了它的实用性，并应用在实际的实例上，取得了很好的效果。 时间规划中d 时刻表的设计及应用 1 3 本文的主要内容 第一章介绍时间规划的发展状况，对不同规划算法的优缺点进行比较。 第二章介绍时间区间的关系约束和时间关系矩阵，以及如何用时间关系矩 阵描述时间区间的关系约束。 第三章介绍d 时刻表算法。事件相互之间存在着关系约束，同时每一个事 件持续的时间区间也存在着宽度约束，d 时刻表算法可以从中求得一个满足双 重约束的时刻表。 第四章在实际应用中我们发现d 一时刻表算法存在一定的局限性和不完善 之处，如时间关系矩阵的化简会破坏事件区间和矩阵的对应关系，如不记录这种 变化，将无法得到区间端点在时间关系矩阵中的位置：两个事件问可能会有一个 最小间隔，算法中对事件之间的间隔无法按照要求调整；在实际中我们会要求某 些事件在一个确定的时刻发生，而在算法中却无法指定某时间点的赋值。 结合运动会比赛规目的次序编排，我们对d 时刻表算法进行了深入的研究， 并在原算法的基础上，提出了合并链的概念、空事件的概念和重定位的算法，并 给出对d 时刻表算法进行改进的方案。 第五章基于改进的d 时刻表算法，设计了一个通用的时间规划应用软件， 用以完成事件区间的基本信息、各种约束条件的输入，关系矩阵的生成，时间关 系矩阵的化简，d 时刻表的求解，结果的显示等功能。初步形成了一个基于d 时刻表算法的完整的时间规划软件。 第六章通过两个实例，对通用时间规划软件的实际运行效果进行考察，得 到了基本令人满意的结果。 第七章总结全文，并就以后可以继续开展的研究方向加以说明。 4 第二章时间关系的矩阵表示 第2 章时间关系的矩阵表示 2 1 时间关系的表示方法 一般来说讲，有三种方式来表示时间的结构： 一、基于事件的时间逻辑( e v e m - b a s e dt e m p o r a ll o g i c ) ，即以事件作为时间 的基本单元； 二、基于区间的逻辑结构( i n t e r v a l b a s e d ) ，即以时间区间作为时间的基本单 元： 三、基于点的结构( p o i n t - b a s e d ) ，即以时刻作为时间的基本单元。 显然以上三种时间结构可以相互转换，因为任何事件总是在一定的时间中发 生，而时间区间又可用其起始和终了的时刻来表示。 2 2 时间规划的关系矩阵方法 2 2 1 基于点关系的时间逻辑 在a l l e n 的时间规划模型中，越i e n 将事件a 与事件发生的时间区间i 联系在 一起，于是讨论不同事件之间在时间上的关系时，就转化为两对应的时间区间之 间的对应关系。两区间之间的不同关系有1 3 种，这称为基于区间的时间逻辑。 从另一角度看，一个区间由其两个端点所确定，于是两个区间之问的关系， 当然也可以用其四个端点的相对位置来表示，这种表示方法称为基于点的时间逻 辑。两者的对应关系见表1 1 。用基于点的时间逻辑来描述事件之间的时间关系， 比基于区间的时间逻辑有其方便之处，因为在一维的时间轴上，任何二元素之间 的关系只有 三种情况，也就是实数之间的关系，而对于实数我们是比较 熟悉的。 一个区间i 可用两个端点来表示，即用a b 的有序数对由( a b ) 来表示。 时间点t 与该区间i 的关系有五种：t a ；t = a ；a t b ，依次标记为 1 、2 、3 、4 、5 ，可以用一个数轴表示，如图2 ，1 。 时闻规划中d 时刻表的设计及应用 t 。亡二二兰二= j 。 a i b t at - a a a 2 是必然的，平面上 位于直线x = y 的下方的点是没有意义的，那么就可以用于直线x = y 的上方的点来 表示区间i l 和i ：的关系，在这个两维的平面上可以很方便地表示出两个区间之 间的1 3 种不同关系，详见图2 2 和2 3 。 图中两个区间为：1 1 = ( a l ，b 1 ) ，a l b l ；1 2 = ( a 2 b 2 ) ，a 2 b 2 。 四条射线l l ：x = b 2 ；l 2 ：y = b 2 ： l 3 ：x = a 2 ； l 4 ：y = a 2 ； 把上半平面划分为六个区间，从下而上，从左而右依次代表 ；把四条射线划分为六个线段，从下而上，从左而右依次代表m 、f i 、s 、 s i 、f 、i 【1 i ；和一个交叉点，代表= 。 l 2 l 4 d i 蝴_ 飞 形；。 圳刁 局 f d5d 血 x 图2 - 2 时间关系的平面表示( 一)图2 3 时间关系的平面表示( 二) 从图2 - 2 中我们可以看小，当1 2 ( a 2 ，b 2 ) 固定之后，a l 在x 轴上地取值范围可分 成五种情况：a 1 a 2 ；a 1 _ a 2 ；a 2 a 2 ，x l 与y l 是相关的。当a 1 a 2 ，a 1 只能小于b 2 ，a l 是不可能再满足a l b 2 的。 2 2 2 单成份时间关系约束下的关系矩阵表示法 1 、两个时间点a 、b 关系的表示，a ，b 的关系有三种，a ( b 、a - b 、a b ，我 们用一l 、o 、1 表示，两时间点的关系可以用 一l ，o ，1 ) 的子集表示。 2 、点与区间关系x 的表示，根据图2 4 ，x = x l x 2 ，我们可以用矩阵 x 1 ，x 2 表示，x l 和x 2 都是 一1 ，o ，1 ) 的子集。 3 、两区间的关系r ( 1 1 ，1 2 ) = x y 表示，x 和y 可以表示成另两个积空 间的子集。 x = x l x 2 y = y l x y 2 即用一个2 2 的矩阵m 2 专妻 表示两区间的关系，矩阵的每一元素是 一1 ，o ，1 ) 的子集。 4 、n 个事件间关系的表示，可以用关系矩阵 第二章时间关系的矩阵表示 f m ( 1 ，1 ) m ( 1 ，2 )m ( 1 ，刀) m ：fm ( 2 ，1 ) m ( 2 ，2 ) m ( 2 ，”) l a 彳( 胛，1 ) z ( 胛，2 ) 。 彳( 打，行) n ) ，表示事件m 和事件n 的关系。 表示，m 包含n 2 个2 2 的矩阵，m ( m 经过以上步骤，n 个事件的关系转化为一个2 n 2 n 的关系矩阵，对n 个事件 的操作和运算也转化为对此矩阵的操作和运算。 两区间1 3 种相互关系可以用矩阵表示如下 表2 1 两区间1 3 种关系的矩阵表示 x 和y 的符号图形示意矩阵表示 关系表示 口1 l ，口1 2 1b e f o r o 01ll 1 o 11 c = 一c = = 一 一l一1 0一l l一110 l o 第三章d 二时刻表 表。 第3 章d 时刻表 本文中时刻表均为单成分约束下的时刻表，分为两种：r - 时刻表和d _ 时刻 r _ 时刻表就是一致满足时间关系约束的一个端点集的有序划分。 d _ 时刻表就是一个既满足时间关系约束又满足时间宽度约束的时刻表。 3 1 r 时刻表 本文主要讨论d _ 时刻表，但要用到r _ 时刻表的一些知识，再次对r - 时刻 表作简要介绍。 3 1 1 几个概念： 有序划分：设t = x l ，x 2 ，x 3 x n 是一有限集台，令e = ( e l ，e 2 e l l l ) 是t 的一个划分，在e 中定义关系如下： x 岛，y e ! i ，x y 甘岣，记为x y ( e ) ， 若x ，y e i ；，则记为x y ( e ) 。 则称划分e 连同上面定义的序为t 的一个有序划分。 r _ 时刻表：设m 是时间规划的关系矩阵，t = t 1 ，t 2 t 2 。) 是对应n 个时间 区间的端点时刻的集台。令e ； e l ，e 2 e m ) 是t 的有序划分，且满足 v x ，丁，z y ( e ) = 一1 m ( 墨j ，) 帆，y ，x j ，( e ) = 亨o 历( x ，y ) 则称有序划分e 是m 的一个r 时刻表。 显然，将t 的元素按e 的序安排在时间轴上( x y ( e ) 的x ，y 放在同一点上) ， 即得到一个一致满足所有时间关系约束的时间安排。因此所谓r 时刻表就是一 致满足时间关系约束的一个端点集的有序划分。 非正行向量：设m i = ( m ( i ，1 ) ，m ( i ，2 ) ，m ( i ，2 n ) ) 是时间关系矩阵m 中第i 行 行向量。 令8 日= r n i n t | t m ( 巧) ) 时问规划中d l 时刻表的设计及应用 得a i = ( a i l ，a 卧a i 2 n ) 若a i 每个分量均小于等于零，则称m i 是非正行向量。 3 1 2 简化关系矩阵 关系矩阵中存在m ( x ，y ) 一 o ) 的元素，表示x ，y 两个时间点是同时发生 的，这时可以把这两点合并，如若不然这两点互相牵扯，给后续的运算带来不利 的影响，使算法陷于无休止局部调整。所以首先要化简矩阵。 设m 是关系矩阵，化简算法如下： l 若m 中不存在m ( x ，y ) = o ) 的元素，则令m = m ，称m 是m 的简 化矩阵，停止。否则进入下一步。 2 取x ，y j ( m ) ，且m ( x ，y ) = f 0 ) v z j ( m ) ，令 m ( x ，z ) = m ( x ，z ) n m ( y ，z ) ，x 仨j ( m ) m ( x ，x ) 2 0 ，m ( z ，x ) = 一m ( x ，z ) 若j z ，使得m ( x ，z ) = 庐，失败。 不然将m 中x ，y 行( 列) 删去，加上x 行( 列) ，这个运算称为将x ，y 行( 列) 合并成x 行( 列) 。得到的矩阵记为m 1 简记j o 田= j 。 令m m 1 ，j 一( j u x ) ( k y ) 。回第一步 3 1 3 求r 一时刻表的算法 1 求m 的简化矩阵，若失败，则停止。不然得到一个简化矩阵( 不妨仍记为 m 1 。令s - ，j = j ( m ) ，进入步骤2 。 2 若j = 矽，输出s ，称s 是m 的基本划分。停止，成功。否则，进入步骤 3 。 3 若m 存在非正行向量，以e i ( 开始时i = 1 ) 表示这些非正行向量的行号 的集合。进入步骤4 。否则，失败，停止。 4 ( 1 ) 若e i = 矽，先败，停止。 第三章d 二时刻表 ( 2 ) 若e i 矽，求e 的相容子集，若失败，停止。不然得e i 的一组相容子集记 为畦，进入步骤5 。 5 将m 中v j d i 的第j 行( 列) 删去得到的子矩阵记为m l 。 令m m l ，j j ，d i ，i i + 1 ，s 一( s ，d i ) 。回步骤2 。 3 2 d 时刻表 上节介绍了r 时刻表，它是一致满足时间关系约束的端点集合的有序划分。 但在实际应用中，单单满足时间关系约束还不够，一般对每个时间的长度也有一 定的限制条件，称为时间宽度约束。 d 一时刻表，就是一个既满足时间关系约束又满足时间宽度约束的时刻表。 d 一时刻表是t 一 o ，m ) 的一个函数，其中t 是区间端点的集合，函数值是某端 点对应的发生时刻，函数记为d ，则d 时刻表可以表示为： s ( d ) 一( d ( t 1 ) ，d ( t 1 ) ，d ( t 2 。) ) t = ( t 1 ，t 2 ，t 2 。) 3 2 1 几个定义 a ( b ) 型点：设事件集为 e i ，i i ) ，i i 是e i 事件对应的时问区间。令i = 【a i ， b i 】，设x 是i i 的起点，称x 是a 型点，并以b ( x ) 表示b 的终点。 反之，若x 是i i 的终点，称x 是b 型点，并以a ( x ) 表示i i 的起点。 区间宽度：对任一区间i i ，以6 ( i i ) ( 或6 ( i ) ) 表示i i 对应的宽度。 宽度上界( 下界) ；v i 满足：6 1 ( i ) = 6 ( j ) = 6 2 ( i ) ，其中6 1 ( j ) 和6 2 ( i ) 是预先给定的常数。称6 l ( i ) 和6 2 ( i ) 是区间i i 的宽度上界和宽度下界。 v x i i ，我们有时也可以表示如下： 区间宽度：6 ( x ) 宽度上界：6 1 ( x ) 宽度下界：6 2 ( x ) 起点：a ( x ) 终点：b ( x ) 时间规划中d 时刻表的设计及应用 d _ 时刻表：设s ( d ) = ( d ( t 1 ) ，d ( t z ) ，d ( t 柚) 是一个时刻表，若满足： ( 1 ) v x ，y t ，若d ( x ) d ( y ) 贝0 1 m ( x ，y ) ；若d ( x ) = d ( y ) ， 则o m ( x ，y ) 。 ( 2 ) 设x 是b 型点，令( x ) 兰d ( x ) 一d ( a ( x