11. 排队论
11.1基本概念
排队现象是指到达服务机构的顾客数量超过服务机构提供服务的容量,也就是说顾客不能够立即得到服务而产生的等待现象。顾客可以是人,也可以是物,比如说,在银行营业部办理存取款的储户,在汽车修理厂等待修理的车辆,在流水线上等待下一到工序加工的半成品,机场厂上空等待降落的飞机,以及等待服务器处理的网页等,都被认为是顾客。服务机构可以是个人,像理发员和美容师,也可以是若干人,像医院的手术小组。服务机构也还可以是包装糖果的机器,机场的跑道,十字路口的红绿灯,以及提供网页查询的服务器等等。
因为顾客到达,服务时间具有不确定性,排队系统又称随机服务系统,它的基本结构如图11所示:
1.
11
图1.
11给出了一些现实排队系统的例子。
表1.
表11.1: 排队系统应用
商业服务理发店,银行柜台,机场办理登机手续的柜台,快餐店的点餐柜台
运输行业城市道路的红绿灯,等待降落或起飞的飞机,出租车
制造业待修理的机器,待加工的材料,生产流水线
社会服务法庭,医疗机构
11.1.1排队系统的特征
为了描述一个排队系统,我们需要说明输入(到达)和输出(服务)过程,及其他基本特征。表11列举了一些排队系统的到达和服务过程。
2.
表11.2: 排队系统举例
)1(到达过程
通常,我们假设顾客的相继到达间隔时间是相互独立并且都具有相同概率分布。在许多
(Poisson流,或指数分布。顾客源可能是有限实际情况中,顾客的相继到达间隔是服从泊松)
的,也可能是无限的。顾客到来方式可能是一个接一个的,也可能是批量的。比如,到达机场海关的旅行团就是成批顾客。
一般来说,我们假设到达过程不受排队系统中顾客数量的影响。以银行为例,无论银行内有3位顾客还是300位顾客,顾客来到银行的到达过程是不会受到影响的。但是在两种情况下到达过程与排队系统中的顾客数量相关。第一种情况发生在顾客源是有限的系统,比如某工厂共有五台机床,若在维修部中已有两台机床,接下来到达维修部的最大量是三台。另一种情况是当顾客到达排队系统时,如果服务机构的设施都被占用,顾客可能耐心等待,也可能选择离开。比如,当一家航空公司的电话订票中心出现排队时,如果顾客等待时间太长,他就可能挂断电话。顾客就会选择另外一家航空公司。
)2(服务过程
为了描述排队系统的服务过程,我们需要确定服务时间的概率分布。在大多数情况下,服务时间是独立于排队系统中的顾客数量,即服务机构不会因为顾客数量增多而加快服务进度。不同服务机构提供的服务时间之间是相互独立,并都服从同一种概率分布,而且也独立于顾客相继到达间隔时间。服务时间一般分为确定型的和随机型的。在大多数情形下,服务时间的是随机型的,排队论主要研究随机型的服务时间。对于随机型的服务时间,我们必须知道它的概率分布,通常假定是指数分布。
从服务队列的安排上来说,我们将重点研究以下几种形式。从队列的数目来看,可以是单
11说明了一个服列,也可以是多列。服务机构在提供服务时,可以有一个或多个服务台。图2.
务台的排队系统:
顾客到达流顾客队列服务台
11
图2.
在有多个服务台的情形中,它们可以是并列,可以是串列,也可以是混合排列,最典型的是以下二种排队方式:
顾客到达流顾客队列服务台
11
图3.
顾客队列 服务台
图4.11
图3.11表示在排队系统中存在多个队列,且服务机构提供多个服务台的排队模型,而图4.11则表示排队系统中存在单队列,且服务机构提供多个服务台的排队模型。在日常生活中,这两种排队方式都是常见的。
)3(排队规则
服务机构确定的排队规则是排队系统中的一项重要条件,服务机构为顾客提供服务的规
则可以采用下列几种规则,即:先到先服务)(FCFS ,后到先服务)(LCFS ,随机服务)(SIRO
,和具有优先权的服务)(NPRP .
---- 先到先服务,顾客按到达排队系统的顺序接受服务,这是最普遍情况。
--- 后到先服务,卡车的卸货和乘用电梯的顾客都是后进入排队系统先接受服务的。 --- 随机服务,服务机构从等待的顾客中随机地选取其一进行服务。 --- 有优先权的服务,航空公司的金卡旅客有优先登机权。 我们将区分有限和无限等待空间。随着顾客数目的增加,排队系统的等待空间将被占满。例如在数据通信网络中,交换机每次只能传输有限量的数据,如果数据流是无穷大,就会导致系统阻塞现象。如果不断有顾客到达排队系统,服务机构必须连续提供服务。所以排队系统的服务强度反应了服务机构的繁忙程度。
11.1.2 到达和服务过程的分布
我们首先讨论排队系统到达过程的概率分布。设i t 为第i 个顾客到达排队系统的时间.对于1≥i ,定义i i i t t T -=+1为第1+i 个顾客与第i 个顾客的到达时间间隔。图5.11说明了到达间隔i T 和到达时间i t 的关系.比如,4591=-=T ,及79162=-=T .为了推导顾客到达过程的概率模型,我们假设到达间隔i T 之间是相互独立,对应于连续随机变A .如果A 的密度函数为)(t a ,那么对于足够小的t ?,概率)(t t A t P ?+≤≤近似于)(t ta ?.
? ? ?
51=t 92=t 163=t
图5.11
我们定义
λ
1
为到达间隔的平均值,则有:
?∞
=0
)(1
dt t ta λ
)1.11(
如果时间是按分钟度量的,
λ
1
就是每次到达的平均间隔分钟。而λ则表示单位时间内的到达
率,即在1分钟内的顾客的到达数。
在排队论的应用中,一个重要方面是选择到达过程的概率分布。而最常用的概率分布是指数分布。具有参数为λ的指数分布的密度函数为：
??
?<≥=-0
)(t t e t a t
λλ )2.11( 那么到达间隔T 服从指数分布。它的分布函数是：
??
?<≥-=-0
1)(t t e t F t
λ )3.11( 我们可以证明到达间隔T 的期望值,方差,和标准差分别为：
λ1
][=
T E ，2
1
][λ=
T Var ，λ
σ1
][=
T )4.11(
指数分布具有”无记忆性”.对于任意的0,0>>y x ,有:
)()()()|()
(y T P e e
e x T P y x T P x T y x T P y x y x >===>+>=>+>--+-λλλ
比如,3=y ,对于3=x ,2=x ,和1=x
λ3)1|4()2|5()3|6(-=>>=>>=>>e T T P T T P T T P
指数分布具的无记忆性说明了如果我们希望预测下一位顾客到达时间的概率分布,那么,它是
与上一位到达时间无关。
如果相继到达间隔服从指数分布,发生在任何一段时间内的到达数服从泊松分布。离散随机变量N 服从参数为λ的泊松分布是指对于,...2,1,0=n ,有:
λ
λ-==e n n N P n !
)()( ,....2,1,0=n )5.11(
设)(t N 表示在时间区间),[t T T +内的到达数)0(>t ，那么,随机变量
)()()(t N t s N t N -+=服从下述泊松分布:
t
n e n t n t N P λλ-==!
)())(( ,....2,1,0=n )6.11(
随机变量)(t N 的均值和方差分别为：
t t N E λ=)]([；t t N Var λ=)]([ )7.11(
式)7.11(表明泊松分布的一个重要特征是期望值等于方差。
我们可利用Excel 来计算指数分布和泊松分布的概率。设具有参数λ指数分布的随机变量,利用Excel 的EXPONDIST 函数,有:
),,(TRUE LAMBDA x EXPONDIST =返回随机变量小于等于x 的概率; ),,(TRUE LAMBDA x EXPONDIST =返回随机变量密度函数值
比如,到达间隔服从均值为5的指数分布。那么2.0=λ,),2.0,10(TRUE EXPONDIST
=给出到达间隔小于等于10分钟的概率为8646647.0。函数),2.0,10(FALSE EXPONDIST
=给出10=x 和2.0=λ的指数密度函数的高度等于0726345.0,参见表3.11。
设泊松分布的随机变量的均值为M ,利用Excel 的POISSON 函数,有下述表达式:
),,(TRUE M x POISSON =返回随机变量的均值M 小于等于x 的概率 ),,(FALSE M x POISSON =返回随机变量的均值M 等于x 的概率
比如,如果顾客平均到达率为30/每小时,并服从泊松分布,那么函数
),30,30(TRUE POISSON =给出在一小时内到达排队系统的顾客小于等于30的概率为5483515.0。函数),30,30(FALSE POISSON =给出在一小时内到达排队系统的顾客正好
等于30的概率为0270671.0,参见表3.11。
表11.3: 指数和泊松分布
接下来,我们再讨论排队系统的服务过程的概率模型。我们假设不同顾客的服务时间是
相互独立的随即变量。设每位顾客服务时间随即变量为S ,密度函数为)(t s ,设μ
1
为每位顾客
的平均服务时间,那么
?∞
+=0
)(1
dt t ts μ
)8.11(
变量
μ
1
表示每为顾客的平均服务时间,所以μ每小时服务的顾客数。这样,我们也称μ为服
务率。比如说,2=μ意味着排队系统每小时可服务2位顾客每位顾客的平均服务时间为
2
1
小时。如果我们能够用指数分布来描述服务时间的随机性,我们就能直接确定顾客的剩余服务时间,而不需要知道顾客在排队系统中已经接受服务的时间。如果服务时间服从指数分布,它的密度函数为t e t s μμ-=)(,每位顾客的平均服务时间为μ
1
。
11.1.3排队系统的分类
根据排队系统的基本特征,Kendall )1951
(对排队系统设计出一个简便分类方法。任何一类排队系统都可用下述标记来表示
F E D C B A ///// )9.11(
第一个字符A 表示到达过程的基本特性
--M 到达时间间隔相互独立,服从指数分布 --D 到达时间间隔相互独立,确定型
--G 到达时间间隔相互独立,服从一般概率分布
第二个字符B 说明服务过程的基本特性
--M 服务时间相互独立,服从指数分布 --D 服务时间间隔相互独立,确定型
--G 服务时间间隔相互独立,服从一般概率分布
第三个字符C 表示排队系统中的服务台数。第四个字符D 代表排队规则:
--FCFS 先到先服务 --LCFS 后到先服务 --SIRO 随机服务 --GD 其他排队规则
第五个字符E 说明排队系统的最大容量,即排队系统能够接受顾客的最大值(排队顾客加接收服务的顾客)。第六个字符F 说明了顾客源的总体大小。那么,∞∞///1//FCFS M M 表示到达时间间隔服从指数分布,服务时间服从指数分布,单服务台,先到先服务,无限容量和无限顾客源的排队模型。∞∞///3//SIRO G M 表示到达时间间隔为指数分布,服务时间为一般概率分布,有三个平行服务台,随机服务,无限容量和无限顾客源的排队模型。
11.1.4排队论研究的内容和目的
排队论研究的内容主要有：数量指标：队长、等待时间和逗留时间的分布、忙期和闲期的分布、服务设备利用率、顾客损失率等；排队系统优化问题：系统最优设计问题和动态控制问题。而研究目是利用排队系统数量指标的概率规律，设计排队系统,使系统达到成本最小的最优设计和最优控制,或到达以最小费用实现系统的最大效益。
排队系统的数量指标是为了判断排队系统运行的效率,评估服务质量,确定系统参数的最理想值。在排队论中,用于评估排队系统的主要运行指标有:
)1(排队时间和逗留时间的分布
排队时间: 顾客在排队系统中排队等待的时间也是随机变量,以q W 表示等待时间的平均值。
逗留时间: 顾客在排队系统中的停留时间,即排队等待时间加服务时间。以W 表示等待时间的平均值。并且: 逗留时间 = 等待时间 + 服务时间
)2(排队长和系统队长分布
排队长: 在排队系统中排队等待服务的顾客数,显然它也是随机变量。以q L 表示排队等待服务顾客数的平均值。
系统队长:在排队系统中的顾客数,即排队等待服务的顾客数加正在接受服务的顾客数。以L 表示顾客数的平均值,即排队系统的平均队长。 系统队长 = 等待服务的顾客数 + 正接受服务的顾客数
)3(服务机构忙期的分布
忙期: 服务机构连续工作的时间长度,也是随机变量。以B 表示服务机构连续工作的时间长度的平均值。
)4(工作量的分布
工作量:在排队系统中,顾客排队等待服务的时间加上正在接受服务顾客的剩余服务时间。
)5(Little 定律
Little 定律给出了系统的平均队长L 和平均逗留时间W 之间的重要关系,假设系统的容
量是足够大,那么:
W L λ= 由于顾客到达排队系统的时间间隔和服务机构的服务时间都是随机变量,上述排队指标也都是随即变量。所以说,为了计算这些指标,我们需要知道它们的概率分布。我们将会看到,这些概率分布与排队系统的状态概率分布,即:排队系统队长的概率分布直接相关。如果在排队系统中有n 个顾客,则系统的状态就是n 。状态概率一般是随时刻t 而变化,若以)(t P n 表示在时刻t 系统状态为n 的概率。通常,我们用它的极限值:
n n t P t P =∞
→)(lim
作为系统状态为n 的概率。我们称极限值n P 为系统状态到达稳态的概率,在实际应用中,对于大多数排队问题,系统会很快趋于稳定。
11.2 ∞∞///1//FCFS M M 排队模型
在本节中,我们将讨论到达排队系统的时间间隔服从指数分布,服务时间服从指数分布,单服务台,服务规则是单队列,先到先服务,无限系统容量和顾客源的排队系统,根据Kendall 记号,我们将它表示为∞∞///1//FCFS M M 模型。在下面讨论中,我们定义系统的输入和输出参数分别为:
--λ 单位时间内到达排队系统的平均数;
--μ排队系统在单位时间内的平均服务数 那么,
λ
1
就表示平均到达时间间隔,
μ
1
表示平均服务时间。同时,我们还假设顾客到达排队系
统的时间间隔和服务时间两个随机变量是相互独立的。由于到达时间间隔和服务时间的随机性,系统队长,即排队系统中的顾客数,也具有随机性。我们也称排队系统的系统队长为系统状态。一般来说,系统状态是与时间相关的。下面首先研究∞∞///1//FCFS M M 模型随时间变化的系统状态,然后再分析在稳态情形下系统的状态。
11.2.1依赖时间的系统状态
∞∞///1//FCFS M M 模型的到达和服务过程都服从指数分布,我们假设到达率为λ,服务率为μ。若以)(t P n 表示在时刻t 的系统状态等于n ,那么在时间区间],[t t t ?+内,系统状态的变化由顾客的到达和离开确定。我们首先计算在时间区间],[t t t ?+内,发生1位顾客到达的概率。指数分布的无记忆性告诉我们1位顾客的到达概率不依赖于系统处于状态n 的时间长短,那么在时间区间],[t t t ?+内1位顾客的到达概率为:
t t
t e dt e ?-?--=?
λλλ10
利用泰勒展开式:
)(1t o t e t ?+?-=?-λλ
所以,在时间区间],[t t t ?+内1位顾客的到达概率等于)(t o t ?+?λ。这说明在系统状态等于
n 的情况下的到达率n λ,,...3,2,1=n 等于系统的到达率λ。
为了计算在时刻t 的离去(服务)率,我们注意到如果系统状态等于0,没有顾客在接受服务,所以,在时间区间],[t t t ?+内的服务率等于0,即00=μ。如果系统状态等于1≥n ,这时只有1位顾客在接受服务。根据指数分布的无记忆性,在时间区间],[t t t ?+内1位顾客完成服
务的概率为:
tt t
t e dt e μμμ-?--=?
10
所以,对于1≥n ,μμ=n 。
根据上述结论,我们来求解排队系统在时刻t 的状态变化。在时间区间],[t t t ?+内,系统状态等于0的概率是由下述两个事件构成:
)(a 在时刻t 的系统状态为0,在时间区间],[t t t ?+内无顾客到达,则状态变化的概率
为t ?-λ1;
)(b 在时刻t 的系统状态为1,在时间区间],[t t t ?+内有1位顾客离去, 则状态变化的概
率为t ?μ;
所以系统状态为0的概率等于: :
)()()()1()(100t o t tP t P t t t P ?+?+?-=?+μλ
其中)(t o ?表示多于一个顾客到达或离去的概率,当t ?非常小时,)(t o ?是可以忽略的,即
0)
(lim
0=??→?t t o t 。
系统状态等于n 的概率可由下述四个事件构成,参见表4.11表示。
表4.11系统状态等于n 的事件构成情况 方式 时刻t 的状态 概率
],[t t t ?+内发生的事件
发生的概率
1 n
)(t P n 无到达,无离去 )1(t ?-λ)1(t ?-μ
2 1-n )(1t P n - 到达一个,无离去 t ?λ)1(t ?-μ
3 1+n
)(1t P n + 无到达,离去一个 )1(t ?-λt ?μ
4 n
)(t P n
到达一个, 离去一个
t ?λt ?μ
在],[t t t ?+内, 系统状态等于n 的概率就表示为: =?+)(t t P n )1(t ?-λ)1(t ?-μ)(t P n t ?+λ)1(t ?-μ)(1t P n -
)1(t ?-+λt ?μ)(1t P n +t ?+λt ?μ)(t P n
对上式整理后并只考虑t ?项:
),()()())(1()()(11t o t tP t P t t tP t t P n n n n ?+?+?+-+?=?++-μμλλ...2,1=n
其中,当0→?t 时,0)(→?t o 。
整理后,有:
),()()()
()('1000t o t P t P t
t P t t P ?++-=?-?+μλ
),()()()()()
()('11t o t P t P t P t
t P t t P n n n n n ?+++-=?-?++-μμλλ
...2,1=n
其中: 当0→?t 时,0)('→?t o
那么,令0→?t ,我们得到: ),()()(10'0t P t P t P μλ+-=
),()()()()(11't P t P t P t P n n n n +-++-=μμλλ )10.11(
,...2,1=n
求解随时间t 变化的微分方程式)10.11(是非常困难的。所以我们将主要研究当排队系统状态达到极限或稳态情况下,系统的状态概率。
11.2.2极限系统状态
我们可以证明当+∞→t 时,0)('0→t P ,0)('→t P n ,及n n P t P →)(,,...2,1,0=n 。那么,根据微分方程式)10.11(,在稳态情形下的系统状态概率n P ,,...2,1,0=n 为: ,010P P μλ+-=
,)(011+-++-=n n n P P P μμλλ
...2,1=n
或 ,10P P μλ=
,11+-+=+n n n n P P P P μλμλ )11.11(
...2,1=n
显然,状态概率n P ,...2,1,0=n 还必须满足:
10
=∑∞
=n n
P
)12.11(
我们也可以从另外一个角度更加直观地推导)11.11(中的关系式.考虑
∞∞///1//F C F S M M 模型系统状态的转移情况,参见图6.11。
? ? ?
图6.11
为了方便大家理解,假设图6.11代表在只有1个理发员的理发店中顾客人数(系统状态)的变化情况。如果在理发店中只有1个顾客(状态1),那么,这种状态是从店中无顾客,然后1个顾客到达,或者店中有2个顾客,其中1个顾客接受完服务之后离去。这两种情况由图6.11中两个指向状态1的箭头所表示,一个是从状态0指向状态1的上箭头,另一个是从状态2指向状态1的下箭头。除了状态0之外,其他任何一种状态都存在两种离开该状态的可能性,比如说,状态1的上离开箭头说明从状态1向前进入状态2(从1个顾客增加到2个顾客),而下离开箭头说明从状态1,向后退回状态0(从1个顾客减少到0个顾客)。另一方面,任何一种状态都可由两种方式进入。箭头旁边还标明从一个状态到另一个状态的平均变化率,λ表示向前进入下一个状态的平均变化率,μ表示向后退回下一个状态的平均变化率。在相继到达时间间隔和服务时间都是服从指数分布的情形下,进入和离开同一个状态的可能性是完全相等的。而在非常短的时间段内,状态转换只可能发生在两个相邻的状态,例如状态2到状态3,状态5到状态4,状态6到状态7等。状态转换的概率等于变化率(λ为到达率,μ为服务率)乘以发生状态转换的时间长度:
状态 离开概率=进入概率
,10P P μλ=
1 ,2011P P P P μλμλ+=+
2
,3122P P P P μλμλ+=+ )13.11(
???? ???? ????
n
,11+-+=+n n n n P P P P μλμλ
???? ???? ????
求解式)13.11(,有:
,01P P μ
λ=
,)(022P P μ
λ=
????
,)(0P P n n μ
λ=
,...2,1=n
考虑到1)(
0=μ
λ,那么000)(P P μλ
=,所以有:
,)(0P P n n μ
λ=
,...2,1,0=n
如果令μ
λ
ρ=
,则上式可以被表示为:
,)(0P P n n ρ=
,...2,1,0=n
)14.11(
根据)12.11(我们有:
10
00
==∑∑∞
=∞
=n n n n
P P
ρ )15.11(
为了避免队列出现无限长的排队现象,我们有必要假设1<ρ,这样一来,等比序列收敛于:
ρ
ρ
-=
∑∞
=110
n n
将其带入式)15.11(左端后,得:
110
=-ρ
P 对其整理后,我们获得:
ρ-=10P
把0P 代入公式)14.11(,有:
n n P ρρ)1(-= ...2,1,0=n )16.11(
所以,公式)16.11(是∞∞///1//FCFS M M 排队系统在稳态情形下,系统状态为n 的概率计算公式。
11.2.3系统指标
我们可以利用系统状态概率公式)16.11(推导∞∞///1//FCFS M M 的其他重要数量指标的概率分布和特征值。
)(a 平均系统队长
n n n n n P n L ρρ)1(0
-==∑∑∞
=∞=
∑∑∞=∞
=-=-=0
0)1()1(n n
n n d d d d ρρρρρρρρ
2
)
1(1
)1(11)1(ρρρρρρ
ρ--=--=d d
λ
μλρρ
-=
-=
)
1( )17.11(
)(b 平均排队长
n n q P n L )1(1-=∑∞
=
∑∑∞
=∞
=-=
1
1n n
n
n P
P n
)(00
1
P P P
n n n n
n --=
∑∑∞
=∞
=
ρρ
ρ
--=
--=1)1(0P L
ρ
ρρρρ
-=
--=112
)
(2
λμμλ-= )18.11(
)(c 平均逗留时间
λ
μλ
-=
=
1
L
W )19.11( )(d 平均排队时间
)
(λμμλ
λ
-=
=
q
q L W )20.11(
11.2.4应用举例
例1.11 短信以平均每分钟240条的速度到达短信发送平台,线路的传输速度是每秒800汉字。短信长度的分布近似于期望值为176汉字的指数分布。假设短信处理中心的容量非常大,请计算下列系统指标:
)(a 系统中短信的平均数量, )(b 系统中等待发送短信的平均数量,
)(c 短信在系统中的平均逗留时间, )(d 短信在系统中等待发送的时间,
)(e 系统中等待发送短信的数量多于10条的可能性有多大?
解: 以μ表示发送短信的速率,以λ表示短信的到达速率。我们先计算发送短信的速率,因为发送一条短信平均耗时为:
短信平均长度/线路的传输速度22.0800
176
==
秒/条 所以,发送短信的速率等于:
55.422
.01
==
μ条/秒 短信的平均到达速率为:
240=λ条/分钟
460240
==
条/秒 那么,
88.055
.44
==
ρ
)(a 系统中短信的平均条数:
33.788
.0188
.0=-=
L 条
)(b 系统中等待发送短信的平均条数:
45.688
.0188.02
=-=
Q L 条 )(c 短信在系统中的平均逗留时间
83.14
33
.7==
W )(d 短信在系统中等待发送的时间
61.14
45
.6==
q W )(e 系统中等待发送短信的条数多于10条的概率可以被表示为:
1111
10
10
01111)1(1)1(11ρρρρρρ=----=--=-=∑∑∑==∞
=n n
n n n n P P
所以,系统中等待发送短信的条数多于10条的概率为:245.088.011
= 11.2.5用Excel 电子表格求解∞∞///1//FCFS M M 排队模型
例2.11 考虑首都经贸公司办公用品领取问题的管理。在正常工作时间内,公司职员可以到办公用品库房领取办公用品,根据统计,到达办公用品库房职员的平均人数是每小时25人。公司专门雇佣一个工作人员负责处理办公用品的领取,包括检查手续和发放办公用品,平均完成办理一个职员的领取时间为两分钟。检查手续和发放的方式完全是手工操作。请用Excel 电子表格计算以下指标:
)(a 库房中职员的平均人数,
)(b 库房中等待办理领取手续职员的平均人数,
)(c 职员在库房中的平均逗留时间,
)(d 职员在库房中等待办理领取手续的时间,
)(e 库房中等待职员是26人的可能性有多大?
解: 如果以小时为到达间隔和服务时间的基本单位,那么平均到达率为:25=λ,平均服务速度:30=μ。表5.11给出了关于以上五个问题的解:
)(a 库房中职员的平均人数可由电子表格的单元格10H 获得:5=L ;
)(b 库房中等待办理领取手续职员的平均人数可由电子表格的单元格13H 获得:
17.4=q L ;
)(c 职员在库房中的平均逗留时间可由电子表格的单元格11H 获得:2.0=W ; )(d 职员在库房中等待办理领取手续的时间可由电子表格的单元格14H 获
得:17.0=q W ;
)(e 库房中等待职员是26人的概率可由电子表格的单元格45D 获得:0015.026=P ;
表11.5: 办公用品管理排队系统
11.2.6 ∞∞///1//FCFS M M 排队模型的经济分析
对于∞∞///1//FCFS M M 排队系统来说,提高服务机构的服务水平能够降低顾客平均逗留时间,参见式)19.11(,从而节省顾客的等待成本;另一方面,提高服务效率会增加服务机构的成本,所以排队系统的优化目标之一是使两者成本之和为最小。我们将看到对于
∞∞///1//FCFS M M 模型,排队系统的优化问题完全等同于求解最优服务率。如果以s
C 表示服务机构服务每位顾客的平均成本,以w C 表示每位顾客在排队系统中的逗留成本,以ω表示在单位时间内排队系统的服务成本与顾客的逗留成本之和,那么:
L C C w s +=μω )21.11(
根据)17.11(,有:λ
μλ-=
L ,将其代入上式,获得:
λ
μλμμω-+=w
s C C )( )22.11(
为了求使)(μω达到最小值的μ,令
0=μ
ω
d d ,那么有:
0)(2
=--λμλ
w
s C C
求出两个最优解:
λλμs w C C +
=*1 和 λλμs
w C C -=*
2 但是为了保证排队系统能够有效地运行,必须要求λμ>,选择*
1μ为最优解,所以式)
22.11(的最优解为:
λλμs
w
C C +
=* )23.11( 接下来,我们对例2.11办公用品领取管理的排队系统进行成本分析。假设负责办理办公用品领取手续的库房管理员的工资是每小时5元,公司职员的平均工资是每小时7元。 那么,公司职员在领取办公用品的小时逗留成本为:
7=w C 元/小时
由于每个职员在领取办公用品的过程中平均需要逗留2.0小时,那么每位职员的平均排队成本为:
4.12.07=?=?W C w 元/小时
而在1小时之内,系统的逗留成本为:
35254.1=?=??λW C w 元/小时
库房管理员服务1位顾客的服务成本为:
17.030
5
==
s C 元 在1小时之内,系统的服务成本为:
53017.0=?=μs C 元/小时
所以,在1小时之内,因领取办公用品而产生的逗留成本和服务成本(都是公司的成本)之和为:
40535=+=ω元/小时 我们看到职员花费在领取办公用品的成本是相当高的,7倍于库房管理员的工资。有两种方法可以补救。第一种方法是提高服务效率,比如说,用工作效率更高的库房管理员替代,改进检查领取手续的流程,或者利用半制动化技术等;另一种方法是再增加一个库房管理员,我们将在下一节介绍这种方法。
假设公司考虑引进半制动化系统,使库房管理员的服务效率提升%100,即每小时可检查60个手续,如果半制动化系统的成本是每小时25.6元,那么系统每小时的平均成本是多少?该成本是否是最优成本?
这时,系统每小时的平均排队成本变成:
52535
1
71=??=?-?
λλμw C 元/小时 系统每小时的平均服务成本变为:
25.1125.65=+元/小时 那么系统每小时的平均排队成本加平均服务变为:
25.1625.115=+=ω元/小时 所以,引进半制动化后,排队系统每小时平均节约:
75.2325.1640=-元 根据)13.2(,最优服务率为:
λλμs
w
C C +
=*
10.572517
.07
25=?+
= 所以60=μ接近最优服务速率。
11.3 ∞∞///1//FCFS M M 排队模型的改进
由于在∞∞///1//FCFS M M 排队模型中,关于到达,服务分布,排队规则,系统容量,和顾客源的假设非常严格,现实排队问题很难满足其所有条件。接下来我们介绍几类应用广泛的排队模型,它们都是通过对∞∞///1//FCFS M M 排队模型的部分条件进行修改而得到
的,所以它们是∞∞///1//FCFS M M 排队模型的拓展。
11.3.1 ∞///1//M FCFS M M 排队模型
∞///1//M FCFS M M 排队模型是设定系统的容量是有限的,即系统只能容纳有限数量的顾客。其中,M 表示系统能够接受顾客数的上限,在这种情况下,系统中排队等待的顾客数最多为1-M 。在任何一个时刻,当某个顾客到达排队系统时发现系统中已经有M 个顾客,则这个顾客就被拒绝进入排队系统。
我们只考虑在稳态情形下,如何计算∞///1//M FCFS M M 排队系统的状态概率n P ,根据式)14.11(,有:
,)(0P P n n ρ=
M n ,...1,0= )24.11(
根据概率分布的基本特性,有:
10
=∑=M
n n
P
把式)24.11(代入上式,则有:
10
0=∑=M
n n P ρ
由于上式左端的等比数列可以被表示为:
ρρρ--=+=∑111
M M
n n
我们可以求出:
1
011+--=
M P ρρ
将上式代入式)24.11(,获得:
n
M n P ρρ
ρ1
11+--=
M n ,...2,1=
因为0P 可被改写为01
011ρρ
ρ
+--=
M P ,所以:
1
11+--=M n
n P ρ
ρ
ρ M n ,...2,1,0=
)25.11(
根据系统状态概率公式)25.11(和
11
=∑=M
n n
P
,我们可以计算出∞
///1//M FCFS M M
排队系统的主要指标:
)(a 平均系统队长
1
1
1)1(1++-+--=M M M L ρ
ρρρ
)26.11( )(b 平均排队长
)1()111(01
P L L L M q --=---
-=+ρρ
)27.11(
)(c 平均逗留时间
)
1(M P L
W -=
λ )28.11(
)(d 平均排队时间
)
1(M q
q P L W -=
λ )29.11(
表6.11计算了在领取办公用品的库房只能容纳5人的情况下,办公用品领取排队模型的主要数量指标。
表11.6: 办公用品管理排队系统(有限容量)
排队论模型 排队论也称随机服务系统理论。它涉及的是建立一些数学模型，藉以对随机发生的需求提供服务的系统预测其行为。现实世界中排队的现象比比皆是，如到商店购货、轮船进港、病人就诊、机器等待修理等等。排队的内容虽然不同，但有如下共同特征： 有请求服务的人或物，如候诊的病人、请求着陆的飞机等，我们将此称为“顾客”。 有为顾客提供服务的人或物，如医生、飞机跑道等，我们称此为“服务员”。 由顾客和服务员就组成服务系统。 顾客随机地一个一个（或者一批一批）来到服务系统，每位顾客需要服务的时间不一定是确定的，服务过程的这种随机性造成某个阶段顾客排长队，而某些时候服务员又空闲无事。 排队论主要是对服务系统建立数学模型，研究诸如单位时间内服务系统能够服务的顾客的平均数、顾客平均的排队时间、排队顾客的平均数等数量规律。 一、排队论的一些基本概念 为了叙述一个给定的排队系统，必须规定系统的下列组成部分： 输入过程 即顾客来到服务台的概率分布。排队问题首先要根据原始资料，由顾客到达的规律、作出经验分布，然后按照统计学的方法（如卡方检验法）确定服从哪种理论分布，并估计它的参数值。我们主要讨论顾客来到服务台的概率分布服从泊松分布，且顾客的达到是相互独立的、平稳的输入过程。所谓“平稳”是指分布的期望值和方差参数都不受时间的影响。 排队规则 即顾客排队和等待的规则，排队规则一般有即时制和等待制两种。所谓即时制就是服务台被占用时顾客便随即离去；等待制就是服务台被占用时，顾客便排队等候服务。等待制服务的次序规则有先到先服务、随机服务、有优先权的先服务等，我们主要讨论先到先服务的系统。 服务机构 服务机构可以是没有服务员的，也可以是一个或多个服务员的；可以对单独顾客进行服务，也可以对成批顾客进行服务。和输入过程一样，多数的服务时间都是随机的，且我们总是假定服务时间的分布是平稳的。若以ξ 表示服务员为 n }，n=1，2，…第n个顾客提供服务所需的时间，则服务时间所构成的序列{ξ n 所服从的概率分布表达了排队系统的服务机制，一般假定，相继的服务时间ξ ， 1ξ2，……是独立同分布的，并且任意两个顾客到来的时间间隔序列{T n}也是独立的。 如果按服务系统的以上三个特征的各种可能情形来对服务系统进行分类，那么分类就太多了。因此，现在已被广泛采用的是按顾客相继到达时间间隔的分布、服务时间的分布和服务台的个数进行分类。 研究排队问题的目的，是研究排队系统的运行效率，估计服务质量，确定系统参数的最优值，以决定系统的结构是否合理，设计改进措施等。所以，必须确
第六章排队论模型 排队论起源于1909年丹麦电话工程师A. K．爱尔朗的工作，他对电话通话拥挤问题进行了研究。1917年，爱尔朗发表了他的著名的文章—“自动电话交换中的概率理论的几个问题的解决”。排队论已广泛应用于解决军事、运输、维修、生产、服务、库存、医疗卫生、教育、水利灌溉之类的排队系统的问题，显示了强大的生命力。 排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院看病常常要排队。此时要求服务的数量超过服务机构（服务台、服务员等）的容量。也就是说，到达的顾客不能立即得到服务，因而出现了排队现象。这种现象不仅在个人日常生活中出现，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机待修，水库的存贮调节等都是有形或无形的排队现象。由于顾客到达和服务时间的随机性。可以说排队现象几乎是不可避免的。 排队论（Queuing Theory）也称随机服务系统理论，就是为解决上述问题而发展的一门学科。它研究的内容有下列三部分： （i）性态问题，即研究各种排队系统的概率规律性，主要是研究队长分布、等待时间分布和忙期分布等，包括了瞬态和稳态两种情形。 （ii）最优化问题，又分静态最优和动态最优，前者指最优设计。后者指现有排队系统的最优运营。 （iii）排队系统的统计推断，即判断一个给定的排队系统符合于那种模型，以便根据排队理论进行分析研究。 这里将介绍排队论的一些基本知识，分析几个常见的排队模型。 §1 基本概念 1.1 排队过程的一般表示 下图是排队论的一般模型。 一定的排队规则等待服务，直到按一定的服务规则接受完服务后离开排队系统。 凡要求服务的对象统称为顾客，为顾客服务的人或物称为服务员，由顾客和服务员组成服务系统。对于一个服务系统来说，如果服务机构过小，以致不能满足要求服务的众多顾客的需要，那么就会产生拥挤现象而使服务质量降低。因此，顾客总希望服务机构越大越好，但是，如果服务机构过大，人力和物力方面的开支也就相应增加，从而会造成浪费，因此研究排队模型的目的就是要在顾客需要和服务机构的规模之间进行权衡决策，使其达到合理的平衡。 1.2 排队系统的组成和特征 一般的排队过程都由输入过程、排队规则、服务过程三部分组成，现分述如下： 1.2.1 输入过程 输入过程是指顾客到来时间的规律性，可能有下列不同情况： （i）顾客的组成可能是有限的，也可能是无限的。 （ii）顾客到达的方式可能是一个—个的，也可能是成批的。
３２８ 习题十三 13.1 某市消费者协会一年365天接受顾客对产品质量的申诉。设申诉以λ＝4件/天的普阿松流到达，该协会每天可以处理申诉5件，当天处理不完的将移交专门小组处理，不影响每天业务。试求： （1）一年内有多少天无一件申诉； （2）一年内多少天处理不完当天的申诉。 13.2 来到某餐厅的顾客流服从普阿松分布，平均每小时20人。餐厅于上午11：00开始营业，试求： （1）当上午11：07有18名顾客在餐厅时，于11：12恰好有20名顾客的概率（假定该时间段内无顾客离去）； （2）前一名顾客于11：25到达，下一名顾客在11：28至11：30之间到达的概率。 13.3 某银行有三个出纳员，顾客以平均速度为4人/分钟的泊松流到达，所有的顾客排成一队，服务时间服从均值为0.5分钟的负指数分布，试求： （1） 银行内空闲时间的概率； （2） 银行内顾客数为n 时的稳态概率； （3） 平均队列长Lq ； （4） 银行内的顾客平均数Ls ； （5） 平均逗留时间Ws ； （6） 平均等待时间Wq 。 13.4 某加油站有一台油泵。来加油的汽车按普阿松分布到达，平均每小时20辆，但当加油站中已有n 辆汽车时，新来汽车中将有一部分不愿等待而离去，离去概率为4 n （n ＝0，1，2，3，4）。油泵给一辆汽车加油所需时间为具有均值3分钟的负指数分布。 （1）画出此排队系统的速率图； （2）导出其平衡方程式； （3）求出加油站中汽车数的稳态概率分布； （4）求那些在加油站的汽车的平均逗留时间。 13.5 某无线电修理商店保证每件送到的电器在一小时内修完取货，如超过一小时则分文不取。已知该商店每修理一件平均收费10元，其成本平均每件5.50元。已知送来修理的电器按普阿松分布到达，平均每小时6件，每维修一件的时间平均为7.5分钟，服从负指数分布。试问： （1）该商店在此条件下能否盈利； （2）当每小时送达的电器为多少件时该商店的经营处于盈亏平衡点。 13.6 某企业有5台车运货，已知每台车每运行100小时平均需维修2次，每次需时20分钟，以上分别服从普阿松及负指数分布。求该企业全部车辆正常运
《运筹学》第六章排队论习题 转载请注明 1. 思考题 （1）排队论主要研究的问题是什么； （2）试述排队模型的种类及各部分的特征； （3）Kendall 符号C B A Z Y X /////中各字母的分别代表什么意义； （4）理解平均到达率、平均服务率、平均服务时间和顾客到达间隔时间等概念； （5）分别写出普阿松分布、负指数分布、爱尔朗分布的密度函数，说明这些分 布的主要性质； （6）试述队长和排队长；等待时间和逗留时间；忙期和闲期等概念及他们之间的联系 与区别。 2．判断下列说法是否正确 （1）若到达排队系统的顾客为普阿松流，则依次到达的两名顾客之间的间隔时间 服从负指数分布； （2）假如到达排队系统的顾客来自两个方面，分别服从普阿松分布，则这两部分 顾客合起来的顾客流仍为普阿松分布； （3）若两两顾客依次到达的间隔时间服从负指数分布，又将顾客按到达先后排序， 则第1、3、5、7，┉名顾客到达的间隔时间也服从负指数分布； （4）对1//M M 或C M M //的排队系统，服务完毕离开系统的顾客流也为普阿松流； （5）在排队系统中，一般假定对顾客服务时间的分布为负指数分布，这是因为通过对大 量实际系统的统计研究，这样的假定比较合理； （6）一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行足够长的时间后， 系统将进入稳定状态； （7）排队系统中，顾客等待时间的分布不受排队服务规则的影响； （8）在顾客到达及机构服务时间的分布相同的情况下，对容量有限的排队系统，顾客的 平均等待时间少于允许队长无限的系统； （9）在顾客到达分布相同的情况下，顾客的平均等待时间同服务时间分布的方差大小有 关，当服务时间分布的方差越大时，顾客的平均等待时间就越长； （10）在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下，由1名工人 看管5台机器，或由3名工人联合看管15台机器时，机器因故障等待工人维修的平均时间不变。 3．某店有一个修理工人，顾客到达过程为Poisson 流，平均每小时3人，修理时间服从负 指数分布，平均需19分钟，求： （1）店内空闲的时间； （2）有4个顾客的概率； （3）至少有一个顾客的概率； （4）店内顾客的平均数； （5）等待服务的顾客数； （6）平均等待修理的时间； （7）一个顾客在店内逗留时间超过15分钟的概率。 4．设有一个医院门诊，只有一个值班医生。病人的到达过程为Poisson 流，平均到达时间间隔为20分钟，诊断时间服从负指数分布，平均需12分钟，求： （1）病人到来不用等待的概率； （2）门诊部内顾客的平均数； （3）病人在门诊部的平均逗留时间； （4）若病人在门诊部内的平均逗留时间超过1小时，则医院方将考虑增加值班医生。问 病人平均到达率为多少时，医院才会增加医生？ 5．某排队系统只有1名服务员，平均每小时有4名顾客到达，到达过程为Poisson 流，，服务时间服从负指数分布，平均需6分钟，由于场地限制，系统内最多不超过3名顾客，求：
排队模型之港口系统 本文通过排队论和蒙特卡洛方法解决了生产系统的效率问题，通过对工具到达时间和服务时间的计算机拟合，将基本模型确定在//1 M M排队模型，通过对此基本模型的分析和改进，在概率论相关理论的基础之上使用计算机模拟仿真（蒙特卡洛法）对生产系统的整个运行过程进行模拟，得出最后的结论。好。关键词：问题提出： 一个带有船只卸货设备的小港口，任何时间仅能为一艘船只卸货。船只进港是为了卸货，响铃两艘船到达的时间间隔在15分钟到145分钟变化。一艘船只卸货的时间有所卸货物的类型决定，在15分钟到90分钟之间变化。 那么，每艘船只在港口的平均时间和最长时间是多少 若一艘船只的等待时间是从到达到开始卸货的时间，每艘船只的平均等待时间和最长等待时间是多少 卸货设备空闲时间的百分比是多少 船只排队最长的长度是多少 问题分析： | 排队论：排队论(Queuing Theory) ，是研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法，又称随机服务系统理论，为运筹学的一个分支。本题研究的是生产系统的效率问题，可以将磨损的工具认为顾客，将打磨机当做服务系统。【1】 M M：较为经典的一种排队论模式，按照前面的Kendall记号定义，前//1 面的M代表顾客(工具)到达时间服从泊松分布，后面的M则表示服务时间服从负指数分布，1为仅有一个打磨机。 蒙特卡洛方法：蒙特卡洛法蒙特卡洛(Monte Carlo)方法，或称计算机随机模拟方法，是一种基于“随机数”的计算方法。这一方法源于美国在第一次世界大战进研制原子弹的“曼哈顿计划”。该计划的主持人之一、数学家冯·诺伊曼用驰名世界的赌城—摩纳哥的Monte Carlo—来命名这种方法，为它蒙上了一层神
第四章 排队模型 两类排队模型： 1. Markov 排队模型 2. 非Markov 排队模型 Markov 排队模型： 4-0 Little 定理 1961 年 J.D.Little 证明 1974 年 S.Slidhan 一般性证明 定理 : 在极限平稳状态下,排队系统内顾客平均数L 系 和 顾客在系统内平均逗留时间W 系 之间的关系,不管到达流的分布如何,也不管服务规则如何,均有以下关系: 为到达流的强度 系 系λλ1 4.-=L W 证明: 设 X(t) ---- t 时刻前到达的瞬时顾客数, Y(t)--- t 时刻前离开的瞬时顾客数. Y(t)
在稳定后,流入与流出的顾客数应相等, 则在t 时刻留在系统内的顾客数为: Z(t)=X(t)-Y(t) 在足够长的时间T 来考虑有: 队 队系 系系系同理可以证明所以有逗留时间系统内每个顾客的平均时 间的总和所有顾客在系统内逗留时间个顾客在系统内的逗留第其中的小面积的总和高度为长度为阴影部分的面积W L W L W T t t i t t T t T t T T dt t Z T L i i i i i i i i i i T .: .:. ..,: .11 ]1*[1][1)(10λλλλλ ==--=--= ?= ===∑∑∑∑?
4-1 M/M/1/0 (单通道损失制) 服务员数：n=1 队长：m=0 M -- 到达流为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得： λ
11. 排队论 11.1基本概念 排队现象是指到达服务机构的顾客数量超过服务机构提供服务的容量,也就是说顾客不能够立即得到服务而产生的等待现象。顾客可以是人,也可以是物,比如说,在银行营业部办理存取款的储户,在汽车修理厂等待修理的车辆,在流水线上等待下一到工序加工的半成品,机场厂上空等待降落的飞机,以及等待服务器处理的网页等,都被认为是顾客。服务机构可以是个人,像理发员和美容师,也可以是若干人,像医院的手术小组。服务机构也还可以是包装糖果的机器,机场的跑道,十字路口的红绿灯,以及提供网页查询的服务器等等。 因为顾客到达,服务时间具有不确定性,排队系统又称随机服务系统,它的基本结构如图11所示: 1. 11 图1. 11给出了一些现实排队系统的例子。 表1. 表11.1: 排队系统应用 商业服务理发店,银行柜台,机场办理登机手续的柜台,快餐店的点餐柜台 运输行业城市道路的红绿灯,等待降落或起飞的飞机,出租车 制造业待修理的机器,待加工的材料,生产流水线 社会服务法庭,医疗机构 11.1.1排队系统的特征 为了描述一个排队系统,我们需要说明输入(到达)和输出(服务)过程,及其他基本特征。表11列举了一些排队系统的到达和服务过程。 2. 表11.2: 排队系统举例 )1(到达过程 通常,我们假设顾客的相继到达间隔时间是相互独立并且都具有相同概率分布。在许多
(Poisson流,或指数分布。顾客源可能是有限实际情况中,顾客的相继到达间隔是服从泊松) 的,也可能是无限的。顾客到来方式可能是一个接一个的,也可能是批量的。比如,到达机场海关的旅行团就是成批顾客。 一般来说,我们假设到达过程不受排队系统中顾客数量的影响。以银行为例,无论银行内有3位顾客还是300位顾客,顾客来到银行的到达过程是不会受到影响的。但是在两种情况下到达过程与排队系统中的顾客数量相关。第一种情况发生在顾客源是有限的系统,比如某工厂共有五台机床,若在维修部中已有两台机床,接下来到达维修部的最大量是三台。另一种情况是当顾客到达排队系统时,如果服务机构的设施都被占用,顾客可能耐心等待,也可能选择离开。比如,当一家航空公司的电话订票中心出现排队时,如果顾客等待时间太长,他就可能挂断电话。顾客就会选择另外一家航空公司。 )2(服务过程 为了描述排队系统的服务过程,我们需要确定服务时间的概率分布。在大多数情况下,服务时间是独立于排队系统中的顾客数量,即服务机构不会因为顾客数量增多而加快服务进度。不同服务机构提供的服务时间之间是相互独立,并都服从同一种概率分布,而且也独立于顾客相继到达间隔时间。服务时间一般分为确定型的和随机型的。在大多数情形下,服务时间的是随机型的,排队论主要研究随机型的服务时间。对于随机型的服务时间,我们必须知道它的概率分布,通常假定是指数分布。 从服务队列的安排上来说,我们将重点研究以下几种形式。从队列的数目来看,可以是单 11说明了一个服列,也可以是多列。服务机构在提供服务时,可以有一个或多个服务台。图2. 务台的排队系统: 顾客到达流顾客队列服务台 11 图2. 在有多个服务台的情形中,它们可以是并列,可以是串列,也可以是混合排列,最典型的是以下二种排队方式: 顾客到达流顾客队列服务台 11 图3.
排队论例题 Document number：PBGCG-0857-BTDO-0089-PTT1998
几种典型的排队模型 （1）M/M/1///FCFS 单服务台排队模型 系统的稳态概率n P 01P ρ=-，/1ρλμ=<为服务强度；(1)n n P ρρ=-。 系统运行指标 a.系统中的平均顾客数（队长期望值） 0.s n i L n P λμλ∞=== -∑； b.系统中排队等待服务的平均顾客数（排队长期望值） 0(1).q n i L n P ρλμλ ∞==-= -∑； c.系统中顾客停留时间的期望值 1[]s W E W μλ == -； d.队列中顾客等待时间的期望值 1q s W W ρμμλ=- =-。 (2) M/M/1/N//FCFS 单服务台排队模型 系统的稳态概率n P 011,11N P ρρρ+-= ≠-； 11,1n n N P n N ρρρ +-=<- 系统运行指标 a ．系统中的平均顾客数（队长期望值） b ．系统中排队等待服务的平均顾客数（排队长期望值） c ．系统中顾客停留时间的期望值 d ．队列中顾客等待时间的期望值 。1q s W W μ=- (3) M/M/1//m/FCFS （或M/M/1/m/m/FCFS ）单服务台排队模型 系统的稳态概率n P 00 1!()()!m i i P m m i λμ==-∑； 0!(),1()!n n m P P n m m n λμ=≤≤- 系统运行指标 a ．系统中的平均顾客数（队长期望值） b ．系统中排队等待服务的平均顾客数（排队长期望值） c ．系统中顾客停留时间的期望值
第十二章排队论 1．排队 一般的排队系统都有3个基本组成部分：输入过程，排队规则，服务机构。 输入过程： (1)顾客源的组成可能是有限的也可能是无限的。 (2)顾客到达的方式可能是一个一个的，也可能是成批的。 (3)顾客相继到达的间隔时间可以是确定的，也可以是随机的。 (4)顾客之间到达可以是相互独立的或关联的。 (5)输入过程可以是平稳的，或称对时间是齐次的，即指间隔时间的分布和所含参数均与时间无关，否则称为非平稳的，不过一般总假定是平稳的。 2．三种排队规则 (1)损失制：顾客到达后发现服务台正被占用，则离去。 (2)等待制：顾客到达后发现服务台正被占用，排队等侯。 等待制的服务规则：①先到先服务；②后到先服务；③随机服务；④有优先权服务。 (3)混合制：是等待制和损失制相结合的一种排队服务规则。有两种： ①队长有限制的情况，即当顾客排队等待服务的人数超过规定数量时，后来的顾客就自动离去，另求服务。 ②排队时间有限制的情况，当顾客排队时间超过一定时间时，顾客就自动离去。 服务机构情况：服务机构可以从下述几个方面来描述。 ①服务台数量及布置形式。
从数量上来看，是单服务台还是多服务台，在多服务台的情况下，是串列的还是并列的，或是串、并列结合的，如图12—1所示。 ②在某一时刻接受服务的顾客数，即每个服务台每次对单个顾客还是成批顾客。 ③服务时间分布，服务时间和顾客来到时间一样，多数情况下是随机的。 常见的分布有：泊松分布，负指数分布，爱尔朗分布等。 3．排队模型有关指标与记号 (1)系统状态——指一个排队服务系统中顾客数(包括正在被服务的顾客数)； (2)队长——指系统中等待服务的顾客数，它等于系统状态减去正在被服务的顾客数； (3)N(t)——在时刻t排除服务系统中的顾客数，即系统在时刻t的瞬时状态；
《运筹学》第六章排队论习题 1. 思考题 （1）排队论主要研究的问题是什么； （2）试述排队模型的种类及各部分的特征； （3）Kendall 符号C B A Z Y X /////中各字母的分别代表什么意义； （4）理解平均到达率、平均服务率、平均服务时间和顾客到达间隔时间等概念； （5）分别写出普阿松分布、负指数分布、爱尔朗分布的密度函数，说明这些分 布的主要性质； （6）试述队长和排队长；等待时间和逗留时间；忙期和闲期等概念及他们之间的联系 与区别。 2．判断下列说法是否正确 （1）若到达排队系统的顾客为普阿松流，则依次到达的两名顾客之间的间隔时间 服从负指数分布； （2）假如到达排队系统的顾客来自两个方面，分别服从普阿松分布，则这两部分 顾客合起来的顾客流仍为普阿松分布； （3）若两两顾客依次到达的间隔时间服从负指数分布，又将顾客按到达先后排序， 则第1、3、5、7，┉名顾客到达的间隔时间也服从负指数分布； （4）对1//M M 或C M M //的排队系统，服务完毕离开系统的顾客流也为普阿松流； （5）在排队系统中，一般假定对顾客服务时间的分布为负指数分布，这是因为通过对大 量实际系统的统计研究，这样的假定比较合理； （6）一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行足够长的时间后， 系统将进入稳定状态； （7）排队系统中，顾客等待时间的分布不受排队服务规则的影响； （8）在顾客到达及机构服务时间的分布相同的情况下，对容量有限的排队系统，顾客的 平均等待时间少于允许队长无限的系统； （9）在顾客到达分布相同的情况下，顾客的平均等待时间同服务时间分布的方差大小有 关，当服务时间分布的方差越大时，顾客的平均等待时间就越长； （10）在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下，由1名工人 看管5台机器，或由3名工人联合看管15台机器时，机器因故障等待工人维修的平均时间不变。 3．某店有一个修理工人，顾客到达过程为Poisson 流，平均每小时3人，修理时间服从负 指数分布，平均需19分钟，求： （1）店内空闲的时间； （2）有4个顾客的概率； （3）至少有一个顾客的概率； （4）店内顾客的平均数； （5）等待服务的顾客数； （6）平均等待修理的时间； （7）一个顾客在店内逗留时间超过15分钟的概率。 4．设有一个医院门诊，只有一个值班医生。病人的到达过程为Poisson 流，平均到达时间间隔为20分钟，诊断时间服从负指数分布，平均需12分钟，求： （1）病人到来不用等待的概率； （2）门诊部内顾客的平均数； （3）病人在门诊部的平均逗留时间； （4）若病人在门诊部内的平均逗留时间超过1小时，则医院方将考虑增加值班医生。问 病人平均到达率为多少时，医院才会增加医生？ 5．某排队系统只有1名服务员，平均每小时有4名顾客到达，到达过程为Poisson 流，，服务时间服从负指数分布，平均需6分钟，由于场地限制，系统内最多不超过3名顾客，求： （1）系统内没有顾客的概率； （2）系统内顾客的平均数；
第9章排队论 判断下列说法是否正确： 09100011、若到达排队系统的顾客为泊松流，则依次到达的两名顾客之间的间隔时间服从负指数分布； 09100021、假如到达排队系统的顾客来自两个方面，分别服从泊松分布，则这两部分顾客合起来的顾客流仍为泊松分布； 09100031、若两两顾客依次到达的间隔时间服从负指数分布，又将顾客按到达先后排序，则第1、3、5、7，…名顾客到达的间隔时间也服从负指数分布； 09100041、对M/M/1或M/M/C的排队系统，服务完毕离开系统的顾客流也为泊松流； 09100051、在排队系统中，一般假定对顾客服务时间的分布为负指数分布，这是因为通过对大量实际系统的统计研究，这样的假定比较合理； 09100061、一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行足够长的时间后，系统将进入稳定状态； 09100071、排队系统中，顾客等待时间的分布不受排队服务规则的影响； 09100081、在顾客到达及机构服务时间的分布相同的情况下，对容量有限的排队系统，顾客的平均等待时间将少于允许队长无限的系统； 09100091、在顾客到达的分布相同的情况下，顾客的平均等待时间同服务时间分布的方差大小有关，当服务时间分别的方差越大时，顾客的平均等待时间将越长； 09100101、在机器发生故障的概率及工人修复一台机器的时间分布不变的条件下，由1名工人看管5台机器，或由3名工人联合看管15台机器时，机器因故障等待工人维修 的平均时间不变。 M/M/1 09301012、某理发店只有一名理发师，来理发的顾客按泊松分布到达，平均每小时4人，理发时间服从负指数分布，平均需6小时，求： （1）理发店空闲时间的概率； （2）店内有3个顾客的概率； （3）店内至少有1个顾客的概率； （4）在店内顾客平均数； （5）在店内平均逗留时间； （6）等待服务的顾客平均数； （7）平均等待服务时间； （8）必须在店内消耗15分钟以上的概率。
某修理店只有一个修理工，来修理的顾客到达服从泊松分布，平均4人/小时；修理时间服从负指数分布，平均需要6分钟。试求1.修理店空闲的概率2.店内恰有3个顾客的概率3.店内至少有一个顾客的概率4.在店内的平均顾客数5.每位顾客在店内的平均逗留时间6.等待服务的平均顾客数7.每位顾客平均等待服务时间 本问题可以看成一个M/M/1/∞排队问题，其中 λ=4，μ=1/0.1=10；ρ=λ/μ=0.4<1 (1)修理店空闲的概率 p0=1-ρ=1-0.4=0.6 (2)店内恰有三个顾客的概率 p3=p0ρ3=0.6×0.43=0.038 (3)店内至少有一个顾客的概率 P{N≥1}=1-p0=0.4 (4)在店内的平均顾客数 L=ρ/(1-ρ)=0.4/(1-0.4)=0.667(人) (5)每位顾客在店内的平均逗留时间W=L/λ=0.67/4=10（分钟）W=1/(μ-λ)=1/(10-4)=10（分钟） (6)等待服务的平均顾客数 Lq=ρL=0.4×0.67=0.267(人)Lq=L-ρ=2/3-0.4=0.267（人） (7)每位顾客平均等待服务时间 Wq=Lq/λ=0.267/4=4（分钟）Wq=ρW=0.4×10=4（分钟） 某修理站只有一个修理工，且站内最多停放3台待修的机器。设待修机器按Possion 流到达，平均每分钟到达一台；修理时间服从负指数分布，平均没1.25分钟可修理一台。试求该系统的有关指标 该系统可以看出为一个M/M/1/4排队系统，其中λ=1，μ=1/1.25=0.8，ρ=λ/μ=1.25，K=4 由公式，p0=(1-ρ)/(1-ρk+1)=(1-1.25)/(1-1.255)=0.122 顾客的损失率 p4=ρ4p0=1.254×0.122=0.298 顾客有效到达率 λe=λ(1-p4)=1-0.298=0.702 平均队长L L=2.44(台) 等待队长Lq Lq=L-(1-p0)=2.44-(1-0.122)=1.56(台) 平均逗留时间 W=L/λe=2.44/0.702=3.48(分钟) 平均等待时间 Wq=W-1/μ=3.48-1/0.8=2.23（分钟） 设货船按Possion 流到达某一港口，平均到达率为λ=50条/天，平均卸货率为μ。又已知船在港口停泊一天的费用为1货币单位，平均卸货费为μcs ，其中cs=2，现求出使总费用最少的平均服务率μ* 解：λ=50，cw=1，cs=2，带入公式得 即使总费用最省的平均服务率为55艘/天 M/M/1/∞模型 ρ为服务强度，表示服务台忙碌的概率 服务台空闲的概率p0为1-ρ pn=ρnp0 平均队长L=ρ/(1-ρ)=λ/(μ-λ) 平均等待队长Lq=L-ρ=Lρ 平均逗留时间W=L/λ 平均等待时间Wq=Lq/λ=W -1/μ M/M/1/K 模型 p0会告诉数值 pn=p0ρn L=p/(1-p)-(k+1)p*(k+1)/1-p*(k+1) p 不等于1 L=k/2 p=1 平均等待队长Lq=L-(1-p0) p0系统中没有顾客的概率 有效到达率λe=λ(1-pK) pn 顾客的损失率 平均逗留时间W=L/λe 平均等待时间Wq=Lq/λe=W -1/μ 当k=1时，上述结论仍成立 P0=1/(1+p) P1=p/(1+p) L=P1 拉e=拉P0=拉/(1+p) W=L/拉e=p/拉=1/u Lq=0 Wq=0 M/M/s/∞模型 5525050*=+=+=λλμs w c c