下载文档原格式
第八章排队论排队（queue）是社会活动中经常遇到的现象，如顾客到商店购物，学生去图书馆借书，病人上医院看病，仪器等待维修等等，当售货员、图书管理员、医生和修理员的数量满足不了顾客或病人及时服务的需要时，就出现了排队等待的现象．由于接受服务的顾客数和服务时间的随机性，排队现象是不可避免的．当然增加服务能力可以减少排队现象，但这样势必增加投资，有时因供大于求造成资源浪费．因此，在这样一个排队系统中，作为管理人员不但需要了解排队等待服务的顾客数，等待服务时间长度，系统内服务设施的空闲率等数量指标的变化规律，而且需要在满足顾客服务基本要求的条件下，研究如何提高服务质量、降低排队系统运行成本等问题．排队论就是解决这类问题的一门科学．在排队系统中要求得到某种服务的对象统称为顾客（customer），为顾客服务者统称为服务台（service facility）．根据顾客和服务台的不同情况，组成不同的排队系统．本章研究的主要内容是排队系统的状态概率、队长、等待时间、服务时间、服务台利用效率等运行指标，以及排队系统的优化问题．第一节排队系统的基本概念一、排队系统的组成一个排队系统或称服务系统（service system），有三个基本组成部分：即输入过程（arrival process）、排队规则（queue discipline）和服务规则（service discipline）．图8-1给出了排队系统的一般结构．1．输入过程：指顾客到达排队系统的规律，可用到达时间间隔或单位时间内顾客到达数的概率分布来描述；按到达的时间间隔分有确定的时间间隔和随机的时间间隔；按顾客到达的方式有单个到达和成批到达；从顾客源总体看，分有限源总体和无限源总体．2．排队规则：排队系统一般分为等待制、损失制和混合制．(1) 等待制 顾客到达系统时，如果服务台没有空闲，则顾客排队等候服务．等待制服务的方式有：① 先到先服务（first come first service ，FCFS ）：按顾客到达先后给予服务，这是最常见的服务规则．② 后到先服务（last come first service ，LCFS ）：如情报收集中最后到达的信息最有价值，往往最先采用．③ 优先权服务（priority ，PR ）：如医院对危重病人给予优先治疗．④ 随机服务（service in random order ，SIRO ）：排队系统随机抽取等待服务的顾客．(2) 损失制 顾客到达系统时，如果服务台没有空闲，则顾客离去，另求服务．如没有足够医生或医疗器械救治急诊患者，医院药物、卫生材料暂缺等．(3) 混合制 它是介于等待制和损失制之间的形式．方式有：① 队伍长度有限，当队伍的长度小于N 时，新到顾客就排队等待；当队伍长度为N 时，新来顾客离去．如患者住院所需要的病床数有限就属此类．② 等待时间有限，新到顾客排队等候服务，一段时间后仍未得到服务，顾客离去．例如医院血库的血浆、生物制剂等．③ 逗留时间（等待时间与服务时间之和）有限，顾客在系统中的逗留时间不得超过确定的时间．例如药品的有效期．3．服务机构：指排队系统中服务台的个数、排列及服务方式．排队系统中服务台的个数可以是一个或多个．多个服务台可以是串联或并联．排列结构大体有：(1) 单服务台、单列图8-2输出(2) 多服务台、单队列（多队列）(3) 多服务台串列(4) 多服务台混合医院里的CT室就是(1)的例子，口腔科、理疗室就是(2)的例子，先挂号候诊再住院手术就是(3)或(4)的例子．服务方式上有单个服务，也有成批服务的，如医院里的上下电梯．二、排队系统的评价指标排队论研究的问题，可以分成两大类，第一类问题是在服务设施设置之前，根据顾客输入过程与服务过程的要求，结合对系统的一定数量指标与服务过程要求（如规定服务质量的必需水平），确定服务设施（如诊断室、检验科、供应中心等等）的图8-3图8-4图8-5…图8-6规模；第二类问题是对已有的服务系统施以最优控制，改进和提高排队系统工作效率．排队系统的数量指标主要有：1．单位时间内到达的顾客数的期望值，即单位时间内的平均到达率，记作λ．而λ1表示相邻两个顾客到达的平均间隔时间．2．单位时间内服务的顾客数的期望值，即单位时间内顾客的平均离去率，记作μ．同样，μ1表示每个顾客的平均服务时间．3．在时刻t时排队系统中恰有n个顾客的概率()tPn ，显然()tP为系统空闲率．4．系统内的平均顾客数称为队长（queue length），记作L．5．系统内排队等待服务的平均顾客数称为等待队长，记作qL．6．顾客从进入系统到接受完服务后离开系统的平均时间称为平均逗留时间，记作W．7．顾客在系统内排队等待服务的平均时间称为平均等待时间(waiting time)，记作qW．三、排队模型的符号表示由于排队系统的特征可以有许许多多的组合，从而形成不同的排队模型．本章采用A/B/C/m/N形式表示不同排队模型．其中：A——顾客到达间隔时间概率分布B——服务时间的概率分布C——服务台数m——顾客源总数N——系统内顾客的容量例如：M/M/ 1 / ∞/ 12排队模型的特点是：顾客到达间隔时间和服务时间均服从负指数分布（M指负指数分布，具有无记忆性，即Markov性），单服务台，顾客来源总体数无限，系统的顾客容量为12．四、排队系统的常见分布顾客到达和离开分别构成排队系统的输入与输出过程流．到达分布和离开分布确定了到达系统和离开系统的顾客数这两个随机变量的分布．求解排队系统有关数量指标问题，首先要确定顾客到达流的概率分布，即在一定的时间间隔内来n 个顾客的概率是多大．其次是要确定顾客离开流的概率分布，即在一定的时间内服务完m 个顾客的概率是多大．实际问题研究中，可根据原始资料测算顾客在单位时间平均到达流的经验分布，然后按照统计学的方法（例如，2χ检验法）确定资料适合于哪种理论分布，并估计理论分布的参数值，这是确定排队模型的前提．1．泊松分布（Poisson distribution ）在排队论中，最基本的排队模型是在给定时间内到达系统的顾客数服从泊松分布，即顾客到达流是泊松流（也称最简单流）．它具有如下性质：(1) 平稳性：在时间+t △t 内，到达n 个顾客的概率只与△t 和n 的大小有关，而与时刻起点t 无关．(2) 无后效性：在时间+t △t 内到达n 个顾客的概率与起始时刻之前到达多少个顾客无关．(3) 普通性：对于充分小的时间间隔△t ，在时间+t △t 内最多有一个顾客到达系统．即在时间+t △t 内有2个或2个以上顾客到达的概率极小，有()0lim2=∆+∑∞=→∆t t P n nt可以证明，在长为t 的时间内到达n 个顾客的概率为：()(),2,1,00!)(=>=-n t e n t t P tn n λλ （8-1）当1=t 时，即单位时间内到达n 个顾客的概率为：()λλ-==e n P P nn n !1其中λ为单位时间内到达系统的顾客的期望值． 2．负指数分布(negative exponential distribution )理论上可以证明若顾客在单位时间内到达系统的个数X 是服从参数为λ的泊松分布，则顾客到达系统的间隔时间T 服从参数为λ的负指数分布，反之亦然．即同一随机过程可从两种不同的角度用两种分布来描述．负指数分布的概率密度为：)0()(>=-t e t f tT λλ间隔时间T 的期望值。
