运筹学排队论

1、第十四章排队系统的理论、基本概念(掌握)输入过程和服务时间分布(掌握)泊松到达、负指数服务排队模型(掌握)其他模型(了解)优化目标和优化问题(了解)。本章重点介绍排队，这是我们日常生活和生产中常见的现象。例如，乘公共汽车上下班；顾客去商店购买商品；病人去医院看医生了。乘客去售票处买票。学生们经常在食堂排队等候用餐。除了上面提到的可见队列，还有大量所谓的“不可见”队列。例如，几个顾客打电话到出租车站要出租车。如果出租车站没有足够的车辆，一些顾客必须在他们各自的等候处等候。他们分散在不同的地方，但形成了一个无形的队列等待出租车。排队不一定是为了人，也是为了东西：例如，前言，通信卫星和一些信息要在地

2、面上传输；生产线上的原材料和半成品正在等待加工；由于故障而停止运转的机器正在等待工人修理。码头上的船只正等着装卸货物。要降落的飞机在空中盘旋，因为跑道不是空的，等等。面对拥堵，人们总是希望尽最大努力减少排队，通常的办法是增加服务设施。然而，增加得越多，人力物力的支出就越大，甚至浪费闲暇时间。如果服务设施太少，顾客会长时间排队等候，这将对顾客产生不利影响。因此，顾客排队的长度和服务设施的规模构成了随机服务系统中的一对矛盾。如何保证一定的服务质量指标，使服务设施成本经济合理，妥善解决顾客排队时间与服务设施成本之间的矛盾，这是随机服务系统理论排队论要解决的问题。排队论是由丹麦工程师艾尔兰在1909年

3、研究电力系统时创立的。在过去的几十年里，排队论得到了越来越广泛的应用，其理论也日益完善。特别是20世纪60年代以来，由于计算机的飞速发展，排队论的应用开辟了广阔的前景。前言，QueuingTheory，也称为随机服务系统理论，是一门研究拥挤(排队，等待)的科学。具体来说，就是在研究各种排队系统的概率规律的基础上，解决相应排队系统的优化设计和最优控制问题。显然，尽管上述问题互不相同，但它们都有需要某些服务的人或事物以及提供服务的人或组织。排队论把需要服务的对象称为“顾客”，把服务提供者或机构称为“服务台”或“服务员”。不同的客户和服务形成不同的服务体系。为了得到一些服务，顾客来到系统。如果他们不

4、能立即得到服务并被允许排队，他们就加入等待小组，并在得到服务后离开系统，如图1至5所示。图2是在单个队列中具有个服务台的并行排队系统，图3S是在单个队列中具有个服务台的并行排队系统，前言，图4是在单个队列中具有个服务台的串联排队系统，图5是多队列多服务台混合连接网络系统，前言，图6-6是随机服务系统，前言，一般排队系统可由下面的图6描述。图6所示的系统通常被称为随机聚集和分散服务系统，并且任何排队系统都是随机聚集和分散服务系统。这里，“聚”是指顾客的到来，“散”是指顾客的离开。所谓的随机性是排队系统的一个共同特征，它指的是顾客的到达(如连续的到达时间间隔)和每个顾客接受服务的时间通常是未知的或

5、事先是随机的。一般来说，在排队论研究的排队系统中，顾客的到达时间和服务台提供的服务时间是随机的，所以这种服务系统称为随机服务系统。(1)排队系统的描述(1)系统特征和基本排队过程虽然实际的排队系统差别很大，但它们有以下共同特征：(1) 个要求服务的顾客；(2)为顾客服务的人或物，即服务员或服务台；(3)顾客到达系统的时间是随机的，每个顾客被服务的时间是随机的，因此整个排队系统的状态也是随机的。排队系统的随机性导致顾客在某个阶段要排队很长时间，而服务员(服务台)在其他时间则是空闲的。任何排队问题的基本排队过程可以在图6中示出。从图6中可以看出，每个顾客通过顾客源以某种方式到达服务系统，首先加入队

6、列等待服务，然后服务台根据一定的服务规则从队列中选择顾客，得到服务的顾客立即离开。(1)基本概念，(2)排队系统的基本组件通常，排队系统有三个组件：输入过程、服务规则和服务台。1.输入过程。这是指需要服务的顾客到达排队系统的过程，有时称为顾客流。通常，输入过程可以从三个方面来描述。(1)客户总数，也称为客户来源和输入来源。这是指客户的来源。客户来源可以是有限的，也可以是无限的。例如，在售票处买票的顾客总数可以被认为是无限的，而由于工厂故障而需要修理的机床数量是有限的。(1)基本概念，(2)客户到达方法。这是为了描述客户是如何到达系统的，是单独到达还是成批到达。病人去医院就诊是一个顾客到来的例子

