排队论在实际当中的应用.docx
《排队论在实际当中的应用.docx》由会员分享，可在线阅读，更多相关《排队论在实际当中的应用.docx（25页珍藏版）》请在冰点文库上搜索。
排队论在实际当中的应用
第一章排队论问题的基本理论知识
排队是日常生活中经常遇到的现象，本章将介绍排队论的一些基本知识和常见的排队论的模型，使我们对排队论有一个基本的认识。
1.1预备知识
下图是排队过程的一般模型：
各个顾客由顾客源（总体）出发，到达服务机构（服
务台、服务员）前排队等候接受服务，服务完成后离开。
我们说的排队系统就是图中
虚线所包括的部分
排队系统示意图
一般的排队系统都有三个基本组成部分：
输入过程；排队规则；服务机构。
1•输入过程
输入过程考察的是顾客到达服务系统的规律。
可以用一定时间内顾客到达数或前后两个顾客相继到达的间隔时间来描述，一般分为确定型和随机型两种。
对于随机型的情形，要知道单位时间内的顾客到达数或到达的间隔时间的概率分布。
2.排队规则
排队规则分为等待制、损失制和混合制三种。
当顾客到达时，所有服务机构都被占用，贝U顾客排队等候，即为等待制。
在等待制中，为顾客进行服务的次序可以是先到先服务，或后到先服务，或是随机服务和有优先权服务。
如果顾客来到后看到服务机构没有空闲立即离去，则为损失制。
有些系统因留给顾客排队等待的空间有限，因此超过所能容纳人数的顾客必须离开系统，这种排队规则就是混合制。
3.服务机构
可以是一个或多个服务台。
服务时间一般也分成确定型和随机型两种。
但大多数情形服务时间是随机型的。
对于随机型的服务时间，需要知道它的概率分布。
1.2模型理论分析
1.2.1模型分类
排队模型的表示：
X/Y/Z/A/B/C
X—顾客相继到达的间隔时间的分布；
丫一服务时间的分布；
M—负指数分布、D—确定型、Ek—k阶爱尔朗分布。
Z—服务台个数；
A—系统容量限制（默认为％）；
B—顾客源数目（默认为％）；
C—服务规则（默认为先到先服务FCFS）。
1.2.2模型求解
一个实际问题作为排队问题求解时，只有顾客到达的间隔时间分布和服务时间的分布须要实测的数据来确定，其他的因素都是在问题提出时给定的。
并且必须确定用以判断系统运行优劣的基本数量指标，解排队问题就是首先求出这些数量指标的概率分布或特征值。
这些指标通常是：
（1）队长：
系统中排队等待服务和正在服务的顾客总数，其期望值记为Ls；
排队长（队列长）：
系统中排队等待服务的顾客数，其期望值记为Lg；
［系统中顾客数］=［在队列中等待服务的顾客数田正被服务的顾客数］
（2）逗留时间：
一个顾客在系统中停留时间，包括等待时间和服务时间，其其期望值记为Ws；
等待时间：
一个顾客在系统中排队等待时间，其期望值记为Wg；
［逗留时间］=［等待时间］+［服务时间］
（3）忙期：
从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度；系统状态：
即指系统中的顾客数；
状态概率：
用Pnt表示，即在t时刻系统中有n个顾客的概率；
要解决排队问题，首先要确定排队系统的到达间隔时间分布与服务时间分布。
要研究到达间隔时间分布与服务时间分布需要首先根据现有系统原始资料统计出它们的经验分布，然后与理论分布拟合，若能对应，我们就可以得出上述的分布情况。
1经验分布
经验分布是对排队系统的某些时间参数根据经验数据进行的统计分析，并依据统计分析结果假设其统计样本的总体分布，选择合适的检验方法进行检验，当通过检验时，我们认为时间参数的经验数据服从该假设分布。
2、泊松分布
下面我们在一定的假设条件下，推出顾客的到达过程就是一个泊松过程。
若设Nt表示在时间区间［0,t）内到达的顾客数（t>0），Pn以2表示在时间区
间ti,t2（t2>t1）内有n（>0）个顾客到达的概率，即
Rti,t2PNt2Ntin（t2>t1，n>0）
当Pnti,t2符合于下述三个条件时，我们说顾客到达过程就是泊松过程。
（1）再不相重叠的的时间区间内顾客到达数是相互独立的。
（2）对于足够小的△t，在时间区间［t，t+t）内有1个顾客到达的概率为
P1t,tttt（入>0是常数，称为概率强度）。
（3）对充分小的△t,在时间区间［t,t+△t）内有2个或2个以上顾客到达的
概率是△t一高阶无穷小，即
Pnt,ttt
n2
为了求Pnt，即R0,t，需要研究它在时刻t到t+△t时刻的改变量，也就
是要建立Rt的微分方程。
就可以得到：
n
Rt丄Itt>0，n=0,1,2,…
n!
负指数分布
设T为时间间隔，分布函数为FttPTt，即：
FttPTto此概率等价于在［0,t）区间内至少有1个顾客到达的概率。
没有顾客到达的概率为：
P0tI七，贝UFtt1P0t1I七（t>0），其概率密度函数为：
fTt吐It（t>0）
dt
由前知，入表示单位时间内顾客平均到达数，这里1/入表示顾客到达的平均间隔
时间，两者是吻合的。
下面我们再谈一下服务时间的分布：
对顾客的服务时间V,实际是系统处于忙期时两顾客相继离开系统的时间间隔，一般地也服从负指数分布，即：
fvt1ItfVtIt。
其中：
表示单位时间内能被服务完成的顾客数，即平均服务率。
1/表示一个顾
客的平均服务时间。
令一则P称为服务强度。
第二章单服务员排队模型在自动存取款机服务中的应用
2.1理论分析
1.稳态概率Pnt的计算
已知顾客到达服从参数为入的泊松过程，服务时间服从参数为卩的负指数分布
在间刻t+△t，系统中有n个顾客不外乎有下列四种情况。
情况
时刻的t顾客
区间（t,t+t）
时刻
t+t的
顾客
（t,t+t）的
概率
[0,t+t]的概
率
（略去（t））
到达
离去
A
n
X
X
n
1-入
t+（t）
1卩
t+（t）
Pn（t）（1-入
t）（1-1t）
B
n+1
X
V
n
1-入
t+（t）
卩t+（t）
Pn+1（t）（1-入
t）（1t）
C
n-1
V
X
n
入t+（t）
1-[1
t+（t）
Pn-1（t）（入
t）（1-1t）
D
n
V
V
n
入t+（t）
1t+（t）
Pn（t）（入
t）（1t）
由于这四种情况是互不相容的，所以Pn（t+△t）应是这四项之和，将所有的高阶无
穷小合并，则有：
PnttP^t1ttPmttRittt
令厶t-0,得关于Pn（t）的微分差分方程：
dt
Pi1tPnit
dPnt
当n=0时，只有表中的（A）、（B）两种情况。
F0ttF01tPt1tt
稳态时，Pn（t）与时间无关，可以写成Pn,它对时间的导数为0,所以由⑴、⑵
两式得：
'Pn1Pn1Pn。
（3）
Y
PoR0（4）
上式即为关于Pn的差分方程。
由此可得该排队系统的状态转移图:
这种系统状态（n）随时间变化的过程就是生灭过程，它可以描述细菌的生灭过程
n
得到：
Pn-RnR（5）
-1（否则排队无限远，无法服务完）
P01
Pn1
上式就是系统稳态概率，以它为基础可以算出系统的运行指标
2.系统的运行指标计算
（1）系统中的平均顾客数（队长期望值Ls）:
⑵队列中等待的平均顾客数Lq（队列长期望值）：
（8）
2
Lqn1Pnn11nLs
n1n11
（3）顾客在系统中的平均逗留时间Ws
Ws
（4）顾客在队列中的等待时间的期望值Wq:
111
WqWsLqW
3.系统的忙期与闲期：
系统处于空闲状态的概率：
Po1
系统处于繁忙状态的概率：
PN01P0
2.2实例
2.2.1问题提出与模型说明
问题提出
顾客排队等待接受服务，在任何一个服务系统中都是不可避免的。
在存取款机排队等待取钱或存钱的排队问题也非常严重，为此，这里拟用排队论的理论和方法，建立评价指标，通过实例来探究如何提高工作效率？
如何使系统更加优化？
模型说明
某街道口只有一个自动存取款机，从而该种情况是单列单服务台的情况，即为
M/M/1模型的情况。
2.2.2调查方法及数据处理
调查内容
（1）顾客到达时间。
（2）服务时间。
调查方法
顾客到达的频率与时间段有关，一般在9：
00—10:
30和下午2：
3O-4：
00顾客到达率比其它的时间高。
我们把时间分成两段，考虑08:
00—9：
00、9：
00-1O00的情况，分别代表了一般情况和繁忙时的情况。
（1服务时间：
顾客开始用自动存取款机到服务完成。
（2顾客到达时间：
顾客进入排队系统排队。
以上两项调查，抽样的时间均是分散的、随机的。
不可连续和集中抽样。
具体数据如下：
其中，顾客编号i，到达时间T，服务时间S，到达间隔ti，排队等待时间Wi
表108:
00—9：
00的统计
1
2
3
4
5
6
7
8
9
10
11
12
Ti
0
2
8
12
19
25
29
34
42
49
54
60
S
3
2
5
7
3
1
6
2
4
2
9
4
ti
2
3
4
7
6
4
5
8
7
5
6
wi
0
1
0
1
1
0
0
1
0
0
0
3
表209:
00—10：
00的统计
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
10
Ti
0
2
6
9
11
15
19
22
28
36
41
45
48
50
56
60
Si
3
2
4
7
2
3
3
2
5
1
6
5
4
3
2
5
ti
2
4
3
3
4
4
3
6
8
5
4
3
2
6
4
wi
0
1
0
2
6
5
4
4
0
0
0
2
4
6
3
1
2.2.3模型求解
1、根据表1计算得：
平均时间间隔为60115.45分钟「人
平均到达率为1260=0.2人「分钟
平均服务时间为4812=4.00分钟；人
平均服务率为1248=0.25人j分钟
2、根据表2计算得：
平均时间间隔为60173.53分钟「人
平均到达率为1660=0.27人.「分钟
平均服务时间为5716=3.56分钟；人
平均服务率为1657=0.25人「分钟
把以上两表结合起来为表3,分析服务时间的分布规律，求出均值和方差。
表3服务时间和频数
服务时间X
1
2
3
4
5
6
7
9
频率P
2
7
6
4
4
2
2
1
服务时间的期望值为:
XXp2227364454627291283.82
服务率期望值：
2822273644546272910.26
2.2.4讨论
理论上讲，顾客到达会形成泊松流，因为：
（1）在不相重叠的时间内顾客到达数是相互独立的，即无后效性；
（2）对于充分小的时间区间内有一个顾客到达的概率与时刻无关，而与区问长成正比；在我们把时问段分开之后来分析，这一点也是满足的；（3）
对于充分小的时间区间，有2个或2个以上顾客到达的概率极小。
顾客到达满足以上三个条件，形成泊松流；所以顾客到达率服从负指数分布。
而服务时问可看作服从正态分布。
然而在统计数据比较少的情况下，并不能得出一一般规律，来精确的算出参数（到达率）和（服务率）。
本文对此问题只做简单的分析。
从表1中可以看出，在8：
00—9：
00时间区问内，有12个顾客到达，其中有5个顾客必须等待，平均等待Wq1111+3120.58分钟。
而在表2中可以得
出，在9：
00—10：
00时间区间内，有16个顾客到达，有11个顾客必须等待，平均等待时间：
Wq12654+4+2+4+6+3+1162.375分钟。
根据以上分析，在8：
00—9：
00时间区间内，顾客平均到达率0.2人「分钟，平均
服务率是0.25人:
分钟，在9：
00—10:
00时问区问内分别为0.27人，分钟和
0.28人，分钟。
可以看出，平均服务律是高于平均到达率的。
但是，通过表3的数据分
析，在8：
00—10:
OO寸间区间内平均服务率为0.26人•分钟，由于表3中的数据量比较大，所以更具有代表性。
如果这样分析，平均服务率就小于9：
00—10:
O的顾客平均
到达率0.27,这样就会使排队越来越长而直到高峰期过后才能得到缓解。
我们认为在这个系统中，当平均等待时间超过1分钟，系统被视为效率低下，而低于1分钟被视为系统有闲置。
通过以上分析，在9:
00—10:
00时间区间内，等待问题比较严重，而在8;00—9:
00系统有闲置现象。
现实中，合理的把等待时间控制在1,1内很难
（为很小的数）。
2.3M\M\1模型中的最优服务率问题
已知有设进入系统的顾客单位时间带来的损失为d,单位时间服务台每服务一位
顾客的服务成本为C2,则单位时间总费用的期望值为：
C（）c1L（）c2c1c2
最优服务率随着进入系统的顾客数和损失费G的增加而增加，随着服务成本
C2的增加而减小
某生产厂家有多台机器，每台机器连续运转的时间服从指数分布，平均为1小时,每台故障机器的损失费为3200元/小时.有1个维修工人，每次维修时间服从指数分布，每台故障机器的修理费用为100元/小时,求最优的每台机器维修时间。
由题意知：
最优服务率为：
5（台/小时）
G!
3200
\c212100
即最优的机器维修时间为：
11
0.2小时12分钟
5
第三章中式快餐店排队系统的优化
3.1理论分析
当系统容量最大为N时，排队系统中多于N个的顾客将被拒绝。
当N=1时，即为瞬时制；N—X时，即为容量无限制的情况。
现在研究系统中有n个顾客的概率Pnt.对于F0t,前面的式子仍然成立，当
n=1,2,…N-1时，也仍能成立。
但当n=N时，有下面两种情况:
情况
时刻t
的顾客
区间[t,t+△t]
时刻t+△t
的顾客数
概率
A
N
无离去（冃疋不到达）
N
PN（t）•（1-小t）
B
N-1
一人到达（无离去）
N
PN-1（t）•入△t
PN（tt）PN（t）（1t）Fn1（t）t
其状态转移图为
N-1
在稳态情况下有:
Pn1
P）
Pn1
Pn
P
（
Pn
0
）Pn
0
P0
解得：
Pn
1
1
1
1
F面计算其运行指标:
（1）平均队长Ls：
Ls
Pn
（pM1,n（N
1
1）
（2）队列长（期望值）：
Lq
（n
n1
1）pn
Ls（1F0）
当研究顾客在系统平均逗留时间和在队列中平均等待时间，要注意平均到达率
是在系统中有空时的平均到达率,
当系统已满是则到达率为0,因此可以验证:
有效到
达率
（1F0）。
（3）
顾客逗留时间
（期望值）
LsLq1
（1P0）（1Pn）
（4）
顾客等待时间
（期望值）
WqWs
3.2
实例
3.2.1
问题提出与模型分析
问题提出
随着经济水平的提高，外出用餐的人越来越多，由于服务生产与消费的同步性、服务的不可储藏性，以及顾客到达的随机性，让顾客进行排队等待是不可避免的。
文中以学校附近一个中式快餐店为例，针对其周末晚上人满为患的现象并结合工作日的客流状况对其排队系统进行研究，进而提出优化策略。
模型分析
本文中小型饭店的排队模型是单队单服务台模型，即为M/M/1模型。
由于快餐店容
量有限为7桌，所以其排队模型M/M/1/K/FCFS（K=7）,为单服务台模型：
顾客的相继到达时间服从参数为的的负指数分布（顾客到达过程为Poisson流），服务时间服从参数
为卩的负指数分布，服务台数为1，系统空间为K,客源容量无限，实行先到先服务的排队规则。
3.2.2数据调查与模型求解
调查方法：
对该中式快餐店客流量进行连续一周人工调查统计，由于其主要客源是学生，所以
分别调查周末和工作日两种情况下的客流量变化。
对每晚（客流高峰期）两小时的顾客数进行调查记录。
数据处理：
根据调查数据可以得出：
平均到达率周末3人•'小时工作日=2人j小时
根据统计服务员对每位顾客的服务时间可得该中式快餐店的平均服务率为：
=4人.'小时
通过计算可以得出：
1、周末的服务指标
、3
服务强度=一=-二0.78
4
134
没有顾客的概率F0务0.2778
134
2、工作日的服务指标
3.2.3讨论
一般情况下，顾客等待10—15分钟是可以忍耐的，上述情况下顾客在周末的等待时间为29.4分钟，这很容易造成顾客的不满。
下面我们将从两个角度对该快餐店排队系统进行优化：
（1）服务效率的提高
中式饭店的服务流程包含很多细节，内容也非常广泛。
如果我们认真对其流程进行调查研究，找出服务的潜在失败点和等待点并着手进行流程优化设计，就能大大提高服务效率。
通过观察并进行对比发现该快餐店服务效率4存在问题，仍可提高。
该饭
店也通过引进标准化设备并对服务人员进行培训以实行标准化流程的规范操作，带来
效率和品质的提升。
服务效率的提高必然会使顾客排队等待的时间降低，这里不再作定量的分析。
（2）在忙期适当的增加桌子
这也是排队系统的常规优化方案设计。
在上例的分析中我们看到在周末排队等候的队列较长，等待时间也较长，这不但会使顾客产生不满，而且一些顾客由于不愿等待如此长的时间而离开，从而使饭店蒙受损失，适当的增加桌子会使队长和等待时间都有所增加。
第四章排队论在门诊注射室管理中的应用
4.1理论分析
标准的［M/M/C］模型与标准的［M/M/1］模型的各特征规定相同，另外，各服务台工作是相互独立且平均服务率相同，即卩仁卩2=卩3=・・=卩c=卩，于是整个服务机构的平均服务率为：
c^（n>c时），n讥n—，只有当一1时，才不会形成无限队列
cc
从下图的队列图，分析系统中的状态转移关系，状态转移图见下图
由上图知，当nWc时，顾客被服务离去的速率为n^,当n>c时，为c^，故可得
差分方程：
这里：
P1,p<1
i0
利用递推法解该差分方程可求得状态概率为:
系统的运行指标为:
Wq
Lq
4.2实例
4.2.1问题提出
排队论，就是对排队现象进行数学研究的理论，也称随机服务理论，是运筹学中一个独立的分支。
作为一种工具或方法，已在许多行业的管理领域包括医院的管理领域应用。
门诊注射室的服务工作，是一种随机性服务，即患者的到达时间、到达数量、注射所用时间，都是一种随机现象。
这种服务以什么指标才能比较客观地表示、反映注射室的工作质、工作效率？
如何评价注射室的人员、设备配备的合理性？
为此，笔者拟用排队论的理论和方法，建立评价指标，为寻求既不使患者排队成龙，又不浪费医院人力物力的最优方案，提供科学依据，使注射室管理从经验管理转为科学管理。
4.2.2调查方法及数据处理
调查内容：
（1）单位时间内到达的患者数。
（2）服务时间。
调查方法
（1）服务时间：
从某患者进人注射室开始记时，到该患者接受注射后走出注射室止。
共随机记录了593人次的服务时间。
⑵单位时间内到达的患者数：
以5分钟为一个时间单位，任意选取若干个时间单位，记录每个5分钟到达的患者数。
共随机抽取了168个时间单位。
以上两项调查，抽样的时间均是分散的、随机的，不可连续和集中抽样。
调查资料经统计处理后如下：
1、单位时间内到达的患者数
单位时间（5分钟）内到达的患者数（人）
频数
概率
0
6
0.04
1
15
0.09
2
30
0.18
3
34
0.20
4
43
0.26
5
16
0.09
6
10
0.06
7
9
0.05
8
4
0.02
9
1
0.01
合计
168
1.00
2、服务时间
服务时间（分钟）
频数
概率
1:
170
0.29
2:
203
0.34
3:
152
0.26
4：
56
0.09
5:
6
0.01
6:
6
0.01
合计
593
1.00
经曲线拟合检验，服务时间的概率分布服从负指数分布，单位时间内到达患者数的概率分布服从泊松分布。
从而求出排队系统的两个重要参数，患者平均到达率和平均服务率。
又因注射室内有两个注射凳一服务台C=2故符合排队论中M/M/C型排队模型。
应用M/M/C型计算公式计算各项指标
4.2.3模型求解
（1基本参数
1、患者平均到达率0.71人「分钟
2、平均服务率=0.45人:
分钟
（2）注射室运行状态指标（C=2）
说明注射室有79%勺时间是忙期，21%勺时间是空闲的。
队列长：
等待注射的患者数。
队长：
队列长+正在接受注射的患者数。
期望值LsLqC2.681.584.26
平均等待时间
4、平均逗留时间
1WsWq3.772.225.99分钟
现假设只配备一名护士负责注射,即C=1,那么服务强度=—=24=1.58。
在排队
0.45
论中，当1时，说明系统处于超负荷状态，将会持续出现排队成龙现象。
故此时不
可取的。
4.2.4讨论
1、排队论的应用，可以为合理使用人力、物力提供客观依据。
由下表可见注射室现有的服务台C=2时，注射室有71%勺时间被利用，在等注射的人数为2.68个，等待时间为3.77分钟。
如果服务台增为3个时，注射室将53%勺时间被利用，排队等待的平均人数小于1,平均等待时间不足半分钟。
若服务台增为4个，排队人数和排队时间几乎为0,但是注射室被利用的时间只有39%,61%勺时间处于空闲,造成
人力浪费。
因此，设两个服务台，基本合理,若条件允许，设三个服务台，将是最佳选择。
指标名称
服务台个数（C）
2
3
4
服务强度
0.79
0.53
0.39
空闲概率P0
0.12
0.19
0.20
等待人数Lq
2.68
0.31
0.05
等待时间Wq
3.77
0.44
0.07
升级会员 