运筹学 第十章 排队论

1、排队论、排队论、引言生灭过程和Poisson过程M/M/s排队模型、第一节引言、一、排队系统的特征和排队论、排队论和随机服务系统理论具体来说，在研究各种排队系统的概率规律的基础上，解决相应排队系统的优化设计和最优控制问题。 排队是我们在日常生活和生产中经常遇到的现象。 例如，上班、下班是乘坐公共汽车的客人去店里买东西的病人，在医院看病的旅客，在售票处买票的学生，在食堂吃饭等，经常会排队和等待。 除了这种有形的行列之外，如果有几个客人打电话到出租车车站要求送货，如果出租车车站没有足够的车辆，一些客人必须在各自的要求处等待，他们虽然分散在不同的地方，但形成了无形的队伍在等待送货车。 排队的不一定是

2、人，也可以是物。 例如，通信卫星和地面上的一些应该传达的信息生产线上的原料，半成品因为等待加工故障而停止运转的机器，等待工人修理的码头上的船正在等待卸货的飞机因为跑道不空而在空中盘旋等。 显然，上述各种问题互不相同，但有些人需要某种服务，有些人提供物品和服务。 在行列论中，把要求服务的对象称为“顾客”，把提供服务的人和机关称为“服务人员”和“服务机构”。 实际的排队系统可以是千差万别的，但一般地，如果客户到达系统以接收特定的服务，并且客户不能立即接收服务，则可以对系统进行排队，然后离开系统直到客户接收服务为止，如图10-1至10-4、10-10 请参见图10-2中的单队列s服务台并行排队系统图

3、10-3 S个队列s个服务台并行排队系统，图10-4个队列的多个服务台串行排队系统，同样是其他形式的队列系统，例如可以描述网络队列系统等，并可以参考图10-5描述，尽管各种队列系统的具体形式不同。 图10-5的随机服务系统通常被称为上图所示的系统或随机分布式服务系统，任何队列系统都是随机分布式服务系统。 其中，“集合”表示顾客的到来，“分散”表示顾客的离开。 随机性是矩阵系统的普遍特征，顾客的到达状况(连续到达时间间隔等)和每位顾客接受服务的时间，通常事先不知道或是随机的。 一般来说，在矩阵论研究的矩阵系统中，由于顾客到达的时间和服务台提供服务的时间长度是随机的，所以这种服务系统被称为随机服务

4、系统，归纳起来，矩阵系统由随机服务系统请求服务的人和结构：客户到达- -矩阵- -服务公司服务- -客户离开，二、矩阵系统的描述，实际的矩阵系统各不相同，但概括地说由三个基本部分组成：1输入过程2矩阵和矩阵规则3服务机制，1输入过程是什么？ 在请求服务的客户以什么样的规则到达矩阵系统的过程中，有时被称为客户流，通常可以从三个方面描述输入过程。 (1)顾客总数也称为顾客来源、输入来源。 这是指顾客的来源。 客户来源可以是有限的，也可以是无限的。 例如，可以认为在售票处购买票的顾客总数是无限的，但是在工厂内停止修理的机器显然是有限的。 (2)顾客到达方式这是记述顾客是如何到达系统的，他们是单独到达

5、的，还是统一到达的。 患者到医院就诊是顾客个别到达的例子。 在库存问题上，如果把生产器材的进货和产品的入库看作顾客，这个顾客就会一并到达。(3)顾客流的概率分布，或者顾客到达的时间间隔的分布相继出现。 这是在解决与排队系统运行指标有关的问题时，首先应该确定的指标。 这也可以理解以一定时间间隔到达k位顾客(k=1，2， )的概率是多少。 顾客流的概率分布一般包括固定长度分布、二元分布、泊松流(最简单的流)、爱尔兰分布等几个种类。 2排队和排队规则，排队分为有限排队和无限排队。 有限矩阵指的是矩阵系统中的客户数量有限，即系统空间有限，导致系统已满时，后续客户不能进入系统的无限队列指的是系统客户数量

