第10章-排队论-《运筹学》课件全

第十章排队论OperationalResearch(OR)排队系统特征及排队论队列服务机构顾客源到达离去排队系统的特征及排队论现实世界中形形色色的排队系统到达的顾客要求的服务服务机构1.不能运转的机器修理修理工人2.修理工人领取修配零件管理员3.病人就诊医生4.打电话通话交换台5.文稿打字打字员排队系统的特征及排队论排队系统的具体形式：图1单服务排队系统顾客到达服务完成后离去服务台…队列正在接受服务的顾客顾客到达服务完成后离去服务台2…队列服务台s服务台1...图2s个服务台，一个队列的排队系统排队系统的特征及排队论…队列2顾客到达服务完成后离去服务台2…队列1服务台s服务台1...…队列s服务完成后离去服务完成后离去图3s个服务台，s个队列的排队系统顾客到达…………服务台1…………服务台2服务完成离去队列队列图4多个服务台的串联排队系统排队系统的特征及排队论上述形式都可概括为：服务机构聚散（输入）（输出）图5随机服务系统排队系统的描述1.输入过程（1）顾客总体（顾客源）数：•无限(如来商店购物的顾客数量)•有限

m

（如车间里待修理的机器）（2）到达方式：单个到达还是成批到达。（3）顾客(单个或成批)相继到达时间间隔的分布：①定长分布（D）②最简流（或称Poisson流）（M）排队系统的描述2.排队及排队规则(1)排队，排队分为有限排队和无限排队两类，对有限排队系统，可进一步分为两种：①损失制排队系统②混合制排队系统，具体说来，又分为以下三种：

(i)队长有限

(ii)等待时间有限

(iii)逗留时间(等待时间与服务时间之和)有限排队系统的描述(2)排队规则，当顾客到达时，若所有服务台都被占用且又允许排队，则该顾客将进入队列等待。服务台对顾客进行服务所遵循的规则通常有：①先来先服务(FCFS)②后来先服务(LCFS)③具有优先权的服务(PS)排队系统的描述3.服务机制

排队系统的服务机制主要包括：服务员的数量及其连接形式(串联或并联)；顾客是单个还是成批接受服务；服务时间的分布。记某服务台的服务时间为V，其分布函数为B(t)，密度函数为b(t)，则常见的分布有：(1)定长分布(D)(2)负指数分布(M)(3)k阶爱尔朗分布(Ek)：排队系统的符号表示排队系统的符号表示“Kendall记号”，其一般形式为：X/Y/Z/A/B/C，其中

XX：顾客到达时间间隔的分布

YY：服务时间的分布

ZZ：服务台个数A：系统容量BB：顾客源数量

CC：服务规则例（M/M/1/FCFS）表示：到达间隔为负指数分布，服务时间也为负指数分布，1个服务台，顾客源无限，系统容量也无限，先到先服务。若只讨论先到先服务的情况，可略去第6项。排队系统的主要数量指标和记号描述一个排队系统运行状况的主要数量指标有：1.队长和排队长2.等待时间和逗留时间3.忙期和闲期上述一些主要数量指标的常用记号：N(t)：时刻t系统中的顾客数(又称为系统的状态)，即队长；Nq(t)：时刻t系统中排队的顾客数，即排队长；T(t)：时刻t到达系统的顾客在系统中的逗留时间；Tq(t)：时刻t到达系统的顾客在系统中的等待时间。排队系统的主要数量指标和记号记pn(t)为时刻t时系统处于状态n的概率，即系统的瞬时分布。我们将主要分析系统的平稳分布，即当系统达到统计平衡时处于状态n的概率，记为pn。又记N：系统处于平稳状态时的队长，其均值为L，称为平均队长；Nq：系统处于平稳状态时的排队长，其均值为Lq，称为平均排队长；T：系统处于平稳状态时顾客的逗留时间，其均值记为W，称为平均逗留时间；Tq：系统处于平稳状态时顾客的等待时间，其均值记为Wq，称为平均等待时间；排队系统的主要数量指标和记号λn：当系统处于状态n时，新来顾客的平均到达率(单位时间内来到系统的平均顾客数)；μn：当系统处于状态n时，整个系统的平均服务率(单位时间内可以服务完的顾客数)；当λn为常数时，记为λ；当每个服务台的平均服务率为常数时，记每个服务台的服务率为μ，则当n≥s时，有μn=sμ。因此，顾客相继到达的平均时间间隔为1/λ，平均服务时间为1/μ。令ρ=λ/sμ，称ρ为系统的服务强度。另外，记忙期为B，闲期为I，平均忙期和平均闲期分别记为和，记s为系统中并行的服务台数。排队论研究的基本问题排队论研究的基本问题：(1)通过研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统运行的基本特征。(2)统计推断问题，建立适当的排队模型是排队论研究的第一步，建立模型过程中经常会碰到如下问题：检验系统是否达到平稳状态；检验顾客相继到达时间间隔的相互独立性；确定服务时间的分布及有关参数等。(3)系统优化问题，又称为系统控制问题或系统运营问题，其基本目的是使系统处于最优或最合理的状态。系统优化问题包括最优设计问题和最优运营问题，其内容很多，有最少费用问题、服务率的控制问题、服务台的开关策略、顾客(或服务)根据优先权的最优排序等方面的问题。生

