第10章 排队论讲解.ppt

第10章　排队论 §10.1 排队论概述 §10.2 Ｍ／Ｍ／1模型 §10.3 Ｍ／Ｍ／Ｓ模型 §10.1 排队论概述 §10.1 排队论概述 10.1.1 排队论及排队系统 二、 排队系统的一般特征 　　随机服务（ＲＳ），如电话交换系统中的服务。 三、表示排队系统的通用符号　　排队系统的表示一般采用“肯得尔记号”（由美国的一位学者D.G.Kendall于1953年提出），其一般形式为：　　　　　　　　　　Ａ／Ｂ／ｍ／ｎ 10.1.2 排队系统中随机变量的有关分布 　　处理排队问题，首先需要根据原始资料做出顾客到达间隔和服务时间的经验分布，然后才能确定其理论分布。 　　一、经验分布 　　通常记录某一随机服务系统中顾客到达的时间间隔和每一位顾客接受服务的时间所形成的分布，就是经验分布。 　　一般以τi表示第 i 号顾客到达的时刻，以ｓi表示他接受服务的时间，于是顾客相继到达的时间间隔ｔi和排队等待时间ｗi可表示为： ｔi+1＝ τi＋１－ τi 表10.1　例10.1的原始记录 表10.2 到达间隔分布　 表10.3 服务时间分布 二、泊松分布（Poisson）　　设Ｎ(t)表示在时间区间（0，ｔ）内到达的顾客数，Pn(t)表示在时间区间（0，ｔ） 内有ｎ个顾客到达的概率，当Pn(t) 符合下列三个条件时，通常就说顾客到达数服从泊松分布： 根据有关数据，不难算出如下的指标值： 平均到达率（λ）＝42／145＝0.29（人／分钟） 平均到达时间（１／λ）＝145／41＝3.46（分钟／人） 平均服务率（μ）＝42／130＝0.323（人／分钟） 平均服务时间（１／μ）＝130／42＝3.1（分钟／人） 这些指标都是排队系统分析中非常重要的数量指标。 二项分布的密度函数是： 　　　表10.4　二项分布与泊松分布的比较 　　泊松分布描述的对象一般属于小概率事件，如给定时段内的事故数、棉纱上的杂质、布匹上的疵点等均遵从泊松分布。在泊松分布中有：　　　　Ｅ［Ｎ（ｔ）］＝Ｄ2［Ｎ（ｔ）］＝λｔ　　即数学期望等于方差等于λｔ，其中λ为平均到达率。 三、负指数分布　　当顾客到达数即输入过程服从泊松分布时，两顾客相继到达的间隔Ｔ就服从负指数分布，其密度函数为： 变量Ｔ的数学期望和方差是：　　　　Ｅ(Ｔ)＝１／λ　　　Ｄ2(Ｔ)＝１／λ2　　 图10.3 负指数分布 四、爱尔朗分布　　如果一个服务系统由ｋ个服务台串联构成，每个服务台的服务时间相互独立，且服从相同的负指数分布（参数为kμ），则一顾客走完这ｋ个服务台所需全部时间T就服从下列的ｋ阶爱尔朗（Erlang）分布： 10.1.3 生灭过程与平稳状态分布　　在排队论的研究中，一类非常重要且广泛存在的排队系统是生灭过程排队系统。生灭过程是一类非常特殊的随机过程，在生物、物理领域有着广泛的应用。在排队论中，生表示顾客到达，灭表示顾客离去，这样ｔ时刻的系统状态Ｎ(ｔ)就构成了一个生灭过程。生灭过程服务系统一般具有以下三个方面的性质： 　　(1)根据泊松过程的普通性假定，对于充分小的Δ t ，在时间区间（t，t＋Δt）内有多于1个顾客到达和离去的概率极小，可忽略不计；　　(2)根据平稳性假定，在区间（t，t＋Δt）内有1个顾客到达的概率与Δt称正比即为λΔt(这实际上是频数，因为只有两种情况即有1个顾客到达和没有顾客到达，且频数和为1，所以λΔt事实上亦即概率)，故没有顾客到达的概率就是：1－ λΔt； 情形Ａ：Ｐn(t)(1－ λΔt)(１－ μΔt)情形Ｂ：Ｐn+1(t)(1－ λΔt)μΔt 情形Ｃ：Ｐn-1(t)λΔt(１－ μΔt) 情形Ｄ：Ｐn(t)λΔtμΔt 　　因此，类似地可得到： 　　 10.2 Ｍ／Ｍ／1 模型 10.2 Ｍ／Ｍ／1 模型 亦即：　　　　　　　　 显见，ρ越接近于1，或者μ－λ越　　　　　　　　　　　　　　　接近于零，Ｌ值就越大，系统中滞留的顾　　　　　　　　　　　　　　　客就越多。 （三）忙期平均长度ｗb　　忙期即服务台连续工作的时间长度。系统处于闲期的概率即Ｐ0 ＝1－ρ，而处于忙期的概率就是Ｐn0＝1－Ｐ0＝ρ。因此忙闲期的预期比值应为：ρ／（1－ρ）；而平均的闲期长度，在顾客到达的时间间隔服从负指数分布的条件下，也就是1／λ即平均到达间隔时间。于是，忙期的平均长度即： 　　（４）等待修理的平均车辆数 10.2.2 容量有限的Ｍ／Ｍ／1模型 ( M / M / 1 / k )　　如果设系统的最大容量为ｋ，对于单服务台排队等待的最多顾客应为ｋ－1个。如果系统饱和，到达的顾客就会被拒绝进入系统。这时对ρ＝λ／μ做