运筹学18排队论

《运筹学18排队论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、排队论(QueueingTheory)（随机服务系统）7/2/20211排队论（QueueingTheory)，也称随机服务系统理论，是运筹学的一个重要分支之一。1909年，丹麦哥本哈根电子公司电话工程师A.K.Erlang的开创性论文“概率论和电话通讯理论”标志此理论的诞生。排队论的发展最早是与电话，通信中的问题相联系的，这些问题仍然是排队论传统的应用领域。近年来在计算机通讯、网络系统、交通运输、医疗卫生系统、库存管理、作战指挥等各领域中均得到了广泛的应用。7/2/20212设备修理修理工人修理工人领取配件管理员病人就诊医生打电话通话交换

2、台文件打印打印机飞机降落跑道指挥机构顾客就餐服务员汽车通过路口红绿灯§1.1排队系统的组成与特征三个基本组成部分：1.输入过程；2.排队规则；3.服务机构。§1排队系统的基本概念输入即为顾客的到达，可有下列情况：1）顾客源：有限的，或无限的。2）到达方式：成批到达，或单个到达。3）到达间隔时间：随机的，或确定的。4）到达关联性：相互独立的，或关联的。所谓独立指t时刻顾客的到达对t时刻以后顾客的到达无影响。5）输入过程可以是平稳的（stationary），也可以是非平稳的。平稳的，指顾客相继到达间隔时间分布及其参数（均值、方差）与时间无关；非

3、平稳的则与时间相关，非平稳的处理比较困难。1.输入过程2.排队规则1）队列数：单列，或多列。（多列时包括各列间可以相互转移、不能相互转移；中途可退出、中途不能退出等。）2）队列的空间：有容量限制，或无容量限制。也可分为有形的和抽象的。3）顾客到达后接受服务，服务分为即时制（损失制）和等待制。即时制不允许排队，不形成队列；而对于等待制将会形成队列，顾客可以按以下规则接受服务：先到先服务FCFS；后到先服务LCFS；随机服务RAND；有优先权服务PS。3.服务机构1）服务机构：单服务台，或多服务台。2)服务方式：单个顾客服务，或成批顾客服务。3

4、)服务时间：确定型(定长时间），或随机型。4)服务时间的分布：假定是平稳的。我们研究的问题是：输入服从某种分布，顾客的到达是相互独立的平稳过程；各列间不能相互转移、中途不能退出；顾客单个到来，服务方式FCFS。最主要的、影响最大的特征是：顾客相继到达间隔时间的分布服务时间的分布服务台数D.G.Kendall，1953提出了分类法，称为Kendall记号：X/Y/Z１９７１年又扩充为：X/Y/Z/A/B/C§1.2排队系统的模型分类式中：X——表示顾客相继到达间隔时间分布；Y——表示服务时间分布；各种分布符号如下：M—负指数分布（负指数分布具

5、有无记忆性，即Markov性）；D—确定型（Deterministic）分布；Ek—K阶爱尔朗分布Erlang；GI—一般相互独立随机分布(GeneralIndependent)；G—一般随机分布。Z——并列的服务台数A——排队系统的最大容量NB——顾客源数量mC——排队规则（FCFS、LCFS等。本章仅研究FCFS排队规则）如[M/M/1/∞/∞/FCFS]即为顾客到达时间间隔为负指数分布，服务时间为负指数分布，单台，无限容量，无限源，先到先服务的排队系统模型。§1.3排队论研究的基本问题1.排队系统的统计推断：即通过对排队系统主要参数的

6、统计推断和对排队系统的结构分析，判断一个给定的排队系统符合哪种模型，以便根据排队理论进行研究。2.系统性态问题：即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等统计指标,包括瞬态、稳态两种情形。3.最优化问题：即包括最优设计(静态优化)，最优运营（动态优化）。§1.4排队问题求解求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标，估计服务质量，确定系统的合理结构和系统参数的合理值，以便实现对现有系统合理改进和对新建系统的最优设计等。认识系统；分析系统；改造系统；设计系统。排队问题的求解：1、确定或拟合排

7、队系统顾客到达时间间隔分布和服务时间分布(可实测)。2、根据排队系统对应的理论模型求解用以判断系统运行优劣的基本数量指标的概率分布或特征数。数量指标主要包括:队长：系统中的顾客数，它的数学期望记为Ls。队列长：系统中排队等待服务的顾客数，它的数学期望记为Lq。系统中顾客数Ls=系统中排队等待服务的顾客数Lq+正被服务的顾客数逗留时间：指一个顾客在系统中的停留时间，它的数学期望记为Ws。等待时间：指一个顾客在系统中排队等待的时间，它的数学期望记为Wq。逗留时间=等待时间+服务时间忙期：指从顾客到达空闲服务机构起到服务机构再次空闲这段时间长度。

8、（忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标，忙期关系到工作强度）为了计算上述的数量指标，必须首先计算系统状态的概率。系统状态：系统状态是指系统中顾客数。状态概