灭

过

程

和Poisson过

程设{N(t),t≥0}为一个随机过程。若N(t)的概率分布具有以下性质：(1)假设N(t)=n，则从时刻t起到下一个顾客到达时刻止的时间服从参数为λn的负指数分布，n=0,1,2,…。(2)假设N(t)=n，则从时刻t起到下一个顾客离去时刻止的时间服从参数为μn的负指数分布，n=0,1,2，…。(3)同一时刻时只有一个顾客到达或离去。则称{N(t),t≥0}为一个生灭过程。一、生灭过程简介定义1生

灭

过

程

和Poisson过

程二、Poisson过程和负指数分布设N(t)为时间［0,t］内到达系统的顾客数，如果满足下面三个条件：(1)平稳性：在［t,t+Δt］内有一个顾客到达的概率为λt+o(Δt)；(2)独立性：任意两个不相交区间内顾客到达情况相互独立；(3)普通性：在［t,t+Δt］内多于一个顾客到达的概率为o(Δt)。则称{N(t),t≥0}为Poisson过程。定义2生

灭

过

程

和Poisson过

程设N(t)为时间［0,t］内到达系统的顾客数，则{N(t),t≥0}为Poisson过程的充分必要条件是：(n=1,2,...)设N(t)为时间［0,t］内到达系统的顾客数，则{N(t),t≥0}为参数为λ的Poisson过程的充分必要条件是：相继到达时间间隔服从相互独立的参数为λ的负指数分布。定理1定理2M/M/s

等

待

制

排

队

模

型一、单服务台模型单服务台等待制模型M/M/1/∞是指：顾客的相继到达时间服从参数为λ的负指数分布，服务台个数为1，服务时间V服从参数为μ的负指数分布，系统空间无限，允许无限排队。单服务台模型1.队长的分布记pn=P{N=n}(n=0,1,2,…)为系统达到平稳状态后队长N的概率分布，并注意到λn=λ,n=0,1,2,…和μn=μ，n=1,2,…记ρ=λ/μ设ρ<1，则(n=1,2,...)故(n=1,2,...)其中，因此，(n=0,1,2,...)单服务台模型2.几个主要数量指标对单服务台等待制排队系统，由已得到的平稳状态下队长的分布，可以得到平均队长L为:平均排队长Lq为：单服务台模型关于顾客在系统中的逗留时间T，可说明它服从参数为μ-λ的负指数分布，即t≥0因此，平均逗留时间W为：因为，顾客在系统中的逗留时间为等待时间和接受服务时间之和，即T=Tq+V。其中，V为服务时间，故由可得平均等待时间Wq为:单服务台模型平均队长L与平均逗留时间W的关系：L=λW平均排队长Lq与平均等待时间Wq有如下关系：Lq=λWq这两个式子通常称为Little公式，是排队论中一个非常重要的公式。单服务台模型3.忙期和闲期忙期的平均长度和闲期的平均长度之比是：平均忙期为：不难发现，一个顾客在系统内的平均逗留时间等于服务员平均连续忙的时间。多服务台模型前提:单队、并列服务台我们仅讨论标准的M/M/C2……1C多服务台模型下面来讨论这个排队系统的平稳分布。记pn=P{N=n}(n=0,1,2，…)为系统达到平稳状态后队长N的概率分布，注意到对个数为s的多服务台系统，有λn=λ(n=0,1,2,…)和n=1,2,...,sn=s,s+1,...记则当ρs<1时，有n=1,2,...,sn≥s多服务台模型故n=1,2,...,sn≥s其中，给出了在平衡条件下系统中顾客数为n的概率，当n≥s时，即系统中顾客数大于或等于服务台个数，这时再来的顾客必须等待，因此记称为Erlang等待公式，它给出了顾客到达系统时需要等待的概率。多服务台模型对多服务台等待制排队系统，由已得到的平稳分布可得平均排队长Lq为：或多服务台模型记系统中正在接受服务的顾客的平均数为，显然也是正在忙的服务台的平均数，故说明，平均在忙的服务台个数不依赖于服务台个数s平均队长L为：L=平均排队长+正在接受服务的顾客的平均数=Lq+ρ对多服务台系统，Little公式依然成立，即有M/M/s混

