排队系统的基本概念

系统建模与仿真第三讲排队系统的基本概念12排队系统知识回顾1.离散事件系统（DEDS或DES)基本概念、基本要素2.DES系统举例3.离散事件系统仿真步骤4.离散事件系统策略5.手工仿真排队系统3排队系统一．排队系统的特征1.排队除了有形的队列外，还可以是无形的队列。•电话预定租车服务；•网络传输；2.排队的可以是人，也可以是物。•生产线上的原材料、半成品；•故障待修的机器；•要进站的火车由于展台被占而等待；•网络打印4排队系统二．排队系统的形式1.单服务台的排队系统服务台...顾客到达完成服务后离去正在接受服务的顾客队列单服务台排队系统5排队系统二．排队系统的形式2.S个服务台，一个队列的排队系统服务台2...顾客到达完成服务后离去队列S个服务台，一个队列的排队系统服务台1服务台36排队系统二．排队系统的形式3.S个服务台，S个队列的排队系统服务台2...顾客到达完成服务后离去队列2服务台1...完成服务后离去队列1服务台3...完成服务后离去队列3S个服务台，S个队列的排队系统7排队系统二．排队系统的形式4.多个服务台的串联排队服务台...顾客到达队列服务台...完成服务后离去队列多个服务台的串联排队8排队系统三．排队系统描述实际中的排队系统各不相同，但概括起来都由三个基本部分组成：输入过程、排队及排队规则和服务机制。9排队系统1.输入过程说明顾客是按什么样的规律到达系统，需要从三个方面来描述：顾客总数。可以是有限的，也可以是无限的；到达方式。单个到达还是成批到达。库存问题中的进货为成批到达；顾客相继到达时间间隔的分布。定长分布（D）。最简流（Poission流）（M）：顾客相继到达的时间间隔为独立的，且同负指数分布，其密度函数为：000)(ttetat（2.1）10排队系统2.排队及排队规则a)排队①无限排队：系统中的顾客是无限的，队列可以排到无限长，顾客到达系统后均可以进入系统排队或接受服务。11排队系统2.排队及排队规则a)排队②有限排队：排队系统中的顾客数是有限的，即系统的空间是有限的，当系统被占后，后面再来的顾客不能进入系统接受服务。又可以分为以下两种：a)损失制排队系统。当顾客到达系统时，如果所有的服务均被占用，则自动离去，并不再回来。b)混合制排队系统。等待制和损失制的结合，有以下三种：I.队长有限，即系统的等待空间是有限的（即队长容量为K）II.等待时间有限。即顾客在系统中的等待时间超过给定的等待时间长度T后，即离去并不再回来。III.逗留时间有限（等待时间和服务时间之和）损失制和等待制都可以看成混合制的特殊情形。如记s为系统中服务台的个数，则当K＝s时，混合制即成为损失制；当K＝∞时，即为等待制。12排队系统2.排队及排队规则a)排队规则①先来先服务（FCFS）②后来先服务（LCFS）：如堆栈③具有优先权的服务（PS）13排队系统服务机制排队系统的服务机制主要包括：服务员的数量及其连接形式（串联或并联）；顾客是单个还是成批接受服务；服务时间的分布。在这些因素中，服务时间的分布更为重要。常见的分布有：•定长分布（D）：即每个顾客接受服务的时间是一个确定的常数。•负指数分布（M）：即每个顾客接受服务的时间相互独立，具有相同的负指数分布：000)(ttetbt（2.2）14排队系统K阶爱尔朗分布（）：每个顾客接受服务的时间服务K阶爱尔朗分布，其密度函数为（2.3）kEtkekktkktb)!1(1)()(爱尔朗分布比负指数分布更具有广泛的适应性。当k=1时，爱尔朗分布为负指数分布；当k增加时，爱尔朗分布逐渐变为对称的。事实上，当k≥30以后，爱尔朗分布近似于正态分布。当k→∞时，由方差为可知，方差将趋近于零，即为完全非随机的。所以，K阶爱尔朗分布可看成完全随机（k＝1）与完全非随机之间的分布，能更广泛的适应于现实世界。21k15排队系统四．排队系统的符号表示根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类，可以给出很多的排队模型。为了方便对众多的模型的描述，D.G.Kendall提出了一种目前在排队论中被广泛采用的“Kendall记号”，一般形式为：X/Y/Z/A/B/CX表示顾客相继达到时间间隔的分布；Y表示服务时间的分布Z表示服务台的个数A表示系统容量，即可容纳的最多顾客数B表示顾客源的数目C表示服务规则16排队系统四．排队系统的符号表示1.M/M/1/∞/∞/FCFS（FIFS/LIFS）2.M/M/13.M/M/s/K17排队系统的数据指标五．排队系统的主要数量指标和记号研究排队系统的目的是通过了解系统的运行的状况，对系统进行调整和控制，使系统处于最优的运行状态。因此，首先需要弄清系统的运行状况。描述一个排队系统的主要数量指标有：1.队长和排队长2.等待时间和逗留时间3.忙期和闲期18排队系统的数据指标队长和排队长1.队长是指系统中的顾客数（排队等待的顾客数与正在接受服务的顾客数之和），2.排队长是指系统中正在排队等待服务的顾客数。3.队长和排队长一般都是随机变量。19排队系统的数据指标等待时间和逗留时间1.等待时间：从顾客到达时刻起到他接受服务止这段时间。2.逗留时间：从顾客到达时刻起到接受服务完成止这段时间。3.等待时间、逗留时间都是随机变量20排队系统的数据指标忙期和闲期1.忙期是指从顾客到达空闲着的服务机构起，到服务机构再次称为空闲止的这段时间。2.闲期是与忙期相对的，是服务机构连续保持空闲的时间。3.忙期和闲期都是随机变量21排队系统的数据指标上述指标的常用记号：时刻t系统中的顾客数（又称为系统的状态），即队长。：时刻t系统中排队的顾客数，即排队长。：时刻t到达系统的顾客在系统中的逗留时间。：时刻t到达系统的顾客在系统中的等待时间。)(tN)(tNq)(tT)(tTq22排队系统的数据指标平衡状态下的指标当系统达到平衡时处于状态n的概率，记为，又记：•N：系统处于平衡状态时的队长，其均值为L，称为平均队长；•：系统处于平衡状态时的排队长，其均值为，称为平均排队长；•T：系统处于平衡状态时顾客的逗留时间，其均值为W，称为平均逗留时间；•：系统处于平衡状态时顾客的等待时间，其均值为，称为平均等待时间；•：当系统处于状态n时，新来顾客的平均到达率（单位时间内新来到系统的平均顾客数）；•：当系统处于状态n时，整个系统的平均服务率（单位时间内可以服务完的顾客数）；npqNqTnn23排队系统的数据指标系统的服务强度当n为常数时，记为；当每个服务台的平均服务率n为常数时，记每个服务台的服务率为，则当sn时，有sn。因此，顾客相继达到的平均时间间隔为/1，平均服务时间为/1。令s/，称为系统的服务强度。24排队系统的数据指标忙期和闲期忙期为B，闲期为I，平均忙期和平均闲期为和，s为系统中并行的服务台数。BI25排队系统的基本问题六．排队系统研究的基本问题排队系统研究的首要问题是排队系统的主要数量指标的概率规律，即研究系统的整体性质，然后进一步研究系统的优化问题。1.通过研究主要数据指标在瞬时或平衡状态下的概率分布及其数字特征，了解系统运行的基本特征。2.统计推断问题，建立适当的排队模型。在建立模型的过程中经常会碰到如下问题：检验系统是否已经到达平衡状态；检验顾客的相继达到时间间隔的相互独立性；确定服务时间的分布及其参数等。3.系统优化问题，又称为系统控制问题或系统运营问题，其基本目的是使系统处于最优或最合理的状态。系统优化问题包括最优设计问题和最优运营问题，其内容很多，有最少费用问题、服务率控制问题、服务台的开关策略、顾客（或服务）根据优先权的最优排序问题。26生灭过程生灭过程简介一类非常重要且广泛存在的排队系统是生灭过程排队系统。生灭过程是一类特殊的随机过程，在生物学、物理学、运筹学中有广泛的应用。在排队系统中，如果用N(t)表示时刻t系统中的顾客数，则｛N(t)，t≥0｝就构成了一个随机过程。如果用“生”表示顾客的到达，“灭”表示顾客的离去，则对许多排队过程来说，｛N(t)，t≥0｝就是一类特殊的随机过程－生灭过程。27生灭过程定义1：设｛N(t)，t≥0｝为一个随机过程。若N(t)的概率分布有如下性质：1.假设N(t)＝n，则从时刻t起到下一个顾客到达的时刻止的时间服从参数为的负指数分布，n＝0，1，2，…。2.假设N(t)＝n，则从时刻t起到下一个顾客离去的时刻止的时间服从参数为的负指数分布，n＝0，1，2，…。3.同一时刻只有一个顾客到达或者离去。则称｛N(t)，t≥0｝是一个生灭过程。nn28生灭过程一般说来，得到N(t)的分布是比较困难的，因此通常是求当系统达到平衡状态后的状态分布，记为：...)2,1,0}()({nntNp,...2,1,0npn，29生灭过程求解状态n的概率为求平稳分布，考虑系统可能处的任一状态n。假设记录了一段时间内进入状态n和离开状态n的次数，则因为“进入”和“离开”是交替发生的，所以这两个数要么相等，要么相差为1。但就这两种事件的平均发生概率是相等的。即当系统运行相当时间到达平稳状态后，对任一状态n来说，单位时间内进入该状态的平均次数和单位时间内离开该状态的平均次数是相等的，这就是系统在统计平衡下的“流入＝流出”原理。根据这一原理，可得到任一状态下的平衡方程如下：,...2,1,0npn，30生灭过程0011pp1112200)(ppp2223311)(ppp11122)(nnnnnnnpppnnnnnnnppp)(1111012┇┇n-1n（2.4）31生灭过程0101pp01221121001121212)(1pppppp01230122323ppp01102111......pppnnnnnnnn0110111......pppnnnnnnnn012┇┇n-1n32生灭过程11021......nnnnnC记：（2.5）0pCpnn则平稳状态的分布为：（2.6）10nnp由概率的要求：1101pCnn1011nnCp于是：即：（2.7）实验课安排以下周四上课时间在院办机房上课1.10.132.10.203.11.34.11.105.11.246.12.22或者上网查询：1.自动化学院的网址上找“实验课表查询”2.