第十二章 排队论(运筹学-上海电力学院,施泉生.ppt

记 N(t)：时刻t(t?0)的系统状态； pn(t)：时刻t系统处于状态n的概率； S：排队系统中并行的服务台数； ?n：当系统处于状态n 时，新来的顾客的平均到达率（单位时间内到达的平均顾客数）； ?n：当系统处于状态n 时，整个系统的平均服务率（单位时间内可以服务完的平均顾客数）； 当?n为常数时记为?；当每个服务台的平均服务率为常数时，记每个服务台的服务率为?，则当n ? s 时，有?n=s?。因此，顾客相继到达的平均时间间隔为1/ ?，平均服务时间为1/ ?，令?= ?/ s?，则?为系统的服务强度。 pn(t)称为系统在时刻t的瞬间分布，一般不容易求得，同时，由于排队系统运行一段时间后，其状态和分布都呈现出与初始状态或分布无关的性质，称具有这种性质的状态或分布为平稳状态或平稳分布，排队论一般更注意研究系统在平稳状态下的性质。 排队系统在平稳状态时一些基本指标有： Pn :系统中恰有n个顾客的概率； L：系统中顾客数的平均值，又称为平均队长； Lq：系统中正在排队的顾客数的平均值，又称为平均排队长； T：顾客在系统中的逗留时间； W=E(T) ：顾客在系统中的平均逗 留时间； Tq：顾客在系统中的排队等待时间； Wq=E(Tq)：顾客在系统中的平均 排队等待时间。 排队论研究的基本问题： 通过研究主要数量指标在瞬时或平稳状态下的概率分布及数字特征，了解系统运行的基本特征。 统计推断问题：建立适当的排队模型是排队论研究的第一步，建立模型过程中，系统是否达到平稳状态的检验；顾客相继到达时间间隔相互独立性的检验，服务时间的分布及有关参数的确定等。 排队研究的基本问题： 系统优化问题：又称为系统控制问题或系统运营问题，其基本目的是使系统处于最优的或最合理的状态。包括：最优设计问题和最优运营问题。 M/M/S 等待制排队模型 单服务台问题，又表示为M/M/1/ ? ：顾客相继到达时间服从参数为?的负指数分布；服务台数为1；服务时间服从参数为?的负指数分布；系统的空间为无限，允许永远排队。 队长的分布 记 Pn=p{N=n} , n=0,1,2….为系统达到平衡状态后队长的概率分布， 则 ?n=?；?n= ?，?= ?/?1， 有Pn= (1-?)?n n=0,1,2…. 几个数量指标 平均队长： L= ?n Pn= ? n (1-?)?n= ?/ (1-?) = ?/(?- ?) 平均排队长： Lq= ?(n-1) Pn= ?2/ (1-?)= ?2/ ?(?- ?) 几个数量指标 平均逗留时间： W=E(T)= 1/(?- ?) 平均等待时间： Wq= ?/ ?(?- ?) 它们之间有关系： L= ? W Lq= ? Wq Little公式。 例12-3：考虑一个铁路列车编组站。设待编列车到达时间间隔服从负指数分布，平均每小时到达2列；服务台是编组站，编组时间服从负指数分布，平均每20分钟可编一组。已知编组站上共有2股道，当均被占用时，不能接车，再来的列车只能停在站外或前方站。求在平衡状态下系统中列车的平均数；每一列车的平均逗留时间；等待编组的列车平 * * 第十二章 排队论 引 言 排队论是研究排队系统（又称随机服务系统）的数学理论和方法，是运筹学的一个重要分支。 有形排队现象：进餐馆就餐，到图书馆借书，车站等车，去医院看病，售票处售票，到工具房领物品等现象。 无形排队现象：如几个旅客同时打电话订车票；如果有一人正在通话，其他人只得在各自的电话机前等待，他们分散在不同的地方，形成一个无形的队列在等待通电话。 排队的不一定是人，也可以是物。如生产线上的原材料，半成品等待加工；因故障而停止运行的机器设备在等待修理；码头上的船只等待装货或卸货；要下降的飞机因跑道不空而在空中盘旋等。 当然，进行服务的也不一定是人，可以是跑道，自动售货机，公共汽车等。 顾客——要求服务的对象。 服务员——提供服务的服务者（也称服务机构）。 顾客、服务员的含义是广义的。 排队系统类型： 服务台 顾客到达 服务完成后离开 单服务台排队系统 排队系统类型： 服务台2 顾客到达 服务完成后离开 S个服务台，一个队列的排队系统 服务台s 服务台1 排队系统类型： 服务台2 顾客到达 服务完成后离开 S个服务台， S个队列的排队系统 服务台s 服务台1 服务完成后离开 服务完成后离开 排队系统类型： 服务台1 顾客到达 离开 多服务台串联排队系统 服务台s 排队系统