随机过程第二次大作业报告

无832008011105随机过程project2袁定波1/13从食堂麻辣烫排队现象引出的排队论分析及仿真随机过程第二次大作业袁定波（清华大学电子工程系无83）【摘要】排队问题是与我们的生活息息相关的一项理论。无论是有形的还是无形的排队问题，都随时随刻地伴随着我们生活的每一天。本文主要从学校食堂的“麻辣烫排队问题”着手，研究一般性的排队问题。同时，笔者编写了MATLAB代码验证了理论推导的正确性。【关键词】排队论M/M/NM/M/1泊松分布Markov链一、介绍在食堂买麻辣烫的同学数量服从参数为λ的泊松分布，每个同学只许买一份麻辣烫。并行做麻辣烫的厨师有r个，每位厨师任何时刻只能做一份麻辣烫、不能同时做两份或两份以上，不同的厨师制作麻辣烫时间长度独立，且都服从参数为μ的负指数分布。同学到达麻辣烫窗口的过程与厨师做麻辣烫的过程相互独立。通常有两种排队方式：A：排成一个大队列。只要有某位厨师空闲，他就给排在队列中的第一位同学做麻辣烫。新到达的同学排到队尾，直到排在他前面的所有同学都买到麻辣烫之后，他才有资格买。按照这种方式，当r个厨师都忙碌时，同学们按照先到先得的原则在排一个大队列。B：自选排成多个队列。每个厨师前面各排一个队列，厨师只给他负责的队列中的同学做麻辣烫。新到达的同学自行选择排哪一个队列。按照这种方式，当r个厨师都忙碌时，同学们排成了r个队列。下文就选择哪一种排队方式更节省时间展开分析讨论并利用matlab进行仿真。二、模型首先，我们给出一般的排队论的数学模型框图如下：图1一般排队问题的模型框图对于“介绍”部分的两种排队问题，我们分别建立其数学模型。对于A排队方式，我们作如下假设：顾客的到来遵循参数为的泊松过程，即任意两个顾客到来的时间间隔遵循参数为的负指数分布；顾客在食堂中排成一路纵队，后到的顾客自动排到队尾；一共有r个服务窗，每个服务窗口服务一次的时间遵循参数为的负指数分布，各个服务窗口之间是相互独立的，且服务窗口与顾客的到来之间也是相互独立的。而每一个顾客到来后，顾客源排队（排队规则）服务窗（服务规则）无832008011105随机过程project2袁定波2/13关心的是在队伍中的等待时间的长短，因此最后我们要求队伍中的等待时间。对于B排队方式，我们作如下两种假设。第一种假设记为1B：顾客的到来遵循参数为的泊松过程，即任意两个顾客到来的时间间隔遵循参数为的负指数分布；顾客在食堂排成r路纵队，每位顾客到来后，随机等概地选择一个队伍并排在该队队尾；一共有r个服务窗口，每个窗口服务一次的时间遵循参数为的负指数分布，每个服务窗口只为其对应的队列服务，各服务窗口之间是相互独立的，且服务窗口与顾客的到来之间也是相互独立的。而每一个顾客到来后，关心的是在队伍中的等待时间的长短，因此最后我们要求队伍中的等待时间。第二种假设记为2B：顾客的到来遵循参数为的泊松过程，即任意两个顾客到来的时间间隔遵循参数为的负指数分布；顾客在食堂排成r路纵队，每位顾客到来后，选择最短的一个队伍并排在该队队尾；一共有r个服务窗口，每个窗口服务一次的时间遵循参数为的负指数分布，每个服务窗口只为其对应的队列服务，各服务窗口之间是相互独立的，且服务窗口与顾客的到来之间也是相互独立的。而每一个顾客到来后，关心的是在队伍中的等待时间的长短，因此最后我们要求队伍中的等待时间。三、理论I、排队系统简介众所周知，研究排队问题的相关规律，使设计人员掌握这种规律，设计出最优化的排队系统，对生产和生活都有很好的指导作用。下面，我们来介绍排队问题的基本理论。从排队问题的系统框图我们可以看出，排队问题有三个基本的参数：输入过程、排队规则、服务窗。对于输入过程：顾客到达的时间间隔可以分为确定型和随机型两种；顾客源可以分为有限和无限两种情况；顾客到达可以为任意分布。对于排队规则，可以分为损失制、等待制、混合制三种。所谓损失制，即顾客到达系统时，如果系统中所有的服务窗口均被占用，则到达的顾客随机离去；所谓等待制，即顾客到达系统时，如果系统中所有的服务窗口均被占用，则系统能提供足够大的排队空间让顾客排队等待；所谓混合制，即损失制和等待制相结合，系统只能提供有限大的排队空间，其余的顾客必须离开。服务规则可以分为先到先服务（队列式）、后到先服务（堆栈式）、随机选择服务、优先级服务（优先级队列）四种情况。而对于服务窗来说，可以使单个或者多个；当服务窗口是多个时，顾客可以平行多对排列，也可以是串列或者串并同时存在的混合队列；一个服务窗口可以同时为单个顾客或者成批顾客服务；各个窗口的服务时间可以使确定型或者随机型的，各窗口的服务时间之间可以是相互独立的，也可以是彼此相关的。但一般服务时间都是平稳的，即与服务的起始时间无关。而衡量一个排队系统的性能指标有很多，这里分别一一说明。1、系统内的顾客数的分布及相应的均值sL。2、系统内排队等候的顾客数的分布及相应的均值qL。3、正在接受服务的顾客数的分布及相应的均值fL。4、顾客在系统内停留时间的均值sT。5、顾客在队伍中排队等待时间的均值qT。无832008011105随机过程project2袁定波3/136、顾客接受服务的时间的均值qT。我们可以从上述几个性能指标中得到很直观的结论：sqfTTT；sqfLLL。通常，为了方便表示，用X/Y/Z/m/K来表示排队模型。X表示顾客相继到达系统的间隔时间t的概率分布类型；Y为服务窗口所耗费的服务时间的概率分布；Z为并行工作的服务机构内的服务窗口的个数；m表示系统内允许的最大排队长度。例如，M/M/r表示顾客到来的时间间隔服从负指数分布，每个窗口的服务时间服从负指数分布，共有r个服务窗口的排队系统。II、Markov链生灭过程简介生灭过程是针对齐次Markov链的一步状态转移过程。以连续时间的生灭过程为例，设队列有k人时的状态记为k状态。在t时间内，状态可能从k状态跳到k+1状态、或者跳到k-1状态，或者保持k状态不变。其设从状态i跳到状态j的概率为()ijpt，则一步状态转移矩阵为P0001101112212223()()00()()()0()0()()()0......ptptptptptPtptptpt状态转移矩阵P，其每行的行和为1。如果只有有限个状态，最后一个状态只能减一，不能加一。同理，第一个状态只能加一，不能减一。而由K-C前向方程''()(),()()ijikkjkPtPtQptptq可知，'(0)ijijqp。其中，Q矩阵称为密度矩阵，或者瞬时概率转移矩阵。对于Q矩阵，不难得出每行行和为0。我们定义i为i状态下的增长率为,1iiiq。定义i为i状态下的消亡率为,1iiiq。我们易知0,||2ijqifij。而Q矩阵的行和为零，我们得到,1,1()()iiiiiiiiqqq。对于泊松过程来说，,1,1,1,1()();()();;;()iiiiiiiiiiiiiiiipttotpttotqqq。故对于一步状态转移过程来说，对应的Q矩阵为00111122223333111()()().........mmmQ而由连续Markov链的平稳分布可知平衡方程11iiii。其中i为i状态时对应的分布。无832008011105随机过程project2袁定波4/13III、M/M/1模型及其求解限于本次题目内容的考虑，这里只推导单服务窗口等待制M/M/1模型。设顾客到达的速率为，服务的速率为，记k状态为队伍里有k个人等待时的状态。则，k状态时的顾客到达率为k，k状态时的服务率为k。设K状态时的概率为kp，则由平衡方程可知11kkkkpp，进一步得出11kkkkpp。由递推法不难得出，0(/)kkpp，由概率的归一化条件001(/)kkkkpp求得0p。求得队伍中等待的顾客数的均值为20(/)(1)1/qkkLkp由此求得顾客需要排队等待的时间的均值为2(/)1/()qqLT。IV、M/M/r模型及其求解限于本次题目内容的考虑，这里只推导多服务窗口等待制M/M/N模型。设顾客到达的速率为，服务的速率为，窗口数为N，记k状态为队伍里有k个人等待时的状态。则，k状态时的顾客到达率为k，k状态时的服务率为,,kkkNNkN。设K状态时的概率为kp，则由平衡方程可知11kkkkpp，进一步得出11kkkkpp。由递推法不难得出，00(/),!{(/),!kkkkNpkNkppkNNN，由概率的归一化条件1000(/)(/)1!!kkNkkNkkkNpppkNN求得1100(/)(/)()(1/())!!NkNkpNNk。求得队伍中等待的顾客数的均值为10002(/)(/)()(){(/())(/())}!!(/)(1)!kNkkqkkNNkNkNkNkNpppLkNpkNkNNNNNNNNN由此求得顾客需要排队等待的时间的均值为10022(/)(/)(1/())!(/)(1)!NNqqLppTNNNNN。无832008011105随机过程project2袁定波5/13四、方法及算法1、麻辣烫排队的A排队方式理论推导A排队方式在稳态时符合M/M/r模型，由上述推导公式可以得出，顾客的平均等待时间为110220(/)(/)(/)(/)()(/)(1)!(/)(1)!(1/())!!rrrkrqkpTrrrrrrk。2、麻辣烫排队的B排队方式的1B假设的理论推导由分类泊松过程的相关知识可知，对于B排队方式的1B假设，顾客的到来服从参数为的泊松分布，其概率母函数求得为()exp{(1)}jwwte，而每个人一等概1r的概率选择r个队伍中的一个，因此任意一个队伍的人数计数也是一个泊松过程，因为其概率母函数为11()exp{(1)}exp{(1)}jwjwrrwteterrr即每个队伍的人的到达情况服从参数为r的泊松过程，其符合M/M/1模型，但是顾客的等效到来率为r，所以顾客的平均等待时间为/(/)()qrTrr。3、麻辣烫排队的B排队方式的2B假设由于R个队伍的长度存在很大的耦合性，因此，我暂时没能在理论上求得其平均等待时间。下面在matlab模拟仿真中求出了这一结果。4、利用MATLAB模拟A排队方式和B排队方式的1B假设算法如下对于A排队方式，设模拟的总人数为N，服务窗口数为R，首先利用一个4*N的矩阵来记录每个人的信息。其中第一行表示到达时刻，第二行表示服务时间长度，第三行表示等待时间长度，第四行表示离开时刻。其中到达时刻和服务时间长度可由已知的求得。我们易知离开的时刻=到达的时刻+服务时间长度+等待时间长度。用长度为R的server_state表示每个窗口的接受服务的人的离开时刻。前R个人到达后不需要等待，故等待时间为零。从第R+1个人开始，先由server_state求出R个窗口中的最早结束服务的窗口，如果结束服务的时刻小于顾客到来的时刻，则该顾客的等待时间为零；如果结束服务的时刻大于顾客到来的时刻，则二者之差为该顾客的等待时间。同时更新该窗口的接受服务的人的离开时刻。在求出所有顾客的等待时间后，对其求平均值即得到最后要求的平均等待时间。对于B排队方式的1B假设，由于我们在理论上已经推出其等效于顾客到达速率为r的单队列单服务窗口的模型，所以其