忙期指服务机构连续繁忙工作的时间。
10
OR:SM
第三节 标准M/M/1模型
一、模型特征
❖ 输入过程
顾客源无限； 顾客到达方式是单个到达，且相互独立； 输入过程服从参数为 的泊松分布，到达过程平稳。
❖ 排队规则
队列为单队； 队长无限，即系统容量无限； 系统按先到先服务的等待制规则进行服务
第12 章 排队理论
• 排队论(Queuing Theory)
▪ 又称随机服务系统理论，研究排队等待问题 • 研究各种排队系统概率规律性 • 排队系统的最优设计 • 排队系统的最优运营
▪ 排队是经常遇到的，若要求服务的数量超过服务机构的容 量，即不能立即得到服务，就出现了排队现象。
▪ 顾客到达和服务时间是随机的，排队现象是不可避免的： • 增设服务机构，就要增加投资，可能发生空闲浪费 • 减少服务机构，排队现象将会严重 • 在需要服务的顾客数与服务机构容量之间取得平衡
OR:SM
第三节 标准M/M/1模型
二、状态方程
在t+⊿t 时刻，系统中有n>0 个顾客的概率Pn(t+⊿t)
t 时刻
(t, t+⊿t) 时间
t +⊿t 时刻
系统状态 概率 到达 概率 离去 概率 系统状态
概率
n
Pn(t) 一个
⊿t 一个 ⊿t
n
n
Pn(t) 没有 1- ⊿t 没有 1-⊿t
n
n-1
2
OR:SM
第一节 排队系统分析
• 顾客由顾客源到达服务机构排队等待接受服务，服务完了离去
逗留时间
等待时间
顾客
到 达
接受 服务
从到达系统 排队等待至 开始接受服 务的时间。
顾客从到达 至离去，在 系统中停留 的时间。
▪ 逗留时间=等待时间+服务时间
3
服务时间
离 去
从开始接受 服务到服务 后离去的时 间。
▪ 单队——多服务台 ··· 1 ····2 ··· … ····c
1
···· 2
c
▪
多队——多服务台
····1 ····2
····c
5
1
···· 2
c
1
···· 2
c
OR:SM
第一节 排队系统分析
二、排队系统的组成
一般排队系统都有三个基本组成部分：
1. 输入过程 2. 服务规则
顾客源的容量 顾客到达方式 到达时间分布
▪ 服务机构的结构是指服务机构的数目及其排列方式。
• 服务机构可以是人，也可以是物；还可以是一个系统。
▪ 排队规则和服务规则是说明顾客接受服务的规则和次序。
4
OR:SM
第一节 排队系统分析
▪ 队列数目可以是单队，也可以是多队； ▪ 服务机构的数目可以是单服务台，也可以是多服务台。 ▪ 对于多服务台,可能是串联,也可能是并列,或者是串并结合 • ▪ 单队——单服务台 ·······1
D ：定长分布； M ：泊松分布或负指数分布； Ek ： k阶爱尔朗分布； GI ：一般独立分布； G ：一般分布。
• 1971年排队论符号标准化会议决定，扩充X/Y/A/A/B/C
A 系统容量限制 N ； B 顾客源数目m ； C 服务规则。
• 例如，M/M/1/∞/∞/ FCFS ，表示输入过程服从泊松分布、 服务时间服从负指数分布、单服务台、系统容量无限、顾客 源无限、先到先服务的排队模型
• 负指数分布
e v
f (v) 0
v0 v0
期望E(v) 1
方差 2 1 2
9
OR:SM
第二节 排队问题求解
三、运行指标
顾客数量 • 平均队长Ls，指系统中顾客数的期望值 • 平均队列长Lq，指系统中排队等待服务顾客数的期望值 Ls=Lq+［正被服务的顾客数］
排队时间 • 平均逗留时间Ws是指一个顾客在系统中停留时间的期望值 • 平均等待时间Wq指一个顾客在系统中排队等待时间的期望值 Ws=Wq+［服务时间］
7
OR:SM
第二节 排队问题求解
一、求解步骤
确定经验分布
• 首先要对所研究的排队系统进行统计推断，
• 根据实际数据确定输入过程分布和服务时间分布，
估计参数值:
• 平均到达率 • 平均服务率 • 服务强度
确定模型类别
• 给定服务台数、系统容量和服务规则， • 按X/Y/Z/A/B/C确定排队模型。
求运行指标:
• 顾客数 • 排队时间 • 忙期
8
OR:SM
第二节 排队问题求解
二、分布函数
• 泊松分布
条件：
输入流的平稳性
输入流无后效性
输入流的普通性
输入流的有限性
性质：
Pn (t)
(t)n
n!
et
期望E(t) t
方差 2 t
t 0, n 0,1,L
▪ 输入过成服从泊松分布，顾客相继到达的间隔时间服从负指数分布。
❖ 服务机构
只有一个服务台； 服务方式为单个服务，服务时间相互独立； 服务时间服从相同参数 的负指数分布。
11
OR:SM
第三节 标准M/M/1排队模型
如何寻求系统运行指标？
• 平均队长
Ls nPn
n0
• 平均队列长
Lq (n 1)Pn
n1
• 平均逗留时间
• 平均等待时间
• 忙期概率
12
第12 章 排队理论
学Sub习tit要le 点
正确理解排队系统中排队规则和服务规则 顾客输入过程和服务过程的时间分布函数 排队问题的求解步骤及运行指标间的关系 标准M/M/1模型的状态方程及其运行指标 标准M/M/c模型与c个M/M/1模型的差别 典型排队系统的结构优化和运行优化问题
1
OR:SM
Pn-1(t) 一个
⊿t 没有
1-⊿t
n
⊿t⊿t Pn(t) (1- ⊿t)(1-⊿t) Pn(t)
⊿t(1-⊿t) Pn-1(t)
n +1
Pn+1(t) 没有
1- ⊿t 一个
⊿t
n
(1- ⊿t) ⊿t Pn+1(t)
OR:SM
第一节 排队系统分析
一、排队系统的一般结构
顾客源
输入
等待队列
服务机构
服务 排队规则 规则
离去
▪ 顾客：
排队系统
• 人：病人、就餐者等； • 物：不能运转的机器、驶入港口的船只等； • 需处理的信息。
▪ 等待队列结构：队列的数目和排列方式。
• 队列有形或无形；顾客走向服务机构或相反(如送货上门)。
即时制 等待制
• 先到先服务 • 后到先服务 •• 时间有限
3. 服务过程
服务机构个数 接受服务方式 服务时间分布
6
OR:SM
第一节 排队系统分析
三、排队问题的模型
• 柯恩达尔(D.G.Kendall)953年提出 X/Y/Z， 即 输入过程分布/服务时间分布/服务台的数目