离散事件动态系统

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散,事件,动态,系统,研究背景,随着信息处理技术,计算机技术和机器人技术等的开展和应用,在通信,制造,交通管理,军事指挥等出现了大量的人造系统,如柔性制造系统,大规模计算机通信网络,C3I系统等.,这些人造系统中,对系统行为起决定作用的是离散事件,所遵循的是一些人为的规那么.对这些人造系统的行为的研究,推动了离散事件动态系统的形成和开展.,离散事件,离散事件是离散事件动态系统的根本要素,是指DEDS中发生在离散时刻的事件,是使DEDS状态发生变动的一个行动或事情.,三个根本特征:,1 离散事件是导致DEDS状态发生跃变和突发新离散事件的唯一因素.,2 离散事件的发生是异步的,非约定的,即发生时刻只能由系统的演化过程决定.,3 离散事件是研究DEDS的主体,对DEDS的分析归结为确定离散事件交互影响所导致的系统状态的演变.对DEDS的控制就是禁止不期望事件的发生或使事件按照期望的时序发生,离散事件,柔性制造系统:工件到达机床,工件等待加工,工件加工完毕等,排队网络:顾客到达效劳中心,等待,接受效劳,离开等,计算机通信网络:信息到达网络,信息传递及其传递结束,离散事件动态系统,离散事件动态系统是由离散事件驱动,并由离散事件按照一定运行规那么相互作用来导致系统状态演化的一类动态系统.,两个根本特点:DEDS的系统属性表现为离散事件驱动,DEDS的人造特性表现为基于人为的运行规那么.如交通规那么，加工工艺约束等,在DEDS中,系统的状态为一批号码和离散变量表征,且只能在离散事件驱动下和在异步离散瞬时发生跳跃式变化.,柔性生产线,系统状态为等待加工的工件号码,作业单,每个加工中心的忙闲状况和开始加工时刻等.,DEDS的动态性一方面表达为离散事件的发生驱动系统状态的跃变；另一方面为系统状态的跃变触发新离散事件的发生，以此形成状态与离散事件的交互作用。,离散事件动态系统,与连续动态系统的区别:,1 DEDS的状态只能在离散时间点发生变化,在驱动事件发生的瞬间状态发生变换,其它时刻不变，这是系统固有的不连续属性，与离散时间系统不同，时间离散是人为通过采样装置实现的，无论同步还是异步，变量的跃变时刻总是确定的。,2 DEDS的状态变化是异步的,并发的.跃变时刻是异步的，一个离散事件的发生，可能导致状态变化出行并发性，导致一些甚至全部状态发生改变。,3 DEDS的状态变换是不确定的.主要是离散事件的发生受到内部和外部因素的约束,是不确定的，因此不可编码要考虑随机因素等。,4 DEDS的状态变化服从的是人为规那么，不能采样常规的方法进行建模。,柔性制造系统：能够按所要求的工件品种混合比来同时加工多种不同工件，适应小批量多品种加工的任务。,由四个局部组成：,1 不同类型的加工中心，加工中心是FMS加工的主体，在加工中心，配备多达几十种不同功能的刀具。对不同的工件和不同类型的加工，从刀具的选择到加工工艺的选择都有计算机控制。,2 物料自动传输系统。FMS物流自动传送采用由计算机控制且一定速度按指定路径巡驶的物料小车，工件在自动小车，缓冲区，加工中心之间的传递由机械手完成。,3 计算机控制单元 FMS的控制中心,根本功能包括：对工件流向的控制，加工任务的调度，运行状态的监控，物流小车的调度等,4 分布于各加工中心前的缓冲区。,缓冲区存放暂时不加工的工件，设置缓冲区的目的在于改善由于各加工中心在作业时间上的不同而造成的物流不均衡性，防止出现阻塞。,各加工中心对各类工件的加工活动构成系统的状态，工件和加工中心组成系统的资源，资源的投入和释放构成离散事件。,建模与分析,逻辑层次:主要关心,状态和事件,这两个主要因素相互作用和演化的逻辑顺序关系.这两种都是离散,有限的集合,因此,所用的大多数是离散的数学模型,如形式语言和有限自动机,Petri网,有限递归过程等.它们的共同困难是离散运算的组合复杂性问题.,代数层次:主要在物理时间层次上研究DEDS的,代数特性和运动过程,主要方法是极大极小代数.,统计性能层次:主要在,性能层次,上研究随机情况下DEDS的各种平均性能及其优化,主要方法有排队论,广义半马尔柯夫过程等,建模与分析的困难,离散事件的不连续本质,计算可行性,大多数性能指标的连续本质,不确定性,排队系统,排队系统的组成,包括三局部：,(1)到达模式，指顾客按怎样的规律到达，描述顾客到达的统计特性,(2)效劳台，包括效劳台的数量，效劳时间等,(3)排队规那么，包括FIFO,LIFO,随机效劳等,排队系统研究的主要内容是如何通过的到达模式何效劳时间的概率分布，来研究排队系统的队列长度何效劳台的效劳效率。,到达模式,平均到达间隔时间Ta，,平均到达速率 单位时间内到达的顾客数，为平均到达间隔时间的倒数,到达间隔分布函数,到达时间变化系数,指到达间隔时间的标准差与平均到达间隔时间之比。,顾客到达，可能一个一个，可能成批，到达的时间间隔可以确定，也可以随机；到达过程可以平稳，指相继到达的时间间隔分布与参数与时间原点无关，也可以是非平稳的,效劳台,平均效劳时间，平均效劳速率，效劳时间分布。,按几个形式，可以没有效劳元，可以有多个；多个效劳台时，效劳台可以并列，串列，混合。,排对规那么,两种：损失制，指顾客到达时，如所有效劳台被占用，随即离去；或者系统中的顾客数到达一定数量后，到达的顾客损失掉了。,等待制，顾客到达时，如没有效劳台可以为之效劳，那么等待。排队规那么有,FIFO,LIFO如做电梯，仓库里存放钢板等,随机效劳如 接线台,优先权效劳如急诊病人优先,最短处理时间先效劳SPT,对于n个效劳台，可以1,n+1,2n+1,排一对，2，n+2,2n+2,排一队，也可以排一个对，对首的顾客先效劳，现在银行的排对就是这样；也可以这样排成几对，顾客到达时，以概率pi 排到第i对，,混合制,排队过长时，顾客离开。,或者等待时间小于某一时间时，顾客等待；否那么离去,队列的度量,平均到达速率和平均效劳速率,设备利用率为两种之比，,队列长度和排对时间，都是随机量,排队模型的分类,X/Y/Z分别指相继到达间隔时间的分布，效劳时间的分布和效劳台数量。前两种有一些符号代表分布如M-负指数分布，D-确定性，Ek-k阶爱尔朗分布,排队网络方法,排队网络:假设干效劳中心按一定的网络结构所组成的一个系统,效劳中心有顾客和效劳台组成,一个效劳中心通常拥有一个或多个效劳台,效劳中心按某种约定的顺序规那么,依次对到来的顾客提供效劳,顾客按一定的统计规律进入某个效劳中心,等待并接受效劳,在一个效劳中心接受完效劳的顾客以一定的统计规律到其它效劳中心接受效劳,直到离开网络,排队网络的特性:顾客相继到达系统的间隔时间的分布;效劳时间的分布;效劳台的个数.,主要指标:系统中顾客数的稳态规律分布,队列的平均对长,效劳台的平均利用率,顾客平均逗留时间,系统平均输出等,排队网络方法,单一效劳中心模型:M/M/c:顾客到来的间隔时间是平均到达率为一定值的负指数分布;效劳时间的分布是平均效劳率为一定值的负指数分布;拥有c个平行效劳台;到达时间和效劳时间彼此独立.,排队系统分析,对于随机排对系统，在给定到达和效劳条件下，研究主要指标:系统中顾客数的稳态规律分布,队列的平均对长,效劳台的平均利用率,顾客平均逗留时间,系统平均输出等,这些研究都是以求解任意时刻系统状态为n的概率Pn(t)为根底。,M/M/1模型,到达模式：顾客数无限，顾客单个到达，相互独立，一定时间的到达数服从泊松分布,排对规那么，单对，队列长度没有限制，FIFO,单效劳台，各顾客效劳时间独立，服从相同的指数分布，还假定到达间隔和效劳时间相互独立。,排队系统分析,系统的到达模式效劳参数为的泊松分布，效劳时间服从参数为的指数分布，那么在t,t+t内,有一个顾客到达的概率为t+O(t2),没有顾客到达的概率为1-t+O(t2),有顾客接受效劳时，一个顾客被效劳完的概率为 t+O(t2),没有顾客离去的概率为1-t+O(t2),多于一个顾客到达或离去的概率为O(t2),在t+t时刻，系统中还有n个顾客，只有四种可能，,t时刻顾客数,时间区间,到达 离去,时刻,t+t,n,n,n+1,n,n-1,n,n,n,M/M/c的稳态性能分析各个效劳台的平均效劳速率相等,t时刻顾客数,时间区间,到达 离去,时刻,t+t,n,n,n+1,n,n-1,n,n,n,M/M/c的稳态性能分析,生灭过程,损失制M/M/c/K排队网络,损失制的特点在于:其输入受到限制,当系统中的顾客数到达事先规定的K值时,继续到达的顾客将被损失掉,这类排队系统在通信工程,制造系统中有比较广泛的应用,效劳速率依赖于状态的M/M/1,Jackson开环排队网络,1 网络包含M个效劳中心,每个效劳中心为单一效劳中心的M/M/c,2对于第i个效劳中心,具有ci个相同的平行效劳台,输入到第i个效劳中心的顾客形成相互独立且速率为i的Possion流.顾客在第i个效劳中心接受效劳,其效劳时间为均值为一定值的负指数分布.顾客的到达间隔和效劳时间彼此独立,2 效劳规那么为FCFS,3 顾客在第i个效劳中心接受效劳后,或以转移概率转移到其它效劳中心或离开系统,4 每个效劳中心的缓冲区容量无限大.,Fork-Join排队网络,Fork-Join广泛存在于包含并行处理和并行作业系统中。,计算机并行处理中，一个任务首先被分解成几个子任务，并由不同的处理机对它们进行处理。对一些子任务，需要等待全部完成处理后，才能进入下一到程序，进行组合处理。,制造系统中，装配生产线和拆卸生产线,Fork-Join排队网络,两个并联效劳台的Fork-Join排队网络：每个效劳台的缓冲器容量无限或有限，效劳规那么FCFS，顾客到达服从Possion分布，两个效劳台的效劳时间服从指数分布，效劳过程独立,M个并联效劳台的Fork-Join排队网络,具有集中缓冲器的批输入Fork-Join系统：系统具有容量为N的集中排队空间，M个并联效劳台，顾客按批输入方式到达，批顾客中的顾客独立地在各个效劳台接受效劳，完成效劳的顾客在效劳台后的缓冲空间等待，直到同批中的所有顾客效劳完成，然后按批离开系统。,排队网络方法的优缺点,主要优点：可以描述一般类型的排队系统和具有比较成熟的概率论和随机过程的理论根底，当所研究的排队系统为乘积解网络时，分析过程已十分成熟。,局限：对所研究的排队系统引入的假设条件过强，通常要求系统的缓冲区容量为无穷大，这一假设大大限制了排队网络方法的应用范围。,摄动分析法,摄动分析法是性能层次上DEDS的主要建模方法，其实质是排队网络分析方法和计算机仿真方法的有机结合。继承了排队网络方法可以处理一般形式网络和可以分析系统统计性能的优哦点，防止了要求缓冲区容量为无限和效劳时间为指数分布等限制条件。,PA方法根本分析步骤,1 样本轨道的描述即对DEDS的离散事件过程建立相应的状态方程。对于M个效劳中心的DEDS，定义效劳中心的工况状态，事件和变量如效劳中心队列长度，下一事件发生时刻等，然后建立状态方程。,摄动分析法,2 摄动的产生,对于排队系统，参数或状态的摄动，会对系统样本轨道的事件序列表产生影响，摄动样本轨道。常将摄动量的形式取为随机变量的均值。,具体过程：由随机变量均值的摄动导出随机变量样本值的摄动。摄动样本轨道的构造即重新描述状态方程。确定标称样本轨道和摄动样本轨道上的相应事件。所谓相应事件是指对应于同一效劳中心的相同序号的事件。,研究摄动产生的目的是建立标称样本轨道和摄动样本轨道中相应事件发生时刻间的关系。,摄动分析法,3,摄动的传播,即分析由于状态或参数的摄动而导致对系统中其他事件发生时刻的连锁性摄动。,4,估计系统性能对参数的灵敏度,存在的问题：,1 实际排队系统难以满足确定性相似条件,2,摄动分析估计的无偏性和强一致性要求。,