Ch9排队论.ppt

1、Queuing theory，第9章排队论，运筹学Operations Research，9.1排队论的基本概念9.2排队论系统常用分布9.3单服务台模型M/M/1 9.4多服务台模型M/M/s 9.5其他服务时间分布模型9.6行列系统优化2020年7月21日星期二，9.1.1行列系统的记述，行列系统的例子，9.1行列论的基本概念Basic Concepts of Queuing theory，2020年7月21日星期二，行列的过程， 9.1排队理论的基本概念基本概念查询表，2020年7月21日星期二，根据服务台数量和排队方式，排队系统如下： (1)单服务台单工作团队，(2)多服务台单工作团队

2、， 图9-2单服务台单工作团队系统可以分为、图9-3多服务台单工作团队系统、9.1矩阵论的基本概念Basic Concepts of Queuing theory、2020年7月21日星期二、(3)多服务台马克(4)，多服务台串联服务9.1排队论的基本概念Basic Concepts of Queuing theory，顾客到达，服务台，客户流失， 服务台矩阵系统由输入过程、服务台规则和服务台三部分构成，这是指要求服务台的顾客以什么样的规则到达矩阵系统的过程，有时也称为顾客流。 (1)顾客总数也称为顾客来源、输入来源。 顾客来源可以是有限的也可以是无限的。 (2)顾客到达的形式。 它描述了客户

3、是如何来到系统的，是单独到达的，还是分批到达的。 (3)客户流的概率分布，或者客户相继到达的时间间隔分布。 这是必须首先决定的指标。9.1排队论的基本概念基本概念查询，1 .输入法，2020年7月21日星期二，(1)先来先服务服务(FCFS，First Come First Serve )； (2)从后到前的服务(LCFS，Last Come First Serve) (3)优先级的服务(PR，Priority) (4)随机服务(SIRO，Service in Random Order )， 9.1矩阵论的基本概念basicconceptsofqueuingtheooor (2)损失制是指顾客

4、到达系统时，所有服务台被占用，顾客不等就离开系统。 2020年7月21日星期二，(3)混合系统是一个由待机系统和丢失系统组合而成的服务规则，一般来说是行政许可队列，但是队列不允许无限长。 大致有以下三种：队长有限。 如果等待服务的顾客数超过规定数，之后的顾客就会自动离开，另外要求服务，也就是说系统的等待空间有限。 等待时间有限。 也就是说，顾客在系统上的等待时间不超过某个规定的长度t，当等待时间超过时间t时，顾客自动离去，不出门。 停留时间(等待时间和服务时间之和)有限。 9.1队论的基本概念Basic Concepts of Queuing theory，2020年7月21日星期二，(1)从

5、服务台的数量和构成形式数量来说，服务台分为一台和多台。 从配置形式来看，如图9-2至9-5所示，有单工作团队单服务台、单工作团队多服务台并列式、多工作团队多服务台并列式、单工作团队多服务台串联式等(2)服务台在某个时刻(3)服务时间的分布通常是某个顾客的服务时间是随机变量，与顾客到达的时间间隔分布一样，服务时间的分布有一定长度分布、负指数分布、爱尔兰分布等。、3 .服务台、9.1矩阵论的基本概念基本概念查询表、服务台可以从以下三个方面进行描述： 2020年7月21日星期二、9.1.3矩阵系统的主要数量指标、 符号和符号9.1行列论的基本概念Basic Concepts of Queuing t

6、heory，(1)队长和行列长(行列长)队长是指系统中的顾客数(排队的顾客数和接受服务的顾客数之和)行列长是指系统中排队的顾客数。 队长和队列长度都一般把随机变量(2)的等待时间和逗留时间从顾客到达时刻到他开始接受服务为止的时间称为等待时间。 从顾客到达的时间到他接受完服务所需的时间叫做停留时间。 在这两个时间中，随机变量(3)的繁忙时段和繁忙时段是指从到达空闲服务机构开始到服务再次空闲为止，服务机构连续繁忙的时间。 这是随机变量。 与繁忙时段相反，繁忙时段，即服务机构连续保持空闲的时间。1 .主要数量指标，2020年7月21日星期二，9.1排行论的基本概念Basic Concepts of

7、Queuing theory，2 .符号，时刻t系统的顾客数(也称为系统状态)，即排列在队长时刻t系统的顾客数， 即排长时刻t到达系统的顾客在系统的停留时间t到达系统的顾客的系统的等待时间、l :平均队长，即稳定系统的任意时刻的顾客数的期待值Lq :平均等待队长， 即在稳定系统任意时刻等待服务的顾客数的期待值w :平均停留时间，即在任意时刻进入稳定系统的顾客停留时间的期待值Wq :平均等待时间，即在任意时刻进入稳定系统的顾客等待时间的期待值在稳定的状态下为3360，2020年7月21日星期二， 9.1矩阵论的基本概念Basic Concepts of Queuing theory，客户到达的平

