运筹学-8、排队论

运筹学OperationsResearchQueuingtheory第7章排队论7.1排队论的基本概念7.2排队系统常用分布7.3单服务台模型[M/M/1]7.4多服务台模型[M/M/s]7.5其它服务时间分布模型7.6排队系统的优化WheretheTimeGoes美国人一生中平均要花费--6年吃5年排队等待4年做家务2年回电话不成功1年寻找放置不当的物品8个月打开邮寄广告6个月停在红灯前排队系统的基本特征离开排队规则到达过程排队结构服务过程退出离开需求群体商业服务系统系统类型 顾客 服务台理发店 人 理发师银行出纳服务 人 出纳ATM机服务 人 ATM机商店收银台 人 收银员管道服务 阻塞的管道 管道工电影院售票窗口 人 售票员机场检票处 人 航空公司代理人经纪人服务 人 股票经纪人内部服务系统系统类型 顾客 服务台秘书服务 雇员 秘书复印服务 雇员 复印机计算机编程服务 雇员 程序员大型计算机 雇员 计算机急救中心 雇员 护士传真服务 雇员 传真机物料处理系统 货物 物料处理单元维护系统 设备 维修工人质检站 物件 质检员运输服务系统系统类型 顾客 服务台公路收费站 汽车 收费员卡车装货地 卡车 装货工人港口卸货区 轮船 卸货工人等待起飞的飞机 飞机 跑道航班服务 人 飞机出租车服务 人 出租车电梯服务 人 电梯消防部门 火灾 消防车停车场 汽车 停车空间急救车服务 人 急救车到达过程静态动态预约定价接受/拒绝不加入排队退出排队恒定到达率的随机到达变动到达率的随机到达由设施控制顾客控制到达过程到达过程的内容顾客总体数或顾客源数有限或无限顾客的到达类型单个或成批顾客的到达间隔时间间隔时间分布排队结构领号多条队列有限队长有限队长有限或无限队长快速通道排队结构单一队列允许或不允许移动排队结构-例多队多服务台领号34826101211579单队多服务台入口排队规则排队规则静态(FCFS规则)(LCFS规则).动态基于排队状况选择即与特定顾客特征选择等待的顾客数协商优先级强占顾客服务时间(SPT规则)排队规则的内容损失制系统服务台被占用时新到的顾客将离开等待制系统FCFSLCFSRSPR混合制系统损失制与等待制的混合服务过程服务过程静态服务过程动态服务过程自我服务机械速度不同的服务率开关服务通道服务过程的内容服务台数量单个或多个每次服务顾客的数量单个或成批服务顾客的时间分布时间分布常用的记号n––系统中的顾客数

––平均到达率，即单位时间内平均到达的顾客数

––平均服务率，即单位时间内服务完毕的顾客数Sn(t)––时刻t系统中有n个顾客Pn(t)––时刻t系统状态Sn(t)的概率C––服务台的个数M––顾客相继到达的时间间隔服从负指数分布D––顾客相继到达的时间间隔服从定长分布Ek––顾客相继到达的时间间隔服从k阶Erlang分布排队系统的符号表示一个排队系统的特征可以用六个参数表示，形式为：