6、无限，队列可以是无限长度。 可以进入系统进行排队或接收服务的系统，这种系统也称为待机队列系统. 有限排队系统、损失排队系统、混合排队系统、(排队空间为0的系统)、(允许排队，但不允许无限长的排队)，只要客户到达排队系统时，所有服务台都已被来的客户占用典型的例子是，如果电话拔号后出现急促的声音，顾客不等待就自动挂断电话，但重新打电话还需要拔号的服务规则是损失制。 另外，丢失控制排队系统(排队空间为0的系统)、混合控制排队系统是待机制与丢失控制组合的服务规则，通常是可以进行排队的，但不允许无限长队列。 具体来说，大致有三种。 队长是有限的。 排队等待服务的顾客数超过规定数的话，之后的顾客就会自动离

7、开服务，系统的等待时间是有限的。 酒店的床有限。 等待的时间有限。 也就是说，如果顾客在系统中的等待时间不超过一定的长度t，等待时间超过t，顾客就不会自动离开了。 客人在饭馆吃饭的话，等了一定时间再不等就自动回去，在别的饭馆吃饭。(队列允许，但队列不允许无限长)，停留时间(等待时间和服务时间之和)有限。 比如用高射炮射击敌机，敌机在高射炮射击的有效区域飞行的时间是t时，如果不在这个时间内被击落，就不能再被击落了。 损害制和待机制可以看作是混合制的特殊情况，如果把s标记为系统的服务台数，那么K=s时，混合制就成为损害制，K=时，混合制就成为待机制。 (k是系统中可容纳的客户数)，(2)队列规则当

8、客户到达时，所有服务台都被占用，并且队列被允许时，该客户将排队等待。 例如，售票员，等待修理故障设备等。 服务台向顾客服务的规则通常是先到服务(FCFS )后到服务(LCFS )优先级(PS )随机服务，在这种情况下，仓库里的钢材是先读取之后堆积的钢材。 也就是说，服务台空闲时，不按照行列的顺序，自由指定某个顾客来接受服务。 例如，电话交换台打电话是一个例子。 3服务机制、排队系统的服务机制可以从以下三个方面进行说明：服务台的数量和配置形式。 在数量上，服务台有单一服务台和多个服务台的区别。 从配置形式来看，服务台为：有单个团队的服务台单个团队的服务台和串联混合式，多个团队的多个服务台并联连接

9、着单个团队的多个服务台系列单个团队的多个服务台(2)服务方式。 这是在某个时刻接受服务的顾客数，有单一服务和批量服务两种。 如果公共汽车可以一次承载多名乘客的话，属于批量服务。 (3)服务时间的分布通常是每客户的服务时间是随机变量，其概率分布包括固定长度分布、负指数分布、k阶爱尔兰分布、一般分布(所有客户的服务时间独立分布)等。三、矩阵系统的符号是肯德尔(D.G.Kendall )分类： X/Y/Z/A/B /C中： x客户到达的分布y服务台数a系统容量b客户方的个体数。 c服务规则表示分布的符号： M-负指数分布或泊松输入D-固定长度分布Ek-k层爱尔兰分布GI-一般独立随机分布G-一般随机

10、分布，例如，如果队列问题为MMSFCFS，则客户到达间隔时间为负指数分布(泊松流) 表示服务时间为负指数分布的s(s1 )个服务台系统待机空间容量无限(待机)客户来源无限，采用先到先得的服务规则。 有时，矩阵问题只使用上述表示形式中的前3、4、5符号。 除非另有说明，系统的待机空间容量是无限的，客户的来源是无限的，按先到顺序提供服务，单一服务的待机系统，四、矩阵系统的主要数量指标是评价矩阵系统的优劣。 下面示出的这些数量指示符一般是与系统操作的时间相关的随机变量，并且一般而言，难以确定这些随机变量的瞬时分布。 为了分析上的简便，需要注意的是，相当部分排列的系统在经过一定的时间后，就会成为平衡状

11、态(或稳定状态)。 在平衡状态中，队长的分布、等待时间的分布、繁忙期间的分布与系统放置的时间无关，并且系统的初始状态的影响也没有。 因此，本章将讨论与系统所处的时刻无关的性质，即统计平衡的性质。 1、队长和队长(1)队长：系统上的客户数(n) N(t)-N-L (2)队列长：系统上排队等待服务的客户数Nq(t)- Nq-Lq， 2、停留时间和等待时间(1)停留时间：是指一个客户在系统中停留的所有时间T(t)-T-W (2)等待时间：是指客户在系统中的等待时间TQ (t )- TQ-wq， 这四个主要性能指标(也称为主要工作指标)的值越小，系统队列越少，等待时间越少，系统性能越好。 显然，这些都

