第8章 排队论.ppt

排队论(Queuing Theory)排队论作为排队系统(随机服务系统)的数学理论和方法,是运筹学的一个重要分支。排队是日常生活中经常遇到的现象,如进餐馆就餐、图书馆借书、在车站候车、售票处购票等等。排队问题的表现形式往往是拥挤现象,随着生产与服务的日益社会化,由排队引起的拥挤现象会越来越普遍。一些排队系统的例子排队系统顾客服务台服务电话系统电话呼叫电话总机通呼叫或取消呼叫售票系统购票旅客售票窗口收款、售票设备维修出故障的设备修理工排除设备故障防空系统进入阵地的敌机高射炮瞄准、射击直至敌机被击落或离开飞机降落达到机场上空的飞机跑道降落诊疗系统病人医生或设备诊断(或治疗)注:要求服务的对象统称为顾客,提供服务的统称为服务台,顾客和服务台构成一个排队系统。3排队可以是有形的队列,也可以是无形的队列。排队可以是人,也可以是物。顾客源队列服务机构顾客到来顾客离去排队系统排队系统及其特征排队系统及其特征4常见排队系统结构图常见排队系统结构图1单队——多服务台(并联)系统2S...1单队——单服务台系统1…S单队——多服务台(串联)系统51多队——多服务台(并联)系统.........2S常见排队系统结构图常见排队系统结构图多队——多服务台(混联、网络)系统基本的排队模型基本组成概念与记号常用概率分布(指数分布等)基本组成输入来源队列服务机构排队系统顾客服务完离开排队系统的三个基本组成部分.?输入过程(顾客按照怎样的规律到达);?排队规则(顾客按照一定规则排队等待服务);?服务机构(服务台的数量,服务的方式,服务时间分布等)8排队系统的三大要素描述排队系统的三大要素描述一、输入过程说明顾客按怎样的规律达到系统,通常从3 方面刻画:(a )顾客总体(顾客源)数,(b )达到方式,(c )顾客相继达到的时间间隔分布。二、排队及排队规则排队:(a)损失制排队(b)等待制排队(c)混合制排队排队规则:(a)先到先服务FCFS(b)后到先服务LCFS,(c)有优先权服务PS,(d)随机服务RF。三、服务机制说明顾客按怎样的规律接受服务,通常从3方面刻画:(a )服务台数目及其连接形式(并联或串联),(b )顾客接受服务的方式(单个或成批),(c )服务时间分布。基本排队模型-记号方案ServerQueueArrival顾客到达时间间隔分布/服务时间分布/服务台数目/排队系统允许的最大顾客容量/顾客总体数量/排队规则(Kendall 记号)M/M/1/?/?/FCFSM/M/1 /?M: 指数分布(Markovian)D: 定长分布(常数时间)Ek: k阶Erlang分布G: 普通的概率分布(任意概率分布)——研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征,了解系统的基本运行特征。——检验系统是否达到平稳状态;检验顾客达到间隔的独立性;确定服务时间分布及参数。——系统的最优设计和最优运营问题。排队论研究的基本问题