离散事件动态系统课件

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 不同类型的加工中心，加工中心是不同类型的加工中心，加工中心是

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

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

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

11、,服务中心有服务中心有顾客和服务台顾客和服务台组成组成,一个服务中心通常拥有一个或一个服务中心通常拥有一个或多个服务台多个服务台,服务中心按某种约定的顺序规则服务中心按某种约定的顺序规则,依次对到来的顾依次对到来的顾客提供服务客提供服务,顾客按一定的顾客按一定的统计规律统计规律进入某个服务中心进入某个服务中心,等待并等待并接受服务接受服务,在一个服务中心接受完服务的顾客以一定的统计规在一个服务中心接受完服务的顾客以一定的统计规律到其它服务中心接受服务律到其它服务中心接受服务,直到离开网络直到离开网络排队网络的特性排队网络的特性: 顾客相继到达系统的间隔时间的分布顾客相继到达系统的间隔时间的分布

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

13、立彼此独立.离散事件动态系统离散事件动态系统离散事件动态系统离散事件动态系统 111121121111111111110, nnnnnnnnnnnnnnnnnnnPtttPtttPtttPtttPttPtttPtttPtttPtttPtttPtPtOtOtPttPtPPPttttdPtPPdt整理得 10010010,11 nnPtnP ttP ttPttdP tPPdt离散事件动态系统 110121002000000021000,11,1,11111 nnnnnnnnnnnnnnqnntPttPPPPPPPP PPPPPPPLnPnLnPnn=0研究稳态解， 很大，与 无关，且导数为 ，设

14、1, 由概率的性质由P得稳态平均顾客数稳态平均对长顾客在系统,/1,WM ME W中的逗留时间在服从参数为的负指数分布，平均逗留时间就是平均等待时间则等于平均逗留时间减去服务时间离散事件动态系统 2111123415nnnpp L nnqq,n, pnnLww =0=0归一化条件 为顾客数是顾客数为 的稳态概归一化条件 为顾客数是顾客数为 的稳态概率, 为输入顾客流的平均速率, 为平均服务率.率, 为输入顾客流的平均速率, 为平均服务率.1顾客稳态概率分布1顾客稳态概率分布稳态平均顾客数 =稳态平均顾客数 =稳态平均对长稳态平均对长顾客稳态平均等待时间顾客稳态平均等待时间顾客稳态平均逗留时间顾

15、客稳态平均逗留时间1M / M / 的的稳稳态态性性能能分分析析离散事件动态系统1qqwwLqLittleM / M /, wLM / M / c,Little. 公公式式系系统统 稳稳态态平平均均等等待待时时间间稳稳态态平平均均对对长长之之间间稳稳态态平平均均顾顾客客数数和和稳稳态态平平均均逗逗留留时时间间之之间间分分别别成成立立如如下下关关系系式式 对对应应稳稳态态存存在在的的公公式式同同样样成成立立离散事件动态系统离散事件动态系统 1111001,1,11 nnnnnnnndPtPPccPtncdtdPtPPnnPtncdtdP tPPdtncnncn当系统中存在 个顾客，服务速率为或者

16、当系统中存在 个顾客，服务速率为或者离散事件动态系统M/M/c的稳态性能分析 101000211213nn0qpp L nnnccnnnn ccq,c,n,pnpnccn!,p,n!c! cpnccc!pc! cw = =0 0归归一一化化条条件件 为为顾顾客客数数是是顾顾客客数数为为 的的稳稳态态概概率率, , 为为输输入入顾顾客客流流的的平平均均速速率率, , 为为平平均均服服务务率率. .1 1顾顾客客稳稳态态概概率率分分布布稳稳态态平平均均对对长长 = =顾顾客客稳稳态态平平均均等等待待时时间间 021cpc! c 离散事件动态系统 020214151L ccwpc! cpc! c 稳

17、稳态态平平均均停停留留时时间间稳稳态态平平均均顾顾客客数数 = =离散事件动态系统 1111100121nnn,nn,nnn,nn,nnN t ,t,n,tt,thnnPht,Phho hnnPhtPhho h 考考虑虑非非负负整整数数集集合合上上的的一一个个连连续续时时间间随随机机过过程程如如果果对对某某个个整整数数存存在在正正常常数数并并在在时时间间 的的一一个个区区间间内内同同时时成成立立1 1 从从状状态态 转转移移到到的的概概率率与与 无无关关从从状状态态 转转移移到到状状态态的的概概率率与与 无无关关, ,生灭过程生灭过程离散事件动态系统 1310n,mnnnm,nmPho hN

18、t ,t, 对对任任一一满满足足的的非非负负整整数数 从从状状态态 转转移移到到状状态态的的概概率率就就称称这这个个连连续续时时间间随随机机过过程程为为生生灭灭过过程程 其其中中参参数数为为增增生生率率 消消亡亡率率离散事件动态系统 11110011002 30nnnnnnnN t ,tptptptn,ptpt 设生灭过程的状态存在稳态概率分布,设生灭过程的状态存在稳态概率分布, 111110001102 3nnnnnnnnnptN t ,ttn,dptptptptn,dtdptptptdt 设为生灭过程在时刻 处于状态 的概率设为生灭过程在时刻 处于状态 的概率则其微分方程组为则其微分方程组

