离散事件动态系统

1、 随着信息处理技术随着信息处理技术,计算机技术和机器人技术等的发展计算机技术和机器人技术等的发展 和应用和应用,在通信在通信,制造制造,交通管理交通管理,军事指挥等出现了大量军事指挥等出现了大量 的人造系统的人造系统,如柔性制造系统如柔性制造系统,大规模计算机通信网大规模计算机通信网 络络,c3i系统等系统等. 这些人造系统中这些人造系统中,对系统行为起决定作用的是对系统行为起决定作用的是离散事件离散事件, 所遵循的是一些人为的规则所遵循的是一些人为的规则.对这些人造系统的行为的对这些人造系统的行为的 研究研究,推动了离散事件动态系统的形成和发展推动了离散事件动态系统的形成和发展. 离散事件离

2、散事件是离散事件动态系统的基本要素是离散事件动态系统的基本要素,是指是指 deds中发生在离散时刻的事件中发生在离散时刻的事件,是使是使deds状态发状态发 生变动的一个行动或事情生变动的一个行动或事情. 三个基本特征三个基本特征: 1 离散事件是导致离散事件是导致deds状态发生跃变和突发新离散事件的唯状态发生跃变和突发新离散事件的唯 一因素一因素. 2 离散事件的发生是异步的离散事件的发生是异步的,非约定的非约定的,即发生时刻只能由系统即发生时刻只能由系统 的演化过程决定的演化过程决定. 3 离散事件是研究离散事件是研究deds的主体的主体,对对deds的分析归结为确定离的分析归结为确定离

3、 散事件交互影响所导致的系统状态的演变散事件交互影响所导致的系统状态的演变.对对deds的控制就的控制就 是禁止不期望事件的发生或使事件按照期望的时序发生是禁止不期望事件的发生或使事件按照期望的时序发生 柔性制造系统柔性制造系统:工件到达机床工件到达机床,工件等待加工工件等待加工,工件加工工件加工 完毕等完毕等 排队网络排队网络:顾客到达服务中心顾客到达服务中心,等待等待,接受服务接受服务,离开等离开等 计算机通信网络计算机通信网络:信息到达网络信息到达网络,信息传递及其传递结信息传递及其传递结 束束 离散事件动态系统是由离散事件驱动离散事件动态系统是由离散事件驱动,并由离散事件按照一定并由离

4、散事件按照一定 运行规则相互作用来导致系统状态演化的一类动态系统运行规则相互作用来导致系统状态演化的一类动态系统. 两个基本特点两个基本特点:deds的系统属性表现为离散事件驱动的系统属性表现为离散事件驱动 deds的的人造特性表现人造特性表现为基于人为的运行规则为基于人为的运行规则.如交通规则，如交通规则， 加工工艺约束等加工工艺约束等 在在deds中中,系统的状态为一批号码和离散变量表征系统的状态为一批号码和离散变量表征,且只能在离且只能在离 散事件驱动下和在异步离散瞬时发生跳跃式变化散事件驱动下和在异步离散瞬时发生跳跃式变化. 柔性生产线柔性生产线,系统状态为等待加工的工件号码系统状态为

5、等待加工的工件号码,作业单作业单,每个加工每个加工 中心的忙闲状况和开始加工时刻等中心的忙闲状况和开始加工时刻等. deds的动态性一方面体现为离散事件的发生驱动系统状态的的动态性一方面体现为离散事件的发生驱动系统状态的 跃变；另一方面为系统状态的跃变触发新离散事件的发生，以跃变；另一方面为系统状态的跃变触发新离散事件的发生，以 此形成状态与离散事件的交互作用。此形成状态与离散事件的交互作用。 与连续动态系统的区别与连续动态系统的区别: 1 deds的状态的状态只能在离散时间点发生变化只能在离散时间点发生变化,在驱动事件发生的在驱动事件发生的 瞬间状态发生变换瞬间状态发生变换,其它时刻不变，这

6、是系统固有的不连续属其它时刻不变，这是系统固有的不连续属 性，与离散时间系统不同，时间离散是人为通过采样装置实性，与离散时间系统不同，时间离散是人为通过采样装置实 现的，无论同步还是异步，变量的跃变时刻总是确定的。现的，无论同步还是异步，变量的跃变时刻总是确定的。 2 deds的状态变化是的状态变化是异步的异步的,并发并发的的.跃变时刻是异步的，一跃变时刻是异步的，一 个离散事件的发生，可能导致状态变化出行并发性，导致一个离散事件的发生，可能导致状态变化出行并发性，导致一 些甚至全部状态发生改变。些甚至全部状态发生改变。 3 deds的状态变换是不确定的的状态变换是不确定的.主要是离散事件的发

