数学建模排队论讲解
简介
排队论(Queuing Theory),又称随机服务系统理论 (Random Service System Theory),是一门研究拥挤 现象(排队、等待)的科学。具体地说,它是在研究 各种排队系统概率规律性的基础上,解决相应排队 系统的最优设计和最优控制问题。
目录
§1 排队系统综述及常用分布 §2 单服务台 M / M /1排队模型 §3 多服务台 M / M / C 排队模型 §4 排队系统的优化问题
负指数分布的概率密度为: fT (t) ? ? e? ? t (t ? 0)
间隔时间 T 的期望值:
E (T ) ? 1
?
1.5 排队系统的常用分布
同样,对顾客服务时间常用的概率分布也是负指数分布,
概率密度为: f (t) ? ? e?? t (t ? 0)
其中? 表示单位时间内完成服务的顾客数,也称平均服务率.
1)顾客源 ——可以是有限的,也可以是无限的.
2)顾客到达的方式——描述顾客是怎样来到系统的,是单个 到达还是成批到达.
3)顾客流的概率分布——或称相继顾客到达的时间间隔的分 布,相继到达的时间间隔可以是确定的也可以是随机的, 常见的分布有定长分布、二项分布和负指数分布等.
1.2 排队系统的组成
排队规则:指从队列中挑选顾客进行服务的规律.
多有一个顾客到达系统.即在时间 ?
t
?
?
t内有2个或2个以上顾客
? 到达的概率极小,有 lim Pn ?t ? ? t ?? 0 ?t? 0
n? 2
可以证明,在长为t的时间内到达个顾客的概率为:
Pn ?t ??
(? t) n e? ?t
n!
?t ? 0 ? n ? 0,1,2,?
期望为: E n ( t ) ? ? t
§1 排队系统综述及常用分布
1.1 排队系统的描述
任何一个排队问题的基本排队过程都可以用图1.1表示。 每个顾客由顾客源按一定方式到达服务系统,首先加入队 列排队等待接受服务,然后服务台按一定规则从队列中选 择顾客进行服务,获得服务的顾客立即离开。
图1.1
1.2 排队系统的组成
通常的排队系统可以分为3个组成部分:输入过程、排队 规则和服务台. 输入过程:顾客到达的规律
排队方式还分为单列、多列和循环队列。
1.2 排队系统的组成
服务台: 1)服务台数量及构成形式——从数量上说,服务台有单服务 台和多服务台之分。从构成形式上看,有单队列单服务台、 单队多服务台并联、多队多服务台并联式、单队多服务台串 联式等.
2) 服务方式——指在某一时刻接受服务的顾客数,有单个服 务和成批服务两种.
其中,
X——顾客到达间隔时间概率分布 Y——服务时间的概率分布 Z——服务台数 A——系统容量限制,即系统中允许的最多顾客数 B——顾客源总数 C——服务规则
1.3 排队系统的符号表示( Kendall 符号)
表示顾客相继到达间隔时间和服务时间的各种分布 符号有:
M——表示到达过程为泊松过程或负指数分布; D——表示定长输入; Ek——表示k阶爱尔朗分布; G——表示一般相互独立的随机分布.
1)泊松分布:
泊松过程具有如下性质:
(1) 平稳性:在时间 t ? ? t 内,到达个顾客的概率只与? t和 n
的大小有关而与时刻起点 t 无关.
(2) 独立性:在时间 t ? ? t内到达 n个顾客的概率与起始时
刻之前到达多少个顾客无关.
(3) 普通性:对于充分小的时间间隔 ? t,在时间 t ? ? t内最
务的顾客数,记为 L s 4.一位顾客花在排队上的平均时间,记为 W q 5.一位顾客花在系统里的平均逗留时间,包括排队时间和
被服务的时间,记为 W s
6.顾客到达系统时,得不到及时的服务,必须排队等待服 务的概率,记为 Pw
7.系统里正好有n 个顾客(包括排队的和正在被服务的顾客 的概率记为Pn
1.5 排队系统的常用分布
1.5 排队系统的常用分布
当 t ? 1 时,即单位时间内到达个顾客的概率为:
Pn ?
Pn (1 ) ?
?
n
e??
n!
其中? 为单位时间内到达系统的顾客的期望值.
2)负指数分布
理论上可以证明若顾客在单位时间内到达系统的个数 X 是
服从参数为 ? 的泊松分布,则顾客到达系统的间隔时间 T 服从 参数为 ?的负指数分布,反之亦然.
1)等待制 —— 当顾客到达时,所有的服务台均被占用,顾客 就排队等待,直到接 受完服务才离去。例如出故障的机器 排队等待维修就是这种情况.
2)损失制——当顾客到达时,所有的服务台均被占用,顾客 随即离去.
3)混合制——介于损失制和等待制之间,即既有等待又有损 失.有队列长度有限和排队等待时间有限两种情况,在限度 以内就排队等待,超过一定限度就 离去.
3)服务时间的分布——在多数情况下,对每一个顾客的服务 时间是一随机变量,其概率分布有定长分布、负指数分布、 爱尔朗分布等.
1.3 排队系统的符号表示( Kendall 符号)
根据不同的输入过程、排队规则和服务台数量,可以形成 不同的排队模型,为方便对模型的描述,通常采用如下的符 号形式:
X /Y /Z / A/ B/C
比如,M/M/c/N/m/FCFS表示相继到达时间间 隔和服务时间为负指数分布,c个服务台,系统容量为N, 顾客源数目为m,采用先到先服务规则的排队模型.
1.4 排队系统主要数量指标和记号
1.在系统里没有顾客的概率,即所有设施空闲的概率,记 为 P0
2.排队的平均长度,即排队的平均顾客数记为 Lp 3.在系统里的平均顾客数,包括排队的顾客数和正在被服
排队论
Queuing Theory
简介
排队是日常生活和生产中经常遇到的现象。
顾客到商店购买物品 面病对员拥到挤医现院象看,病如果服务设施太少,顾客排队等 待的时旅间客就到会售很票长处,购对买顾车客票会带来不良影响。而随服 务设施学增生加去,食人堂力就、餐物力的支出就越大。 顾客等待出租车 如通何讯做卫到星既与保地证面一若定干的待服传务递质的量信指息标,又使服务 设施费码用头经的济船合只理等,待恰装当卸地货解物决顾客排队时间与服务 设施费要用降大落小的这飞对机矛因盾跑,道这不就空是而排在队空论中所盘要旋研究解决 的问题等。等......