优先级队列的应用——多服务台排队系统的模拟.docx

《优先级队列的应用——多服务台排队系统的模拟.docx》由会员分享，可在线阅读，更多相关《优先级队列的应用——多服务台排队系统的模拟.docx（5页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、多服务台排队系统的模拟一、与单服务台排队系统相比在多服务台系统中，先到达的顾客先获得服务，这个规则仍然存在；但后获得服务的顾客可能先离开，这是因为每个顾客要求的服务时间是不一样的。如果各科i要 求的是一个复杂业务，服务台j提供服务；而顾客i+1要求的是一个简单业务，服务台k提供服 务，那么顾客i+1虽然比顾客i晚到达，却比顾客i先离开。1. 在单服务台系统中，到达次序和离开次序是一致的，所以只需要一个先进先出的队列；在多服务台系统中，离开事件不再与到达事件保持一致，先处理的到达事件对应的离开事件可能 比后处理的到达事件对应的离开事件发生得晚，因此需要一个优先级队列，将事件发生得时间作 为优先级

2、，发生时间早的事件先处理，发生时间晚的事件后处理。二、多服务台排队系统模拟过程.模拟开始时，产生所有的到达事件，存入优先级队列，此时队列只有到达事件。1 .模拟器开始处理事件。首先从队列中取出一个事件，这是第一个顾客的到达事件，根据各科的 服务要求生成对应的服务时间，当前时间+服务时间=这个顾客的离开时间，生成一个这个时候离 开的事件插入队列，这样在队列中就有了两类事件：到达事件和离开事件。2 .这样模拟器从队列中取出的事件也可能是离开事件，这时只要将这个离开事件从队列中删去， 为它服务的服务台就可以为别的顾客服务。综上：(1)产生所有的顾客到达事件，存入事件队列；(2)模拟器从事件队列中取事

3、件，按照不同的事件类型处理事件。若是到达事件，先检查有没有空闲的服务台，如果有，则为此顾客生成服务时间，并产生 一个离开事件，插入事件队列。如果处理到达事件时，没有空闲的服务台，则该顾客进入到等待队列排队。等待队列是一 个普通的先进先出的队列。(3)如果处理的是离开事件，则释放该服务台。如果此时等待队列有人排队，则服务台为他服 务，并统计等待时间，如果等待队列没有人排队则置服务台为空闲。三、伪代码产生CustomNum个顾客的到达事件，按时间的大小存入事件队列;置等待队列为空；置所有柜台为空闲；设置等待时间为0;While（事件队列非空）队头元素出列；设置当前时间为该事件发生的时间；switc

4、h （事件类型）case到达：if （柜台有空）柜台数T；生成所需的服务时间；修改事件类型为“离开”；设置事件发生时间为当前时间+服务时间；重新存入事件队列；else将该事件存入等待队列；case离开：if （等待队列非空）队头元素出队；统计该顾客的等待时间；生成所需的服务时间；修改事件类型为“离开”；设置事件发生时间为当前时间+服务时间；存入事件队列；else空闲柜台+1；计算平均等待时间;返回；四、代码分析代码清单6-9模拟类的定义class simulator以下定义了保存模拟参数的数据成员int noOfServer; /服务台的个数int arrival Low; 到达间隔时间的下界

5、int arrivalHigh; /到达间隔时间的上界int serviceTimeLow; 服务间隔时间的下界int serviceTimeHigh; 服务间隔时间上界int customNum; 模拟的顾客数struct eventT定义了一个私有内嵌类eventT,用于保存一个事件信息，是事件队列和等待队 列中的元素类型，eventT有两个数据成员，time表示事件发生的时间，type表示事件类型 int time; 事件的大小取决于事件发生的时间，发生时间早的事件优先级高，发生时间晚的 事件优先级低int type; 事件类型，0为到达，1为离开bool operator(const

6、eventT &e)constreturn timenoOfServer;cout请输入到达时间间隔的上下界(最小间隔时间最大间隔时间)：；cinarrivalLowarrivalHigh;coutserviceTimeLow serviceTimeHigh;cout请输入模拟的顾客数：;cincustomNum;srand (time (NULL);完成随机数发生器的初始化代码清单6Tl avgWaitTime函数的实现int simulator: :avgWaitTime()根据模拟参数进行模拟，并统计出平均等待时间 int serverBusy=O; 正在工作的服务台数int curre

7、ntTime; 表示现在模拟到了什么时间int totalWaitTime=0; 记录整个模拟过程中所有顾客的等待时间总和1 inkQueuewaitQueue; 定义了一个类型为 eventT 的链接队列 waitQueue,这个队 列是等待队列，用来保存正在排队的顾客信息priorityQueueeventQueue; 定义了一个类型为 eventT 的优先级队列 eventQueue, 保存的是整个模拟过程中发生的所有事件eventT currentEvent;根据模拟参数中指定的顾客数生成所有顾客的到达事件，并存入事件队列int i;currentEvent. time=0;curre

8、ntEvent. type=0;for (i=0;icustomNum;+i) currentEvent. time+=arrivalLow+ (arrivalHigh-arrivalLow+1) *rand () /(RAND MAX+l); 每 个顾客的到达时间为前一顾客的到达时间加上随机生成的到达时间间隔eventQueue. enQueue(currentEvent);while(!eventQueue. isEmpty()只要队列非空,就要处理事件,直到队列为空currentEvent=eventQueue. deQueue();先从事件队列中取出一个事件current?ime=cu

9、rrentEvent. time; 把模拟时钟直接拨到事件发生的时间switch(currentEvent. type) 然后根据事件发生类型进行不同的处理case 0: 如果是到达事件if (serverBusy!=noOfServer) 首先检查有没有空闲的服务台+serverBusy; 如果有空闲的，则分配服务台currentEvent. time+=serviceTimeLow+(serviceTimeHigh-serviceTimeLow+1)*rand()/ (RAND MAX+l); 离开时间二服 务时间+当前时间currentEvent. type=l; 服务完后，生成一个离开

10、事件eventQueue. enQueue (currentEvent); 入队，事件队列 )else waitQueue. enQueue(currentEvent); 否如果没有空闲的服务台，这位顾客要到 等待队列排队，入队，等待队列break;case 1: 若是离开事件if(!waitQiieue. isEmpty()检查有没有顾客在排队，即等待队列是否为空currentEvent二waitQueue. deQueue();若有顾客在排队，则为等待队列队头的顾客 服务，即让等待队列队头元素出队totalWaitTime+=currentTime-currentEvent. time;

11、把这位顾客的等待时间加入 到总的等待时间，currentTime为当前时间，currentEvent. time为顾客进入到等待队列的时间， 即事件发生的事件currentEvent. time=currentTime+serviceTimeLow+(serviceTimeHigh-serviceTimeLow+1)*rand()/(RAND MAX+l);/currentEvent. time在这指离开时间二当前时间+随机数生成的服务时间currentEvent. type=l; 服务完后，生成一个离开事件eventQueue. enQueue (currentEvent); 入队，事件队列)else-serverBusy; 若没有人排队，则服务台可以休息，所以正在工作的服务台T return totalWaitTime/customNum; 计算并返回平均等待时间