运筹学第11章-排队论

运筹学毕德春辽东学院信息技术学院信息管理系第10讲排队论第一节排队论的基本概念第二节第三节第四节第一节排队论的基本概念排队论（queuingtheory）作为排队系统（随机服务系统）的数学理论和方法，是运筹学的一个重要分支。排队是日常生活中经常遇到的现象，如进餐馆就餐、图书馆借书、在车站候车、售票处购票等等。排队问题的表现形式往往是拥挤现象，随着生产与服务的日益社会化，由排队引起的拥挤现象会越来越普遍。下面我们列举出部分形形色色的排队系统。排队论的基本概念基本概念生活和工作中形形色色的排队系统达到的顾客要求服务的内容服务的机构出故障的机器修理技工病人电话呼叫进港货船入水库河水达到机场上空的飞机刑事案件达到路口的车辆来犯敌机修理领取修配零件诊断（或治疗）通话装（卸）货放水、调整水位降落侦破通过路口截击修理技工发放修配零件的管理员医生（或治疗设备）交换台装（卸）货码头（泊位）水闸、管理员跑道刑侦部门交通信号灯我防空部队排队论的基本概念基本概念排队可以是有形的队列，也可以是无形的队列。排队可以是人，也可以是物。顾客源排队结构服务机构顾客到来排队规则服务规则顾客离去排队论的基本概念基本概念1单队——单服务台系统排队论的基本概念常见排队系统结构图1单队——多服务台（并联）系统2S...排队论的基本概念常见排队系统结构图1…S单队——多服务台（串联）系统排队论的基本概念常见排队系统结构图1多队——多服务台（并联）系统.........2S排队论的基本概念常见排队系统结构图多队——多服务台（混联、网络）系统排队论的基本概念常见排队系统结构图一、输入过程说明顾客按怎样的规律达到系统，通常从3个方面刻画：顾客总体（顾客源）数达到方式顾客相继达到的时间间隔分布。排队论的基本概念排队系统的三大要素描述二、排队及排队规则排队损失制排队等待制排队混合制排队排队规则先到先服务FCFS后到先服务LCFS有优先权服务PS随机服务RF排队论的基本概念排队系统的三大要素描述三、服务机制说明顾客按怎样的规律接受服务，通常从3个方面刻画：服务员的数量及其连接形式（并联或串联）顾客接受服务的方式（单个或成批）服务时间分布其中服务时间分布是最重要因素，其常见的分布有：定长分布（D）负指数分布（M）k阶爱尔朗分布（Ek）排队论的基本概念排队系统的三大要素描述一般形式：X/Y/Z/A/B/CX——顾客相继达到时间间隔的概率分布Y——服务时间的概率分布Z——服务台的个数A——服务机构的容量（容纳所有顾客的数量）B——顾客源的容量C——排队规则排队论的基本概念排队系统分类衡量一个排队系统的好坏以及对一个排队系统作经济分析，需要一系列描述排队系统特征的数量指标，主要的数量指标通常有：Ls：系统中顾客数的期望（平均）值。Lq：系统中排队顾客数的期望（平均）值。Ws：顾客在系统中逗留时间的期望（平均）值。Wq：顾客在系统中排队等待时间的期望（平均）值。Pl：系统损失概率（系统满容量的概率）。A：占用服务台的平均数。：服务台的利用率。排队论的基本概念排队系统的主要数量指标数量指标：研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统的基本运行特征。统计推断：检验系统是否达到平稳状态；检验顾客达到间隔的独立性；确定服务时间分布及参数。系统优化：系统的最优设计和最优运营问题。排队论的基本概念排队论的基本问题一类重要且广泛存在的排队系统是生灭过程排队系统。生灭过程是一类特殊的随机过程。在排队论中，“生”表示顾客的达到，“灭”表示顾客的离去。排队论的基本概念排队系统的生灭过程无限状态生灭过程定义：设｛N（t），t≥0｝是一个随机过程（其中N（t）表示时刻t系统中的顾客数）。若的概率分布具有如下性质：假设N（t）=n，则从时刻t起到下一个顾客达到时刻止的时间服从参数为n的负指数分布，n=0，1，2，…。假设N（t）=n，则从时刻t起到下一个顾客离去时刻止的时间服从参数为n的负指数分布，n=0，1，2，…。同一时刻只有一个顾客达到或离去。则称｛N（t），t≥0｝是一个生灭过程。排队论的基本概念排队系统的生灭过程Nn+1nn-1nN-10101n-1nn+1NN-1……有限状态生灭过程：p0p1pn-1pnpn+1pN-1pN稳态方程组：0p0-1p1=0(n=0)N-1pN-1-NpN=0(n=N)(n-1pn-1+n+1pn+1)–(npn+npn)=0(1≤n≤N-1)nn-1n0101n-1nn+1N…n+1…p0p1pn-1pnpn+1pN…稳态方程组：0p0-1p1=0(j=0)(n-1pn-1+n+1pn+1)–(npn+npn)=0(j≥1)无限状态生灭过程：排队论QueuingTheory（QT）生灭过程简介无限状态生灭过程的解记Cn=n-1n-2…10nn-1…21n=1，2，…则平稳状态时生灭过程的解为：Pn=CnP0n=1，2，…其中P0=11+∑Cn∞n=1注意！无穷级数∑Cn收敛时上式方有意义，这点可由系统进入平稳状态得到保证。排队论QueuingTheory（QT）Poisson过程和负指数分布Poisson过程Poisson过程（又称为Poisson流、最简流）是排队论中最为常见的一种描述顾客达到规律的特殊随机过程。定义：设N（t）为时间0，t内达到系统的顾客数，如果满足下面三个条件：1.平稳性：在t，t+t内有一个顾客达到的概率为t+(t)；2.独立性：在任意两个不相交时间区间内顾客达到相互独立；3.普通性：在t，t+t内多于一个顾客达到的概率为(t)。则称｛N（t），t≥0｝为Poisson过程。排队论QueuingTheory（QT）Poisson过程和负指数分布Poisson过程与负指数分布定理1设N（t）为时间0，t内达到系统的顾客数，则｛N（t），t≥0｝为Poisson过程的充要条件是：P｛N（t）=n｝=（t）n/n！e-tn=1，2，…定理2设N（t）为时间0，t内达到系统的顾客数，则｛N（t），t≥0｝为参数为的Poisson过程的充要条件是：相继达到时间间隔服从相互独立的参数为的负指数分布。上述定理阐述了Poisson过程与负指数分布的等价性。排队论QueuingTheory（QT）常见排队系统生灭过程排队系统M/M/n/n损失制排队系统M/M/n/∞等待制排队系统M/M/n/N混合制排队系统M/M/n/∞/N顾客源有限排队系统排队论QueuingTheory（QT）常见排队系统单服务台模型M/M/1（M/M/1/∞/∞）01n-1nn+1N……p0p1pn-1pnpn+1pN…解为：P0=1-，（=/）Pn=（1-）n，（n≥1）排队论QueuingTheory（QT）常见排队系统M/M/1（M/M/1/∞/∞）主要系统指标1.Ls=/（1-）=/（-）其中0＜＜12.Lq=Ls-=2/（1-）3.Ws=Ls/=1/（-）4.Wq=Lq/=Ws-1/=/（-）排队论QueuingTheory（QT）常见排队系统多服务台模型M/M/s（M/M/s/∞/∞）s01s-1ss+1N…s…p0p1ps-1psps+1pN…解为：排队论QueuingTheory（QT）常见排队系统多服务台系统与单多服务台系统的比较一个M/M/3与三个M/M/1的比较台1台2台3台1台2台3一个M/M/3三个M/M/1从这两个系统的主要指标比较可以看出混合排队比独立排队具有显著的优越性，这一点是在排队系统的排队方式的设计时应该注意的。排队论QueuingTheory（QT）常见排队系统非生灭过程排队系统一个排队系统的特征是由输入过程、服务机制和排队规则三大要素决定的。前面所讨论的排队模型“M/M/”型的，这类排队系统的一个主要特征是马尔可夫性，而马尔可夫性的一个主要性质是由系统当前的状态可以推断未来的状态。但是，当系统不是“M/M/”型时，仅仅知道系统内当前的顾客数，对于推断系统未来的状态是不充足的，因为正在接受服务的顾客，已经被服务了多长时间，将影响其离开系统的时间。因此，须引入新的方法来分析具有非负指数分布的排队系统。一般而言，具有非负指数分布的排队系统的分析是非常困难的。排队论QueuingTheory（QT）常见排队系统非生灭过程排队系统一般服务时间模型M/G/1模型M/G/1系统是顾客达到为Poisson流，单服务台，服务时间为一般分布的排队系统。设：——顾客的平均达到率；T——服务时间；ET——平均服务时间；2——VarT方差；——ET，为使系统达到稳态，必须有＜1。当时，系统可以达到平稳状态，而要给出平稳分布的显示是比较困难的。已有的几个结果是：排队论QueuingTheory（QT）常见排队系统非生灭过程排队系统波拉切克（Pollaczek）—欣钦（Khintchine）公式（P-K）公式：Lq=2+222（1-）此外有：Ls=Lq+Ws=Ls/Wq=Lq/排队论QueuingTheory（QT）常见排队系统非生灭过程排队系统波拉切克（Pollaczek）—欣钦（Khintchine）公式由以上的（P–K）公式可以看出Ls、Lq、Ws、Wq等排队系统的重要指标仅仅依赖于和服务时间的方差2，而与分布的类型无关，这是排队论中一个非常重要而又令人惊奇的结果！从（P–K）公式不难看出，当确定后，当方差2减少时，平均队长和等待时间都将减少。因此，可通过服务时间的方差来缩短平均队长，当且仅当2=0，即服务时间为定长时，平均队长和等待时间可减少到最少水平，这一点是符号直观的，因为服务时间越有规律，等待的时间也就越短。排队论QueuingTheory（QT）排队系统的优化排队系统的最优化设计1、以最少的“设备”获得最大的效益，或者说，在一定的服务质量指标下要求服务机构最为经济。2、给出排队系统的某种费用结构，要求总费用最优的情况下对系统的服务率、服务台数n、系统容量N、以及排队规则等等进行设计。排队论QueuingTheory（QT）排队系统模拟分析方法随机模拟当排队系统的达到间隔时间和服务时间的概率分布比较复杂，或不能用公式给出时，就不能用解析方法求解，这时可以应用随机模拟方法进行分析，为了阐明此方法，举例如下：例设某仓库前有一卸货场，货车一般是夜间达到，白天卸货。每天只能卸货3车，为定长分布。若一天内达到的货车超过3辆，必须推迟到次日卸货。下表给出了货车达到数量的经验分布，平均为2.4车/天，求每天推迟卸货的平均车数。达到车数012345≥6概率0.050.300.300.100.050.200.00排队论QueuingTheory（QT）排队系统模拟分析方法随机模拟解该问题是一个单服务台的排队系统，可验证达到车数不服从Poisson分布，服务时间也不是负指数分布（是定长分布）故不能采用以前的方法分析。模拟方法见ExcelSpreadsheet随机模拟方法只能得到数字结果，不能得到解析表达式！