8、均速率，即单位时间内平均到达的客户数1/:平均到达时间间隔平均服务速率，即单位时间内服务完成的客户数1/:平均服务时间s :系统中服务台的数量服务台的数量服务强度，即每个服务台的每单位时间的平均服务时间，有/(s ) n :稳定系统的任意时刻的状态(即系统内的全部顾客数) u :任一顾客在稳定系统中的停留时间q :任一顾客在稳定系统中的等待时间PnPN=n :稳定体系任一时刻的状态为n的概率特别是n=0时，PnP0，即稳定系统的所有服务台全部空闲的概率e :有效平均到达率，不要、2020年7月21日星期二，3 .矩阵系统的象征符、一个矩阵系统的特征可以采用XYZ:ABC或X/Y/Z/A/B/C

9、的形式，x客户到达的概率分布可以采用m、d，等等，优选y服务时间的概率分布可以采用m、d、Ek、g等z服务台数量，取正整数的a排队系统的最大容量。 正整数或b客户源的最大容量优选为正整数或c排队规则或FCFS、LCFS，等等。 例如，M/M/1:/FCFS指示服务系统，其中，顾客到达的时间间隔为负指数分布，服务时间为负指数分布，服务台、排队系统和顾客源的容量为无限，并且执行先来先服务服务。9.1队列的基本概念基本概念查询表，2020年7月21日星期二，下一节：队列系统常用分布，9.1队列的基本概念查询表，9.2 9.2.1负指数分布，随机变量t服从负指数分布， 其分布函数为、密度函数为、t的期

10、望值为、t的色散值为、9.2矩阵系统常用分布，2020年7月21日星期二，负指数分布具有性质另一方面，当随机变量x的概率密度是9.2.2泊松分布时，x顺序变量被称为正泊松分布，并且被标记为XP ()。 其平均和方差分别为，9.2矩阵系统常用分布，2020年7月21日星期二，【定义9.1】对于随机过程，满脚丫子则为1.Poisson流的定义，9.2客户到达和服务的时间分布，(1)独立增量性(无)增量平滑性， 即，在长度t的时间区间内，正好k位顾客到达的概率与区间长度t无关，(3)普遍性，即t为一盏茶小的情况下，称为Poisson过程，N(t )根据泊松分布，在2020年7月21日星期二满足该随机

11、过程顾客的到达数相互独立的(2)在时间区间t，t )内的顾客的到达数仅与区间长度t有关，与区间开始点t无关的(3)对于一盏茶小的t，在时间区间t，t )内2个以上的顾客到达的概率极小，如果可以忽略，则顾客到达系统的过程此外，在【定理9.1】矩阵系统中，如果到达的顾客数遵循以t为残奥仪表的泊松分布，则证明了顾客连续到达的时间间隔遵循以残奥仪表的负指数分布，证明了教材参照，其中，顾客在2020年7月21日星期二、9.2顾客到达服务时的时间分布、 根据定理9.1可知，“到达的顾客数被认为是残奥仪表的泊松流”和“顾客陆续到达的时间间隔服从被认为是残奥仪表的负指数分布”这两个事实等价，在2020年7月2

12、1日星期二，“定理9.2”为X1、X2、Xk，k个x 或者简单地表述，随机变量x的平均和方差分别为、9.2矩阵系统的常用分布，2020年7月21日星期二，是每单位时间的平均到达乘客数，也称为平均到达率。 也有人说顾客到达是服从泊松分布，顾客到达形成泊松流(最简单的流程)。 例1 :一台修正器由1000个组件构成，各组件在一年的工作时间内发生故障的概率为0.001，而且与其他组件的状况无关，在一年内求出2个以上组件发生故障的概率。 解： X=组件故障发生个数，n=1000 P=0.001较小，故视觉感知故障服从泊松分布，其中=nP=1，故9.2客户到达和服务时间分布，2020年7月21日星期二，

13、下一节：单服务台2020年7 9.3单服务台模型，9.3.1基本模型是指每单位时间到达系统的顾客数，每单位时间服务的顾客数。 因为是单服务台，而且顾客源无限，在各种各样的状态下，系统的“生育率”，系统的“死亡率”。 如图9-6所示，在系统稳定态中的状态转移表示，其中从以上状态迁移图获得下一平衡方程、(91 )、1系统状态概率Pn(t )的校正值、2020年7月21日星期二、9.3的平均到达率与平均服务率之比，被称为服务强度，2020年7月21日星期二9.3单服务台模型【例91】高速公路收费站，设置收费路线，汽车到达按泊松分布，平均到达率按150台的时间，收费时间按负指数分布，平均收费时间按15

14、秒台；(1)求收费站空闲的概率；(2)收费站繁忙的概率；(3)系统根据标题，=150台/小时，1/=15秒=1/240 (时间/台)，即240 (台/小时)。 (1)系统空闲的概率是，P0=1=1(5/8)=3/8=0.375 (2)系统忙的概率是，1-P0=5/8=0.625 (3=0. 2340.625=0.146系统中有3辆车2020年7月21日星期二(2)队列中的平均客户数，9.3单服务台型号，(94 )，(95 )，2020年7月21日星期二，9.3单服务台型号，(3)系统中的客户平均停留时间w， (97) 9.3单服务台模型，【例92】轻轨入口的售票处有售票处，乘客的到达按照泊松分布，平均到达率为200人/小时，售票处时间按照负指数分布，平均售票处时间为15秒/人。 求出l、Lq、w、Wq。 根据标题，=200人/小时，=240人/小时，=5/6。 2020年7月21日星期二，9.