第十章 排队论.ppt

第十章 排队论 第一节 引言 一、排队系统的特征及排队论 排队论研究排队系统的数学理论和方法， 是运筹学的一个重要分支。 排队问题表现： 食堂排队，买车票，以及无形排队系统 排队问题的时间特性 排队系统的一般描述; 顾客为了得到服务而到达系统，如果不能 立刻得到服务而又允许排队等待，则加入 等待队伍，待获得服务后离开系统。 二、排队系统的描述 1、输入过程：说明顾客按照怎样的规律到达系统。 (1)顾客总体数：按顾客源顾客的数量，可分为有限顾客源和无限顾客源； (2)按顾客到达的形式，分为单个到达和成批到达； (3)按顾客相继到达的时间间隔分布，可分为 定长分布[D]：顾客相继到达的时间间隔为确定性的常数。 最简流（poisson流） [M]：顾客相继到达的时间间隔{X(n)}独立的，同负指数分布： 2、排队及其规则 （1）排队 分为有限排队和无限排队。 无限排队：系统空间无限；又称为等待制排队系统。 有限排队：系统空间有限；又分为： a.损失制：排队空间为零的系统，不允许排队；到达的顾客有一部分未接受服务就离去； b. 混合制：损失制和等待制系统的结合；顾客到达后，一直等到服务完毕以后才离去；不允许队列无限等待。又分为: (i)队长有限：系统等待空间有限。 有限系统的空间为K, 顾客到达时的队长为L。若LK，则顾客进入队列等待服务，若L=K，则顾客离去。 (ii)等待时间有限： 顾客对等待时间具有不耐烦性的系统。设最长等待时间是T0，某个顾客从进入队列后的等待时间为T。若TT0，顾客继续等待；若T=T0，则顾客脱离队列而离去。 (iii)逗留时间：等待时间与服务时间之和。 损失制和等待制可认为混合制的特殊形式。s为系统服务台的个数，当k=s，混合制为损失制；当k=? ，为等待制； 作业：10.1 预习第11章 例 一个铁路列车编组站，设待编列车到达时间间隔服从负指数分布，平均到达2列/h；编组时间服从负指数分布，平均每20min可编一组。已知编组站上共有2股道，当均被占用，不能停车，再来的列车只能停在站外或前方站。 求在平稳状态下系统的列车的平均数； 每一列的平均停留时间； 等待编组的列车平均数。 如果列车因为站内的2股道均被占用而停在外面。每列车的费用为a元/h，求每天由于列车在站外等待而造成的损失。 问题：编组站上共有2股道？ 解：M/M/1/ ? ?=2; ?=60/20=3, ?= ?/ ?=2/31 1.系统的平均停车数 2.列车在系统的平均停留时间（Little） 3.系统内等待编组的列车平均数（Little） 4.列车系统内平均等待编组的时间（Little） 5.列车平均延误（站内2股道均被占用不能进入车站）时间为W0 列车由于等待 而支出的费用 E=24 ? W0a =14.2a 例 某修理店只有一个修理工，来修理的顾客到达过程为poisson流，平均4人/h，修理时间服从负指数分布，平均需要6min. 1.修理店空闲的概率； 2.店内恰好有3个顾客的概率； 3.店内至少1个顾客的概率； 4.在店内的平均顾客数； 5.每位顾客在店内的平均逗留时间； 6.等待服务的平均顾客数； 7.每位顾客平均等待服务时间； 8.顾客在店内等待时间超过10min的概率。 解：M/M/1/ ? ?=4; ?=60/6=10, ?= ?/ ?=4/101 1.修理店空闲的概率 P0=1- ?=1-2/5=0.6 2.修理店内有3位顾客的概率 3.修理店内有至少1位顾客的概率 4.修理店内平均顾客数量 5.修理店内顾客平均逗留时间 6.修理店内等待服务平均顾客数量 7.修理店内每位顾客等待服务时间 8.修理店内顾客逗留时间超过10min的概率 二、多服务台模型 M/M/s模型是研究单队、并列的多服务台排队系统。如同单服务台系统一样，分为以下几种情况进行讨论： (1)标准的M/M/s/∞/∞/FCFS模型； (2)系统容量有限的M/M/s/N/∞/FCFS模型； 标准的M/M/s/∞/∞/FCFS模型 顾客到达后，进入队列尾端；当某一个服务台空闲时，队列中的第一个顾客即到该服务台接收服务， ?n= ?,n=0,1,2,3… ；服务完毕后随即离去,各服务台互相独立且服务速率相同，即μ1=μ2=…=μs =μ 。 μn = nμ,n=1,2,3,…s su,n=s,s+1,s+2,… 整个系统的最大服务速率为sμ ,服务强度： 则当ρs＜1时系统才不会排成无限的队列。 这个系统的特点是，系统的服务速率与系统中的顾客数有关。当系统中的顾客数k不大于服务台个数，即1≤k≤s时，系统中的顾客全部在服务台中，这时系统的服务速率为kμ；当系统中的顾客数k＞s时，服务台中正在接受