7、。在库存问题中，如果生产设备的采购或产品的仓储被视为顾客，那么这些顾客就成批到达。(1)基本概念，(3)顾客流的概率分布，或连续顾客到达之间的时间间隔分布。这是解决排队系统运行指标问题时首先要确定的指标。这也可以理解为到达K个客户的概率(K=1，2等)。)在一定的时间间隔内。客户流的概率分布一般包括固定长度分布、二项分布、泊松流(最简单的流)、埃尔隆德分布等。2。服务规则。这是指服务台从排队顾客中选择服务的顺序。一般来说，它可以分为三类：损失制、等待制和混合制。(1)损失制度。这意味着，如果顾客到达排队系统，所有服务台都被第一个顾客占用，他们将自动离开系统，再也不会回来。一个典型的例子是，如果

8、拨号后出现忙音，客户不会等待并自动挂断电话。如果他想再打电话，他需要再拨一次。这种服务规则被称为损失系统。(2)等待系统。这意味着当顾客来到系统时，所有服务台不是空的，顾客加入排队等待服务。例如，排队购票、故障设备等待维修等。在等候系统中，服务台在选择服务对象时通常有以下四条规则：先到先得。根据顾客到达的顺序为他们服务是最常见的情况。(2)第一次服务后。仓库中堆放的钢材首先被取走时就是这种情况。基本概念和随机服务。也就是说，当服务台空闲时，不会根据排队顺序随机分配客户接受服务。例如，电话交换机连接到一个呼叫。优先服务。如老年人、儿童高级站；危重病人先去看医生。此服务规则适用于需要处理重要数据并

9、立即中断其他数据处理的计算机。(1)基本概念，(3)混合制度。这是一个结合了等待系统和损失系统的服务规则。一般来说，这意味着允许排队，但不允许排队无限期地持续下去。具体来说，大致有三种类型：有限的团队领导。当排队等候服务的顾客数量超过规定数量时，后续顾客将自动离开并要求其他服务，即系统的等候空间有限。例如，它在系统中最多只能容纳K个客户。当新客户到达时，如果系统中的客户数量(也称为团队领导)少于K，他们可以进入系统排队或接受服务。否则，他们将离开系统，再也不会回来。例如，水库的容量有限，酒店的床位数量有限。(1)基本概念，(2)有限的等待时间。也就是说，顾客在系统中的等待时间不超过给定的时间长

10、度T。当等待时间超过T时，顾客将自动离开并且不再返回。如果容易损坏的电子元件的库存有问题，超过一定存储时间的元件将自动被视为无效。另一个例子是，当一个顾客去餐馆吃饭，在等了一段时间后，他不想再等了，于是自动离开去另一家餐馆吃饭。(1)基本概念，(3)有限停留时间(等待时间和服务时间之和)。例如，高射炮被用来射击敌机。当敌机飞越高射炮射击有效区域的时间为T时，如果在此时间内没有被击落，就不能再被击落。不难注意到，损失制度和等待制度可以被视为混合制度的特殊情况。如果S是系统中服务台的数量，那么当K=s时，混合系统成为损失系统。当K=时，混合系统成为等待系统。1。基本概念，3。服务台信息。服务台可以

11、从以下三个方面来描述：(1)服务台的数量和组成。从数量上看，服务台可分为单服务台和多服务台。从构成形式来看，服务台包括： 33，354个单项小组和33，354个单项服务台；(2)单组多服务台并联式；(3)多团队多服务台并联式；(4)单团队多服务台系列型；(5)单组多服务台串联混合，多组多服务台串联混合等。参见前面的图1至图5。基本概念和服务方法。这是指在某一时刻接受服务的客户数量。它有两种类型：单一服务和批量服务。如果一辆公共汽车一次能载一批乘客，那就是批量服务。(3)服务时间的分配。一般来说，在大多数情况下，每个客户的服务时间是一个随机变量，其概率分布包括固定长度分布、负指数分布、K-level Ellian分布、一般分布(所有客户的服务时间都是独立且同分布的)等。为了区分不同的排队系统，可以根据输入过程、排队规则和服务机制的变化来描述或分类排队模型，并且可以给出许多排队模型。为了便于描述许多模型，肯德尔提出了一种目前在排队论中广泛使用的“肯德尔符号”。完整的表达式通常使用6个符号，并采用以下固定格式：每一个符号的含义是：1。基本概念，A-表示顾客连续到达之间的时间分布，常用以下符号：M-表示到达过程是泊松过程或负指数分布；D表示固定长度输入；ek-均值k阶埃尔隆德分布；G代表一种随机分布，通常