运筹学-排队论讲解

《运筹学-排队论讲解》由会员分享，可在线阅读，更多相关《运筹学-排队论讲解（90页珍藏版）》请在金锄头文库上搜索。

1、第十二章 排队论(Queuing Theory),排队论的基本概念 到达间隔的分布和服务时间的分布 排队系统的分析,排队论(Queuing Theory)，又称随机服务系统理论(Random Service System Theory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。 排队论是1909年由丹麦工程师爱尔朗(A.KErlang)在研究电话系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。,第一

2、节 基本概念,一、排队系统的一般表示,例1、各个顾客由顾客源出发，到达服务机构前排队等候 服务，服务完了后就离开。,排队结构指队列的数目和排列方式,排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。,排队规则,排队系统,排队是我们在日常生活和生产中经常遇到的现象: 上、下班搭乘公共汽车； 顾客到商店购买物品； 病员到医院看病； 旅客到售票处购买车票； 学生去食堂就餐等就常常出现排队和等待现象。 排队的不一定是人，也可以是物： 通讯卫星与地面若干待传递的信息； 生产线上的原料、半成品等待加工； 因故障停止运转的机器等待工人修理； 码头的船只等待装卸货物； 要降落的飞机因跑道不

3、空而在空中盘旋等等。,一般排队的过程,二、排队系统的组成和特征,输入即指顾客到达排队系统，可能有以下不同情况。,1、输入过程,（1）顾客源的组成,有限的,无限的,（2）顾客到来的方式,一个一个的,成批的,（3）顾客相继到达的间隔时间,确定型的,随机型的,（4）顾客的到来,相互独立的,关联的,（5）输入过程,平稳的，或称对时间是齐次的,非平稳的,2、排队规则,顾客在排队系统中按怎样的规则、次序接受服务的。,（1）顾客到达时，所有服务台被占用,随即离去的 称为即时制（损失制）,排队等候称为等待制,先到先服务,后到先服务,随机服务,有优先权,（2）从队列占用空间,有限的,无限的,（3）从队列的数量,

4、单列,多列,3、服务机构,（1）服务员数量,没有,一个或多个,（2）多服务台时,单队单服务台,单队多服务台（并列）,多队多服务台（并列）,多服务台（串列）,（3）服务方式,对单个顾客进行,对成批顾客进行,（4）服务时间,确定型,随机型,（5）服务时间的分布我们总假定是平稳的，即 分布的期望值、方差等参数都不受时间的影响,多服务台混合,一个排队系统的特征可以用六个参数表示，形式为： X/Y/Z /A/B/C 其中 X 顾客到达的概率分布，可取M、D、Ek等； Y 服务时间的概率分布，可取M、D、Ek等； Z 服务台个数，取正整数； A 排队系统的最大容量，可取正整数或； B 顾客源的最大容量，可

5、取正整数或； C 排队规则，可取FCFS、LCFS等。,三、排队模型的分类(条件参数),表示相继到达间隔时间和服务时间的各种分布的符号:,M负指数分布,D 确定型,Ekk阶爱尔朗分布,GI 一般相互独立的时间间隔的分布,G 一般服务时间的分布,例如：某排队问题为 M / M / s / / /FCFS 则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。 可简记为： M / M / s,四、排队系统的参数(分析结果),1、队长（Ls） 指在系统中的顾客数,期望值,2、排队长（Lq） 指系统中排

6、队等候服务的顾客数,3、逗留时间（Ws） 指一个顾客在系统中的停留时间,4、等待时间（Wq） 指一个顾客在系统中排队等待的时间,Ls=Lq+正被服务的顾客数,Ws=Wq+服务时间,这四项主要性能指标(又称主要工作指标)的值越小，说明系统排队越少，等待时间越少，因而系统性能越好。显然，它们是顾客与服务系统的管理者都很关注的。,5、忙期 指从顾客到达空闲服务机构起到服务机构再次空闲止 这段时间长度，即服务机构连续繁忙的时间长度。,6、系统的状态n：指系统中的顾客数。,8、稳定状态：t时，t=0时的系统不稳定状态将消失，系统的状态概率分布不再随时间变化，即 limPn(t)Pn。,7、系统状态的概率

7、Pn(t)：指时刻t、系统状态为n的概率。一般为关于t的微分方程、关于n的差分方程。,9、其他常用数量指标 s 系统中并联服务台的数目； 平均到达率； 1/ 平均到达间隔。 平均服务率； 1/ 平均服务时间。 服务强度， 每个服务台单位时间内的平均服务时间； 一般有 s ；当s=1时： ,对于损失制和混合制的排队系统，顾客在到达服务系统时，若系统容量已满，则自行消失。这就是说，到达的顾客不一定全部进入系统，为此引入： e 有效平均到达率, 即每单位时间实际进入系统的平均顾客数（期望值），不同于. 对于等待制的排队系统， e ,一、经验分布,例2 某服务机构单服务台，先到先服务，对41顾客记录到

8、达时刻和服务时间s（单位：分钟）如下表，表中第1号顾客到达时刻为0。全部服务时间为127（分钟）。,第二节 到达间隔的分布和服务时间的分布,各栏意义： （1）i，顾客编号；（2）i：顾客i到达的时刻；（3）si：服务时间；以上三栏是原始数据；（4） ti ：到达间隔；（5）wi：排队等待时间；这俩栏是可以通过计算得到的,到达间隔分布表,服务时间分布表,平均间隔时间=142/40=3.55(分钟/人),平均到达率=41/142=0.28(人/分钟),平均服务率=41/127=0.32(人/分钟),平均服务时间=127/41=3.12(分钟/人),输入过程是描述各种类型的顾客以怎样的规律到达系统，

9、一般用相继两顾客到达时间间隔来描述系统输入特征。主要输入过程有：定长输入，泊松输入 1定长输入 是指顾客有规则地等距到达，每隔时间到达一个顾客。这时相继顾客到达间隔的分布函数F(t)为,定长输入,例如，生产自动线上产品从传送带上进入包装箱就是这种情况,二、泊松(Poisson)输入,泊松(Poisson)输入，即泊松流，又称最简单流。 设随机变量X服从Poisson分布，则概率密度,如果一个随机变量，概率分布与时间t有关，则称这个随机变量为一随机过程，排队系统中顾客到达的个数就是一个随机过程。 (1) Poisson流的定义 满足以下四个条件的输入流称为Poisson流(Poisson过程),

10、平稳性：增量与时间起点无关 在时间区间t, t+t)内到达k个顾客的概率与t无关，只与t有关。记为pk(t）。 无后效性 不相交的时间区间内到达的顾客数互相独立。 稀有性：瞬时内只可能有1个顾客到达 设在t, t+t）内到达多于一个顾客的概率为q(t），则 q(t)=o(t). 即 有限性 任意有限个区间内到达有限个顾客的概率等于1。即,简记 Pn(0,t)= Pn(t)。表示0,t)时间内到达n个顾客的概率，即输入。 对于区间0,t+ t)，可分成两个互不重叠的区间0,t)和t,t+ t)。设在区间0,t+ t)上，到达总数为n，会出现A,B,C三种情况：,区间0,t+ t)内到达n个顾客应

