下载文档原格式
第一节引言一、排队系统的特征及排队论排队论（queueing theory）是研究排队系统（又称为随机服务系统）的数学理论和方法，是运筹学的一个重要分支。
在日常生活中，人们会遇到各种各样的排队问题。
如进餐馆就餐，到图书馆借书，在车站等车，去医院看病，去售票处购票，上工具房领物品等等。
在这些问题中，餐馆的服务员与顾客、公共汽车与乘客、图书馆的出纳员与借阅者、医生与病人、售票员与买票人、管理员与工人等，均分别构成一个排队系统或服务系统（见表10-1）。
排队问题的表现形式往往是拥挤现象，随着生产与服务的日益社会化，由排队引起的拥挤现象会愈来愈普遍。
表 10-1排队除了是有形的队列外，还可以是无形的队列。
如几个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆，则部分顾客只得在各自的要车处等待，他们分散在不同地方，却形成了一个无形队列在等待派车。
排队的可以是人，也可以是物。
如生产线上的原材料或半成品在等待加工；因故障而停止运转的机器在等待修理；码头上的船只等待装货或卸货；要降落的飞机因跑道被占用而在空中盘旋等等。
当然，提供服务的也可以是人，也可以是跑道、自动售货机、公共汽车等。
为了一致起见，下面将要求得到服务的对象统称为“顾客”，将提供服务的服务者称为“服务员”或“服务机构”。
因此，顾客与服务机构（服务员）的含义完全是广义的，可根据具体问题而不同。
实际的排队系统可以千差万别，但都可以一般地描述如下：顾客为了得到某种服务而到达系统，若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图10-1至图10-4。
类似地还可画出许多其他形式的排队系统，如串并混联的系统，网络排队系统等。
尽管各种排队系统的具体形式不同，但都可由图10-5加以描述。
图10-1 单服务台排队系统图10-2 s 个服务台，一个队列的排队系统图10-3 s 个服务台，s 个队列的排队系统图10-4 多个服务台得串联排队系统顾客到达顾客到达图10-5 随机服务系统通常称由10-5表示的系统为一个随机聚散服务系统，任一排队系统都是一个随机聚散服务系统。
M/G/1型排队系统分析与仿真一、排队系统排队论(queuing theory), 或称随机服务系统理论, 是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。
它是数学运筹学的分支学科。
也是研究服务系统中排队现象随机规律的学科。
广泛应用于计算机网络, 生产, 运输, 库存等各项资源共享的随机服务系统。
排队论研究的内容有3个方面：统计推断，根据资料建立模型；系统的性态，即和排队有关的数量指标的概率规律性；系统的优化问题。
其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。
一般的排队过程为：顾客由顾客源出发，到达服务机构（服务台、服务员）前，按排队规则排队等待接受服务，服务机构按服务规则给顾客服务，顾客接受完服务后就离开。
排队过程的一般过程可用下图表示。
我们所说的排队系统就是指图中虚线所包括的部分。
排队系统又称服务系统。
服务系统由服务机构和服务对象（顾客）构成。
服务对象到来的时刻和对他服务的时间（即占用服务系统的时间）都是随机的。
描述一个排队系统一般需要分析其三个组成部分：输入过程、排队规则和服务机构。
输入过程输入过程考察的是顾客到达服务系统的规律。
它可以用一定时间内顾客到达数或前后两个顾客相继到达的间隔时间来描述，一般分为确定型和随机型两种。
例如，在生产线上加工的零件按规定的间隔时间依次到达加工地点，定期运行的班车、班机等都属于确定型输入。
随机型的输入是指在时间t内顾客到达数n（t）服从一定的随机分布。
如服从泊松分布,则在时间t内到达n个顾客的概率为或相继到达的顾客的间隔时间T 服从负指数分布，即式中λ为单位时间顾客期望到达数，称为平均到达率；1/λ为平均间隔时间。
在排队论中，讨论的输入过程主要是随机型的。
排队规则排队规则分为等待制、损失制和混合制三种。
第四章 排队模型两类排队模型：1. Markov 排队模型2. 非Markov 排队模型Markov 排队模型：4-0 Little 定理1961 年 J.D.Little 证明 1974 年 S.Slidhan 一般性证明定理 : 在极限平稳状态下,排队系统内顾客平均数L 系 和 顾客在系统内平均逗留时间W 系 之间的关系,不管到达流的分布如何,也不管服务规则如何,均有以下关系:为到达流的强度系系λλ14.-=L W证明:设 X(t) ---- t 时刻前到达的瞬时顾客数, Y(t)--- t 时刻前离开的瞬时顾客数.Y(t)在稳定后,流入与流出的顾客数应相等, 则在t 时刻留在系统内的顾客数为:Z(t)=X(t)-Y(t)在足够长的时间T 来考虑有:队队系系系系同理可以证明所以有逗留时间系统内每个顾客的平均时间的总和所有顾客在系统内逗留时间个顾客在系统内的逗留第其中的小面积的总和高度为长度为阴影部分的面积W L W L W Tt t i t t Tt T t T T dtt Z T L iiii i iiii i T.:.:...,:.11]1*[1][1)(10λλλλλ==--=--=⨯====∑∑∑∑⎰4-1 M/M/1/0 (单通道损失制)服务员数：n=1 队长：m=0M -- 到达流为Poisson,流强λM -- 服务时间服从指数分布：)0()(>=⋅-t e t f t μμ 状态为系统内顾客数，I={0,1}"0"表示服务员闲，其概率为：P 0(t)；"1"表示服务员忙，其概率为：P 1(t)； 状态转换图：Fokker-Plank k 方程：可得:)0(1)0(:341)()(24)()()(14)()()(1010011100==-=+-+-=-+-=∙∙P P t P t P t P t P t P t P t P t P 初始条件λμμλ联立求解4-1与4-3得：λμλλμλμμλλμλλλμλλμμμμλμλμλμλ+=∞+=∞∞→==+-+=-=+++=-++-=-+-=+----+-∙∙)(,)()0(,1)0(0)(1)()(44)()()()(1[)()(1010)(01)(000000P P t P P t e t P t P e t P t P t P t P t P t P tt定义：系统负载能力：μλρ=指标：(1) ρμλμ+=+===110P Q 请求服务的顾客数被服务顾客数 (2) 绝对通过能力：ρλμλλμλ+=+===1Q A 数单位时间被服务的顾客(3) 损失概率(即顾客来时，系统服务员忙，顾客离去)ρρμλλμλμ+=+=+-=-==1111Q P P 损例一：一条电话线，呼叫率为：0.8次/分(λ=0.8)，每次平均通话时间为：τ=1.5分。
求相对通过能力，绝对通过能力，损失率，比较实际通过能力与最大(额面)通过能力。
解：分次通过能力额面最大电话损失概率绝对通过能力相对通过能力系统负荷水平额损/667.05.111:)(545.011:364.02.118.01:455.02.11111:2.1667.08.0:667.05.1110=====-=+==+=+==+=+========μτρρλρμλρτμA Q P A P Q Erlang4-2 多通道损失制 ( M/M/n/0)服务员数：n系统内最大顾客数(排队最大顾客数)：m=0系统状态："0"---n 个服务员闲，系统内顾客数为0； "1"---1个服务员忙，系统内顾客数为1，(n-1)个服务员闲； …………………………………….. "k"---k 个服务员忙，系统内顾客数为k ，(n-k)个服务员闲； "n"---n 个服务员忙，系统内顾客数为n 。
系统状态转换图：(1) 求瞬态解：n B P A P μ-=⇒→⇒∙(2) 求稳态解：[ P 0,P 1,………P n ]a. B A P n μ1-→⇒-=b. 利用状态转换图：n k i k P k P n P P P P P n P P n P n Pk k P P P k P k PP P P P P P P P P ni ikk nk knn nn n n kk k kk ......2,1,0!!!11)!...............!2!11(1........!)(""..................................................................................!!)()(""...............................................................................!2!2)(2:"1":"0"00201001001020222100110====+++=++============∑∑==--ρρρρρρρμλρμλμλρμλμλμλρρμλμλ对对对对指标：(1) 系统损失概率：0!P n P P nn ρ==损(2) 系统的相对通过能力：0!11P n P Q nρ-=-=损(3) 系统绝对通过能力：)1()!1(0n nP P n Q A -=-==λρλλ(4) 占用的服务员的平均数=占用通道的平均数：μλρρρρρρρρρρρρρρρAAP P n n P P n k P k P kP P k P k kkP k E n nn nn k kn k knk k nk knk knk k ==-=-=-=-∑=∑=∑-=∑-=∑=∑=-=-==-===]1[]!1[]!1[]!![!)!1()!1(!][00010101100100(5) 通道利用率：nk E ][=η 例二：某电话总机有三条中继线(n=3)，其它条件同例一，求系统的极限概率，绝对与相对通过能力，损失概率，占用通道的平均数。
解： λ=0.8 μ=0.667 ρ=0.8/0.667=1.2极限概率：090.0312.0*228.0!3224.0312.0*7.0!2374.0312.0]!3!21[033022011320=========+++=-P P P P P P P ρρρρρρ系统损失概率：09.03==P P 损 相对通过能力：91.009.011=-=-=损P Q绝对通过能力：728.091.0*8.0===Q A λ 占用通道的平均数：09.1667.0728.0===-μA k通道利用率：363.0309.1====-n k η 比较n=1，与n=3的情况：P 损 Q A k ηn=1 0.545 0.455 0.364 0.545 0.545 n=3 0.09 0.91 0.728 1.09 0.363 由上表可见，增加外线数n 可使损失概率减小，通过能力增加，通道利用率减小。
4-3 单通道等待制( M/M/1/∝=M/M/1)n=1 一个服务员m=∝ 无穷大队长，服务员有空，顾客被服务；服务员忙，顾客排队，直到得到服务"状态"定义为系统中的顾客数， " 0 " ---系统中无顾客，服务员闲；" 1 " ---系统中有一个顾客，正在服务, 服务员忙； " 2 " ---系统中有2个顾客，1个正在服务，另一个在排队，服务员忙； ……………………………………………… " k " ---系统中有k 个顾客，1个正在服务，(k-1)个在排队，服务员忙。
……………………………………………..可以证明：当 ρ<1 时，虽然状态数为无穷大，仍然存在极限概率。
其状态转换图:列稳态K-F 方程：Zz g P P P P P P P P P P P P P P P P P P P k k k kk k k ρρρρρρρρρρρμλμλμλρμλμλ--∞==⇔-=-==∴=++++=++++===+=+==∴=∑1100202100202212000110)()1(111.........).......1(1....................................)()(求系统指标：(1) 系统内顾客数的均值：..λμλρρρρρρρρρρρρρρρρρρρ-=-=--=--=∑-=∑-=∑-=∑=∞=-∞=1)1(1)1()1()1()1()1()1(2010d d d d kk kP L k k k k k k 第二种方法:λμλρρρρρρρ-=-===--=--==1])([][)1()1()(11)(12Z dz z dg k E L Z dz z dg Zz g(2) 顾客在系统中平均逗留时间：利用Little 定理：λμρμλ-=-==1)1(1L W (3) 顾客排队平均队长： L q =L - L sLs -- 在服务的顾客数平均值，由于只有一个服务员，他的平均值就是忙的概率P 忙； 而：P 忙+P 0=1Ls = P 忙=1-P 0=1-(1-ρ)=ρ 所以有：)(1122λμμλρρρρρ-=-=--=-=Ls L L q (4) 顾客平均排队时间：)1(2ρλρλ-==qq L W(5) 系统内有多于一个顾客的概率：P(k>1)=1-P 0-P 1=1-(1-ρ)-ρ(1-ρ)=ρ2 (6) 系统内有多于m 各顾客的概率：111)1(11)(++==--=∑-=>m m mk k P m k P ρρ(7) 系统内顾客数的方差：202)1()()(ρρ-=∑-=∞=k k P L k k D 证明：利用矩生成函数 (母函数)ρρρρρρρρρρρρρρρρρρρρρρρρρρρρρ--++--='-'+''=-='==--=-----=''--=--='--=∑-=∑-=∑=∞=∞=∞=11)1()1(2)]1([)1()1(][1)1(][)1()1(2)1())(1(2)1()()1()1()1()1()(11)()1()1()(322324220g g g k D g k E L Z Z Z Z g Z Z Z g ZZ Z Z P z g k kk kk k k k 2)1(ρρ-=或写成均方差：ρσρρσ1)()()(:1)(==-==k E k k V k D 偏离系数(8) 排队中的顾客数的方差：243222332233222222121211212)1()1(1)1()1(2)]1([)1()1()(1)1()()1()1(2)()1()1()(111)1()1()111)(1()1(]1)[1()1()1()1()1()1()()1(0)10(01)1()1(11,0)(ρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρρ--+=---+--='-'+''=-='==--=''--='-+--=--+-=---+-=∑--+-=∑-+-=∑-+-=∑=⎩⎨⎧>>===-=-+-=∴⎩⎨⎧≥-==∑=∞=∞=∞=+∞=+∞=q q q qq qq q q q q qq q qq q qq q q q q qg g g q D g q E L Z Z g Z Z g ZZ Z ZZ ZZ Z Z Z P Z g k q k k q P k k k k q qP q D(9) 顾客在排队时间的分布，均值与方差：先求排队时间的分布密度：设随机变量：w q =第n+1个顾客排队等待服务的时间，即前面已有n 个顾客在系统中，其中一个在服务，n-1个在排队，这第n+1个顾客要等n 个顾客服务完毕后才能得到服务，所以等待时间为：w q =s 1+s 2+…..+s n ；而s 1,s 2,…..s n 服从均值(1/μ)的指数分布，则w q 服从k-Erlang 分布，其分布函数为：)!1()()(1-=--n t e t g n tw q μμμ 考虑到n 可从1到∝变化，所以有：tttm m tn n tn nn tnn w w ee e m t en t e n t eP t g t f q q .)..(..1.11.111)1(.)1()!()()1()!1().()1()1()!1()()()(λμλμμμμρρμρρμλρρμρμρρμρρμμ+--∞=--∞=-∞=--∞=-=-=∑-=-∑-=∑--=∑=平均排队时间为：)1(.)1(..)1()(.0.)..(0.)..(0ρμρρμρμρρλμλμ-=⎰-=⎰-=⎰=∞--∞--∞dt e t dt e t dt t f t W t t w q q(10) 顾客在系统中逗留时间的分布，均值：第n+1个顾客在系统中逗留时间为：tn n tn t nn n nw w tnn w n n e n t ee n t P tf t f e n t tg Erlang n s s s s w .)..(0..10.1121)1(!).()1()1(!)()(!)(:1....λμμμμρμμρρμρρμμ--∞=--+∞=-++-=∑-=-∑=∑==+++++=分布阶它服从顾客在系统中逗留的平均时间：)1(1.)1(.).1()(.0)..(0.)..(0ρμρμρμλμλμ-=⎰-=⎰-=⎰=∞--∞--∞dte t dte t dt tf t W t t w验算：)1(11)1(ρμμρμρ-=+-=+=s q W W W 例：一个批处理计算机系统，作业处理时间服从指数分布，平均时间为三分钟/作业，作业的到达服从Poison 分布，平均为：1作业/4分钟，服务规则为：先到先服务(FCFS)。
