系统仿真-第-3-章-排队系统

工业工程与管理系IndustrialEngineering&Management第三章排队系统§3-1排队论的基本概念§3-2到达时间间隔和服务时间的分布§3-3排队系统的分析§3-4排队系统的仿真工业工程与管理系IndustrialEngineering&Management日常生活中，排队现象无所不在•排队现象•排队现象的特征•排队问题解决的方法•排队问题研究的关键商店购物医院看病生产过程中，工位加工水库的蓄水电话交换机交通堵塞当某个时刻要求服务的动态实体数量超过服务机构的容量时，就会出现排队现象排队现象可以是人或是物排队系统中，顾客到达的时刻与接受服务的时间都是不确定的，随着不同时机与条件而变化，因此排队系统在某一时刻的状态也是随机的增加服务台的个数，即：增加服务设施的数量。增加服务设施所带来的问题：1）系统的投入成本增加，服务成本增加；2）设备的利用率降低，设备产生空闲浪费；3）服务设备太少，系统建设的投入减少了，但排队问题较为严重。排队问题研究的关键：在服务质量、服务成本中取得一个平衡。引言工业工程与管理系IndustrialEngineering&Management排队系统的基本组成•到达模式•服务机构•排队规则指动态实体(顾客)按怎样的规律到达，描写实体到达的统计特性。一般，动态实体的到达模式是符合概率统计的方式。在仿真处理过程中，通常假定顾客总体是无限的。指同一时刻有多少服务设备可以接纳动态实体，它们的服务需要多少时间。它也具有一定的概率分布特性。通常，假定系统的容量(包括正在服务的人数加上在等待线等待的人数)是无限的。指对下一个实体服务的选择原则。通用的排队规则包括先进先出(FIFO)、先进后出(FILO)、随机服务()、优先服务(PR)等3.1排队论的基本概念工业工程与管理系IndustrialEngineering&Management排队系统的基本结构服务离开排队到达动态实体以一定的到达模式来到服务机构请求服务，由于服务机构的服务设备有限，服务要有服务时间，因此某些动态实体来到服务机构之后不能马上得到服务，需要排队等待，当服务机构完成对某个动态实体的服务之后，就可接纳新的动态实体。排队规则将确定在队列中哪些动态实体可以最先得到服务。在很多实际问题中，动态实体的到达时间是随机的，服务机构的服务时间也是随机的，这样动态实体排队的长度也会是随机的，最后反映在服务机构处于“忙”或“闲”的时间也是随机的。如果通过已知的到达模式和服务时间的概率分布，来研究排队系统的队列长度和服务机构“忙”或“闲”的程度，即服务效率，这就是离散事件仿真所需要解决的问题。3.1排队论的基本概念工业工程与管理系IndustrialEngineering&Management到达模式的基本概念•平均到达间隔时间Ta：指在考虑模型的总时间T中，共到达n个顾客的情况下的比值。•平均到达速率λ：指单位时间内到达的顾客数•到达间隔时间的分布函数A0(t)：指到达间隔时间大于t的概率。因为累积分布函数F(t)是到达间隔时间小于t的概率，所以A0(t)=1-F(t)•到达时间变化系数：指到达间隔时间的标准差Sa与平均到达间隔时间Ta的比值nTTaaT1aaTS变化系数是个无量纲的值，它描述了数据围绕平均值的分散程度。指数分布的平均值与标准差相同，其变化系数为1。所以，如果观测数据的变化系数接近于1,则假定用指数分布去拟合这些数据是合理的。当变化系数比1小很多时,经常应用爱尔朗分布。3.1排队论的基本概念工业工程与管理系IndustrialEngineering&Management到达模式的注意点到达模式按顾客到来的方式可能是一个一个的，也可能是成批的；按相继到达的间隔时间可以是确定型的，也可以是随机型的；按到达过程可以是平稳的，指描述相继到达的间隔时间分布和所含参数(如期望值、方差等)都是与时间原点无关的，也可以是非平稳的。3.1排队论的基本概念工业工程与管理系IndustrialEngineering&Management服务机构的基本概念•平均服务时间Ts：指在考虑模型的总时间T中，共服务n个顾客的情况下的比值。•平均服务速率μ：指单位时间内服务的顾客数•服务时间的分布函数As(t)：指服务时间大于t的概率。因为服务累积分布函数Fs(t)是服务时间小于t的概率，所以As(t)=1-Fs(t)nTTssT13.1排队论的基本概念工业工程与管理系IndustrialEngineering&Management服务机构的基本形式12c......多队-多服务台（并列）排队系统12c...单队-多服务台（并列）排队系统12c...多服务台（串列）排队系统12c......12d多服务台（混合）排队系统3.1排队论的基本概念工业工程与管理系IndustrialEngineering&Management服务机构的注意点•按服务方式可以对单独顾客进行，也可以对成批顾客进行。•按服务时间可以是确定型的，也可以是随机型的；•按服务过程可以是平稳的，也可以是非平稳的。非平稳情形的数学处理是很困难的，所以同到达过程一样，服务时间的分布也假定是平稳的。3.1排队论的基本概念工业工程与管理系IndustrialEngineering&Management排队规则什么是排队规则？系统中的顾客依一定的次序和规则接受服务。排队准则主要有：•损失制•等待制•混合制指顾客到达时，如所有服务台都正被占用，随即离去。顾客决不排队。指顾客到达时，如所有服务台都正被占用，就排成队伍，等待服务。服务次序可以采用下列各种规则：1）先到先服务(FIFO)即按到达次序接受服务，这是最通常的情形。2）后到先服务(LIFO)如乘用电梯的顾客常是后入先出的，仓库中存放的钢板也是如此。在情报系统中，最后到达的信息往往是最有价值的，因而常采用后到先服务的规则。3）随机服务(GIRO)当服务台空时，从等待的顾客中随机地选取一名进行服务，而不管到达的先后，如电话交换台接通呼唤的电话便是如此。4）优先权服务(PR)如医院中急诊病人优先得到治疗。最短处理时间先服务(SPT)例如设备选择工件时,首先选择所需加工时间最少的工件进行加工例：对于n个服务台的情形，当顾客到达时，可按如下规则在每个服务台前排成一个队，第1,n+1,2n+1,...个顾客排入第一个队,第2,n+2,2n+2,...个顾客排入第二个队等等。或者所有顾客排成一个公共的队，每当有一个服务台得空闲时，队首的顾客接受服务。也可以这样来排成几个队，当某个顾客到达时，以概率排入第i个队，且满足。例如，当排队过长时，后到的顾客会自动离去，此时可定义队长qN时就排入队列；若q=N，则到达的顾客将自动离去。另一种是当等待时间或逗留时间(等待时间与服务时间之和)小于某一时间T时，顾客将等待p大于T时，顾客将自动离去。在使用优先权时，必须考虑当一个比现在正在接受服务的实体具有更高优先权级别的实体到达后，系统将作何处理。通常可有两种选择：其一，优先权仅仅决定一个动态实体排队的先后，优先权高的排在队列的前面，而不影响正在接受服务的实体。其二，立即停止当前的服务，为新到的具有更高优先权的实体服务，这种情形称为抢占服务，这时被抢占的实体等待新实体离开后再重新接受服务。3.1排队论的基本概念工业工程与管理系IndustrialEngineering&Management队列的度量已知平均到达速率λ和平均服务速率μ,定义业务量强度u为在某些场合下，到达的动态实体并不全都能够得到服务。因此有必要区分实际到达速率λ’以及得到服务的到达速率λ。此时的业务量强度u为u'u3.1排队论的基本概念工业工程与管理系IndustrialEngineering&Management服务设备利用率•服务设备利用率ρ定义为得到服务的动态实体的到达速率与服务速率之比：•在多服务设备系统中式中，n为服务设备数目，μ为每个服务设备的平均服务速率，这里假设每个服务设备的服务速率相同。显然在多服务设备系统中，服务员人数越少，服务设备利用率就越高。正常情况是服务设备利用率1，这样每个动态实体才有希望得到服务。利用率越高，则动态实体排队等待的时间越长。n3.1排队论的基本概念工业工程与管理系IndustrialEngineering&Management队列度量的观察量对于队列的度量，通常考察两个量：队列的长度和排队的时间这两个量都是变量，不同时间的队列长度是不同的，不同动态实体的排队时间也是不同的。在仿真实验中，对这两个量的变化进行统计，计算出其均值、方差、最大值、最小值等。这些值反映了一个服务系统的重要特征。3.1排队论的基本概念工业工程与管理系IndustrialEngineering&Management排队模型的分类（D.G.Kendall）•根据上述讨论的排队问题的三个组成部分：排队模式、服务机构、排队规则•中最主要的特征，D.G.Kendall提出一个分类方法，它只针对并列的服务设备的情形，用的符号形式是X/Y/Z其中，X——表示相继到达间隔时间的分布；Y——表示服务时间的分布；Z——表示并列的服务设备的数目。各种常见的分布符号是：M——负指数分布(M是Markov的字头，因为负指数分布具有无记忆性，即Markov性)。D——确定性(Deterministic)。Ek——k阶爱尔朗(Erlang)分布。GI——一般相互独立(GeneralIndependent)的随机分布。G——一般(General)随机分布。3.1排队论的基本概念工业工程与管理系IndustrialEngineering&Management排队模型的分类——例题M/M/1客户到达系统的间隔时间为负指数分布系统服务机构的服务时间为负指数分布系统并行的服务机构数量为1台表示的是单服务机构的服务系统，客户的到达以及服务时间均符合负指数分布。3.1排队论的基本概念工业工程与管理系IndustrialEngineering&Management排队模型的分类——例题D/M/2客户到达系统的间隔时间为确定的定长分布系统服务机构的服务时间为负指数分布系统并行的服务机构数量为2台（单队排队）表示的是并行双服务机构的服务系统，客户到达的时间间隔符合定长分布，服务时间符合负指数分布。3.1排队论的基本概念工业工程与管理系IndustrialEngineering&Management排队模型的分类——例题GI/G/1客户到达系统的间隔时间为一般相对独立分布系统服务机构的服务时间为一般分布系统的服务机构数量为1台表示的是单服务机构的服务系统，客户的到达时间间隔符合一般相对独立分布，服务时间符合一般分布。3.1排队论的基本概念工业工程与管理系IndustrialEngineering&Management引言实际问题收集顾客到达的时间间隔收集服务的时间统计值运用回归法等统计方法，计算得到到达模式分布的理论值运用回归法等统计方法，计算得到服务时间分布的理论值运用χ2检验理论结果的显著性计算分布的参数3.2到达时间间隔和服务时间分布工业工程与管理系IndustrialEngineering&Management几种常用的概率分布•定长分布：这是一种确定性的分布函数，是概率统计中最简单的情形，每个动态实体在相同的时间间隔到达，或每个动态实体的服务时间是常数，其分布函数为atattTPtA,1,00atattS,1,003.2到达时间间隔和服务时间分布工业工程与管理系IndustrialEngineering&Management几种常用的概率分布•泊松分布：如果动态实体到达的分布满足下列四个条件：–平稳性在区间内[a，a+t[有k个顾客到来的概率与a无关，而只与t，k有关，记此概率为Vk(t)；–无后效性不相交区间内到达的顾客数是相互独立的；–普通性令Ψ(t)为时间t内至少有两个顾客到达的概率，则：当t→0，Ψ(t)=0。–有限