合

制

排

队

模

型一、单服务台混合制模型M/M/1/K：顾客的相继到达时间服从参数为λ的负指数分布(即顾客的到达过程为Poisson流)，服务台个数为1，服务时间V服从参数为μ的负指数分布，系统的空间为K。单服务台混合制模型平稳状态下队长N的分布pn=P{N=n},n=0,1,2,…。由于所考虑的排队系统中最多只能容纳K个顾客(等待位置只有K-1个)，因而有n=0,1,2,...,K-1n≥Kn=1,2,...Kn=0,1,2,...,Kn>K有故n=1,2,…,K其中，ρ≠1ρ=1单服务台混合制模型由已得到的单服务台混合制排队系统平稳状态下队长的分布，可知当ρ≠1时，平均队长L为：当ρ=1时单服务台混合制模型类似地可得到平均排队长Lq为:或ρ≠1ρ=1单位时间内实际可进入系统的顾客的平均数为：λe=λ(1-pK)=μ(1-P0)称λe为有效到达率，而pK也被称为顾客损失率，它表示了在来到系统的所有顾客数中不能进入系统的顾客的比例。单服务台混合制模型根据Little公式，可得：平均逗留时间平均等待时间且仍有特别，当K=1时，M/M/1/1为单服务台损失制系统，在上述有关结果中令K=1，可得到：多服务台混合制模型二、多服务台混合制模型M/M/s/K：顾客的相继到达时间服从参数为λ的负指数分布(即顾客的到达过程为Poisson流)，服务台个数为s，每个服务台服务时间相互独立，且服从参数为μ的负指数分布，系统的空间为K。多服务台混合制模型n=0,1,2,...,K-1n≥K0≤n<ss≤n≤K由得0≤n<ss≤n≤K其中ρs≠1ρs=1多服务台混合制模型由平稳分布pn,n=0,1,2,…,K，可得平均排队长为：ρs≠1ρs=1平均队长:顾客的有效到达率:利用Little公式，得到多服务台混合制模型平均被占用的服务台数(也是正在接受服务的顾客的平均数)为：因此，又有其他排队模型简介一、有限源排队模型……服务台顾客源队列图1有限源排队系统顾客总数是有限的。每个顾客来到系统中接受服务后仍回到原来的总体，还有可能再来，这类排队问题的典型例子是机器看管问题。有限源排队模型平稳状态下队长N的分布pn=P{N=n},n=0,1,2,…,mn=1,2,...,sn=s,s+1,...m其中有限源排队模型系统的有关运行指标：或有限源排队模型特别，对单服务台(s=1)系统，有（n=1,…,m）或系统的相对通过能力Q=1，绝对通过能力A=λeQ=λ(m-L)=μ(1-p0)非生灭过程排队模型三、非生灭过程排队模型以上讨论的系统，其前提均为泊松输入和负指数服务处理，在实际中，有时到达仍为泊松过程，但服务时间并不服从负指数分布，这时不能用生灭过程处理，必须引入新的方法来分析具有非负指数分布的排队系统。下面仅就几种特殊情形给出有关的结果。非生灭过程排队模型1.M/G/1排队模型M/G/1系统：顾客的到达为Poisson流，单个服务台，服务时间为一般分布的排队系统。现假设顾客的平均到达率为λ，服务时间的均值为1/μ，方差为σ2，则可证明：当ρ=λ/μ<1时，系统可以达到平稳状态，而给出平稳分布的表示是比较困难的。已有的几个结果为：Lq,L,W,Wq等仅依赖于ρ和服务时间的方差σ2，而与分布的类型没有关系，这是排队论中一个非常重要且令人惊奇的结果。通常被称为Pollaczek\|Khintchine(P\|K)公式。非生灭过程排队模型2.爱尔朗(Erlang)排队模型对爱尔朗排队模型研究的一般方法是根据k-阶Erlang分布恰为k个相同负指数分布随机变量和的分布这个关系，把服务时间或到达过程假想地(实际并非如此)分为k个独立的同分布的位相(或阶段)，然后利用负指数分布的性质来加以分析。非生灭过程排队模型作为一个特例，给出M/Ek/1/∞的主要数量指标：服务时间为k-阶Erlang分布，其分布密度函数为：t≥0其均值和方差分别为：排队系统的优化我们主要研究静态优化，目标:费用(损失)最小。ïìïíî系统设计优化（静态）：如何设计一个系统（如何定μ，C，服务规则）使费用最经济（未必最小）。

系统控制优化（动态）：一个给定