运筹学排队论.ppt

第十三章排队论
1
第一节基本概念
一、排队系统的一般表示
例1、各个顾客由顾客源出发,到达服务机构前排队等候服务,服务完了后就离开。
排队结构指队列的数目和排列方式
排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。
顾客源
排队结构
排队规则
服务规则
服务机构
离去
顾客到来
排队系统
2
到达的顾客
要求服务内容
服务机构
1、不能运转的机器
修理
修理技工
2、修理技工
领取修配零件
发放修配零件的管理员
3、病人
诊断或做手术
医生(或包括手术台)
4、电话呼唤
通话
交换台
5、文件稿
打字
打字员
6、提货单
提取存货
仓库管理员
7、驶入港口的货船
装(卸)货
装(卸)货码头(泊位)
8、上游河水进入水库
放水,调整水位
水闸管理员
现实生活中的排队系统
3
二、排队系统的组成和特征
输入即指顾客到达排队系统,可能有以下不同情况。
1、输入过程
(1)顾客源的组成
有限的
无限的
(2)顾客到来的方式
一个一个的
成批的
(3)顾客相继到达的间隔时间
确定型的
随机型的
(4)顾客的到来
相互独立的
关联的
(5)输入过程
平稳的,或称对时间是齐次的
非平稳的
4
2、排队规则
顾客在排队系统中按怎样的规则、次序接受服务的。
(1)顾客到达时,所有服务台被占用
随即离去的称为即时制(损失制)
排队等候称为等待制
先到先服务
后到先服务
随机服务
有优先权
(2)从队列占用空间
有限的
无限的
(3)从队列的数量
单列
多列
5
3、服务机构
(1)服务员数量
没有
一个或多个
(2)多服务台时
1
单队—单服务台
多队—多服务台(并列)
单队—多服务台(并列)
1
2
c
…
1
2
c
…
6
(3)服务方式
对单个顾客进行
对成批顾客进行
(4)服务时间
确定型
随机型
(5)服务时间的分布我们总假定是平稳的,即分布的期望值、方差等参数都不受时间的影响
多服务台(串列)
1
2
3
1
2
多服务台混合
1
2
c
……
7
三、排队模型的分类
(1)1953年,
X/Y/Z
X处填写表示相继到达间隔时间的分布;
Y处填写表示服务时间的分布;
Z处填写并列的服务台的数目.
表示相继到达间隔时间和服务时间的各种分布的符号:
M—负指数分布
D —确定型
Ek—k阶爱尔朗分布
GI—一般相互独立的时间间隔的分布
G—一般服务时间的分布
8
(2)1971年关于排队论符号的标准化会议上决定,将Kendall符号扩展成为:
X/ Y/ Z/ A/ B/ C
前三项意义不变,而
A处填写系统容量限制N;
B处填写顾客源数m;
C处填写服务规则。
约定:
9
四、排队系统的参数
1、队长(Ls) 指在系统中的顾客数(统计意义下)
2、排队长(Lq) 指系统中排队等候服务的顾客数
3、逗留时间(Ws) 指一个顾客在系统中的停留时间
4、等待时间(Wq) 指一个顾客在系统中排队等待的时间
Ls=Lq+正被服务的顾客数
Ws=Wq+服务时间
5、忙期指从顾客到达空闲服务机构起到服务机构再次空闲止这段时间长度,即服务机构连续繁忙的时间长度。
6、系统的状态n:指系统中的顾客数(某时刻) 。
8、稳定状态:t→时,t=0时的系统不稳定状态将消失,系统的状态概率分布不再随时间变化,即 limPn(t)→Pn。
7、系统状态的概率Pn(t):指时刻t、系统状态为n的概率。一般为关于t的微分方程、关于n的差分方程。
10