文库 >教育类

排队论模型

赵倩倩_20192019-10-28原创

排队论也称随机服务系统理论。它涉及的是建立一些数学模型，藉以对随机发生的需求提供服务的系统预测其行为。现实世界中排队的现象比比皆是，如到商店购货、轮船进港、病人就诊、机器等待修理等等。排队的内容虽然不同，但有如下共同特征：

 有请求服务的人或物，如候诊的病人、请求着陆的飞机等，我们将此称为“顾客”。

 有为顾客提供服务的人或物，如医生、飞机跑道等，我们称此为“服务员”。由顾客和服务员就组成服务系统。

 顾客随机地一个一个（或者一批一批）来到服务系统，每位顾客需要服务的时间不一定是确定的，服务过程的这种随机性造成某个阶段顾客排长队，而某些时候服务员又空闲无事。

排队论主要是对服务系统建立数学模型，研究诸如单位时间内服务系统能够服务的顾客的平均数、顾客平均的排队时间、排队顾客的平均数等数量规律。

一、排队论的一些基本概念

为了叙述一个给定的排队系统，必须规定系统的下列组成部分：

 输入过程

即顾客来到服务台的概率分布。排队问题首先要根据原始资料，由顾客到达的规律、作出经验分布，然后按照统计学的方法（如卡方检验法）确定服从哪种理论分布，并估计它的参数值。我们主要讨论顾客来到服务台的概率分布服从泊松分布，且顾客的达到是相互独立的、平稳的输入过程。所谓“平稳”是指分布的期望值和方差参数都不受时间的影响。

 排队规则

即顾客排队和等待的规则，排队规则一般有即时制和等待制两种。所谓即时制就是服务台被占用时顾客便随即离去；等待制就是服务台被占用时，顾客便排队等候服务。等待制服务的次序规则有先到先服务、随机服务、有优先权的先服务等，我们主要讨论先到先服务的系统。

 服务机构

服务机构可以是没有服务员的，也可以是一个或多个服务员的；可以对单独顾客进行服务，也可以对成批顾客进行服务。和输入过程一样，多数的服务时间都是随机的，且我们总是假定服务时间的分布是平稳的。若以ξ n 表示服务员为第 n 个顾客提供服务所需的时间，则服务时间所构成的序列 { ξ n } ， n=1 ， 2 ，…所服从的概率分布表达了排队系统的服务机制，一般假定，相继的服务时间ξ 1 ，ξ 2 ，……是独立同分布的，并且任意两个顾客到来的时间间隔序列 { T n } 也是独立的。

如果按服务系统的以上三个特征的各种可能情形来对服务系统进行分类，那么分类就太多了。因此，现在已被广泛采用的是按顾客相继到达时间间隔的分布、服务时间的分布和服务台的个数进行分类。

研究排队问题的目的，是研究排队系统的运行效率，估计服务质量，确定系统参数的最优值，以决定系统的结构是否合理，设计改进措施等。所以，必须确定用来判断系统运行优劣的基本数量指标，这些数量指标通常是：

 队长

指排队系统中的顾客数，它的期望值记为 L 系；排队长，指在排队系统中排队等待服务的顾客数，其期望值记为 L 队。

系统中的顾客数 = 等待服务的顾客数 + 正被服务的顾客数

所以 L 队（或 L 系）越大，说明服务效率越低。

 逗留时间

指一个顾客在排队系统中的停留时间，即顾客从进入服务系统到服务完毕的整个时间。其期望值记为 W 系。等待时间，指一个顾客在排队系统中等待服务的时间，其期望值记为 W 队。

逗留时间 = 等待时间 + 服务时间

 忙期

指从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度，即服务机构连续工作的时间长度。它关系到服务员的工作长度，即服务机构连续工作的时间长度。它关系到服务员的工作强度、忙期的长度和一个忙期中平均完成服务的顾客数，这些都是衡量服务效率的指标。

要计算以上这些指标必须知道系统状态的概率，所谓系统状态即时刻 t 时排队系统中的顾客数。如果时刻 t 时排队系统中有 n 个顾客，就说系统的状态是 n ，其概率一般用 P n (t) 表示。求 P n (t) 的方法，首先要建立含 P n (t) 关系式，因 t 为连续变量而 n 只取非负整数，所以建立的 P n (t) 的关系式一般是微分差分方程，这时要求方程的解是不容易的，有时即使求出也很难利用。因此，往往只求稳态解 P n ，求 P n 并不一定求 t →∞时的 P n (t) 极限，而只需由
=0 ，用 P n 代替 P n (t) 即可。

下面分析几个排队系统。