7、生受到内主要是离散事件的发生受到内 部和外部因素的约束部和外部因素的约束,是不确定的，因此不可编码要考虑随机是不确定的，因此不可编码要考虑随机 因素等。因素等。 4 deds的状态变化服从的是人为规则，不能采样常规的方法的状态变化服从的是人为规则，不能采样常规的方法 进行建模。进行建模。 柔性制造系统：能够按所要求的工件品种混合比来同时加柔性制造系统：能够按所要求的工件品种混合比来同时加 工多种不同工件，适应小批量多品种加工的任务。工多种不同工件，适应小批量多品种加工的任务。 由四个部分组成：由四个部分组成： 1 不同类型的加工中心，加工中心是不同类型的加工中心，加工中心是fms加工的主体，在

8、加加工的主体，在加 工中心，配备多达几十种不同功能的刀具。对不同的工件工中心，配备多达几十种不同功能的刀具。对不同的工件 和不同类型的加工，从刀具的选择到加工工艺的选择都有和不同类型的加工，从刀具的选择到加工工艺的选择都有 计算机控制。计算机控制。 2 物料自动传输系统。物料自动传输系统。fms物流自动传送采用由计算机控制物流自动传送采用由计算机控制 且一定速度按指定路径巡驶的物料小车，工件在自动小车，且一定速度按指定路径巡驶的物料小车，工件在自动小车， 缓冲区，加工中心之间的传递由机械手完成。缓冲区，加工中心之间的传递由机械手完成。 逻辑层次逻辑层次: :主要关心主要关心状态和事件状态和事件

9、这两个主要因素相互作用和这两个主要因素相互作用和 演化的逻辑顺序关系演化的逻辑顺序关系. .这两种都是离散这两种都是离散, ,有限的集合有限的集合, ,因此因此, , 所用的大多数是离散的数学模型所用的大多数是离散的数学模型, ,如形式语言和有限自动如形式语言和有限自动 机机,petri,petri网网, ,有限递归过程等有限递归过程等. .它们的共同困难是离散运算它们的共同困难是离散运算 的组合复杂性问题的组合复杂性问题. . 代数层次代数层次:主要在物理时间层次上研究主要在物理时间层次上研究deds的的代数特性代数特性 和运动过程和运动过程,主要方法是极大极小代数主要方法是极大极小代数.

10、统计性能层次统计性能层次:主要在主要在性能层次性能层次上研究随机情况下上研究随机情况下deds 的各种平均性能及其优化的各种平均性能及其优化,主要方法有排队论主要方法有排队论,广义半马广义半马 尔柯夫过程等尔柯夫过程等 离散事件的不连续本质离散事件的不连续本质,计算可行性计算可行性 大多数性能指标的连续本质大多数性能指标的连续本质 不确定性不确定性 排队网络排队网络:若干服务中心按一定的网络结构所组成的一个系统若干服务中心按一定的网络结构所组成的一个系统, 服务中心有服务中心有顾客和服务台顾客和服务台组成组成,一个服务中心通常拥有一个或一个服务中心通常拥有一个或 多个服务台多个服务台,服务中心

11、按某种约定的顺序规则服务中心按某种约定的顺序规则,依次对到来的顾依次对到来的顾 客提供服务客提供服务,顾客按一定的顾客按一定的统计规律统计规律进入某个服务中心进入某个服务中心,等待并等待并 接受服务接受服务,在一个服务中心接受完服务的顾客以一定的统计规在一个服务中心接受完服务的顾客以一定的统计规 律到其它服务中心接受服务律到其它服务中心接受服务,直到离开网络直到离开网络 排队网络的特性排队网络的特性: 顾客相继到达系统的间隔时间的分布顾客相继到达系统的间隔时间的分布;服务服务 时间的分布时间的分布;服务台的个数服务台的个数. 主要指标主要指标:系统中系统中顾客数的稳态规律分布顾客数的稳态规律分

