运筹学第14章排队论.ppt

第十四章　排队论 1、排队的组成及基本概念 2、生灭过程 3、六个排队模型 第十四章　排队论 排队是日常生活中经常遇到的现象，如顾客到商店去买东西，病人到医院去看病，当售货员、医生的数量满足不了顾客或病人及时服务的需要时，就出现了排队的现象。 出现这样的排队现象，使人感到厌烦，当然增加服务设施（如售货员、医生）能减少排队现象，但这样势必增加投资又因供大于求使设施常常空闲、导致浪费。 作为管理人员，就要研究排队问题，把排队时间控制在一定的限度内，在服务质量的提高和成本的降低之间取得平衡，找到适当的解。 如果顾客相继到达的时间间隔是确定的，如自动装配线上装配的各部件就必须按确定的时间间隔到达装配点；服务每一个顾客的时间也是确定的，如自动冲洗汽车的装置对每辆汽车冲洗的时间是确定的。 对于这类服务系统的设计计算比较方便。 但在大多数的服务系统中，情况不是这样。顾客的到达经常是随机的，并且服务设施用于每个顾客身上的服务时间往往也是随机的。对于这样一类随机服务系统的计算就要复杂得多。 排队论(Queuing Theory)又称随机服务系统理论(Random Service System Theory)，是研究排队系统的数学理论和方法，是运筹学的一个重要分支。 一般来说，排队论所研究的排队系统中，顾客相继到达时间间隔和服务时间这两个量中至少有一个是随机的。 具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制的问题。 一、基本概念 一些排队系统的例子 排队系统 顾 客 服务台 服 务 电话系统 电话呼叫 电话总机 接通呼叫或取消呼叫 售票系统 购票旅客 售票窗口 收款、售票 设备维修 出故障的设备 修理工 排除设备故障 防空系统 进入阵地的敌机 高射炮 瞄准、射击，敌机被击落或离开 排队的过程可表示为： 排队过程的组成部分 实际中的排队系统各有不同，但概括起来都由三个基本部分组成：输入过程、排队及排队规则、服务机制 1、输入过程 输入过程说明顾客按怎样的规律到达系统，需要从以下三个方面来刻画一个输入过程。 （1）顾客总体数，又称顾客源、输入源。顾客源可以是有限的，也可以是无限的。如到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。 （2）顾客到达的形式。单个到达，还是成批到达。如大学生到图书馆借书是单个到达，而购买的材料入库则可以看成成批到达。 （3）顾客流的概率分布，即单位时间内到达的顾客数，也可用顾客相继到达的时间间隔描述。这是刻画输入过程的最重要的内容。排队论中常用到的分布： 定长分布(D)，这种分布顾客相继到达的时间间隔是确定的，如产品通过传送带进入包装箱就是定长分布的例子。 泊松流(M) ： 1）在一定时间区间内，恰好到达k个顾客的概率仅与区间长度有关，而与区间起始时刻无关。即在时间区间[0，t]或[a，a+t]内，恰好到达k个顾客的概率相等。 2）在不相交的时间区间内到达的顾客数是相互独立的。或者说在时间区间[a，a+t]内来到k个顾客的概率与时刻a之前来到多少个顾客无关。 3）在足够小的时间区间内只能有一个顾客到达，不可能有两个以上顾客同时到达。单位时间里有x个顾客到达的概率为： 其中，λ为单位时间平均到达的顾客数，此时顾客相继到达的时间间隔是独立的，服从参数为λ的负指数分布。 2、排队规则 （1）排队系统 排队分为有限排队和无限排队两类。前者是指系统的空间是有限的，当系统被占满时，后面再来的顾客将不能进入系统；后者是指系统中的顾客数可以是无限的，队列可以排到无限长，顾客到达后均可进入系统排队或接受服务。具体又分为以下三种。 1）等待制。即无限排队。 2）损失制。这种系统是指排队空间为零的系统，实际上是不允许排队。当顾客到大系统时，如果所有服务台均被占用，则自动离去，并不再回来，这部分顾客就被损失掉了。 3）混合制。该系统是等待制和损失制系统的结合，一般是指允许排队，但又不允许队列无限长下去。 （2）排队规则 先来先服务(FCFS) 后来先服务(LCFS)，在许多库存系统中会出现