12、是顾客和服务系统的管理者关注的。 另外，繁忙期和闲期(1)繁忙期：是指从顾客到达空闲的服务机构起服务机构再次空闲的时间，即服务机构变得忙碌的时间。 (2)空闲周期：是服务机构对空闲周期保持空闲的时间。 排队系统中，忙碌期间和空闲期间总是交替出现。 3、其他相关指标(1)繁忙期服务量：指一个繁忙期内系统平均完成服务的客户数；(2)损失率：指客户到达矩阵系统，未得到服务就离开的概率(如果损失限制或系统容量有限) (3)服务强度：=/s 根据前面的约定，我们主要分析系统的平稳分布。 因此，Pn :系统达到统计平衡时达到状态n的概率(pn(t ) )，n :系统达到状态n时新客户的平均到达率(单位时间

13、内到达系统的平均客户数)，n :系统达到状态n时系统整体的平均服务率。 (单位时间内可以服务的客户数) n为常数时，每个服务台的平均服务率为一定时，每个服务台的服务率记录如下。 s表示系统中的并行服务台的数量，对于ns，由于有ns，因此=/s、服务强度、负指数分布、密度函数、平均、方差、随机变量t、分布函数、fT(t )表示严格的下降函数、第二节毁灭过程和poissity 生灭过程是一个特殊的随机过程，广泛应用于生物学、物理学和运营学。 定义1是N(t )，t0是随机过程。 N(t )的概率分布具有以下性质： (N(t)=n，从时刻t到下一个顾客到达时间的时间遵循参数n的负指数分布。如果假定(

14、N(t)=n，则根据参数n的负指数分布，从时间t到下一个顾客离开的时间的时间是n=0，1，2。 (3)一次只有一个顾客到达或离开。 把N(t )、t0称为生灭过程。 顾客到达“生”的顾客离开“灭”，顾客到达，顾客离开，生灭过程的印象：一般来说很难得到，所以通常求出系统成为稳定状态后的状态分布，记为n=0、1、2，各种方式发生概率表。 由于方式1、2、3、4相互不兼容且完备，t2项成为零，上式的求爱在：n=0的情况下，仅发生方式1和3、4，并且在方式1中不分开的概率为1则为：我们假定系统稳定，无论时间如何概率分布要求：有：还有：总结：系统进入稳态后状态分布-Pn，例如，某小型超市有收银台。 存款

15、客人每小时以30人的负面指数分布到达。 如果收银台前只有一个顾客，收款人只提供一个服务，收款时间平均为1.5min的负指数分布的2个以上的顾客，则增加一个助手共同为顾客提供服务，收款时间缩短为平均1min的负指数分布。 收银台前有n个顾客的概率Pn，解：n=1，2 .从级数到：q|1时，和，到：2，Poisson过程和负指数分布，Poisson过程(也称为Poisson流，最简单的流)是用矩阵论经常描述顾客的到来的特殊随机过程实际上这是一个纯粹的过程，它与概率论中的Poisson分布和负指数分布有着密切的关系。 以下，结合排序论的术语来说明Poisson过程的定义：定义2N(t )为时间0，t

16、内到达系统的顾客数满足以下三个条件： (1)稳定性： t，t内顾客到达的概率，其中常数0称为过程n(t )的强度，o (注：(2)在具有独立性的任意两个非交叉区间，顾客的到达状况是相互独立的，(3)普通性在t，t内多个顾客到达的概率，即相对于足够小的t，t，t内出现两个以上质点的概率，与一个质点出现的概率相比可以无视。 时，N(t )，t 0称为Poisson进程(强度为)。 设定理1N(t )为时间0，t内到达系统的顾客数，则n(t )，t 0为Poisson过程的足够的必要条件是n=1，2，定理1显示，若顾客的到达是Poisson流，则到达顾客数的分布是Poisson分布。 例如，客人以泊松流到达餐厅，平均每小时20人，上午11点07分餐厅18人，11点12分之前餐厅20人的概率，分析：问题意识20 (人/小时)，公式：h(1/12 )内有客人到达2人的概率：和在实际问题中比较容易得到和分析的是顾客相继到达系统的时间，或者相继