资源描述：
《运筹学排队论课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第十章排队论(Queuingtheory)引言排队论的基本概念顾客到达数及服务时间的理论分布单服务台(M/M/1)排队模型多服务台的排队模型排队系统费用的优化模型§1引言排队是日常生活和经济领域中常见的现象.如顾客在邮局,银行排队办理业务,病人在医院排队就医,工厂中等待维修的机床,港口内等候卸货或进港的轮船,机场内等候起飞或降落的飞机,等等.这都是有形的排队现象.打电话时占线,需要等待,这是无形的排队现象.排队是怎样产生的?首先,我们把上述现象中的人或物,看做是被服务队象,他们希望得到某种服务,如果在某个时刻,要求服务的对象超过了服务机构所能提供的服务数量时就产生了排队现象.
2、要减少排队,可以增加服务设施,但是如果增加的太多,服务设施又会出现空闲浪费;如果服务设施少,顾客排队太长时,就会损失顾客也会造成很大损失.因此,决策者必须在服务对象和服务台之间取得平衡,达到一种最优配置.此外,在一些大型项目的设计中(港口泊位,机场跑道,电话线路等),也要根据排队理论作到超前设计,同时还要考虑费用的优化问题,这就是排队论研究的内容.排队论的创始人是丹麦哥本哈根市电话局的工程师爱尔朗(A.K.Erlang),他早期研究电话理论,特别是电话的占线问题,就是早期排队论的内容.§2排队论的基本概念一.排队现象的共同特征:为了获得某种服务而到达的顾客,如不能立即得到服务
3、而又允许排队等候,则加入等待的队伍,获得服务后离开.我们把包含这些特征的系统称为排队系统.排队系统的几种情况:1.单服务台排队系统服务台2.C个服务台,一个公共队伍服务台1服务台2服务台C3.C个服务台,C个队伍服务台1服务台2服务台C二.排队系统的三个组成部分1.输入过程:指顾客按怎样的规律到达.⑴顾客的总体数或顾客源:指可能到达服务机构的顾客总数.顾客总体数可以是有限的,也可以是无限的;⑵顾客到达的类型:顾客是单个到达还是成批到达;⑶顾客相继到达时间间隔的分布,如按泊松分布,定长分布还是负指数分布.2.排队规则:指顾客接受服务的先后次序问题⑴损失制:顾客到达时,服务台被占
4、用,顾客随即离去,不再接受服务;⑵等待制:服务台被占用,顾客排队等候.根据服务台对顾客服务的先后顺序又分为ⅰ.先到先服务;ⅱ.后到先服务;ⅲ.随机服务;ⅳ.优先权服务.⑶混合制:顾客起初排队,看到队伍太长又离去.3.服务机构:又称服务台⑴服务台的数目:有单服务台,多服务台;⑵任一时刻接受服务的顾客数;⑶服务时间的分布:对每个顾客的服务时间是随机变量,但是其概率分布多按负指数分布来处理,也有的服从定长分布.二.排队系统的描述符号及分类n:排队系统中顾客的数目:顾客到达的平均速率,即单位时间内到达的顾客数:系统的平均服务速率,即单位时间内可服务完的顾客数:在时刻t时系统中有n个顾
5、客的概率C:服务台的个数FCFS:先到先服务的排队规则LCFS:后到先服务的排队规则PR:优先权服务的排队规则M:到达过程为泊松过程或负指数过程D:定长型分布:k阶爱尔朗分布a:顾客到达过程的概率分布(输入)b:服务过程的概率分布(输出)d:排队系统的最大容量e:顾客总体的数量f:排队规则1953年由K.D.Kendall提出了排队模型记号方案,由a/b/c/d组成,即输入/输出/并联服务台数/顾客总体数量如:M/M/1/表示:排队系统中顾客到达是泊松过程,服务时间服从负指数分布,单服务台,顾客源无限.1971年国际排队符号标准会上将上述符号扩充到六项,即a/b/c/d/e/
6、f.如:M/M/1///FCFS)M/M/4/N//FCFS)§3顾客到达数及服务时间的理论分布在排队服务过程中,单位时间内顾客到达数,顾客到达时间间隔,服务时间都是随机变量,因此必须了解它们的概率分布.一.泊松流现将上式参数引入时间因素,即将换为,得到表示长为t的时间区间内到达n个顾客的概率为,且服从泊松分布.这称为泊松流或泊松过程或简单流.设t时间内到达的顾客数为随机变量N(t),则有二.负指数分布现在研究当输入过程是泊松流时,两顾客先后到达时间间隔T的概率分布.由可知,当n=0时即在[0,t]内没有顾客到达的概率为则至少有一个顾客到达的概率分布函数为相应的概率密度为三.
7、服务时间v的概率分布一般总是假定顾客接受服务的时间v也服从负指数分布负指数分布的一个重要特征是“无记忆性”，也称无后效性或马尔科夫性。这个性质为排队轮问题的求解带来了方便。如果输入分布或服务分布为负指数分布，则不论实际排队过程进行了多长时间，要研究从现在起以后的情况，只要考虑当前排队所处的状况就可以了，在此以前的情况可以不考虑，就好像过程刚开始一样。例9.1某仓库全天都可以进行发料业务，假设顾客到达的时间间隔服从均值为1的负指数分布现在有一位顾客正好中午12：00到达领料，试求：（1）下一个顾客将在下午
