运筹学第十章 排队论.ppt

运筹学第十章 排队论
排队论
引言
生灭过程和Poisson过程
M/M/s等待制排队模型
第一节 引言
一、排队系统的特征及排队论
排队论(Queuing Theory)，又称随机服务系统理论
(Random
仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。
即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。
3．服务机制
排队系统的服务机制可以从以下3方面来描述：
服务台数量及构成形式。
从数量上说，服务台有单服务台和多服务台之分。从构成
形式上看，服务台有：
①单队——单服务台式；
②单队——多服务台并联式；
③多队——多服务台并联式；
④单队——多服务台串联式；
⑤单队——多服务台并串联混合式
以及多队——多服务台并串联混合式等等。
(2) 服务方式。
这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。
(3) 服务时间的分布
一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K阶爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。
三、排队系统的符号表示
肯道尔（）分类：X / Y / Z / A / B /C
其中： X 顾客到达的分布；
Y 服务时间的分布；
Z 服务台数；
A 系统容量；
B 顾客源的个体数。
C 服务规则
表示分布的符号：
M---负指数分布或泊松输入；D----定长分布；
Ek----k阶爱尔朗分布；GI----一般独立随机分布；G----一般随机分布
例如：某排队问题为M／M／S／∞／∞／FCFS／，则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s＞1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。
某些情况下，排队问题仅用上述表达形式中的前3个、4个、5个符号。如不特别说明则均理解为系统等待空间容量无限；顾客源无限，先到先服务，单个服务的等待制系统
四、排队系统的主要数量指标
——评价排队系统的优劣。
下面给出的这些数量指标一般都是和系统运行的时刻有关的随机变量，求这些随机变量的瞬时分布一般是很困难的。为了分析上的简便，并注意到相当一部分排队系统在运行了一定时间后，都会趋于一个平衡状态(或称平稳状态)。在平衡状态下，队长的分布、等待时间的分布和忙期的分布都和系统所处的时刻无关，而且系统的初始状态的影响也会消失。因此，我们在本章中将主要讨论与系统所处时刻无关的性质，即统计平衡性质。
1、队长与排队长
(1)队长: 系统中的顾客数（n）；
N(t)----N----L
(2)排队长: 系统中排队等待服务的顾客数;
Nq(t)---- Nq----Lq
2、逗留时间与等待时间
(1)逗留时间:
——指一个顾客在系统中的全部停留时间；
T(t)----T----W
(2)等待时间:
——指一个顾客在系统中的排队等待时间；
Tq(t)---- Tq-----Wq
这四项主要性能指标(又称主要工作指标)的值越小，说明系统排队越少，等待时间越少，因而系统性能越好。显然，它们是顾客与服务系统的管理者都很关注的。
2、忙期和闲期
(1)忙期:
是指从顾客到达空闲着的服务机构起，到服务机构再次
成为空闲止的这段时间，即服务机构连续忙的时间。

(2)闲期:
与忙期相对的是闲期，即服务机构连续保持空闲的时间。
在排队系统中，忙期和闲期总是交替出现的。
3、其他相关指标
(1)忙期服务量：指一个忙期内系统平均完成
服务的顾客数；
(2)损失率: 指顾客到达排队系统，未接受服务
而离去的概率;
（对损失制或系统容量有限而言）
(3)服务强度： = /s ；