11、是表中三种互不相容的情况之一，所以概率Pn(t+ t)应是三个概率之和 ，即：,Pn（t+t）= Pn（t）（1- t ）+Pn-1（t） t+ o（t）,Pn（t+t）- Pn（t）/ t = Pn（t）+ Pn-1（t）+ o（t）/ t,令t0,求出,整理后得：,由此可见，泊松输入，即在 t 时段内到达n个顾客的概率服从参数为的泊松分布。,注意：我们要把泊松输入同前面提到的系统状态Pn区分开,参数的实际意义 设N(t)表示在0，t）内到达的顾客数的期望值 由此得到 即的实际意义为单位时间内到达的顾客数的期望值，或称平均到达速率。,泊松分布,由概率论可知，如果随机变量X服从参数为泊松分布，

12、则其分布函数为（注：不是很重要） 密度函数为 X的期望值为 X的方差为,由概率论可知，如果随机变量T服从负指数分布，则其分布函数为 密度函数为 T的期望值为 T的方差为,三、负指数分布（指数分布）,Poisson流与负指数分布之间的关系 定理 在排队系统中，如果到达的顾客数服从以为参数的Poisson分布，则顾客相继到达的时间间隔服从以为参数的负指数分布。 证明：设Poisson流中顾客相继到达的时间间隔为随机变量T，并且在时刻0有一个顾客到达，则下一个顾客将在时刻T到达。T的分布函数为 其中pTt表示在0，t）内没有顾客到达的概率，因此 所以，T的分布函数为,T的密度函数为 因此，顾客相继到