二、单通道等待制排队问题

对于单通道等待制排队问题主要讨论输入过程服从泊松分布，服务时间服从负指数分布，单服务台的情形。分两种模型来分析：

 标准模型

所谓标准模型是指顾客源为无限，顾客单个到来，相互独立，一定时间的到达数服从泊松分布，到达过程是平稳的，排队为单队，队长没有限制，先到先服务，各顾客的服务时间服从负指数分布，且相互独立。同时还假定顾客到达的时间间隔和服务时间是相互对立的。可以证明，顾客相继到达的时间间隔独立且为负指数分布的充要条件是输入过程服从泊松分布。

首先求出排队系统在任意时刻 t 的、状态为 n 的概率 P n (t) ，不妨假设顾客到达规律服从参数为λ的泊松分布，服务时间服从参数为μ的负指数，由此决定了 [t ， t+ △ t] 时间间隔内：

1、有 1 个顾客到达的概率为λ△ t+o( △ t) ，没有顾客到达的概率是 1- λ△ t+o( △ t) 。

2、当有顾客在接受服务时， 1 个顾客被服务完了的概率是μ△ t+o( △ t) ，没有服务完的概率是 1- μ△ t+o( △ t) 。

3、多于一个顾客到达或服务完的概率为 o( △ t) ，均可忽略。

注 1 ：因为单位时间内顾客到达数 X ～ P （λ），所以 Δ t 时间间隔内顾客到达数 Y ～ P （λΔ t ），因而在Δ t 时间间隔内有一个顾客到达的概率为： P{ Y=1 } = λΔ t · e - λΔ t = λΔ t + o( Δ t) ，没有顾客到达的概率为 P{Y=0}= e - λΔ t =1- λΔ t + o( Δ t) 。

注 2 ：由于服务时间 T ～ E （μ），故在有顾客接受服务时，一个顾客被服务完的概率为 P{T ≤ Δ t }=1 - e - μΔ t = μΔ t + o( Δ t) ，没有被服务完的概率为 1 - μΔ t + o( Δ t) 。

在 t+ △ t 时刻，系统中有 n 个顾客的状态由 t 时刻的以下状态转化而来：① t 时刻系统中有 n 个顾客，没有顾客到达且没有顾客服务完毕，其概率为： [ 1- λ△ t+o( △ t) ][ 1- μ△ t+o( △ t) ]= (1- λ△ t - μ△ t)+o( △ t) ；② t 时刻系统中有 n +1 个顾客，没有顾客到达且有一个顾客服务完毕，其概率为： [ 1- λ△ t+o( △ t) ][ μ△ t+o( △ t) ]= μ△ t+o( △ t) ；③ t 时刻系统中有 n -1 个顾客，有一个顾客到达且没有顾客服务完毕，其概率为： [ λ△ t+o( △ t) ][1- μ△ t+o( △ t) ]= λ△ t+o( △ t) ；④其他状态的概率为 o( △ t) 。

因此，在 t+ △ t 时刻，系统中有 n 个顾客的概率 P n (t+ △ t) 满足：

P n (t+ △ t)= P n (t)(1- λ△ t - μ△ t)+ P n+1 (t) μ△ t + P n-1 (t) λ△ t+o( △ t)

[P n (t+ △ t) - P n (t)]/ △ t= λ P n-1 (t)+ μ P n+1 (t)-( λ + μ )P n (t)+o( △ t)/ △ t

令△ t → 0 ，得到

n=0 时，因为

P 0 (t+ △ t)= P 0 (t)(1- λ△ t)+ P 1 (t)(1- λ△ t) μ△ t+o( △ t)

所以，有

对于稳态情形，与 t 无关，其导数为零。因此，得到差分方程

求解此差分方程

P n =( λ / μ ) n P 0

由概率的性质知
，将上式代入λ / μ <1 时可得到

P 0 =1- λ / μ

P n =(1- λ / μ )( λ / μ ) n

因为顾客到达规律服从参数为λ的泊松分布，服务时间服从参数为μ的负指数分布，其期望值就分别为λ， 1/ μ。所以λ表示单位时间内平均到达的顾客数，μ表示单位时间内能服务完的顾客数。如果令ρ = λ / μ，这时ρ就表示相同区间内顾客到达的平均数与能被服务的平均数之比，它是刻画服务效率和服务机构利用程度的重要标志，称ρ为服务强度。上面在ρ <1 的条件下得到了稳定状态下的概率 P n ， n=0 ， 1 ， 2 ，…。其实，如果ρ >1 ，可以证明排队长度将是无限增加的，即使ρ =1 的情况下， P 0 (t) 也是随时间而变化的，系统达不到稳定状态。因此，这里只讨论ρ <1 时情况，从上面的推导知

