（控制理论与控制工程专业论文）基于关键路径离散事件动态系统的仿真优化方法研究.pdf

分析的新算法. b ) 文【 1 2 0 研究了串 联加工网路的 关键路径问 题， 分析了 其性质， 并在此基 础上提出了扰动分析方法. 在此工作的基础上， 首先讨论了串联加工网络的关键 路径计算间题， 分存储器容量有限和无限分别给出了相应的计算方法. 之后讨论 了系 统性能函 数的可微性， 并在此基础上提出了扰动分析的 新方法. 最后把对串 联加工网络的 研究结果推广到分层无论系统， 进而推广到具有偏序结构的一类网 络系统中. c ) 在文 1 7 8 对一 般生 产线的 研究 成 果的 基础 上， 在极大代数框架下 研究了 循环排队网 络模型， 分析了系 统的稳定性， 证明了系统性能函 数的导数与求数学 期望的可 交换性， 最后给出了用扰动分析方法计算系 统性能函 数关于系统参数导 数的方法. d ) 对串 行系 统， 在一定条件下构造其再生轨迹. 在一再生周期内 ， 基于关健 路径思想， 用扰动分析( p e r t u r b a t i o n a n a l y s is , p a) 方法， 用有限长度的 观测值 估计性能指标对可调参数的梯度， 将估计值代入随机逼近算法， 递推地求最优参 数 ， 得 到 了 基 于 扰 动 分 析 的 优 化 算 法 t 2 .基于关键路径的d e d s 仿真应用研究 a ) 通讯网络系统是排队网络的典型应用对象. 考察了通讯网络的扰动分析， 它的每个 服务台具有确定的服务时间和两个独立的信元到达流， 分别由“ 可观测” 信元流与 “ 不可观测” 信元流组成， 不可观测信元到达服从p o i s s o n 分布. 对这 类系 统， 基于关键路径思想， 采用扰动分析方法， 对通讯网络的 性能进行分析. i i b ) 探讨了串 行生 产线 存储单元的 序优 分配间 题. 综合关键路径与序 优 原理 给出了存储单元的优化分配算法. 仿真结果表明该方法利用至多两次仿真便能得 到存储单元的合理分配方案. c ) 研究了d e d s 中 多 级服 务台系 统的 优化间 题. 设顾客进入系 统的 顺序固 定， 系统指标是使总服务时间 最短， 系统的建立者可以用一定的投入来改善某些 服务台的效率. 基于关键路径， 在一次采样的基础上， 利用扰动分析方法确定待 优 化 的 r * 台 ， 通 过 弓 队 裕 度 的 概 念 来 确 定 待 优 化 服 务 自 kkj 厦 优 投 资 额 ， 使 得 在 一定的 资金条件下， 系 统的总 服 务时间 达 到最小 i 关链词: 离散事件动态系统， 关 优 丫0 径， 极大代数， 、了 扰动分析， 了再 铲， 序 abs tract wi t h t h e d e v e l o p m e n t o f c o m m u n i c a t i o n s y s t e m , c o m p u t e r s y s t e m a n d m a n u f a c - t u r i n g s y s t e m , e t c , a b r o a d e r s p a c e o f a p p l i c a t i o n f o r d i s c r e t ed y n a m i c s y s t e m ( d e d s ) w a s p r o v i d e d , a t t h e s a m e t i m e , m a n y ，p r o b l e m s w e r e p r e s e n t e d f o r t h e s t u d y o f d e d s , w h i c h e n r i c h e s t h e t h e o r y o f i t . t o s t u 勿 a c o m p l e x s t o c h a s t i c s y s - t e m , i t s h o u l d b e d o n e u n d e r t h e s t r i c t h y p o t h e s i s i f m a t h e m a t i c a l t o o l s a r e o n l y u s e d , w h i c h , i n m o s t c a s e s , c a u s e s t h e a c a d e m i c r e s u l t s h a v i n g n o a p p l i c a t i o n v al u e s . h e n c e i t i s n o t o n l y勿 me a n s o f t h e ma t h e m a t i c a l t o o l s i n mo s t c a s e s . o n t h e o t h e r h a n d , t h r o u g h t h e s i m u l a t io n , al t h o u g h i t n e e d s n o t t h e s t r i c t h y p o t h e s is , t h e lo w s i m u l a t i o n e ff i c i e n c y o f mo n t e - c a r l o t e c h n 询 u s a n d t h e c o m p l e x i t y o f d e d s m a k e s i t s s i m u l a t i o n - b a s e d o p t i m i z a t i o n p r o b l e m s c h a l l e n g i n g . c o m b i n i n g m a t h e m a t i c al t o o l s w i t h t h e s i m u l a t i o n t e c h n i q u e s i s a n i m p o r t a n t d i r e c t i o n f o r s t u d y i n g t h e o p t i m i z a t i o n o f de ds . wh e n t h e p r e f o r m a n c e o f o n e d e d s s y s t e m i s a n al y z e d a n d o p t i m i z e d , t h e p e r - fo r m a n c e fu n c t io n h a s t h e f o r m j =l im l ( x n ) , w h e r e x n is t h e t i m e t h e o b j e c tn o m b e i n g p r o c e s s e d d e p a r t s t h e s y s t e m.i f t h e e x p r e s s i o n o f 二 回 i s o b t a i n e d , t h e n t h e l ( x n ) i s o b t a in e d e a s i l y t o o , s o t h e v al u e a n d a ll d e r i v a t i v e s o f t h e f u n c t i o n j w i l l b e c o m p u t e d e a s i l y , c r i t i c al p a t h h a s b e e n p r o p o s e d 场 p r o f . t u i n 1 7 9 , 1 7 8 , 1 7 6 , t o c o m p u t e t h e e x p r e s s x 间 i n o n e s i m u l a t i o n . i n t h i s p a p e r , t h e p r o b l e m t o c r i t i c al p a t h i v w i l l b e d i s c u s s e d f u r t h e r b a s e d o n t h e r e s l u t s o b t a i n e d衍 m a n y f o r m e r r e s e a r c h e r s . b a s i c a l l y , t h e f o l l o w i n g t w o p r o b l e m s w i l l b e d i s c u s s e d i n t h i s p a p e r . 1 .t h e s t u d y o f t h e o r y a n d m e t h o d o l o g y o f d e d s s i m u l a t i o n o p t i mi z a t i o n b a s e d o n c r i t i c a l p a t h a ) i n 1 7 6 , 1 7 8 , 1 7 9 , w i t h t h e d e s c r i p t i o n o f s y s t e m i n ma x - a l g e b r a , t h e p e r t u r b a t i o n a n a l y s i s w a s d i s c u s s e d b a s e d o n t h e i d e a o f c r i t i c a l p a t h f o r t h e t a n d e m q u e u e s y s t e m , a n d t h e p r o p e r t i e s o f c r it i c a l p a t h w e r e g i v e n . b a s e d o n t h e r e s u l t s , t h e c a l c u l a t i o n o f c r i t i c al p a t h s o f t h e t a n d e m q u e u e s y s t e m i n h a s s e g r a p h w i l l b e s t u d i e d , a n d t h e c o r r e s p o n d i n g a l g o r i t h m s w il l b e g i v e n f o r t w o c a s e s : n o b u ff e r s a n d fi n i t e. f i n a l l y , b a s e d o n t h e al g o r i t h m s , a m e t h o d f o r p e r t u r b a t i o n a n al y s i s i s p r o p o s e d r e s p e c t i v e l y f o r t h e t a n d e m q u e u e s y s t e m . b ) i n 1 2 0 , w i t h t h e d e s c r i p t i o n o f l in e a r s y s t e m i n m a x - al g e b r a , t h e p e r t u r b a t i o n a n al y s i s w a s d i s c u s s e d b a s e d o n t h e i d e a o f c r i t i c al p a t h f o r t h e t a n d e m p r o d u c t i o n n e t w o r k , a n d t h e p r o p e r t i e s o f c r i t i c a l p a t h w e r e g i v e n . b a s e d o n t h e r e s u l t s , t h e c a l- c u l a t i o n o f c r i t i c al p a t h s f o r t h e t a n d e m p r o d u c t i o n n e t w o r k w i l l b e s t u d i e d , a n d t h e c o r r e s p o n d i n g al g o r i t h m s w i l l b e g i v e n f o r t w o c a s e s : n o b u ff e r s a n d fi n i t e b u f f e r s . t h e d i ff e r e n t i a b i li t y o f t h e s y s t e m w a s s t u d i e d , a n d a n e w al g o r i t h m f o r p e r t u r b a t i o n a n al y s i s i s p r o p o s e d . f i n al l y , al l r e s u l t s f o r t h e t a n d e m p r o d u c t i o n n e t w o r k a r e e x - t e n d e d t o h i e r a r c h i c al s y s t e m , t h e n t o a c l a s s o f n e t w o r k s y s t e m w i t h b l o c k i n g a n d h a v i n g t h e p r o p e r t y o f t h e p a r t i a l o r d e r . s o m o s t o f r e s u l t s f o rt h e t a n d e m p r o- v d u c t i o n n e t w o r k c a n b e a p p l i e d t o t h e s t u d y o f t h i s c l a s s o f g e n e r a l n e t w o r k h a v i n g t h e p r o p e r t y o f p a r t i al o r d e r . c ) b a s e d o n t h e m a x - a l g e b r a , t h e s t a t e e q u a t i o n f o r c y c l i c q u e u e n e t w o r k w a s d e r i v e d , a n d t h e s t a b i li t y o f t h e s y s t e m w i l l b e a l s o d i s c u s s e d . m o r e o v e r , t h e i n t e r - c h a n g e a b i l i t y b e t w e e n t h e d e r i v a t i o n a n d e x p e c t a t i o n o f t h e p e r f o r m a n c e f u n c t i o n i s p r o v e d , a n d t h e n t h e m e t h o d f o r c o m p u t i n g t h e d e r i v a t i o n o f t h e p e r f o r m a n c e f u n c t i o n a r e d t o t h e s y s t e m p a r a m e t e r w i l l b e g i v e n t h r o u g h t h e p e r t u r b a t i o n a n a l y s i s . d ) f o r t h e t a n d e m q u e u e s y s t e m , t h e r e g e n e r a t i v e p a t h i s c o n s t r u c t e d . i n a n i n t e r - r e g e n e r a t i o n t i m e , t h e s e n s i t i v i t y o f p e r f o r m a n c e m e a s u r e w i t h r e s p e c t t o t h e 确 u s t a b l e p a r a m e t e r i s d e r i v e d b a s e d o n fi x e do f o b s e r v a t i o n . f u r t h e r m o r e , a n e w al g o r i t h m o f p a r a m e t e r o p t i m i z a t i o n f o rq u e u e s y s t e m w i l l b e wh i c h n e e d s l e s s e r s i m u l a t i o n a n d o m i t s a n al y s i s f o r p e r t u r b a t i o n t r a n s m i s s i o n a n d m a k e s t h e e s t i m a t i n g v a l u e o f t h e s e n s i t i v i t y b e t t e r . 2 . t h e d i s c u s s i o n o f a p p li c a t i o n o f t h e s i m u l a t i o n m e t h o d o l o g y f o r t h e d e d s b a s e d o n c r i t i c a l p a t h . a ) t h e p e r f o r ma n c e a n al y s i s f o r a f i f o c o m m u n i c a t i o n q u e u e w i l l b e d i s c u s s e d , w i t h i d . d . s e r v i c e t i m e a n d t w o i n d e p e n d e n t a r r i v a l s t r e a m s o f “ o b s e r v e d ” a n d“ u n o b s e r v e d ” p a c k e t s . t h e a r r i v a l s o f “ u n o b s e r v e d ” p a c k e t s a r e p o i s s o n p r o c e s s w i t h a k n o w n r a t e . i n t r o d u c i n g t h e i d e a o f c r i t i c a l p a t h , t h e m o d e l i n g a n d p e r t u r b a t i o n a n a l y s i s m e t h o d w i l l b e p r o p o s e d f o r t h e q u e u e . f u r t h e r m o r e , p e r f o r m a n c e m e a s u r e vi e n d - t o - e n d d e l a y a n d p r o b a b i l i t y o f c e l l l o s s a r e e s t i m a t e d , t h e t r a d e - o ff b e t w e e n t h e s e t w o i n d i c e s i s o b t a i n e d . b ) t h e o r d i n a l o p t i m i z a t i o n a s s i g n m e n t p r o b l e m o f t h e b u ff e r s i n t a n d e m p r o d u c - t i o n s y s t e m . a n al g o r i t h m i s p r o p o s e d b a s e d o n t h e o r d i n a l o p t i m i z a t i o n m e t h o d a n d c r i t i c a l p a t h . t h e s i m u l a t i o n r e s u l t s i n d i c a t s t h a t t h e n e a r - o p t i m al a s s i g n m e n t s c h e m e c a n b e o b t a i n e d b a s e d o n t h i swi t h a t mo s t t w o s i mu l a t i o n s . c ) t h e p r o b l e m o f o p t i m iz a t i o n o f m u l t i- s t a g e s e r v e s t a t io n s y s t e m s ( m s s s ) i n d e d s i s d e v e l o p e d . c u s t o m e r s e n t e r e d ms s s w i t h a fi x e d o r d e r . t h e d e s i g n e r o f ms s s w i l l p u t c e r t a i n i n v e s t me n t o n s o me s t a t i o n s t o s h o r t e n t o t al s e r v e t i me . b a s e d o n t h e c r i t i c a l p a t h , w i t h a s a m p l e , t h e s e r v e s t a t i o n s t h a t s h o u l d b e o p t i m i z e d a r e d e t e r m i n e d b y p e r t u r b a t i o n a n a l y s i s , t h e o p t i m a l i n v e s t m e n t f o r t h e s e s t a t i o n s i s d e t e r m i n e d勿 i n t r o d u c i n g s l a c kw h i c h , u n d e r t h e g i v e n i n v e s t m e n t , s h o u l d g e t t h e s e r v e t i me. ke y w o r d s : d i s c r e t e e v e n t d y n a m i c s y s t e m s ( d e d s ) , c r i t i c a l p a t h , m a x - a l g e b r a , p e r t u r b a t i o n a n al y s i s , r e g e n e r a t i o n , o r d i n a l o p t i m i z a t i o n vi i 致谢 本文是在恩师涂奉生教授的悉心指导下完成的. 在我攻读博士学位期间， 涂 奉生教授从科研、 学习 和生活各方面都给予了无微不至的关怀和帮助. 涂奉生教 授渊博的 学识、 敏锐的洞察力、 严谨的治学态度和崇高的敬业精神与风范 将使我 终身收益. 在此， 谨向 涂奉生教授表示衷心的感谢. 感谢c i m s 研究室全体老师和同 学三年来给予的帮 助与支持. 特别感谢邵秀 丽老师在学习 和生活方面给予的 热情帮 助， 感谢贾春福， 陈 秋双， 袁晓 洁三位老 师的合作研究. 感谢师兄谭思 彤， 吴民， 师弟贾茂林， 刘明铭， 药蓬， 于涵， 郑 辉等同学在生活上给予的帮助. 感谢多位朋友和同 学三年来对我的生活和学习的 关心和帮 助. 特别感谢数学 所孙善忠博士与我共同 度过了 十年的 学习生涯， 感谢他多年来对我 学术研究 和生 活上的帮 助. 感谢历史系周正庆博士、 中 文系王红旗博士、 计算机系崔宝江博士 在生活方面给予的帮助. 感谢资料室和办公室老师们给予的帮助. 感谢妻子对我的学业的关心、 支持和鼓励. 本 文得 到国 家 攀 登 计划基金( 9 7 0 2 1 1 0 1 7 ) 和国 家自 然 科 学 基 金项目( 6 9 6 7 4 0 1 3 ) 资助，特此致谢. vi i i 第一章综述 动态系统的研究具有一个漫长而辉煌的历史， 可以毫不夸张地说， 控制论及 其应用的 成功， 极大地得益于几个世纪来积累的 有关动态系统的知 识. 我们 现在 正进入一个动态系 统发展的 新时 期， 并且存在着对一类新系统进行分析和建立模 型的 令人振奋的可能性. 习 惯上， 动态系统一般是指随时间 连续变化的、 满足一 些物理原理( 如关于运动、 守恒等定律) 的系统， 常称之为连续变量动态系统， c o n t i n u o u s v a r ia b l e d y n a m i c s y s t e m ， 简称 为c v d s . 微分( 差 分) 方程 在其 研究中 已 经取得了 高度的成功. 然而， 近十多年来， 我们越来越多地发现， 某些动态系 统不能简单地用常微分或偏微分方程来构造模型. 这类系统的典型例子就是在计 算机/ 通讯网 络、 交通问 题、 制造工程等的 研究中 发现的 . 简言之， 这类系统完全 都是人造的. 通常， 这样的系 统是由 离散事件的 发生所驱动的， 例如一个信息或 一个要求服务的到来， 一个任务或服务的 完成. 这些事件还进一步按照各种“ 运 行法则” 在系统的另一部分触发其它的事件， 对这类系统进行研究和分析的饶有 兴趣和具有挑战性的方面是: 当系统随着时间 演变时， 这些事件的错综复杂的相 互 作用， 也 就是这类系 统的 离散事件 动态 过程8 7 . 这 样的 人造 系 统我们 称 之 为 离散事件动态系统( d i s c r e t e e v e n t d y n a m i c s y s t e m ， 简称为d e d s ) . 关于c v d s 与 d e d s 的 联系 和区 别见c a o 2 4 . 对于离散事件动态系统( d e d s ) 至今还没有一个具有概括性和简明 性并被广 泛承认的定义. 粗略地说， 它是指由 离散事件按照一定的运行规则相互作用来导 致状态演化的一类动态系统. 它通常 关注的只 是系 统中 忽略定量的、 连续微变化 的 某些离散物理形态的 演化， 这些变化仅在一些异 步( 不规则、 没有统一时钟) 离 散瞬间 突 发， 而不是在连续时间内 逐渐发生. 系 统的 状态具有离散的 状态空间 和 分段定义的状态轨迹， 其变化是由一些物理事件驱动的， 如队列中 顾客的到来和 离去; 制造系统中 取工件、 加工开始和完成、 机器故障的发生与修复; 通讯系 统 信号的 发送与接收; 计算机中 数据的 读取与写人; 复杂工业过程控制系统中 过程 第 一 章 激活、 装置启动、 关闭以 及干扰的发生、 工作基点的变化等等， 可见事件亦可看 作状态的转移， 每个事件发生的时刻以及哪个事件实际发生的必然性一般是不可 预测的， 系统的状态变化具有相应的不确定性. 在d e d s 中， 系统的行为由事件 轨迹和状态轨迹共同 刻画， 不过事件比 状态起着更本质的作用， 系统的 演化取决 于离散事件之间 错综复杂的相互作用. 目 前，d e d s 已 在各种各样的 应用中 起着重要的作用， 如软件验证、 分布 式 计算、 计算机操作系统、 数据库管理系统、 计算机网 络、 通讯协议、 办公自 动化 系 统、 柔性制造系统的 分布加工优化与性能评估、 后勤服务系 统、 基于计算机的 复杂装置监控系统、多模态 ( m o d e ) 过程的高级智能控制系统以及具有逻辑 ( 即 非数伺 元件的复杂动态系统的高层协调、 或在较高层次上考虑定性的逻辑因素 ( 象电 力系 统的 设备投切与保护、 过程 控制系 统中 的 流 程等 ) ， 无不 体现d e d s 的 多 样性与复杂性， 这从客观上对d e d s 的 研究提出了 新的 要求， 要求对d e d s 的 建 模与 控 制提 供形式 化的 理 论与系 统、 详 尽的 设计 和 分析方 法， 从而 使d e d s 的 研究进人一个广泛、深人、系统探索的新阶段. 1 . 1 d e d s 的特点 d e d s 主要有以下特点: 1 . 不 连续性. d e d s 的物理状态在本质上是离散的， 尽管在某些场合可以 用 扩散模型等逼近方法来成功的处理d e d s ， 但要完全地避免d e d s 的离散性似乎 是不可能的. 任何一种想尽量一般化的d e d s 建模框架都必须要考虑到这一点. 2 . 性能a ll 度的 连续 性 . d e d s 中 的 性能 测 度往 往要用 连 续的 变量来表示， 如 平均输出、 等待时间等. 实际上， 作为一个基本的 性能变量， 时间 从其本身的 含 义来说是连续的.在 d e d s中， 将时间视为离散没有任何技米上和数学上的优 点， 而排队网络中的 各种方法、 扰动分析等正是依靠在期望或平均算子的 光滑性 质之基础上才使所进行的分析成为可能的. 3 . 随 机性 . d e d s 的 运行总 有 诸 如失效等 类不可 预知的因 素 起作 用. 所有随 机品质类模型在建模时都考虑到了随机因素. 而确定性模型和方法在它们的 应用 领域中 尽管有其各自 的 价值， 但是在做有用的随机性推广之前， 不可能替代随 机 品质类模型和方法. 4 . 层次性. 很多系统的运行是有层次性的. 不同层次上的分析和控制的要求 一宣 开 大 学 博 士 学 位 论 文3 不同， 需要各种本质不同的模型和方 . 法. 而同一层次上的各个子系统之间又有着 复杂的相互关联.这是产生d e d s 复杂性的原因之一 5 . 动态性. 仅仅研究d e d s 的稳态行为是不够的. 大多数d e d s 在到达稳态 之前 所呈 现的 动态行为与用稳态 分析计算得到的 结果有 很大的偏差. 有些系 统不 进行动态控制则达不 到稳态( 如通信网络中的 信道碰撞模型) . 因 此我们 所选择的 模型必须能充分描述系统的动态性， 在对d e d s 进行动态控制时尤其如此. 6 . 计井复杂性， d e d s 的物理状态呈指数增长，即使在大型计算机上， 要想 不使用附加结构来处理诸如马氏链并非易事甚至是不可能的. 为减少计算量需要 将 各 种降 阶 简 化 技 术 和启 发 式 方 法引 人到d e d s 中 来. 7 ， 知识和经脸的重要性 由 于d e d s 往往是一个人造系统， 而不是一个物 理上的 或自 然的系统， 因 此， 它与人的 关系就比自 然系统与人的 关系 要更密切一 些. 因 此， 在d e d s 的研究中， 理论方法必须与 人的知 识、 经验相结合， 必须充 分考虑到人机交互的重要性. 所以在 d e d s中很可能会形成一种由 各种数学理 论所刻画的定量规则和来自 专家的知识、 经验的定性规则综合起来的理论/ 知 识 集成系统. 综上所述各特点可知，d e d s 是复杂的 人造大系统，需要系统理论、控制论、运筹 学、 人工智能和计算机科学等多学科的交叉 研究. 从原理上说，d e d s 属于运筹学( o p - e r a t i o n r e s e a r c h ) 的 范畴 . 尽 管运筹 学 仅仅是 由 一些方法组成的: 线性规划、 非线性规划、 动态规划、 决策分析、 排队论、 马氏 决策规划 等. 但运筹学的定义本身是说 “ 运筹学是关 图l l d e d s研 究 的 地 位 于人造系 统中 事件和运行的 一门 科学” . 而d e d s 是由“ 运行规则” 确定的 人造系 统. 因 此， 从这个意义上说，d e d s 只 是运筹学的一 个分支. 然而，d e d s 发展 至今已 从控制论和系统论中吸 取了 许多 有益的养分， 诸如时间 响应、 频率响应、 能抄性 、 能观性等概念均已 在d e d s 的研究中 起了 重要的 作用. 再由 于d e d s 的 人造系统的特征，人工智能在 d e d s的发展也起到了相当大的作用.实际上， d e d s 是一门多学科的交叉领域. d e d s 模型的研究范畴如图 1 . 1 所示. 第 一 章综述 1 .2 d e d s 的主要模型和研究方法 d e d s 的建模与控制间 题已 经变成系 统控制领域中比 较有意义的 研究课题. 许多方法被提出 并研究了 许多间 题. 特别是一些重要性质如可控性、 可观测性和 正态 性在监控框架下被研究. 在监控过程中 ， 用监控器来监控系 统以 使受控d e d s 能够满足某种行为. 分析受控d e d s 的关键是验证系统是否满足某种期望特性; 而合成受控d e d s 的关键是构造一个反馈监控器使闭环系统满足期望性质的集 合 由 于d e d s 应用领域的多样性、 复杂性; 系统固 有的 模块、 递阶结构特点以 及并发、 通讯相互作用特征， 使 d e d s 的建模方法与相应的研究方法各异，不 能 象传统的 控制理论那样可有微分、 差分方程对系 统进行统一的描述、 并加以 研 究. 现有的比 较成熟的d e d s 理论模型和数学研究工具大致是按抽象程度的高 低和研究细节的多寡， 从逻辑、 时间、 随机品质这三个层次分别展开的 1 . 2 . 1 逻 辑层次 模 型 逻 辑层 次 模型8 0 , 1 1 9 , 1 3 7 , 1 9 3 主 要 关注 系 统的 定 性 结 构性 质 和各 部 分 行 为、 功能间的 逻辑关系. 人们根据逻辑模型研究系 统的内 在运行机制和外部条件 产生的影响， 作出最优运行方案. 该层次模型主要关心事件和状态这两个因素的 相互作用和演化逻辑顺序关系， 事件和状态都是离散集合， 因 此多用离散事件模 型来刻画， 如有限自 动机和形式语言、p e t r i 网、 有限递归过程以及图论、 有限域 代数和时态逻辑语言等. 其中， 由r a m a d g e 和w o n h a m ( r - w) 提出 的有限自 动 机 1 1 9 , 1 3 7 , 1 4 5 , 1 9 1 , 1 9 2 , 1 9 3 方 法 给出 t 逻 辑 层 次 建 模 与 控 制 的 最 基 本、 最 一 般的 框架， 是一种公认的 有效控制方法， 它将现代控制理论中的主要概念全都移植了 过 来! 1 2 8 , 2 0 1 ， 该 模型已 经 在很 多实际间 题中 得到 应用( 见 综 述 1 8 6 ) ; 用p e t r i 网 ( p n ) 1 2 8 , 1 3 6 , 2 0 6 研究d e d s 定性间 题的 控 制方 法【 1 1 5 , 1 9 5 , 2 0 6 也 是一 种很 有 前途的方法， 因为p n能够很直观地反映系统的动态过程且很紧凑地描述系统的 状态， 更主要的是p n能够很有效地表达d e d s 各组件间的并发相互作用特征: 它比 有限自 动机的描述能力强， 因此对p n控制方法的研究， 不仅是吸取有限白 动机方法的成果， 更应充分利用自 身的描述特点， 进行深入地探索; 时态逻辑方 法 1 3 4 , 1 6 刃适合于形式地确定伽范) 欲解的 实时d e d s 间 题， 它能 很经济地描 述装置、 控制器的状态转换结构，由 于它给出了关于系统转换的自 动推理， 因此 _ 南 开 大 学 博 士 学 位 论 文5 可以 处理无限 状态系统， 有助于得出 并验证符合要求的 控制器. 下面简要介绍有 限自 动机和p e t r i 网模型. 1 .2 . 1 . 1 有限自 动机模型 自 动机理论是2 0 世纪5 0 年代发展起来的，7 0 年代逐渐成熟的一门学科. 起 初作为计算机的一个重要分支在编译系统、 模式识别等方面得到广泛应用. 自8 0 年代以 来， 它在控制科学、 系统科学中 也得到广 泛应用. 比 较有影响的 有r a m a d g e 和w o n h a m 1 3 7 创立的基于有限自 动 机的d e d s r - w控制模型，m i t r o p o l is 等人 发 展 的 基于 形 式 语 言 的 非 线 性系 统 特 征 模 型一 实 用 符 号 动 力 学!2 1 6 在r - w模型中， 用有限自 动机 g = ( q , 艺， 6 , 。 ， q m ) 表示受控系统. 其中q为一有限状态集，9 o q为初始状态. e: 有限事件 集.当某个事件。 任 e发生时， 将导致状态按规律 : q 、 艺一q 转移到新的 状态.q mcq为标识状态集( 某些特殊状态集) ， 常用以 研究系统是 否到达该集合.系统行为由 事件串 e l e 2 二和相应的状态串4 o g i 来表示. 一 个 有限自 动 机g对 应于 一 个点 集为q的 有向 图 ， 它的 边集 为 集 合 ( 4 , 妇 存在o r e e ， 使得6 ( o , 4 ) = q ， 即 状态。 与4之间 存 在一 条由 事 件。 e e来 标 识 的 有向 边， 如果事件。 能使系统从状态9 转换到9 . 反之， 该图 也定义了一个有 限自 动机. 令e . 表示所有可能事件串的全体， 则e . 的任何一个子集都构成事件集e 上一个语言， 它是e元素组成的 有限事件串 ， 其中只 有一部分语言能 被自 动机g 接受， 成为由g所产生的语言， 其中 有部分事件串 对应的 状态结束于q 二中的 状 态， 它们 构成的 集合l - ( g ) c l ( g ) 称为由g 标识的 语言， 其中l ( g ) = i s : s e e * 并且6 ( s , 9 o ) 有定义 ， l - ( g ) = 。 : 。 e l ( g ) 并且6 ( s , 4 o ) e q m . 一个有限自 动机 g的事件集e分为可控事件集e 。 和不可控事件 e 。 两 类， 监控器s 能够使能/ 非使能有限自 动机g的可控事件来使得g产生的语言 满足期望行为规范，s = ( s o , 12 ) , s a 是一个 有限自 动机s a = ( e , x , e , x 0 , x - ) , 第一 章综述 lp是一个输出函数( 控制模式). r.，、1 一一 kk : 又x x一( 0 : 非 使 能 ; 1 : 使 能 ) 使 得kk ( a , x ) 0或 1 ,如果 如果 。任e。 口eu 有限自 动机g和其监控器s 组成一个闭环系统s i g ， 它产生如下3 类主要 语言: l ( s i g ) = l ( g ) f 1 l ( s ) 描述系统s i g的闭 环 行为 lm(sig) = l . ( g ) n l . ( s ) 描述系 统s i g的目 标 行为 l ( s / g ) = l . ( g ) n l ( s i g ) 描 述系 统s i g的 控 制 行 为 则有如下主要结论 1 . 设k l ( g ) 且k0 4) ， 则 存 在一 个监 控器s 使得l ( s i g ) = k的 充 要 条 件是k= 万( 即k的前闭 ) 且是可控的. 2 . 设k l ( g ) 且k544 i ， 则 a ) 存在一个监控器s 使得l - ( s i g ) 二 k的充 要条件是k是可控的. b ) 存在 一 个监控器s 使 得l ( s / g ) = k的 充 要 条 件是k是可 控的 且l - ( g ) 是封闭的. r - w的 工作奠定了基于有限自 动机的d e d s 监控理论的基础，吸引了一大 批 研 究 工 作 者. 人们 从正 规 语 言 的 极 大可 控 子 语 言的 唯 一 存 在 性 及 其 计 算2 1 、 部 分 信 息 监 控1 0 6 , 1 1 9 、 分 散 递 阶 监 控2 1 9 、 状 态 反 馈 控 制1 8 1 、 实 时 控 制1 1 4 等诸方面展开了 深入广泛的 研究， 极大地丰富了 这一理论体系. 同时， 也出 现了 一批应用研究的成果. 文献 1 0 9 应用这一理论于数据库管理系统中 用户事务的 并 发执 行间 题， 文献4 2 将 分散 监 控方法用 于控 制通讯网 络 数据传输 过程， 文 献 1 3 应用 监 控理 论解 决半导 体集成电 路 制造 车间 速 热多 处 理器的 控制间 题， 文 献 2 0 将该 理论用 于 处理车间 的 管 理间 题.