19、为离散事件动态系统 101111111001021ninniinnnnniniinnniinniiN t ,tp ,ppN t,sup,sup,N tp,pppp,p 结结论论1 1: :如如果果生生灭灭过过程程的的状状态态存存在在稳稳态态概概率率分分布布则则结结论论 : : 稳稳态态概概率率分分布布解解存存在在条条件件, ,假假设设生生灭灭过过程程的的增增生生率率和和消消亡亡率率有有界界即即上上确确界界则则生生灭灭过过程程的的稳稳态态概概率率分分布布存存在在的的充充要要条条件件并并且且当当稳稳态态概概率率分分布布存存在在时时的的参参数数化化表表达达式式111nnii 离散事件动态系统损失制的

20、特点在于损失制的特点在于:其输入受到限制其输入受到限制,当系统中的顾客数达到事当系统中的顾客数达到事先规定的先规定的K值时值时,继续到达的顾客将被损失掉继续到达的顾客将被损失掉,这类排队系统在这类排队系统在通信工程通信工程,制造系统中有比较广泛的应用制造系统中有比较广泛的应用 00nnnnn nncnn pt K =cncKtnn,0n 设为时刻 系统中顾设为时刻 系统中顾为顾客数为 的输出速率为顾客数为 的输出速率客数为 的概率,包括正在接受服务客数为 的概率,包括正在接受服务的顾客和排队的顾客.为顾客数为的顾客和排队的顾客.为顾客数为, ,的的约定，约定，输入速率输入速率离散事件动态系统1

21、110011000M M/c/K111!1111!10,1,1!1!ncK cncncncnnnnn cpccnccpKccncpncnppncc 结论1 稳态概率分布，损失制/的稳态概率分布存在，且具有如下表达式,1,c cK离散事件动态系统0121002111! 13!11qcKK cK cqnn cnKcnqn=0nKK M M/c/KLpcLnc pKccc M M/c/KLcncL=npLcpnM M/c/KWLW =pp 结论 损失制/的稳态平均对长为结论 损失制/的稳态平均顾客数 为结论4损失制/的稳态平均逗留时间为其中为稳态下实际进入系统的顾客的输入速率离散事件动态系统05/

22、/16/ /1!qqqKKKKK cM M c KWLWpM M c Kpppcc结论 损式制的稳态平均等待时间为结论 损失制的稳态平均顾客损失率，即单位时间内内系统容量有限而损失的顾客数与达到顾客数之比离散事件动态系统 服务速率依赖于状态的M/M/1100011/1,01,1,2,!2/1,013/1,0nnnnnnnnqqnnnnMMppppnnnMMLLnpMM结论 稳态概率分布，对服务速率为的如果，则其稳态概率分布存在，结论 稳态平均对长，对服务速率为的如果，则其稳态平均对长结论 稳态平均顾客数，对服务速率为的如果，则其稳态平均顾1qnnLLnp客数离散事件动态系统1 网络包含网络包含

23、M M个服务中心个服务中心, ,每个服务中心为单一服务中心的每个服务中心为单一服务中心的M/M/cM/M/c2对于对于第第i个服务中心个服务中心,具有具有ci个相同的平行服务台个相同的平行服务台,输入到第输入到第i个服个服务中心的顾客形成相互独立且速率为务中心的顾客形成相互独立且速率为i i的的PossionPossion流流. .顾客在第顾客在第i i个服务中心接受服务个服务中心接受服务, ,其服务时间为均值为一定值的负指数分布其服务时间为均值为一定值的负指数分布. .顾客的到达间隔和服务时间彼此独立顾客的到达间隔和服务时间彼此独立2 2 服务规则为服务规则为FCFSFCFS3 3 顾客在第

24、顾客在第i i个服务中心接受服务后个服务中心接受服务后, ,或以转移概率转移到其它或以转移概率转移到其它服务中心或离开系统服务中心或离开系统4 4 每个服务中心的缓冲区容量无限大每个服务中心的缓冲区容量无限大. .离散事件动态系统Fork-Join广泛存在于包含并行处理和并行作业系统中。广泛存在于包含并行处理和并行作业系统中。计算机并行处理中，一个任务首先被分解成几个子任务，并由计算机并行处理中，一个任务首先被分解成几个子任务，并由不同的处理机对它们进行处理。对一些子任务，需要等待全部不同的处理机对它们进行处理。对一些子任务，需要等待全部完成处理后，才能进入下一到程序，进行组合处理。完成处理后

25、，才能进入下一到程序，进行组合处理。制造系统中，装配生产线和拆卸生产线制造系统中，装配生产线和拆卸生产线离散事件动态系统两个并联服务台的两个并联服务台的Fork-Join排队网络排队网络：每个服务台的缓冲器：每个服务台的缓冲器容量无限或有限，服务规则容量无限或有限，服务规则FCFS，顾客到达服从，顾客到达服从Possion分分布，两个服务台的服务时间服从指数分布，服务过程独立布，两个服务台的服务时间服从指数分布，服务过程独立M个并联服务台的个并联服务台的Fork-Join排队网络排队网络具有集中缓冲器的批输入具有集中缓冲器的批输入Fork-Join系统系统：系统具有容量为：系统具有容量为N的集

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