运筹学第十章排队论.ppt

运筹学第十章排队论
第1页，本讲稿共87页
排队论
引言
生灭过程和Poisson过程
M/M/s等待制排队模型
第2页，本讲稿共87页
第一节 引言
一、排队系统的特征及排队论
排队论(Queuing Theo的顾客将不能
进入系统；
无限排队是指系统中顾客数可以是无限的，队列可以排到
无限长，顾客到达系统后均可进入系统排队或接受服务，
这类系统又称为等待制排队系统。
第17页，本讲稿共87页
有限排队系统
损失制排队系统
混合制排队系统
（排队空间为0的系统）
（允许排队，但又不允许队列无限长）
第18页，本讲稿共87页
这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。
损失制排队系统
（排队空间为0的系统）
第19页，本讲稿共87页
混合制排队系统
这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：
① 队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。 如旅馆的床位是有限的。
② 等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T 时，顾客将自动离去，并不再回来。
如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。
（允许排队，但又不允许队列无限长）
第20页，本讲稿共87页
③ 逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t 时，若在这个时间内未被击落，也就不可能再被击落了。
不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=∞时，混合制即成为等待制。(K为系统中可容纳的顾客数)
第21页，本讲稿共87页
(2)排队规则
当顾客到达时，若所有服务台都被占用且又允许排队，则该顾客将进入队列等待。例如，排队等待售票，故障设备等待维修等。服务台对顾客进行服务所遵循的规则通常有：
先到先服务（FCFS）
后到先服务（LCFS）
优先权（PS）
随机服务
仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。
即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。
第22页，本讲稿共87页
3．服务机制
排队系统的服务机制可以从以下3方面来描述：
服务台数量及构成形式。
从数量上说，服务台有单服务台和多服务台之分。从构成
形式上看，服务台有：
①单队——单服务台式；
②单队——多服务台并联式；
③多队——多服务台并联式；
④单队——多服务台串联式；
⑤单队——多服务台并串联混合式
以及多队——多服务台并串联混合式等等。
第23页，本讲稿共87页
(2) 服务方式。
这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。
(3) 服务时间的分布
一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K阶爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。
第24页，本讲稿共87页
三、排队系统的符号表示
肯道尔（）分类：X / Y / Z / A / B /C
其中： X 顾客到达的分布；
Y 服务时间的分布；
Z 服务台数；
A 系统容量；
B 顾客源的个体数。
C 服务规则
表示分布的符号：
M---负指数分布或泊松输入；D----定长分布；
Ek----k阶爱尔朗分布；GI----一般独立随机分布；G----一般随机分布
第25页，本讲稿共87页
例如：某排队问题为M／M／S／∞／∞／FCFS／，则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s＞1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。
某些情况下，排队问题仅用上述表达形式中的前3个、4个、5个符号。如不特别说明则均理解为系统等待空间容量无限；顾客源无限，先到先服务，单个服务的等待制系统
第26页，本讲稿共87页
四、排队系统的主要数量指标