运筹学第7章随机服务理论概述-课件（PPT·精·选）.ppt

? 管理与人文学院忻展红 1999 ,4第七章随机服务理论概述确定型只是随机现象的特例 2 随机服务系统?系统的输入与输出是随机变量? . Erlang 于 1909~1920 年发表了一系列根据话务量计算电话机键配置的方法,为随机服务理论奠定了基础?又称为排队论( Queuing Theory )或拥塞理论( Congestion Theory ) 顾客源三个服务台离去的顾客随机服务系统排队等待顾客...3 与服务系统性能相关的特性?服务系统存在来自两个矛盾方面的要求–顾客希望服务质量好,如排队等待时间短,损失率低–系统运营方希望设备利用率高?给用户一个经济上能够承受的满意的质量?哪些系统特性会影响系统的性能? –服务机构的组织方式与服务方式–顾客的输入过程和服务时间分布–系统采用的服务规则 服务机构的组织方式与服务方式–单台制和多台制–并联服务–串联服务–串并联服务、网络服务–全利用度、部分利用度 4 与服务系统性能相关的特性 输入过程和服务时间–顾客单个到达或成批到达–顾客到达时间间隔的分布和服务时间的分布–顾客源是有限的还是无限的 服务规则–损失制–等待制:先到先服务( FIFO) ,后到先服务,随机服务,优先权服务–混合制–逐个到达,成批服务;成批到达,逐个服务 5 随机服务过程?单台服务系统、等待制、先到先服务?顾客在系统中的总时长:逗留时间=等待时长+服务时长?等待时长与顾客到达率和服务时长有关顾客到达时刻开始服务时刻服务终结时刻t 1234 ? 1? 2? 3? 4 w 2w 3h 1h 2h 3h 4空 12346 ?当服务台连续不断服务时,有如下关系: w i +1+? i +1 = w i+h i?w i+h i表示了累计的未完成的服务时长,一般地有????????????????0 if0 0 if 1 1 1 1iii iiiiiiihw hw hww????? i ,w i , h i可通过写实来获得,另一种写实法?(t)代表时段(0, t)中累计到达顾客数?(t)代表时段(0, t)中累计接受服务的顾客数?(t)代表时段(0, t)中累计服务完毕的顾客数?则在任意考察时刻 t,有正在等待的顾客数: L (t)= ?(t ) ??(t) 正在接受服务的顾客数: L s (t)= ?(t ) ??(t) 系统中逗留的顾客数: N (t)= ?(t ) ??(t) 7 ?上述关系是普遍成立的,与服务台设置和服务规则无关?下面分析等待顾客数、等待时间和顾客到达率的关系–到达率定义为单位时间内平均到达的顾客数,即? t = ?(t ) / t–令?(t ) 表示在时段(0, t)内到达系统内顾客的总逗留时长–则每一个顾客的平均逗留时间为 W dt = ?(t ) /?(t) –系统中平均逗留顾客数可表达为 L dt = ?(t ) / t = ( ?(t ) / t )(?(t ) /?(t ) ) = ? t W dt ( Little formula ) t 系统中逗留顾客数平均逗留顾客数 8 ?系统处于稳态时的利特尔公式: L d = ?W d ?利特尔公式也是普遍成立的,已知其中任两个量,可以求出另一个量?利特尔公式的分解: L d = ?W d = ?(W q + h ) = L q + L nL q = ?W qL n = ?h –W q是顾客的平均排队等待时间–L q是排队等待的平均队长–h是顾客的平均服务时长–L n是同时接受服务的平均顾客数(即平均服务台占用数) 9 服务时间与间隔时间 概述?顾客的服务时间由于多种原因具有不确定性,最好的描述方法就是概率分布;同样顾客到达的间隔时间也具有一定的概率分布?服务时间和到达间隔时间服从什么分布?可以先通过统计得到经验分布,然后再做理论假设和检验?经验分布一般采用直方图来表示,如下图频率% 30 20 1024 68 通话分钟 10 ?若统计区间分得越细,样本越多,则经验分布的轮廓越接近曲线?一般服务时间和间隔时间都是非负的连续实变量,令 h代表服务时间, ?代表间隔时间, t为给定的时间,则它们的概率分布函数分别表示为 F(t )=P{h?t}F(t )=P{??t} ?它们的概率密度函数为 f(t )=F?(t),具有性质: f(t)?0,?f(t)dt =1 ?服务时间落在区间(a, c)的概率为??)()()(aFcF dttfchaP ca???????服务时间落在区间(t, t+?t)的概率为 P{ t < h ?t+?t }= f(t)?t ?平均服务