排队论

排队理论06031101班交通工程专业肖晋昆刘祥磊李其红谢伟恒目录五、具有不耐烦顾客的M/M/C/N排队模型二、预备知识三、M/M/C/N排队模型简介四、简单的M/M/C/N排队模型一、M/M/C/N排队模型发展简介六、输入率可变M/M/C/N的模型M/M/C/N排队模型发展简介2003年•白志惠在中对M/M/n/n型排队系统的优化设计及应用进行了研究,并且当m无限大时,即构成可多服务窗混合制2006年•作者田乃硕,于艳辉针对带有不耐烦顾客及三中阀值策略的M/M/c/K排队进行了研究。2008年•作者赵晓华、樊剑武研究了带有止步和中途拖出的M/M/1/N同步多重工作休假排队系统；作者邱德全，孙妍平研究了具有止步和中途退出的M/M/C/N部分服务员同步多重休假排队系统的等待时间2009年•作者许厅厅,邱德全对有负顾客到达的M/M/C/N可修排队模型进行了研究;作者荣艳蕊讨论了混合制排队模型下中式快餐店排队的优化;2010年•作者陈实于中对多服务台混合制排队模型行了仿真研究作者2011年•李佩佩,邱德全研究了带有止步和中途退出的M/M/R/N同步多重工作休假排队模型；作者陈金阳，汪鸿波在排队论的运用上做文章,研究了基于混合制排队论的高校食堂优化管理模型预备知识马尔可夫链泊松过程生灭过程利特尔公式马尔可夫链马尔可夫链是一种非常重要的随机过程，它的状态空间可以是可数无限的，其特点是：系统从某一个状态出发，通过一段时间之后转变到另一状态，这个过程与以前的历史无关，只与当前出发的状态有关。定义2.1.1设{X(t),t0}是连续型时间参数的随机过程，其状态空间E={0，1，2}若对于任意的非负整数n,及任意及有则称{X(t),t=0}为连续时间参数的马尔可夫链。马尔可夫链是满足下面两个假设的一种随机过程：1、t+l时刻系统状态的概率分布只与t时刻的状态有关，与t时刻以前的状态无关；2、从t时刻到t+l时刻的状态转移与t的值无关。泊松过程（流）定义2.2.1记X（t）为(0,t]时间段内到达系统的顾客数（这里讨论的是顾客单个进入系统的情况）则{X(t),t0}是连续时间参数的随机过程。如果它还满足：生灭过程利特尔（Little）公式设顾客按泊松流到达系统，平均强度为λ；而服务窗的服务时间为负指数分布,平均服务率为μ；Ls为系统内顾客的平均队长；Lq为系统内顾客的平均等待队长,Wq为平均等待时间，Ws表示顾客在系统内平均的逗留时间。则Little公式为M/M/C/N排队模型简介假设系统有C个服务窗口，规定各个窗口工作是相互独立的。规定：顾客之间到达的时间间隔服从参数为λ的负指数分布，且各窗口提供的服务时间服从参数为μ的负指数分布，假设系统容量为N，即系统中最多可以同时容纳N个顾客（NC1），若系统中的顾客数小于N时，顾客进入系统接受服务或等待接受服务。反之，若系统中已有N个顾客，那么新来的顾客就会马上离开另寻服务。显然系统内只有N-C个可供排队等待的位置，我们则称这样的系统为多服务窗混合制排队模型M/M/C/N，用图1.2.1表示：对于该系统，设X(t)表示在时刻t时M/M/C/N系统中的顾客数，则{X(t),t=0}是以状态空间I={0,1,2,..}的生灭过程。其中k表示系统中的顾客数。当0kC时，系统的总服务率为kμ，当C=kN时，系统的总服务率为Cμ，其状态流程图如图2.5.2所示：则有其中，可以得到以下主要指标：（1）系统损失的概率（2）系统的相对通过能力（3）单位时间内平均损失的顾客数和平均进入系统的顾客数分别为（4）平均忙着的服务窗个数(5）平均排队等待队长（或顾客数）为当1时当1时（6）系统平均队长为或比较上面两式可得(7）由Little公式，平均等待时间Wq,平均逗留时间Ws分别为系统的容量有限制的情况（M/M/1/N/∞）如果系统的最大容量为N，对于单服务台的情形，排队等待的顾客最多为N-1，在某时刻一顾客到达时，如系统中已有N个顾客，那么这个顾客就被拒绝进入系统(见图12-8)。图12-8当N=1时为即时制的情形；当N→∞，为容量无限制的情形。若只考虑稳态的情形，可作各状态间概率强度的转换关系见图图12-9。图12-9根据图12-9，列出状态概率的稳态方程：在对容量没有限制的情形，我们曾设ρ1，这不仅是实际问题的需要，也是无穷级数收敛所必需的。在容量为有限数N的情形下，这个条件就没有必要了。(为什么?)不过当ρ1时，表示损失率的PN(或表示被拒绝排队的顾客平均数λPN)将是很大的。根据(12-24)式我们可以导出系统的各种指标(计算过程略)：(1)队长(期望值)1101)1(1NNNnnsNnPL1（2）队列长(期望值))1()1(01PLPnLsNnnq当研究顾客在系统平均逗留时间Ws和在队列中平均等待时间Wq时，虽然(12-22)式仍可利用，但要注意平均到达率λ是在系统中有空时的平均到达率，当系统已满(n=N)时，则到达率为0，因此需要求出有效到达率λe=λ(1-)。可以验证：NPeP01(3)顾客逗留时间(期望值)(4)顾客等待时间(期望值)Wq=Ws-1/μ1)1()1(0NpssPLPLW现在把M/M/1/N/∞型的指标归纳如下(当ρ≠1时)：例4单人理发馆有6个椅子接待人们排队等待理发。当6个椅子都坐满时，后来到的顾客不进店就离开。顾客平均到达率为3人/小时，理发需时平均15分钟。则N=7为系统中最大的顾客数，λ=3人/小时，μ=4人/小时。(1)求某顾客一到达就能理发的概率这种情形相当于理发馆内没有顾客，所求概率2778.0)43(143180P(2)求需要等待的顾客数的期望值39.1)2778.01(11.2)1(11.2)43(1)43(843143088PLLLsqs(3)求有效到达率)/(89.2)2778.01(4)1(0小时人Pe(4)求一顾客在理发馆内逗留的期望时间(5)在可能到来的顾客中不等待就离开的概率(Pn≥7)这就是求系统中有7个顾客的概率：（分钟）小时8.43)(37.089.2/11.2/essLW00878777.3)43(143143)/(1/1P这也是理发馆的损失率。现以本例比较队长为有限和无限，两种结果如下：有限对长N=72.111.390.730.480.2783.7无限队长32.251.00.750.250小时人小时人/4/3sLqLsWqW0P7P系统的容量有限制的情形(M/M/c/c/∞)特别当N=c(即时制)的情形，这时P0=Pn=，0≤n≤c(12-33)其中，当n=c即关于Pc的公式，被称为爱尔朗呼唤损失公式，是A.K.Erlang早在1917年发现的，并广泛应用于电话系统的设计中。这时的运行指标如下：Lq=0，Wq=0，Ws=Ls===cρ(1-Pc)(12-34)它又是使用的服务台数（期望值）例7在某风景区准备建造旅馆，顾客到达为泊松流，每天平均到(λ)6人，顾客平均逗留时间(1/μ)为2天，试就该旅馆在具有(c)1，2，3，⋯，8个房间的条件下，分别计算每天客房平均占用数Ls及满员概率Pc。这是即时式，因为在客房满员条件下，旅客显然不能排队等待。计算过程通过表12-12进行(λ=6，1/μ=2，cρ=λ/μ=12)。第(4)栏：(2)/(3)第(5)栏：第(4)栏各数累加第(6)栏：(4)/(5)得满足概率Pc，注意第(5)(6)两栏的c就是同行的n，Pc的具体意义是：当c=1旅馆只有一个房间，满员(旅客被拒绝)概率0.92当c=5旅馆备有5个房间，满员(旅客被拒绝)概率0.63当c=8旅馆备有8个房间，满员(旅客被拒绝)概率0.42第(7)栏：为求Ls作准备，用第(5)栏同行去除上一行结果。第(8)栏：(7)×12得Ls，为每天客房平均占用数，它的具体意义是：当n=1旅馆只有一个房间，每天客房平均占用数Ls=0.93(间)n=5旅馆备有五个房间，Ls=4.48(间)n=8旅馆备有八个房间，Ls=6.92(间)就是说每天平均都有一间以上的房间是空闲的。输入率可变的M/M/C/N排队模型在现实生活中，我们经常看到顾客因需要排队等待而发生犹豫的情况，究竟是否加入队伍等待服务是有多种因素决定的，除了当时顾客的需要（急与不急）之外，还需考虑到等待队伍的长短，如果等待队长越短，顾客选择等待的概率会越大，反之则越小。令αk表示当队长为k时，新到达顾客加入队伍的概率，此时αk需满足0αk1,k趋近于0时，limαk=0这两个条件。模型假设为了方便对多服务窗混合制M/M/C/N模型的研究，我们做了以下的假设：（1）系统中有C个服务窗，且容量为N（NC）。（2）各个服务台间相互独立，且各服务台的服务时间服从参数为μ的指数分布。（3）记αk表示新来顾客到达系统后选择加入的概率，k表示的是队长，这里我们假定顾客到达系统后选择加入队伍的概率为（4）顾客到达的时间间隔服从参数为λ的指数分布。（5）各服务台的服务时间与顾客的到达时间相互独立,且顾客排队为单列排队。数学模型根据3.1中的模型假设，有如下结论：具有不耐烦顾客的M/M/C/N排队模型在现实生活中我们经常可以看到，有人在排队等待一段时间之后选择离开，排队等待的人可能因为自己有急事需马上处理或者服务台服务效率低下等原因导致顾客迟迟不能接受服务而选择离开，但是在我们现在的生活中，各项硬件设施较为完善的情况下，这种不耐烦顾客是比较少的，由于对数函数的增加速度较为缓慢，所以在离开率中考虑对数函数是较为合理的，比较贴近时间生活，且具有一定的实际意义。bk为等待队长为k时具有不耐烦顾客的中途离开率。模型假设为了方便对多服务窗混合制M/M/C/N模型的研究，我们做了以下的假设：(1)系统中有C个服务窗，且容量为N（NC）；(2)各个服务台间相互独立，且各服务台的服务时间服从参数为的指数分布；(3)记bk为具有不耐烦顾客离开的概率，k表示的是等待队长，这里我们假定具有不耐烦顾客离开的概率为bk=ln(k+1),δ=0(4)顾客到达的时间间隔服从参数为λ的指数分布；(5)各服务台的服务时间与顾客的到达时间相互独立,且排队为单列排队。数学模型根据4.1中的模型假设，有如下结论：Thanks