山大《运筹学》课件08排队论

1、第一节 随机服务系统概论随机服务系统的基本组成部分 输入过程 排队规则 服务机构 记号方案常用的概率分布和最简单流 负指数分布 最简单流 生灭过程排队系统的基本组成部分输入过程顾客按照怎样的规律到达排队规则顾客按照一定规则排队等待服务服务机构服务机构的设置,服务台的数量,服务的方式,服务时间分布等服务台顾客到达列队正在接受服务的顾客服务完成离去顾客到达列队服务台1服务台2服务台3服务完成离去输入过程顾客来源：有限/无限顾客数量：有限/无限经常性的顾客来源 顾客到达间隔时间: 到下一个顾客到达的时间 服从某一概率分布 (指数分布)顾客的行为假定 在未服务之前不会离开 当看到队列很长的时候离开 从

2、一个队列移到另一个队列队列/排队规则队列容量：有限/无限排队规则 先来先服务 (FCFS) 后来先服务 随机服务 有优先权的服务服务机构服务设施， 服务渠道与服务台 服务台数量 服务时间分布： 指数, 常数, k级Erlang记号方案顾客到达时间间隔分布/服务时间分布/服务台数目/排队系统允许的最大顾客容量/顾客总体数量/排队规则(Kendall记号)M/M/1/FCFS M/M/1/M：指数分布(Markovian)D：定长分布(常数时间)Ek：k级Erlang分布G：普通的概率分布(任意概率分布)记号方案系统状态：排队系统顾客的数量N(t)：在时间t排队系统中顾客的数量队列长度：等待服务的

3、顾客的数量Pn(t)：在时间t,排队系统中恰好有n个顾客的概率s：服务台的数目续负指数分布f(t)t负指数分布负指数分布 有一个重要的性质，即无记忆性或称无后效性。若把 解释为电子元件的寿命，无记忆性就是不论现在的年龄多大，剩余寿命的条件分布与原分布相同，不受已有年龄的影响，用概率公式表示为P( t+x| t)=P( x)反过来，连续型随机变量的分布函数中，只有负指数分布具有无记忆性。续最简单流随机事件流：随机时刻出现的事件组成的序列最简单流：如果一个事件流N(t),t0，满足3个条件 1o平稳性：以任何时刻t0为起点，(t0,t0+t时间内出现的事件数只与时间长度t有关，而与起点t0无关，即

4、Pk(t)=P(N(t)=k)，t=0,1,2, 2o无后效性：在(t0,t0+t时间内出现k个事件与t0以前出现的事件数无关 3o普通性：在充分小的时间区间t内，发生两个或两个以上事件的概率是比t高阶的无穷小量，即最简单流有上述三个条件下，可以推出续生灭过程生灭过程：设有某个系统具有状态集S=0,1,2, ，若系统的状态随时间t变化的过程N(t);t0满足以下条件设在时刻t统处于状态n的条件下，再经过长为t的时间 (1)转移到n+1(0n+)的概率为nt+o(t) (2)转移到n-1(1n+)的概率为nt+o(t) (3)转移到S-n-1,n,n+1的概率为o(t)其中n0, n0为与t无关

5、的固定常数有限状态生灭过程：若S仅包含有限个元素， S=0,1,2, ,k，也满足以上条件第二节 无限源的排队系统M/M/1/系统M/M/1/k系统M/M/c/系统排队系统费用优化决策M/M/1/系统设顾客流是参数为的最简单流，是单位时间内平均到达的顾客人数，即顾客到达的时间间隔相互独立并且服从期望为1/的负指数分布。只有一个服务台，服务一个顾客的服务时间v服从参数为的负指数分布。平均服务时间为E(v)=1/，在服务台忙时，单位时间平均服务完的顾客数为。称=/为服务强度。用N(t)表示在时刻t顾客在系统中的数量，则系统N(t);t0组成生灭过程M/M/1/系统由生灭过程求平稳解公式，得由假设=

6、/ 0，则从而平稳分布为pn=(1-)n，n0利用平稳分布可以求统计平衡条件下的平均队长L、平均等待队长Lq、顾客的平均等待时间Wq、平均逗留时间W等续一M/M/1/系统用N表示在统计平衡下系统的顾客数，平均队长L是N的数学期望用Nq表示在统计平衡时，排队等待的顾客数，它的数学期望Lq=E(Nq)就是在等待服务的平均顾客人数续二M/M/1/系统由以上公式，得到这四个指标之间的关系Lq=L-(1-p0)W=L，Wq=Lq第二个公式通常称为Little公式上面两组关系式，可以作这样直观解释：当系统内有顾客时，平均等待队长Lq应该是平均队长L减1，当系统内没有顾客时，平均等待队长Lq与平均队长L相等

7、，所以Lq=L-(1-p0)*1+p0*0=L-(1-p0)单位时间内平均进入系统的顾客为个，每个顾客在系统内平均逗留W单位时间。因此系统内平均有W个顾客。同样理由，系统内平均有Wq个顾客在等待服务续三例一例二M/M/1/k系统用N(t)表示时刻t系统中的顾客数，系统的状态集合为S=0,1,2,，则N(t);t0是个有限生灭过程，有M/M/1/k系统平均队长分两种情况： =1时 1时平均等待队长续一M/M/1/k系统pk是个重要的量，它称为损失概率，单位时间平均损失顾客数为单位时间内平均真正进入系统的顾客数为续二M/M/1/k系统当0时，W=Wq+1/ 续三例一例二M/M/c/系统平均等待队长平均忙的服务台