[A／B／C]：[d／e／f]其中A––顾客到达的概率分布，可取M、D、Ek等；B––服务时间的概率分布，可取M、D、Ek等；C––服务台个数，取正整数；d––排队系统的最大容量，可取正整数或；e––顾客源的最大容量，可取正整数或；f––排队规则，可取FCFS、LCFS等。[M/M/1]：[//FCFS]表示：顾客到达的时间间隔是负指数分布服务时间是负指数分布一个服务台排队系统和顾客源的容量都是无限实行先到先服务的一个服务系统

Poisson流（Poisson过程）定义满足以下四个条件的输入流称为Poisson流（Poisson过程）1、平稳性：在时间区间[t,t+t)内到达k个顾客的概率与t无关，只与t有关。记为pk(t）。2、无后效性：不相交的时间区间内到达的顾客数互相独立。3、普通性：设在[t,t+t）内到达多于一个顾客的概率为q(t），则

q(t)=o(t)即

4、有限性：任意有限个区间内到达有限个顾客的概率等于一。即Poisson流与Poisson分布定理

对于一个参数为的Poisson流，在[0，t)内到达k个顾客的概率为

即服从以为参数的Poisson分布。

lll=1=3=7Pkk.4.3.2.10数学家泊松（Poisson）（1781—1840）

“泊松是第一个沿着复平面上的路径实行积分的人.”──克兰

“我建立了描述随机现象的一种概率分布.”──泊松

泊松是法国数学家、物理学家和力学家

Poisson流与负指数分布之间的关系定理

在排队系统中，如果单位时间内顾客到达数服从以为参数的Poisson分布，则顾客相继到达的时间间隔服从以为参数的负指数分布。

l=0.41/为平均到达间隔时间Excel中的泊松分布POISSON

用途：返回泊松分布。泊松分布通常用于预测一段时间内事件发生的次数，比如一分钟内通过收费站的轿车的数量。

语法：POISSON(x，mean，cumulative)

参数：X是某一事件出现的次数，Mean是期望值，Cumulative为确定返回的概率分布形式的逻辑值。Cumulative

为一逻辑值，确定所返回的概率分布形式。如果cumulative为TRUE，函数POISSON返回泊松累积分布概率，即，随机事件发生的次数在0到x之间（包含0和1）；如果为FALSE，则返回泊松概率密度函数，即，随机事件发生的次数恰好为x。

实例：公式“=POISSON(5，10，TRUE)”返回0.067085963，=POISSON(3，12，FALSE)返回0.001769533。k阶Erlang分布定理

设v1，v2，…，vk是k个互相独立的，具有相同参数的负指数分布随机变量，则随机变量

S=v1+v2+…+vk服从k阶Erlang分布，S的密度函数为m=1k=1k=2k=4k=8系统绩效度量

系统总的平均顾客数L

平均等待顾客个数Lq

包括服务的平均等待时间W

平均顾客等待时间Wq基本排队模型[M/M/1]:[//FCFS]顾客到达的时间间隔是负指数分布服务时间是负指数分布一个服务台排队系统和顾客源的容量都是无限实行先到先服务的一个服务系统[M/M/1]:[//FCFS]的分析假设在t+t时刻系统中顾客数为n的概率Pn(t+t)SnSnSn+1Sn-1SnPn(t)Pn-1(t)Pn+1(t)Pn(t)t时刻t+t时刻无到达，无离开无到达，离开一个到达一个，无离开到达一个，离开一个系统的过渡状态与稳定状态过渡稳定稳定状态下的状态概率得到

令

称为服务强度，则得[M/M/1]:[//FCFS]的状态转移分析λ012n-1nn+1例高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为100辆／小时，收费时间服从负指数分布，平均收费时间为15秒／辆。求1、收费处空闲的概率；2、收费处忙的概率；3、系统中分别有1，2，3辆车的概率。解根据题意,=100辆/小时,1/=15秒=1/240（小时/辆）,即＝240（辆/小时）。因此，=/=100/240=5/12。系统空闲的概率为：

P0=1-=1-(5/12)=7/12=0.583系统忙的概率为：

1-P0=1-(1-)==5/12=0.417系统中有1辆车的概率为：

P1=(1-)=0.417×0.583=0.243系统中有2辆车的概率为：

P2=2(1-)=0.4172×0.583=0.101系统中有3辆车的概率为：

P3=3(1-)=0.4173×0.583=0.0421Little公式[M/M/1]:[//FCFS]的系统指标系统中的平均顾客数L

队列中的平均顾客数Lq顾客在系统中的平均逗留时间W顾客在队列中的平均逗留时间Wq例高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为200辆/小时，收费时间服从负指数分布，平均收费时间为15秒/辆。求L、Lq、W和Wq。解根据题意，=200辆/小时，=240辆/小时，=/=5/6。有限队列模型[M/M/1]:[N//FCFS]当队列的容量从无限值变为有限值N时，[M/M/1]:[//FCFS]就转化成为[M/M/1]:[N//FCFS]

系统的状态转移图

λ012n-1n系统的状态概率平衡方程对于状态0： P0=P1

… …对于状态k： Pk-1+Pk+1=(+)Pk0<k<N… …对于状态N： PN-1=PN系统的状态概率由得到

系统的运行指标对于1有有效到达率Little公式例一个单人理发店，除理发椅外，还有4把椅子可供顾客等候。顾客到达发现没有座位空闲，就不再等待而离去。顾客到达的平均速率为4人/小时，理发的平均时间为10分钟/人。顾客到达服从Poisson流，理发时间服从负指数分布。求：1、顾客到达不用等待就可理发的概率；2、理发店里的平均顾客数以及等待理发的平均顾客数；3、顾客来店理发一次平均花费的时间及平均等待的时间；4、顾客到达后因客满而离去的概率；5、增加一张椅子可以减少的顾客损失率。解这是一个[M/M/1]:[N//FCFS]系统，其中N=4+1=5，=4人/小时，=6人/小时，=2/3。

因客满而离去的概率为0.048当N=6时

P5-P6=0.0480-0.0311=0.0169=1.69%即增加一张椅子可以减少顾客损失率1.69%[M/M/1]:[∞/m/FCFS]模型设顾客总数为m。当顾客需要服务时，就进入队列等待；服务完毕后，重新回到顾客源中。如此循环往复。服务台...顾客源需要服务服务完毕队列分析假定每一个顾客在单位时间内需要接受服务的平均次数是相同的，设为λ

。当正在等待及正在接受服务的顾客数为n时，则在单位时间内要求接受服务的平均顾客数为：

λn=λ(m-n)01nm状态转移方程λ0P0=μP1 ……[λn+μ]Pn=μPn+1+λn-1Pn-1

(n=1，2，…，m-1)

……μPm=λm-1Pm-1

(n=1，2，…，m)

运行指标例某车间有5台机器，每台机器的连续运转时间服从负指数分布，平均连续运行时间15分钟。有一个修理工，每次修理时间服从负指数分布，平均每次12分钟。求:(1)修理工空闲的概率；(2)五台机器都出故障的概率；(3)出故障的平均台数；(4)平均停工时间；(5)平均等待修理时间；(6)评价这个系统的运行情况。解根据题意，m=5，λ=1/15，μ=1/12，ρ=λ/μ=0.8

多服务台模型[M/M/c]标准的[M/M/c]:[∞/∞/FCFS]模型系统容量有限的[M/M/c]:[N/∞/FCFS]模型有限顾客源的[M/M/c]:[∞/m/FCFS]模型

[M/M/c]:[∞/∞/FCFS]模型服务台服务台服务台顾客到达顾客离去顾客离去顾客离去队列顾客到达后，进入队列尾端；当某一个服务台空闲时，队列中的第一个顾客即到该服务台接收服务；服务完毕后随即离去。各服务台互相独立且服务速率相同，即μ1=μ2=…=μc

分析系统的服务速率与系统中的顾客数有关。当系统中的顾客数k不大于服务台个数，即1≤k≤c时，系统中的顾客全部在服务台中，这时系统的服务速率为kμ；当系统中的顾客数k＞c时，服务台中正在接受服务的顾客数仍为c个，其余顾客在队列中等待服务，这时系统的服务速率为cμ。

则当ρ＜1时系统才不会排成无限长的队列

状态转移图与状态转移方程对状态0: λP0=μP1

对状态1: λP0+2μP2=(λ+μ)P1 …………对状态c： λPc-1+cμPc+1=(λ+cμ)Pc …………对状态n λPn-1+cμPn+1=(λ+cμ)Pn ………01cn状态概率运行指标例某售票处有三个窗口，顾客到达服从Poisson流，到达速率为0.9人／分，售票时间服从负指数分布，每个窗口的平均售票速率为0.4人／分。顾客到达后排成一队，依次到空闲窗口购票。求：(1)所有窗口都空闲的概率；(2)平均队长；(3)平均等待时间及逗留时间；(4)顾客到达后必须等待的概率。解λ/μ=2.25，ρ=λ/cμ=0.75(1)所有窗口都空闲的概率，即求P0的值

(2)平均队长，即求L的值，必须先求Lq

(3)平均等待时间和平均逗留时间，即求Wq和W和的值

(4)顾客到达后必须等待，即n≥3[M/M/c]:[N/∞/FCFS]模型离开服务台服务台服务台顾客到达顾客离去顾客离去顾客离去队列分析设系统容量为N(N≥c)，当系统中的顾数n＜N时，到达的顾客就进入系统；当n=N时，到达的顾客就被拒绝。设顾客到达的速率为λ，m每个服务台服务的速率为μ，ρ=λ/cμ。由于系统不会无限止地接纳顾客，对ρ不必加以限制。

状态转移图与状态转移方程对状态0: λP0=μP1

对状态1: λP0+2μP2=(λ+μ)P1 …………对状态c： λPc-1+cμPc+1=(λ+cμ)Pc …………对状态N