运筹学排队论山东大学期末考试知识点复习

1、第十二章 排队论 1排队 一般的排队系统都有3个基本组成部分：输入过程，排队规则，服务机构。 输入过程： (1)顾客源的组成可能是有限的也可能是无限的。 (2)顾客到达的方式可能是一个一个的，也可能是成批的。 (3)顾客相继到达的间隔时间可以是确定的，也可以是随机的。 (4)顾客之间到达可以是相互独立的或关联的。 (5)输入过程可以是平稳的，或称对时间是齐次的，即指间隔时间的分布和所含参数均与时间无关，否则称为非平稳的，不过一般总假定是平稳的。 2三种排队规则 (1)损失制：顾客到达后发现服务台正被占用，则离去。 (2)等待制：顾客到达后发现服务台正被占用，排队等侯。 等待制的服务规则：先到先

2、服务；后到先服务；随机服务；有优先权服务。 (3)混合制：是等待制和损失制相结合的一种排队服务规则。有两种： 队长有限制的情况，即当顾客排队等待服务的人数超过规定数量时，后来的顾客就自动离去，另求服务。 排队时间有限制的情况，当顾客排队时间超过一定时间时，顾客就自动离去。 服务机构情况：服务机构可以从下述几个方面来描述。 服务台数量及布置形式。从数量上来看，是单服务台还是多服务台，在多服务台的情况下，是串列的还是并列的，或是串、并列结合的，如图121所示。 在某一时刻接受服务的顾客数，即每个服务台每次对单个顾客还是成批顾客。 服务时间分布，服务时间和顾客来到时间一样，多数情况下是随机的。 常见

3、的分布有：泊松分布，负指数分布，爱尔朗分布等。 3排队模型有关指标与记号 (1)系统状态指一个排队服务系统中顾客数(包括正在被服务的顾客数)； (2)队长指系统中等待服务的顾客数，它等于系统状态减去正在被服务的顾客数； (3)N(t)在时刻t排除服务系统中的顾客数，即系统在时刻t的瞬时状态； (4)Pn(t)在时刻t系统中恰好有n个顾客的概率； (5)n当系统中有n个顾客时，新来顾客的平均到达率(单位时间内新顾客的到达数)，当对所有n值n为常数时，可用代替n； (6)n当系统中有n个顾客时，整个系统的平均服务率(单位时间内服务完毕离去的顾客数)，当n1，n是常数时，可用代替n； (7)S排队服

4、务系统中并联的服务站个数； (8)稳态当一个排队服务系统开始运转时，系统状态很大程度上取决于系统的初始状态和运转经历的时间，但过了一段时间后，系统的状态将独立于初始状态及经历的时间，这时称系统处于稳定状态。由于对系统的瞬时状态研究分析起来很困难，所以排队论中主要研究系统处于稳定状态的工作情况。由于稳定状态时工作情况与时刻t无关，这时Pn(t)可写为Pn，N(t)可写为N。 4常见排队模型 (1)标准的MM1模型(MM10000)。 标准的MM1模型是指适合下列条件的排队系统： 输入过程顾客源是无限的，顾客单个到来，相互独立，一定时间的到达数服从泊松分布，到达过程已是平衡的。 排队规则单队，且对

5、队长没有限制，先到先服务。 服务机构单服务台，各顾客的服务时间是相互独立的，服从相同的负指数分布。在系统中的平均顾客数(队长期望值)在队列中等待的平衡顾客数(队列长期望值)关于顾客在系统中逗留的时间W(随机变量)，在MM1情形下，它服从参数为的负指数分布，即 于是得，在系统中顾客逗留时间的期望值在队列中顾客等待时间的期望值(2)系统容量有限制的情况下(MM1N)。如果系统的最大容量为N，对于单服务台的情形，排队等待的顾客最多为N-1，在某时刻一顾客到达时，如系统中已有N个顾客，那么这个顾客就被拒绝进入系统。当N=1时为即时制的情形；当N，为容量无限制的情形。若只考虑稳态的情形，可作各状态间概率强度的转换关系图，见图122。根据图122，列出状态概率的稳态方程：解差分方程已知 P0+P1+PN=1令=，因而得可以导出系统的各种指标(计算过程略)：(3)顾客源为有限的情形(MM1m)。对于(MM1m)模型的分析可用前述的方法。各状态间的转移差分方程：解这差分方程，用递推方法，并注意到求得系统的各项指标为 5排队系统的随机模拟法 当排队系统的到达间隔时间和服务时间的概率分布很复杂或不能用公式给出时，就不能用解析法求解，这就需要用随机模拟法求解。 随机模拟法首先要求事件能按历史的概率分布规