系统排队.pptx

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