13、达的时间间隔服从以为参数的负指数分布。 可以看出，“到达的顾客数是一个以为参数的Poisson流”与“顾客相继到达的时间间隔服从以为参数的负指数分布”两个事实是等价的。,顾客相继到达的时间间隔服从以为参数的负指数分布,服务时间 服从负指数分布，概率密度为,参数同样具有两层含义：单位时间内服务的顾客人数的期望值，或称平均服务率。,由于的均值为1/ ，即平均对每位顾客的服务时间 为1/ .,服务时间服从以为参数的负指数分布,负指数分布具有无记忆性 定理 设对顾客的服务时间X服从参数为的负指数分布。在对某一个顾客的服务已经进行了一定时间的条件下，这个顾客的剩余的服务时间仍服从以为参数的负指数分布。

14、证明：设服务已经进行的时间为，则剩余时间不少于t的条件概率为 由此看出，服务剩余时间的分布独立与已经服务过的时间，并且与原来的服务时间的分布相同。,设v1，v2，vk是k个互相独立的，具有相同参数的负指数分布随机变量，则随机变量 服从k阶Erlang分布，S的密度函数为,四、k阶爱尔朗(Erlang)分布,期望值为 方差为,注意：当k=1时，爱尔朗分布就是负指数分布，是完全随机的；当k=30时，近似于正态分布；一般k阶爱尔朗分布可看成是完全随机与完全确定的中间型，有更广泛的适应性。,一、M/M/1模型,1、假设,第三节 单服务台负指数分布排队系统的分析,求： （1）系统状态概率Pn； （2）系

15、统运行指标Ls，Lq，Ws，Wq。,2、Pn的计算,注：表示发生（1个）， 表示没有发生。,整理后得：,将Pn(t)移到左边，两边同除以t，得到,令t0时，得到关于Pn(t)的微分方程：,当n=0，则只有表中A，B两种情况，即,同理，求得：,Pn(t)的稳态解Pn 如果能够求解由无限个方程组成的差分微分方程组，就可以得到Pn(t)的瞬态解，即系统中有n个顾客的概率随时间变化的解析表达式，但这是十分困难的。 如果假定当时间足够长，系统有n个顾客的概率Pn(t)会趋于某个稳定值，即当t时系统趋于概率稳态，这个稳态解是可以求出来的。 设当t时，Pn(t)趋于一个常数，这时Pn(t)与t无关，可记为Pn，则Pn关于t的导数为0。,这时(1)式和(2)式可得,状态转移图 以系统中的顾客数0，1，2，n-1，n，n+1，作为系统的状态， (3)和(4)表示系统位于某一状态的概率仅与其相邻状态的概率以及从相邻状态转移到该状态的概率有关。 系统状态（n）随时间变化的过程是生灭过程的一个特殊情况， (3)和(4)关于Pn的差分方程，可以用状态转移图来表示各状态间的转移关系，并能求解。,由(3)和(4)可以递推求解P1，P2，Pn，。 由(3)得到 (5) 由(4)得到 (6) 将(5)代入(6) 用递推方法可以得到 (7),由 得到 令