第六章排队论模型课件.ppt

一、排队系统的组成与特征 排队系统一般有三个基本组成部分：1.输入过程；2.排队规则；3.服务机构。如下图所示： 1、输入过程 这是指服务台从队列中选取顾客进行服务的顺 序。可以分为损失制、等待制、混合制3大类。 (1)损失制。这是指如果顾客到达排队系统时， 所有服务台都已被先来的顾客占用，那么他们就自 动离开系统永不再来。 典型例子是，如电话拔号后出现忙音，顾客不 愿等待而自动挂断电话，如要再打，就需重新拔 号，这种服务规则即为损失制。 (2)等待制。指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。 例如，排队等待售票，故障设备等待维修等。 等待制中，服务台在选择顾客进行服务时，常有如下四种规则： ①先到先服务（FCFS ）。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。 ②后到先服务（LCFS）。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。 ③随机服务(RAND) 。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。 ④优先权服务(PR)。如老人、儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。 (3)混合制．这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种： ① 队长有限。当排队等待服务顾客人数超过规定数量时，后来顾客就自动离去，另求服务，即系统的等待空间是有限的。例如最多只能容纳N个顾客在系统中，当新顾客到达时，若系统中的顾客数(又称为队长)小于N，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。再如水库的库容是有限的，旅馆的床位是有限的。 ② 等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客自动离去，不再回来。 如易损坏的电子元器件的库存问题，超过一定存储时间被自动认为失效。 又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。 ③ 逗留时间(等待时间与服务时间之和)有限。 例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。 不难注意到，损失制和等待制可看成是混合制的特殊情形，如记c为系统中服务台的个数，则当K=c 时，混合制即成为损失制；当K=∞时，混合制即成为等待制。 3、服务台 排队问题求解(主要指性态问题) 求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标，估计服务质量，确定系统的合理结构和系统参数的合理值，以便实现对现有系统合理改进和对新建系统的最优设计等。 排队问题的一般步骤： 1、确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布(可实测)。 2、研究分析排队系统理论分布的概率特征。 3、研究系统状态的概率。系统状态是指系统中顾客数,用n表示。状态概率用Pn(t)表示,即在t时刻系统中有n个顾客的概率，也称瞬态概率。 求解状态概率Pn(t)方法是建立含Pn(t)的微分差分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般求出确定值比较困难，即便求得一般也很难使用。因此常常使用它的极限(如果存在的话)： 4、根据排队系统对应的理论模型求用以判断系统运行优劣的基本数量指标的概率分布或特征数。 数量指标主要包括: (1)平均队长(Ls):系统中的顾客数(包括被服务和正在排队的顾客)。 平均队列长(Lq):系统中排队等待服务的顾客数。 系统中顾客数Ls =系统中排队等待服务的顾客数Lg +正被服务的顾客数c (2)平均逗留时间(Ws):指一个顾客在系统中的停留时间(含等待时间和被服务时间)。 平均等待时间(Wq):一个顾客在系统中排队等待的时间。 (3)平均忙期(Tb)：指从顾客到达空闲服务机构起到服务机构再次为空闲这段时间平均长度。(忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标，忙期关系到工作强度) 输入过程与服务时间的分布 生灭过程 将n=1,2,3…代入（6）得： ∴ ………(6) (注意利用(5)式) 凑成Pn(t)e?t两项乘积的微分 两边积分 如此继续递推下去得： ∴ （2个顾客到达的概率） （n个顾客到达的概率） 即随机变量N(t)=n服从泊松分布。它的数学期望和方差为： ∴ （1个顾客到达的概率） 引入级数 ∴ 令k=n-1，则：