基于泊松过程的食堂排队问题分析

《基于泊松过程的食堂排队问题分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于泊松过程的食堂排队问题分析芦迪*(清华大学电子工程系北京100084)(Email：me@ludics.cn)2016年12月22日摘要利用泊松过程对一个实际的食堂排队问题进行建模，利用排队论的基本概念和随机过程的相关知识，在合理假设的前提下，对M/M/r/1和M/M/r/K两种模型进行理论分析，得到了服务窗口的合适数目。通过Matlab软件生成随机数的方式对排队过程进行模拟，仿真得到了结果。关键词排队论；泊松过程；生灭过程；并行窗口*感谢李刚老师留的这个大作业，让我对排队论这个有难度但也很有实际意义的问题有了初步的了解。2概率论与随机过程1

2、导语考虑若干同学在食堂排队购买麻辣香锅，对买香锅的同学计数服从参数为的泊松分布，每人只许买一份，买完就走。并行做香锅的厨师有r个，每位厨师任何时刻只能做一份香锅，不同厨师做菜时间长度独立，且都服从参数为的负指数分布。食堂给厨师薪水按“小时工”计算，每个单位时间酬劳x元。同学到达窗口与厨师做菜两个事件相互独立。那并行厨师的数目设置为多少比较合适呢？可以从同学和食堂两个角度来考察问题：•从同学角度：希望并行厨师越多越好，节省时间；•从食堂角度：希望控制厨师数量，考虑成本。这实际上可以看作为这样一个优化问题:{}r=argminG(r)=argmi

3、nA0T(r)+M(x)r(1.1)rr其中，G(r)=A0T(r)+M(x)r,为目标函数；r为并行厨师的数量；T(r)为并行厨师数为r时同学买到香锅的平均时间；A0是一个常值，可看作同学花费的平均时间对目标函数的影响因子；M(x)为每增加一个并行厨师所要付出的酬劳，与x相关。这个优化问题的目标即为寻找G(r)取得最小值时r的取值。我们试图运用一些排队论的基本概念和随机过程的相关知识对排队过程中不同并行厨师数时同学的平均用时进行评估，以期解决上述的优化问题。同时和Mat-lab数值计算结合，针对不同的参数值，分析应该聘用多少位并行厨师。下面将首

4、先介绍一些解决此类问题的基本概念和理论。2排队模型与随机过程解决此类问题需要首先明确排队问题的一些基本概念；随机过程是基本的分析工具，这里主要用到了泊松(Possion)过程以及它的相关拓广。下面将结合本文将要探讨的问题就以下预备知识进行简要介绍和回顾：•泊松过程；•生灭过程；•排队问题与排队模型。第二次大作业32.1泊松过程考虑一个计数过程，用N(t)表示在时间区间[0;t]内到达事件的数目，用Pn(t1;t2)表示在[t1;t2]事件计数为n的概率，即Pn(t1;t2)=P(N(t2)N(t1)n)。如果计数过程N(t)满足下述条件：1)

5、N(0)=0；2)N(t)是独立增量过程；3)N(t)是平稳增量过程；1P1(t+∆t;t)4)!0;∆t!0；P1(t+∆t;t)则称其为Poisson过程[4]。运用以上泊松过程的定义，可以得到任意时刻泊松过程的分布为：(t)ntPn(t)=e;n=0;1;2;:::;t>0:(2.1)n!泊松过程中随机变量的均值和方差均为t，表征了单位时间内到达事件的数目，称其为泊松过程的速率。在本次所讨论的排队问题中，假定了对购买麻辣香锅的同学的计数服从参数为的泊松分布，这也就意味着：1)在不重叠的两个时间区间内购买进入排队系统购买麻辣香锅

6、的同学数是彼此独立的；2)在一个时间区间内购买麻辣香锅的同学数只与区间长度有关，与起始时刻无关；3)在一个很短的时间间隔内，到达一位购买麻辣香锅的同学的概率与区间间隔成正比，比例系数是泊松过程的参数，而到达两位及以上同学的概率很小。在某一个时刻认为最多只有一位同学达到排队系统。假设对事件的计数过程为泊松过程，下面考虑两个事件到达的时间间隔T的分布，显然它是一个连续随机变量，其分布函数满足：tF(t)=P(Tt)=1P(T>t)=1P0(t)=1e(t>0)(2.2)4概率论与随机过程所以它的概率密度函数为：tf(t)=e(t>

7、0)(2.3)即泊松过程两事件发生间隔T服从参数为的负指数分布，均值为1/，即泊松过程中两个事件到达的平均时间间隔为1/[4]。在本问题中，假设了食堂厨师制作麻辣香锅的时间服从参数为的负指数分布，也就是说每个同学“接受服务”的时间是负指数分布的。由于同学在接受完服务后就会离开排队系统，一个同学接受服务的时间始于上一个同学离开排队系统、止于该同学离开排队系统，这是以同学的离开为计数的时间间隔。也就是说，同学买到麻辣香锅离开排队系统服从参数为的泊松分布。2.2生灭过程考虑一类状态离散、时间连续的Markov链，其在时间段[t;t+∆t]内的

8、转移概率满足以下条件：8>>>>n(t)∆t+o(∆t);k=n+1