P n =(1- ρ ) ρ n n=0,1,2, …

下面计算出系统的运行指标

可以证明，顾客在系统中逗留时间服从参数为的负指数分布。因此，有

W 系 =1/( μ - λ )

W 队 =W 系 -

由以上结论可以看出，各指标之间有如下关系：

L 系 = λ W 系； L 队 = λ W 队

W 系 =W 队 +1/ μ , L 系 =L 队 + λ / μ

在指标的计算过程中，一般只要计算其中一个，其它的指标便可随之导出。

例 1 病人候诊问题某单位医院的一个科室有一位医生值班，经长期观察，每小时平均有 4 个病人，医生每小时平均可诊 5 个病人，病人的到来服从泊松分布，医生的诊病时间服从负指数分布。试分析该科室的工作状况。如果满足 99% 以上的病人有座，此科室至少应设多少个座位？如果该单位每天 24h 上班，病人看病 1h 因耽误工作单位要损失 30 元，这样单位平均每天损失多少元？如果该科室提高看病速度，每小时平均可诊 6 个病人，单位每天可减少损失多多少？可减少多少个座位？

解由题意知λ =4 ，μ =5 ，ρ =4/5 ，ρ =4/5=0.8 < 1 ，从而排队系统的稳态概率为：

P n =0.2 × 0 .8 n n=0 ， 1 ， 2 …

该科室平均有病人数为：

L 系 = ρ / （ 1- ρ） =0.8/ （ 1-0.8 ） =4 （人）

该科室内排队候诊病人的平均数为：

L 队 =L 系 - λ / μ =4-0.8=3.2 （人）

看一次病平均所需的时间为：

W 系 =L 系 / λ =4/4=1h

排队等候看病的平均时间为：

W 队 = W 系 -1/ μ =1-1/5=0.8h

为满足 99% 以上的病人有座，设科室应设 m 个座位，则 m 应满足：

P { 医务室病人数 ≤ m} ≥ 0.99

所以该科室至少应设 20 个座位。

如果该单位 24h 上班，则每天平均有病人 24 × 4=96 人，病人看病所花去的总时间为 96 × 1=96 h 。因看病平均每天损失 30 × 96=2880 元。

如果医生每小时可诊 6 个病人，ρ =2/3 ，则

L 系 =2 （人）， L 队 =4/3 （人）

W 系 =0.5h ， W 队 =1/3h

这样单位每天的损失费为 96 × 0.5 × 30=1440 元，因而单位每天平均可减少损失 2880-1440=1440 元，这时为保证 99% 以上的病人有座，应设座位数 m ≥ ln0.01/ln(2/3)-1=11 个，比原来减少了 9 个。

下面举一个与决策有关的排队问题。

例 2 修理工录用问题某工厂平均每天有一台机器发生故障而需要修理，机器的故障数服从泊松分布。修理一台机器平均花费 20 元。现有技术水平不同的修理工人 A 和 B ， A 种修理工平均每天能修理 1.2 台机器，每天工资 3 元； B 种修理工平均每天能修理 1.5 台机器，每天工资 5 元，两种修理工修理机器的时间为负指数分布。问工厂录用哪种工人较合算？

解用 N 表示每天发生故障机器的平均数，包括正在修理和等待修理的机器数，即等于排队 L 系， C 1 和 C 2 分别表示修理一台机器的费用和工人的工资，则工厂每天平均损失费用为：

R=NC 1 +NC 2

① 若录用 A 种修理工，据题意知λ =1 ，μ A =0.2 ，ρ A = λ / μ A =5/6 ， L 系 A = ρ A /(1- ρ A )=5 台，则若录用 A 种修理工，工厂每天平均损失费用为：

R A =5 × 20+3=103 元

② 若录用 B 种修理工，据题意知λ =1 ，μ B =1.5 ，ρ b =2/3 ， L 系 B =2 台，则若录用 B 种修理工，工厂每天平均损失费用为：

R B =2 × 20+3=43 元

比较可知，工厂录用 B 种修理工较为合算。如果计入机器停工损失费用，这一选择更为上算。

 系统容量有限的模型

因为是单服务台，设排队系统的容量为 N ，即是排队等待的顾客最多为 N-1 ，在某时刻一顾客到达时，如系统中已有 N 个顾客，那么这个顾客就被拒绝进入系统。在研究系统中有 n 个顾客的概率 P n (t) 时，和标准模型研究方法相同，当 n=N 时有