补充资料：排队

排队
queue; Maccouoro

　　排队[甲.粉;MaCco即ro o6e刃粗一妞“，e皿cTeMa] 一种系统，它包括一个由需要“服务”的请求(用户，呼唤)组成的随机“输入”流以及一个提供这种“服务刀的机构(规则). 排队的典型例子是自动电话交换机.其中请求即电话用户的呼唤(呼唤的输人流)，是随机地发生的，而服务机构是由固定数目的n条通道(线路、服务台、中继线)组成的，其中每条通道可能在一段随机时间即通话时间里，为了服务呼唤而繁忙.如果所有。条通道都繁忙，那么一个新到的呼唤就会遭受“损失”.服务机构(规则)也可能包括有关下一个呼唤要用到的空闲线路的指示，或当想用的线路繁忙时如何等待的建议等等. 还有其他类型的系统，其中每个请求必须得到服务.例如，到达机场要求降落的飞机或在计算机上必须加以处理的问题(程序)等.排队的“随机”部分不难用随机序列或过程来描述.最简单的排队可以用非负值随机变量组成的二维随机控制序列 {T歹，;夕:o‘j<二}来描述·序列{:丁蛋用来定义呼唤流。:它给出请求进人系统的随机时间 ;石，T名+;育，公息+;戈+:复，.“.同样，输人流也可用随机过程{。(t):t)o}来刻画，其中e(t)表示到时刻t为止进人系统的呼唤数.第二个序列{弓}描述服务过程，“随机变量鲜表示第j个呼唤所用的服务时间.服务结束后，呼唤就离开系统. 标值点过程可用来更一般地描述控制序列，其中‘表示点之间的间隔，而‘表示点的标值. 对控制序列的表述并不能唯一地决定系统的性态，还必须同时给出服务规则:决定服务开始的规则及呼唤的行为依赖于系统状态的方式. 不同的服务规则产生多种不同形式的排队.下面给出一些最简单的排队. 工.等待制系统.进入系统而没有立即被服务的呼唤形成排队等待服务.此后，呼唤按到达的顺序接受服务.如果在时刻t有排队或有一个呼唤正被服务，那么就称系统此刻为繁忙的(h旧y)，否则，称系统为空闲的(n优).要区分下面两种排队系统. 工:.常规系统.如果系统空闲，那么当一个呼唤到达时它立即开始工作(服务该呼唤);如果系统繁忙，那么下一个呼唤的服务开始于前一个呼唤服务结束的时刻.这种系统也称为完全可达的(conlP七telyacc七ssible). 工2.自控服务系统.这里服务仅在时刻0，:篇，::十丁孟，…开始. 11.队长有限制的系统(有限等待空间的系统).如果在时刻t有一个呼唤正被服务而其他n一1个呼唤在等待，就称队长q(t)等于n)1.令q。二q(:石+…十::一t)为第n个呼唤到达时刻的队长(该呼唤不计在内).在队长有限制的系统中，如果第”个呼唤到达时队长q。等于最大容许值N)1，那么该呼唤就遭受“损失”而离开系统.数N为此系统的一个基本特征.如果N二田，那么就是队长无限制的常规系统. 也会考虑队长随机限制的系统与等待时间随机限制的系统. 巫.损失制系统.即N=1的队长有限制的系统.对于损失制，显然不用考虑自控服务情形. 对每个最简单系统，对控制序列的描述完全确定系统的行为.换言之，对每个基本事件口及任意时刻t，时刻t系统的状态唯一被确定. 除以上形式服务外，可以有更复杂的系统.它们具有更复杂的控制序列及服务规则. IV.成批输入流与成批服务.这些系统由四维控制序列 {T丁，v夕，:了，，少:j)o蛋来控制，其中，歹与，:皆为非负整数值的·新随机变量的意义如下:呼唤以批量，息，v丁，一进人系统(在相应的时刻:二，下石十;;，…);服务也是成批地进行，第一批有，孟个呼唤被服务，第二批有可个等等(如果排队中没有足够多的呼唤，那么这些批量可能变小).这里:二为第k批服务所用的时间. 对于成批输人与成批服务的系统可以有上面描述的那些服务规则. V.多服务台系统.在这些系统中服务可以在m)1条通道中同时进行，以便下一个呼唤(或在成批服务中下一批呼唤)可以在前一服务完成之前开始服务.多服务台系统的服务规则与所有已考虑过的服务类型类似(每一条通道起一个独立的服务机构的作用).只须补充说明当有”条通道同时空闲时呼唤选择哪个通道.像前面一样，:)为第i批(其批量簇。:)服务所用的时间. 对于一个多服务台系统，如果一个呼唤在其到达时刻发现所有通道皆繁忙而“损失”且因此离开系统，那么就称为损失制系统(1055哪tem). 有时，为了简化多服务台系统的控制序列的性质，不用两个而用爪+l个二维控制序列 (;认vl)，(;)l，v{.)，一，(::’，v)’)是方便的.这样，第k条服务通道被序列(可‘，，:‘)，k=1，·’·，水，控制.例如，;:‘为在第k条通道中第i批呼唤的服务时间. 以上的分类远未详尽.例如，有些具有广泛应用的系统中，呼唤被分成两类或更多类，其中一类相对于其他类具有服务优先权(这种情形出现于当一类呼唤的等待费用高于其他类时).对这种系统的刻画要求对应于不同类型的请求引人若千个输人流.与有优先权的系统有关的还有服务机构要求运行中断的系统.可以用特殊的输人流来刻画这种中断的出现和长度的规律. 在排队论(q坡讹止嗯t玩泊ry)文献中还讨论过其他特殊形式的服务系统.但在这里应记住: I)基本的与最通用类型的排队都包括在以上的分类中; 2)作为规律探讨各种系统的排队的方法大都很类似，而且用研究“基本”系统的方法很好地说明了;这些方法的基础无论从一般方面来说还是从特殊发展的方面来说都是概率论. 主要目的是探讨刻画系统行为的各种参数的分布(例如，队长，直到下一次服务为止的等待时间，给定呼唤的损失概率等等).在这一点上，主要感兴趣的是描述长时间之后这些特征行为的遍历定理.例如，描述自动电话交换机效率的一个特征是呼唤损失率，即当t~的时，时刻t为止损失的呼唤数r(t)与相同时间内到达的呼唤数。(t)之比r(t)/e(t)的极限p(若它存在).很合乎情理地称这个极限为损失概率(1。骆pm恤b正ty)，第n个呼唤的等待时间w。及第n个呼唤到达时刻的队长q。的分布p{叭x}=e一‘’，。>0. 记号{七，}“G，表示随机变量气为独立同分布的(分布可以是任意的).在形如{叮}〔E或{叮}‘玩的关系中，通常还假设控制序列{:了}不依赖于剩余控制序列. 狭义平稳序列类记为G: 这一记法也可以用于多维序列.例如，{:了，;;}“G，表示这二维序列是由平稳的且独立的向量组成. 通常为了简单起见，讨论局限于“单个”输入与输出过程，，歹”，}三l(呼唤单个出现与单个服务).推广到“多个”情形的可能性(呼唤成批出现或成批服务:可笋1或心笋l)分开讲述· 此外，如果排除初始条件，那么控制序列的性质将是简单和一致的.也就是说，如果考虑控制序列{:歹，::}，l簇j(‘，那么总假设q(0)二o且第一个呼唤在时刻瑞=O到达.如果控制是由输人过程e(t)来给定，那么瑞就不是固定的. 参考文献见排队论(que优止名也印印). A .A.B砚p旧xoB撰【补注】D .G.K治耐皿(〔A21)引进一套简短记法，用有关到洛卿呼时卿分布(描述过程{‘夕”，服务时间分布(描述过程{:夕冲和服务台数来描述各种不同的排队情况.在这个记法中符号M表示负指数分布(n睡笋石记expo皿ntialdis州bution)，H表示超指数分布(勿详此xponent润dis苗bution)(F(t)=0，t(0;F(￡)=艺二_。a。(l一e一‘“，)，:>o，又*>o，a*>o，a，+…+a。=1)，E表示D加心乡知节(B加吧曲颐b丽on)，D表示退化为一个正值的分布，K表示其Up】aCe-Stieltjes变换为有理函数的分布，G表示非负随机变量的一般分布.因此，M/G/1表示具有负指数到达间隔分布，一般服务时间分布和单服务台的排队.现在很普遍地使用这种记法.
　　

说明：补充资料仅用于学习参考，请勿用于其它任何用途。