排队论又称随机服务系统,它应用于一切服务系统,包括生产管理系统、通信系统、交通系统、计算机存储系统。它通过建立一些数学模型,以对随机发生的需求提供服务的系统预测。现实生活中如排队买票、病人排队就诊、轮船进港、高速路上汽车通过收费站、机器等待修理等等。 一、排队论的基本构成
(1)输入过程
输入过程是描述顾客是按照怎样的规律到达排队系统的。包括①顾客总体:顾客的来源是有限的还是无限的。②到达的类型:顾客到达是单个到达还是成批到达。③相继顾客到达的时间间隔:通常假定是相互独立同分布,有的是等间隔到达,有的是服从负指数分布,有的是服从k阶Erlang分布。 (2)排队规则
排队规则指顾客按怎样的规定的次序接受服务。常见的有等待制,损失制,混合制,闭合制。当一个顾客到达时所有服务台都不空闲,则此顾客排队等待直到得到服务后离开,称为等待制。在等待制中,可以采用先到先服务,如排队买票;也有后到先服务,如天气预报;也有随机服务,如电话服务;也有有优先权的服务,如危重病人可优先看病。当一个顾客到来时,所有服务台都不空闲,则该顾客立即离开不等待,称为损失制。顾客排队等候的人数是有限长的,称为混合制度。当顾客对象和服务对象相同且固定时是闭合制。如几名维修工人固定维修某个工厂的机器就属于闭合制。
(3)服务机构
服务机构主要包括:服务台的数量;服务时间服从的分布。常见的有定长分布、负指数分布、几何分布等。
二、排队系统的数量指标
(1)队长与等待队长
队长(通常记为)是指系统中的平均顾客数(包括正在接受服务的顾客)。等待队长(通常记为)指系统中处于等待的顾客的数量。显然,队长等于等待队长加上正在服务的顾客数。
(2)等待时间
等待时间包括顾客的平均逗留时间(通常记为)和平均等待时间(通常记为)。顾客的平均逗留时间是指顾客进入系统到离开系统这段时间,包括等待时间和接受服务的时间。顾客的平均等待时间是指顾客进入系统到接受服务这段时间。
(3)忙期
从顾客到达空闲的系统,服务立即开始,直到再次变为空闲,这段时间是系统连续繁忙的时期,称之为系统的忙期。它反映了系统中服务机构工作强度,是衡量服务系统利用效率的指标,即
服务强度=忙期/服务总时间=1─闲期/服务总时间
闲期与忙期对应的系统的空闲时间,也就是系统连续保持空闲的时间长度。
三、排队论中的符号表示
排队论中的记号是20世纪50年代初由D.G.Kendall引入的,通常由3~5个字母组成,形式为:
A/B/C/n
其中A表示输入过程,B代表服务时间,C代表服务台数量,n表示系统空间数。如
(1) M/M/S/∞表示输入过程是Poisson流,服务时间服从负指数分布,系统有S个服务台平行服务,系统容量为无穷大的等待制排队系统。
(2) M/G/S/∞表示输入过程是Poisson流,服务时间服从一般概率分布,系统有S个服务台平行服务,系统容量为无穷大的等待制排队系统。
(3)D/M/S/K表示顾客相继到达时间间隔独立、服从定长分布,服务时间服从负指数分布,系统有S个服务台平行服务,系统容量为K个的混合制系统。
(4) M/M/S/S表示输入过程是Poisson流,服务时间服从负指数分布,系统有S个服务台平行
服务,顾客到达后不等待的损失制系统。
(5)M/M/S/K/K表示输入过程是Poisson流,服务时间服从负指数分布,系统有S个服务台平行服务,系统容量和顾客容量都为K个的闭合制系统。
四、排队论中四种重要的模型
1.等待制模型M/M/S/∞
该模型中顾客到达规律服从参数为的Poisson过程,在时间内到达的顾客数服从的的分布为:
(1)
其单位时间到达的顾客平均数为,时间内到达的顾客平均数为。
顾客接受服务的时间服从负指数分布,单位时间服务的顾客平均数为,服务时间的分布为:
(2)
每个顾客接受服务的平均时间为。
下面分别给出S=1和S>1的一些主要结果。
1.1 只有一个服务台的S=1情形
可以计算出稳定状态下系统有个顾客的概率:
(3)
其中称为系统的服务强度。
则系统没有顾客的概率为:
系统中顾客的平均队长为:
(4)
系统中顾客的平均等待队长为:
(5)
系统中顾客的平均逗留时间为:
(6)
系统中顾客的平均等待时间为:
(7)
从(4)~(6)式可以看出:
, (8)
或 , (9)
该公式称为Little公式。在其它排队论模型中依然适用。
Little公式的直观意义:
表明排队系统的队长等于一个顾客平均逗留时间内到达的顾客数。
表明排队系统的等待队长等于一个顾客平均等待时间内到达的顾客数。
1.2系统有多个服务台S>1情形
当系统中有s个服务台,系统服务能力为,服务强度为。
系统中顾客的平均队长为:
(10)
其中,表示所有服务台都空闲的概率。
系统中顾客的逗留时间为:
(11)
系统中顾客的平均等待时间为:
(12)
系统中顾客的平均等待队长为:
(13)
1.3 LINGO中的相关函数及相关参数计算公式
(1)顾客等待概率的公式:
(14)
其中S为服务台服务台个数,load为系统到达的载荷,即。
(2)顾客的平均等待时间公式:
(15)
其中T为顾客接受服务的平均时间,有。
当load>s时无意义,表示当系统负荷超过服务台个数时,排队系统达到不稳定状态,队伍将越排越长。
(3)系统中顾客的平均逗留时间 (16)
(4)系统中顾客的的平均队长 (17)
(5) 系统中顾客的的平均等待队长 (18)
例1 某机关接待室只有1名对外接待人员,每天工作10小时,来访人员和接待时间都是随机的。设来访人员按照Poisson流到达,到达速率为人/小时,接待人员的服务速率为人/小时,接待时间服从负指数分布。
(1)计算来访人员的平均等待时间,等候的平均人数。
(2)若到达速率增大为人/小时,每个接待人员的服务速率不变,为使来访问人员平均等待时间不超过半小时,最少应该配置几名接待人员。
解答:
(1)该问题属于M/M/1/∞排队模型。
S=1,,需要计算来访人员的平均等待时间,等候的平均人数。
LINGO程序为:
model:
lp=8;
u=9;
T=1/u;
load=lp/u;
S=1;
Pwait=@PEB(load,S);!等待概率;
W_q=Pwait*T/(S-load);!平均等待时间;
L_q=lp*W_q;!顾客的平均等待队长;
end
计算结果:
来访人员的平均等待时间小时=53分钟,等候的平均人数人。
(2)该问题属于M/M/S/∞排队模型。
求最小的S使,来访人员的平均等待时间。
LINGO程序为:
model:
min=S;
lp=20;
u=9; !服务率;