运筹学-排队论1.ppt

排队论(Queueing Theory)(随机服务系统)
第一节
第二节
第三节
6/8/2018
1
运筹学校级重点建设课程电子教案
大纲要求:
掌握排队论的基本概念、常见的到达时间间隔分布和服务时间分布特性,生灭过程及稳态概率。
单服务台负指数分布排队模型;多服务台负指数排队模型;排队系统设计的最优化
重点:掌握M/M/1模型及其应用
难点:到达流的稳态概率和系统状态转移概率及其优化服务设计
自学:M/G/1模型
6/8/2018
2
运筹学校级重点建设课程电子教案
排队论(Queueing Theory),也称随机服务系统理论,是运筹学的一个重要分支之一。
1909年,丹麦哥本哈根电子公司电话工程师A. K. Erlang的开创性论文“概率论和电话通讯理论”标志此理论的诞生。排队论的发展最早是与电话,通信中的问题相联系的,这些问题到现在仍是排队论传统的应用领域。
近年来在计算机通讯、网络系统、交通运输、医疗卫生系统、库存管理、作战指挥等各领域中均得到了广泛的应用。
各种排队问题:
6/8/2018
3
运筹学校级重点建设课程电子教案
机械坏了修理修理工人
修理工人领取配件管理员
病人就诊医生
打电话通话交换台
文件打印打印机
飞机降落降落跑道指挥机构
顾客就餐服务员
汽车路口红绿灯
6/8/2018
4
运筹学校级重点建设课程电子教案
§ 排队系统的组成与特征
首先看一下一般排队系统的组成示意图,不难发现排队系统一般有三个基本组成部分:;;。现分别说明:
§1 排队系统的基本概念
6/8/2018
5
运筹学校级重点建设课程电子教案
输入即为顾客的到达,可有下列情况:
1)顾客源可能是有限的,也可能是无限的。
2)顾客是成批到达或是单个到达。
3)顾客到达的间隔时间可能是随机的或确定的。
4)顾客到达可能是相互独立的或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。
5)输入过程可以是平稳的(stationary),也可以是非平稳的。输入过程是平稳的是指顾客相继到达的间隔时间分布和参数(均值、方差)与时间无关;非平稳的则是与时间相关,非平稳的处理比较困难。
1. 输入过程
6/8/2018
6
运筹学校级重点建设课程电子教案
2. 排队规则
1)顾客到达后接受服务,服务分为即时制(损失制)和等待制。即时制不允许排队,不形成队列;而对于等待制将会形成队列,顾客可以按下规则接收服务:
(1)先到先服务 FCFS ;(2)后到先服务 LCFS (3)随机服务RAND; (4)有优先权服务 PS。
2)从队列的空间可分为有容量限制和无容量限制。也可分为有形的和抽象的。
3)从队列数可分为单列和多列。(多列时包括各列间可以相互转移、不能相互转移;中途可退出、中途不能退出等。)
6/8/2018
7
运筹学校级重点建设课程电子教案
3. 服务机构
1)服务机构分为单服务台和多服务台。不同的输入形式与排队规则和服务机构联合后形成不同的排队服务机构,如:
6/8/2018
8
运筹学校级重点建设课程电子教案
2)服务方式分为单个顾客服务和成批顾客服务。
3)服务时间分为确定型(定常时间)和随机型。
4)服务时间的分布在这里我们假定是平稳的。
我们研究的问题是:输入是服从某种分布,顾客的到达是相互独立到达的平稳过程;各列间不能相互转移、中途不能退出;单个单个地服务方式,服务服从某种分布, FCFS。
6/8/2018
9
运筹学校级重点建设课程电子教案
最主要的、影响最大的是:
顾客相继到达的间隔时间分布
服务时间的分布
服务台数
,1953提出了分类法,称为Kendall记号(适用于并列服务台),1971又扩展成为:
[X/Y/Z/A/B/C]
§ 排队系统的模型分类
6/8/2018
10
运筹学校级重点建设课程电子教案