运筹学 第十三章排队系统分析课件.ppt

《运筹学 第十三章排队系统分析课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十三章排队系统分析（QueueingSystemsAnalysis）第一节排队的基本概念第二节到达与服务的规律第三节M/M/1排队模型第四节M/M/C排队模型第五节排队系统优化第一节排队的基本概念一.排队系统的组成队列服务机构顾客源到达离去现实世界中形形色色的排队系统到达的顾客要求服务的内容服务机构不能运转的机器修理修理技工修理技工领取修配零件发放零件的管理员电话呼唤通话交换台1.输入过程（1）顾客源：分为•无限(如电话呼唤)•有限m（如车间里待修理的机器）（2）到达规律：指到达间隔时间T的分布分为•定长D•负指数M•k阶爱尔朗Ek2.排队规则（1）损失制指顾客到达时若所有服务实施均被

2、占用，则顾客自动离去。（2）等待制指顾客到达时若所有服务实施均被占用，则留下来等待，直至被服务完离去。等待的服务规则又可分为•先到先服务（FCFS）•后到先服务（LCFS）（3）混合制分为•系统容量有限制•等待时间有限制3.服务机构（2）服务规律：指服务时间v的分布分为•定长D•负指数M•k阶爱尔朗Ek•一般分布G（1）服务台个数C(并列多台)二.排队模型的表示用记号（X/Y/Z/A/B/C）表示，其中X：顾客到达时间间隔的分布Y：服务时间的分布Z：服务台个数A：系统容量B：顾客源数量C：服务规则例1（M/M/1/FCFS）表示：到达间隔为负指数分布，服务时间也为负指数分布，1个服务台，

3、顾客源无限，系统容量也无限，先到先服务。若只讨论先到先服务的情况，可略去第6项。三.排队问题的求解主要是计算描述系统运行状态的指标：1.队长和排队长队长：系统中的顾客数；其概率分布称状态概率，记为Pn，表示系统中有n个顾客的概率；队长的平均值记为Ls。排队长：系统中正在排队等待的顾客数，记其均值为Lq。2.逗留时间和等待时间逗留时间：一个顾客在系统中的停留时间，记为W，其均值记为Ws。等待时间：一个顾客在系统中排队等待的时间，记其均值为Wq。第二节到达与服务的规律一.到达的规律描述顾客到达规律可从两方面现实中有许多服务系统，其顾客的到达具有下述特征：（1）无后效性：任一时段的到达数不受前

4、一时段的影响；（2）平稳性：顾客到达是均匀的；（3）稀有性：瞬时内只可能有1个顾客到达。称具有上述特征的输入为泊松流，其在t时段内到达n个顾客的概率为即参数为的泊松分布。由概率论知识可知，泊松分布的参数即其均值。因此，的含义是单位时间到达系统的平均顾客数，即到达率。下面考察，当顾客按泊松流到达时，其到达的间隔时间T是服从什么分布呢？因为到达为泊松流，所以，t时段内没有来顾客的概率为所以，t时段内有顾客到来（即间隔Tt）的概率为而这正是负指数分布的分布函数，说明T服从负指数分布，且参数同为。可证反之也成立。于是得到关于到达规律的重要性质：到达数为泊松流到达间隔服从负指数分布（同参数）。由概

5、率论知识可知，负指数分布的表达式（密度函数）为参数即其均值的倒数。因此，的含义是平均间隔时间，这与为单位时间到达系统的平均顾客数的含义一致。负指数分布有一个有趣的性质：无记忆性，即事实上，直观上看，在已知T>t0的条件下估计T>t的概率，与无条件时估计T>t的概率相同，把以前的t0时间给忘了。假若T表示某种电子元件的寿命，则当元件已使用了t0时间后估计它还能再使用t时间的概率，与刚开始用时的概率一样。说明这种元件是高度耐磨损的。二.服务的规律主要讨论服务时间v服从负指数分布的情形，参数为，即参数的含义：服务率，即单位时间平均服务完人。由于v的均值为，即平均对每位顾客的服务时间为，可得第三

6、节M/M/1排队模型一.标准的M/M/1模型（M/M/1/）1.问题的一般提法设：泊松输入/负指服务/单服务台/系统无限制/顾客源无限制求：（1）系统状态概率Pn；（2）系统运行指标Ls，Lq，Ws，Wq。2.系统状态概率（1）利用状态转移图列出平衡方程状态转移图是处理稳态M/M/C系统的一种工具，设到达与服务率分别为，则由此列出平衡方程：......n-1nn+1021由平衡方程可解得状态概率：记，称为服务强度，规定（为什么？），则（2）由平衡方程解得状态概率3.系统运行指标（1）Ls与Lq（2）Ws与Wq（3）上述4个指标之间的关系——里特公式例2某修理店只有一个修理工人，来修理的顾

7、客到达数服从泊松分布，平均每小时4人；修理时间服从负指数分布，平均需6分钟。求：（1）修理店空闲的概率；（2）店内有3个顾客的概率；（3）店内至少有1个顾客的概率；（4）店内顾客的平均数；（5）顾客在店内的平均逗留时间；（6）等待服务的顾客平均数；（7）平均等待修理时间；（8）必须在店内消耗15分钟以上的概率。二.系统容量有限的M/M/1模型（M/M/1/）1.与（M/M/1/）的区别2.状态概率由此列出平衡方程：nn-1.....