12、布,队列的队列的平均对长平均对长,服服 务台的务台的平均利用率平均利用率,顾客平均逗留时间顾客平均逗留时间,系统平均输出等系统平均输出等 单一服务中心模型单一服务中心模型: m/m/c :顾客到来的间隔时间是平均到达顾客到来的间隔时间是平均到达 率为一定值的率为一定值的负指数分布负指数分布;服务时间的分布是平均服务率为一服务时间的分布是平均服务率为一 定值的定值的负指数分布负指数分布;拥有拥有c个平行服务台个平行服务台;到达时间和服务时间到达时间和服务时间 彼此独立彼此独立. 主要主要 指标指标:系统中系统中顾客数的稳态规律分布顾客数的稳态规律分布,队列的队列的平均对长平均对长,服务服务 台的

13、台的平均利用率平均利用率,顾客平均逗留时间顾客平均逗留时间,系统平均输出等系统平均输出等 n这些研究都是以求解任意时刻系统状态为这些研究都是以求解任意时刻系统状态为n的概率的概率pn(t)为为 基础。基础。 nm/m/1模型模型 n到达模式：顾客数无限，顾客单个到达，相互独立，一定到达模式：顾客数无限，顾客单个到达，相互独立，一定 时间的到达数服从泊松分布时间的到达数服从泊松分布 n排对规则，单对，队列长度没有限制，排对规则，单对，队列长度没有限制，fifo n单服务台，各顾客服务时间独立，服从相同的指数分布，单服务台，各顾客服务时间独立，服从相同的指数分布， 还假定到达间隔和服务时间相互独立

14、。还假定到达间隔和服务时间相互独立。 1 1 11 2 11 2 11 1 11 1 1 1111 1 0, n n n n nnnn nnnn nn nnn n n pttt pttt pttt pttt pttptttptttpttt ptttptttptptot ot pttpt pppt tt t dpt pp dt 整理得 1 001 0 01 0,11 nn pt np ttp ttptt dp t pp dt 11 01 2 100200 00 0 00 2 1 0 0 0 , 1 1,1,1 1 1 1 1 n nnn n n nn n n n n nn qn n tptt p

15、pp pp ppp pppp ppp lnpn lnp n n=0 研究稳态解， 很大，与 无关，且导数为 ， 设 1, 由概率的性质由p 得 稳态平均顾客数 稳态平均对长 顾客在系统 ,/1,wm m e w 中的逗留时间在服从参数为的负指数分布， 平均逗留时间就是 平均等待时间则等于平均逗留时间减去服务时间 2 11 11 2 3 4 1 5 n n n p p l n n q q ,n, pn n l w w =0=0 归一化条件 为顾客数是顾客数为 的稳态概归一化条件 为顾客数是顾客数为 的稳态概 率, 为输入顾客流的平均速率, 为平均服务率.率, 为输入顾客流的平均速率, 为平均服务

16、率. 1顾客稳态概率分布1顾客稳态概率分布 稳态平均顾客数 =稳态平均顾客数 = 稳态平均对长稳态平均对长 顾客稳态平均等待时间顾客稳态平均等待时间 顾客稳态平均逗留时间顾客稳态平均逗留时间 1m / m / 的稳态性能分析的稳态性能分析 1 q q w wl q little m / m /, , wl m / m / c,little. 公公式式 系系统统 稳稳态态平平均均等等待待时时间间稳稳态态平平均均对对长长之之间间 稳稳态态平平均均顾顾客客数数和和稳稳态态平平均均逗逗留留时时间间之之间间分分别别成成立立如如下下 关关系系式式 对对应应稳稳态态存存在在的的公公式式同同样样成成立立 11

17、 11 0 01 , 1,1 1 n nnn n nnn dpt ppccptnc dt dpt ppnnptnc dt dp t pp dt ncn ncn 当系统中存在 个顾客，服务速率为或者 当系统中存在 个顾客，服务速率为或者 m/m/c的稳态性能分析 1 01 0 0 0 2 11 2 1 3 n n 0 q p p l n n ncc n n n n c c q ,c,n,pn pnc c n! ,p, n!c! c pnc cc! p c! c w = =0 0 归归一一化化条条件件 为为顾顾客客数数是是顾顾客客数数为为 的的稳稳态态概概率率, , 为为输输入入顾顾客客 流流的的

