《【大学课件】QuickPass系统排队问题.ppt》由会员分享，可在线阅读，更多相关《【大学课件】QuickPass系统排队问题.ppt（54页珍藏版）》请在三一文库上搜索。
1、QuickPass系统 排队问题,http:/ 尤其是在我们这样的人口大国,电话亭1978年在北京15%的电话要在1小时后才能接通。在电报大楼打电话的人还要带着午饭去排队 银行窗口，ATM 医院、理发、火车售票 游乐场的游乐项目,?,http:/ 会极为扫兴 DisneyLand中 的FastPass (QuickPass)系统 就是想解决这 个问题的,http:/ is QuickPass?,工作原理： 到达的顾客将自己的票插入FastPass的slot中 FastPass计算出建议顾客返回的时间间隔（time interval）或时间点或时间窗（time window） 顾客无需排队，在指
2、定的时间返回就可持票进入,http:/ 只是有序的组织了顾客，并没有减少等待时间 如果能实现知道轮到自己需要等待多少时间，再选择合适的时间来，岂不很好？,http:/ 按时返回却仍需要排队 建议的返回时间间隔太长 如果告诉你4小时以后再回来呢？ 顾客可能不会完全按照安排的时间返回 如果新来的顾客不想使用FastPass系统？,现有的Fast Pass真的那么好用吗？,http:/ 合理的离散统计模型（Distributed Statistical Model），求出最优的顾客返回时间。,建模的一般步骤 以及： * 模型的改进 * 启发与待解决的问题,http:/ 模型的假设,游乐园开放时间为8
3、:00-18:00,一天中不同时间的顾客流量不同，比如上午10:00和下午3:00的顾客流量是最大的。 顾客的到达时间符合非时间齐次泊松过程(Nonhomogeneous Possion Process)，到达速率是,http:/ Process,http:/ Process,http:/ 在我们开始动手建模之前， 先要问几个问题：,http:/ FastPass给出的返回时间只是期望值，而非确定值 假设所有的顾客都使用FastPass,但需考虑有的顾客可能会不遵守FastPass给出的返回时间,2 在我们开始动手建模之前， 先要问几个问题：,http:/ function）是什么？是排队时间
4、吗？,2 在我们开始动手建模之前， 先要问几个问题：,http:/ 模型的建立（1）目标函数,http:/ 模型的建立（1）目标函数,http:/ theory）的分类规则,（X/Y/Z/A）代表一类排队的规则，其中 X:顾客流到达所符合的分布 Y:顾客接受服务的时间所服从的分布 a Z:服务台的个数 A:服务台一次可服务的顾客数量（系统的容量） 针对各个游乐项目的特点，我们主要讨论两种排队系统:,模型的建立（2） 排队模型的分类,http:/ 电话亭模型,http:/ 用MatLab能够作出 的函数，并从图中得出结果,模型的求解（4）电话亭模型,http:/ 这种方法太繁琐，似乎不好用 可否
5、有近似的算法？,http:/ 过山车模型,http:/ 实际的FastPass 系统有两条队列：FastPass 和Standby队列 不考虑standby队列， 将得到Greedy algorithm 模型 考虑standby队列， 将得到效用函数模型,模型的建立（5）过山车,http:/ 只有一条队列，即所有的人都只用FastPass系统 为了防止前面的人等的时间太长，过山车只要载满一定数量的人后就开车，假设为80c。 用贪心算法（greedy algorithm),将每个顾客尽量安排在离顾客到达时间最近的，且还没有安排满人的一班车上。 假设被安排的顾客按照Beta分布到达所被安排的时间段
6、内,模型的建立（5）过山车模型,http:/ 1. 如果开车的时间不固定，则a%是多少最优？就是说顾客坐满多少就开车？ 2.如果开车的时间间隔是固定的，则多长时间开一次是最优的？ 衡量的标准：目标函数,模型的建立（5）过山车模型,http:/ 对于这类复杂的问题，离散仿真是最好 的方法了,http:/ 这里的仿真用MatLab6.5完成： 步骤：1.生成Poisson顾客流（模拟到达时间） 2.给定不同的a%c, 开车时间间隔不定，计算代价函数，画出代价函数性能曲线 3.开车时间固定，给出不同的开车时间间隔，计算画出代价函数性能曲线 4.得出最优的结论,模型的仿真（5）过山车模型,http:/
7、 定时刻 i 采集样本, i=1m, j=1100 形成样本空间的 矩阵,http:/ 估计参数 样本的更新用时间序列的方法（time serial analysis）,计算列向量的Eucilid距离 dthreshold就更新一次,http:/ t2, , tn (t为自变量且t1t2 tn ) 所得到的离散数字组成序列集合x(t1), x(t2), , x(tn)，我们称之为时间序列，这种有时间意义的序列也称为动态数据。时间序列分析是根据系统观测得到的时间序列数据，通过曲线拟合和参数估计来建立数学模型的理论和方法,时间序列分析（time serial analysis）,http:/ 有没
8、有别的方法判别样本如何更新？,如：求样本矩阵的秩， 求样本向量的相关系数,http:/ 某个区间 个顾客到达时间Uniform,http:/ 乘坐的过山车的班次,http:/ function是间隔的单调函数？怎么办？,过山车模型的仿真（5.4）,http:/ 次数愈多，运行成本越大找平衡点 4.67min最优,过山车模型的仿真（5.4）,http:/ 模型的稳健性与优缺点,电话亭模型较精确，虽可行但复杂 过山车模型的贪心算法，简单，但不是最优（quasi-optimal）（为什么不是最优?） Standby队列会有什么影响？ 每个人的c1和c2可能不同,http:/ Theory中的Erla
9、ng C公式，能够得出阻塞概率P(Block)，系统容量C，顾客流的强度A（ ）三者的关系 平均队列长度为： 可将顾客安排在一天之内平均队列短的时刻,7 过山车模型的改进,http:/ C的图形,7 过山车模型的改进,http:/ 说明可以用 统计曲线作安 排返回时间的 依据,7 过山车模型的改进,http:/ 过山车模型的改进,http:/ 过山车模型的改进,统计队列长度曲线应该实时更新！,但是： 可能所有的顾客都被安排 到同一个队列长度短的时 段了,http:/ 过山车模型的改进,使用边际效用函数(Marginal Utility Function)的思想： FastPass队列中每增加一
10、个人，会对Standby队列中的人造成目标函数的损失,http:/ 给顾客提供预计的当天实时队列长度表，顾客可自己选择返回时间，选择t1,t2时间的长度 你的更好的办法？,8 将来的工作：设计更好的FastPass系统,http:/ 怎样求解没有显式表达的式子？ 如何模拟离散随机时间？ 如何通过仿真的结果求参数的优化 使用数学软件，仿真的过程中常常也会的到新的想法与结论 灵活借鉴其他学科中的方法：如Queueing theory(排队论), Trunking Theory(复用论), Greedy Algorithm（贪心算法）, Marginal Utility Function(边际效用函数),9 启发与收获,http:/ Problem,Homework: 相似的问题比如ICM2003 C题， To Screen or not to screen? 飞机场的调度以及安全检查问题 你将如何安排？ Its upto you!,http:/ paper下载：http:/