(精品)(第十章)排队论.ppt

《(精品)(第十章)排队论.ppt》由会员分享，可在线阅读，更多相关《(精品)(第十章)排队论.ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Chapter TwelveQueueing Theory/Waiting Line Models排队论当顾客想要一项服务，而服务器又在忙，所以不得不等候时就形成排队排队n排队n 有形排队：乘客在车站等车，病人排队看病，顾客在超市排队付款，等等n无形排队：电话呼叫，计算机中程序或指令的处理n任何等待一项服务的人或物称为顾客顾客n任何提供这项服务的人或物称为服务器服务器n以顾客排队的时间来评判服务的质量n排队问题无法完全消除。通过增加服务器或提高服务速度可减少排队现象，但这样又会增加成本。n管理排队问题时，需要在服务器数量服务器数量与成本成本之间求得平衡排队系统 顾客到达服务器服务后离去排队排队

2、系统n系统输入：顾客按怎样的规律到达系统n顾客总体数：有限？无限？n顾客到达方式：单个？成批？n顾客到达的间隔：确定的？随机的？n排队与服务规则n排队：单队？多队？(每个服务器前排一队)n服务规则：FCFS(先到先服务)？LCFS(后到先服务)？SIRO(随机服务)？PR(有优先权的先服务)？n服务器n服务器的数量：单台？多台？n服务器的结构形式：串联？并联？n服务方式：单个？成批？n服务时间：确定的？随机的？排队系统的数量指标n用几个数量指标描述排队系统的状况，从而反映服务水平的优劣n平均排队的顾客数Lqn系统中的平均顾客数Lsn一位顾客的平均排队时间Wqn一位顾客在系统中的平均逗留时间Ws

3、n系统中没有顾客的概率P0n顾客必须排队等待的概率Pqn系统中有n个顾客的概率Pn值越大，顾客 越不满意M/M/1/FCFS顾客随机到达(泊松到达)单位时间顾客到达的平均人数为 (平均到达速度)随机服务时间(负指数服务时间)单位时间服务的顾客的平均人数 (平均服务速度)否则队会越来越长，系统永远达不到稳态 称为服务强度或服务器的利用率单台服务器排队长度无限制顾客来源无限制先到者先服务单队系统中没有顾客的概率平均排队的顾客数系统中的平均顾客数一位顾客的平均排队时间一位顾客在系统中的平均逗留时间顾客必须排队等待的概率系统中有n个顾客的概率举例(储蓄所的排队系统)每分钟平均到达人数 ，每分钟平均服务

4、人数 ，该系统的主要指标为：系统中的顾客数概率01234567或7以上25%18.75%14.06%10.55%7.91%5.93%4.45%13.35%改进排队系统方法一：提高服务速度方法二：增加一台服务器(2队)M/M/c/FCFS多台服务器，服务器数量为c顾客随机到达(泊松到达)平均到达速度随机服务时间(负指数服务时间)每台服务器的平均服务速度 ，其中 称为服务强度或服务器的利用率排队长度无限制顾客来源无限制先到者先服务单队顾客到达服务器1服务后离去排队多台服务器的排队系统服务器2服务器3主要数量指标公式举例(储蓄所的排队系统)2 台服务器，2队2 台服务器，排1队相同的成本，不同的服务

5、水平举例n某理发店有若干名理性师，并有足够的位置接待人们排队等待理发。顾客到达间隔服从参数为10(人/小时)的负指数分布，每名顾客的理发时间服从均值为20分钟的负指数分布。理发店经理希望确定满足下述两个条件的理发师人数：1.理发店的利用率不低于60%；2.一个顾客的平均等待时间少于5分钟n这是M/M/c的排队模型，其中 c待定 利用率：4c5.56 当c=4时，Wq=0.329小时=19.74分钟 当c=5时，Wq=0.065小时=3.9分钟故满足上述两个条件的理发师人数为5人排队系统的优化设计n设计一个未来的排队系统，使系统的总费用最小。n以稳态系统单位时间的平均总费用来计量n单位时间系统的

6、平均总费用=单位时间的服务费用+单位时间顾客的等待费用(损失)cs 每台服务器单位时间的服务费用 c 服务器的数量 cw 每个顾客等待单位时间的费用 Ls 系统中的顾客数量 即：系统才能实现稳态故对所有满足上述条件的c的取值，计算相应的总费用，找出费用最小的c值多服务器模型中的最优服务器数量c*单服务器模型中的最优服务率设单位时间的服务费用与平均服务率 成正比，即：，其中 为当 =1时单位时间的服务费用举例每个顾客单位时间成本为20，单个服务器单位时间成本为10，最优服务器数量为多少？服务器数量 服务器成本 顾客成本总成本44090.57130.5755067.08117.0866060.98

7、121.9877060.56130.56举例n货船按泊松流到达某一港口，平均到达率为每天50艘。港口的卸货时间服从负指数分布，平均卸货率为 ，每天卸货费用为1000 元。又知货船在港口停泊一天的滞期费为500元。问港口的最优卸货率。最优平均卸货率为：举例n某设备修理站打算在甲、乙、丙三名工人中聘用一人。甲要求工资每小时15元，他每小时平均能修理4台设备；乙要求工资每小时12元，他每小时平均能修理3台设备；丙要求工资每小时18元，他每小时平均能修理5台设备。一台设备停留在修理站一个小时修理站要支付6元。已知送来修理的设备为泊松流，平均每小时2台。三名工人修理机器的时间均服从负指数分布。问修理站应聘用哪位工人？n费用函数为：TC=Cs+Cw Ls 对于甲工人：对于乙工人：对于丙工人：因此，修理站应聘用甲工人其它排队模型n单服务台泊松到达、任意服务时间的排队模型(M/G/1)适用于服务时间的概率分布不明确的情形n单服务台泊松到达、定长服务时间的排队模型(M/D/1)适用于一些自动控制的设备n多服务器泊松到达、任意的服务时间、损失制排队模型(例如，电话订票系统)n 有限客源的排队模型 顾客总数是有限的，只有m个顾客，每个顾客来到系统中接受服务后仍回到原来的总体，还有可能再来。典型例子：机器看管维修问题n系统容量有限制的排队模型