18、平平均均速速率率, , 为为平平均均服服务务率率. . 1 1顾顾客客稳稳态态概概率率分分布布 稳稳态态平平均均对对长长 = = 顾顾客客稳稳态态平平均均等等待待时时间间 0 2 1 c p c! c 0 2 0 2 1 4 1 5 1 l c c wp c! c p c! c 稳稳态态平平均均停停留留时时间间 稳稳态态平平均均顾顾客客数数 = = 1 1 1 1 1 00 1 21 nn n,n n,nn n,n n,nn n t ,t,n, ,tt,th nnpht, phho h nnpht phho h 考考虑虑非非负负整整数数集集合合上上的的一一个个连连续续时时间间随随机机过过程程

19、如如果果对对某某个个整整数数存存在在正正常常数数 并并在在时时间间 的的一一个个区区间间内内同同时时成成 立立 1 1 从从状状态态 转转移移到到的的概概率率与与 无无关关 从从状状态态 转转移移到到状状态态的的概概率率与与 无无关关, , 生灭过程生灭过程 1 31 0 n,m nn nm,n mpho h n t ,t, , 对任一满足的非负整数 从状态 转移到状态对任一满足的非负整数 从状态 转移到状态 的概率的概率 就称这个连续时间随机过程为生灭过程 其中就称这个连续时间随机过程为生灭过程 其中 参数为增生率 消亡率参数为增生率 消亡率 1111 0011 0 02 3 0 nnnnn

20、nn n t ,t ptptptn, ptpt 设生灭过程的状态存在稳态概率分布,设生灭过程的状态存在稳态概率分布, 1 1111 0 0011 0 2 3 n n nnnnnnn ptn t ,ttn, dpt ptptptn, dt dpt ptpt dt 设为生灭过程在时刻 处于状态 的概率设为生灭过程在时刻 处于状态 的概率 则其微分方程组为则其微分方程组为 1 0 1 1 1 11 11 00 1 0 2 1 n i nn i i nn nn n i ni i nn n ii nn i i n t ,tp,pp n t ,sup,sup, n t p,p ppp,p 结结论论1 1:

21、 :如如果果生生灭灭过过程程的的状状态态存存在在稳稳态态概概率率分分布布则则 结结论论 : : 稳稳态态概概率率分分布布解解存存在在条条件件, ,假假设设生生灭灭过过程程的的增增生生 率率和和消消亡亡率率有有界界即即上上确确界界则则生生灭灭 过过程程的的稳稳态态概概率率分分布布存存在在的的充充要要条条件件 并并且且当当稳稳态态概概率率分分布布存存在在时时的的参参数数化化表表达达式式 1 11 n ni i 损失制的特点在于损失制的特点在于:其输入受到限制其输入受到限制,当系统中的顾客数达到事当系统中的顾客数达到事 先规定的先规定的k值时值时,继续到达的顾客将被损失掉继续到达的顾客将被损失掉,这

22、类排队系统在这类排队系统在 通信工程通信工程,制造系统中有比较广泛的应用制造系统中有比较广泛的应用 0 0 n nn n n nnc n n pt k = = cnc k tn n, 0n 设为时刻 系统中顾设为时刻 系统中顾 为顾客数为 的输出速率为顾客数为 的输出速率 客数为 的概率,包括正在接受服务客数为 的概率,包括正在接受服务 的顾客和排队的顾客.为顾客数为的顾客和排队的顾客.为顾客数为 , , 的的 约定，约定， 输入速率输入速率 1 1 1 0 0 1 1 0 0 0 m m/c/k 11 1 !1 1 11 ! 1 0,1,1 ! 1 ! n ck cn c n cn c n

23、n n n n c p c c ncc p kcc nc pnc n p pn cc 结论1 稳态概率分布，损失制/的稳态概率分布存在，且 具有如下表达式 ,1,c ck 01 2 1 0 0 2 111 ! 1 3 ! 1 1 q c k k ck c qn n c n kc nq n=0n k k m m/c/kl pc lnc pkc c c m m/c/kl cnc l=nplcp n m m/c/kw l w = p p 结论 损失制/的稳态平均对长为 结论 损失制/的稳态平均顾客数 为 结论4损失制/的稳态平均逗留时间为 其中为稳态下实际进入系统的顾客的输入速率 0 5/ / 1

24、6/ / 1 ! q q q k k k k k c m m c kw l w p m m c k p pp cc 结论 损式制的稳态平均等待时间为 结论 损失制的稳态平均顾客损失率，即单位时间内内系统 容量有限而损失的顾客数与达到顾客数之比 服务速率依赖于状态的m/m/1 1 0 0 0 1 1/1,0 1 ,1,2, ! ! 2/1,0 1 3/1,0 n n n nn n n n q qn n n n mm p p ppn n n mm l lnp mm 结论 稳态概率分布，对服务速率为的如果，则其 稳态概率分布存在， 结论 稳态平均对长，对服务速率为的如果，则其 稳态平均对长 结论 稳

25、态平均顾客数，对服务速率为的如果，则其 稳态平均顾 1 qn n l lnp 客数 1 网络包含网络包含m m个服务中心个服务中心, ,每个服务中心为单一服务中心的每个服务中心为单一服务中心的m/m/cm/m/c 2对于对于第第i个服务中心个服务中心,具有具有ci个相同的平行服务台个相同的平行服务台,输入到第输入到第i个服个服 务中心的顾客形成相互独立且速率为务中心的顾客形成相互独立且速率为i i的的possionpossion流流. .顾客在第顾客在第i i 个服务中心接受服务个服务中心接受服务, ,其服务时间为均值为一定值的负指数分布其服务时间为均值为一定值的负指数分布. . 顾客的到达间

26、隔和服务时间彼此独立顾客的到达间隔和服务时间彼此独立 2 2 服务规则为服务规则为fcfsfcfs 3 3 顾客在第顾客在第i i个服务中心接受服务后个服务中心接受服务后, ,或以转移概率转移到其它或以转移概率转移到其它 服务中心或离开系统服务中心或离开系统 4 4 每个服务中心的缓冲区容量无限大每个服务中心的缓冲区容量无限大. . fork-join广泛存在于包含并行处理和并行作业系统中。广泛存在于包含并行处理和并行作业系统中。 计算机并行处理中，一个任务首先被分解成几个子任务，并由计算机并行处理中，一个任务首先被分解成几个子任务，并由 不同的处理机对它们进行处理。对一些子任务，需要等待全部

27、不同的处理机对它们进行处理。对一些子任务，需要等待全部 完成处理后，才能进入下一到程序，进行组合处理。完成处理后，才能进入下一到程序，进行组合处理。 制造系统中，装配生产线和拆卸生产线制造系统中，装配生产线和拆卸生产线 两个并联服务台的两个并联服务台的fork-join排队网络排队网络：每个服务台的缓冲器：每个服务台的缓冲器 容量无限或有限，服务规则容量无限或有限，服务规则fcfs，顾客到达服从，顾客到达服从possion分分 布，两个服务台的服务时间服从指数分布，服务过程独立布，两个服务台的服务时间服从指数分布，服务过程独立 m个并联服务台的个并联服务台的fork-join排队网络排队网络

28、具有集中缓冲器的批输入具有集中缓冲器的批输入fork-join系统系统：系统具有容量为：系统具有容量为n 的集中排队空间，的集中排队空间，m个并联服务台，顾客按批输入方式到达，个并联服务台，顾客按批输入方式到达， 批顾客中的顾客独立地在批顾客中的顾客独立地在各个服务台接受服务各个服务台接受服务，完成服务的，完成服务的 顾客在服务台后的缓冲空间等待，直到同批中的所有顾客服顾客在服务台后的缓冲空间等待，直到同批中的所有顾客服 务完成，然后按批离开系统。务完成，然后按批离开系统。 主要优点：主要优点：可以描述一般类型的排队系统和具有比较成熟的概可以描述一般类型的排队系统和具有比较成熟的概 率论和随机过程的理论基础率论和随机过程的理论基础，当所研究的排队系统为乘积解网，当所研究的排队系统为乘积解网 络时，分析过程已十分成熟。络时，分析过程已十分成熟。 局限：对所研究的排队系统引入的局限：对所研究的排队系统引入的假设条件过强假设条件过强，通常要求系，通常要求系 统的缓冲区容量为无穷大，这一假设大大限制了排队网络方法统的缓冲区容量为无穷大，这一假设大大限制了排队网络方法 的应用范围。的应用范围。 摄动分析法是性能层次上摄动分析法是性能层次上deds的主要建模方法的主要建模方法，其实质是，其实质是排排 队网络分析方法和计算机仿真方法的有