多服务台排队系统的模拟
一、与单服务台排队系统相比
1.
在多服务台系统中，先到达的顾客先获得服务，这个规则仍然存在；
但后获得服务的顾客可能先离开，这是因为每个顾客要求的服务时间是不一样的。如果各科i要求的是一个复杂业务，服务台j提供服务；而顾客i+1要求的是一个简单业务，服务台k提供服务，那么顾客i+1虽然比顾客i晚到达，却比顾客i先离开。 2.
在单服务台系统中，到达次序和离开次序是一致的，所以只需要一个先进先出的队列； 在多服务台系统中，离开事件不再与到达事件保持一致，先处理的到达事件对应的离开事件可能比后处理的到达事件对应的离开事件发生得晚，因此需要一个优先级队列，将事件发生得时间作为优先级，发生时间早的事件先处理，发生时间晚的事件后处理。
二、多服务台排队系统模拟过程
1.模拟开始时，产生所有的到达事件，存入优先级队列，此时队列只有到达事件。
2.模拟器开始处理事件。首先从队列中取出一个事件，这是第一个顾客的到达事件，根据各科的服务要求生成对应的服务时间，当前时间+服务时间=这个顾客的离开时间，生成一个这个时候离开的事件插入队列，这样在队列中就有了两类事件：到达事件和离开事件。
3.这样模拟器从队列中取出的事件也可能是离开事件，这时只要将这个离开事件从队列中删去，为它服务的服务台就可以为别的顾客服务。 综上：
（1）产生所有的顾客到达事件，存入事件队列；
（2）模拟器从事件队列中取事件，按照不同的事件类型处理事件。
①若是到达事件，先检查有没有空闲的服务台，如果有，则为此顾客生成服务时间，并产生一个离开事件，插入事件队列。
②如果处理到达事件时，没有空闲的服务台，则该顾客进入到等待队列排队。等待队列是一个普通的先进先出的队列。
（3）如果处理的是离开事件，则释放该服务台。如果此时等待队列有人排队，则服务台为他服务，并统计等待时间，如果等待队列没有人排队则置服务台为空闲。
三、伪代码
产生CustomNum个顾客的到达事件，按时间的大小存入事件队列； 置等待队列为空； 置所有柜台为空闲； 设置等待时间为0； While(事件队列非空){
队头元素出列；
设置当前时间为该事件发生的时间； switch(事件类型)
{case 到达：if（柜台有空）
{柜台数-1；
生成所需的服务时间； 修改事件类型为“离开”；
设置事件发生时间为当前时间+服务时间； 重新存入事件队列； }
else 将该事件存入等待队列； case 离开：if（等待队列非空）
{队头元素出队； 统计该顾客的等待时间； 生成所需的服务时间； 修改事件类型为“离开”；
设置事件发生时间为当前时间+服务时间； 存入事件队列； }
else 空闲柜台+1； } }
计算平均等待时间； 返回；
四、代码分析
代码清单6-9 模拟类的定义
class simulator{//以下定义了保存模拟参数的数据成员 int noOfServer; //服务台的个数 int arrivalLow; //到达间隔时间的下界 int arrivalHigh; //到达间隔时间的上界 int serviceTimeLow; //服务间隔时间的下界 int serviceTimeHigh; //服务间隔时间上界 int customNum; //模拟的顾客数
struct eventT//定义了一个私有内嵌类eventT，用于保存一个事件信息，是事件队列和等待队列中的元素类型，eventT有两个数据成员，time表示事件发生的时间，type表示事件类型 {int time; //事件的大小取决于事件发生的时间，发生时间早的事件优先级高，发生时间晚的事件优先级低
int type; //事件类型，0为到达，1为离开
bool operator<(const eventT &e)const{return time public: //两个公有函数 simulator();//模拟类的构造函数 int avgWaitTime();//模拟类的平均等待时间函数 }; 代码清单6-10 构造函数的实现 simulator::simulator()//模拟参数的输入 { cout<<\请输入柜台数:\ cout<<\请输入到达时间间隔的上下界(最小间隔时间 最大间隔时间):\ cin>>arrivalLow>>arrivalHigh; cout<<\请输入服务时间的上下界(服务时间上界 服务时间下界):\ cin>>serviceTimeLow >>serviceTimeHigh; cout<<\请输入模拟的顾客数:\ srand(time(NULL)); //完成随机数发生器的初始化 } 代码清单6-11 avgWaitTime函数的实现 int simulator::avgWaitTime()//根据模拟参数进行模拟，并统计出平均等待时间 { int serverBusy=0; //正在工作的服务台数 int currentTime; //表示现在模拟到了什么时间 int totalWaitTime=0; //记录整个模拟过程中所有顾客的等待时间总和 linkQueue priorityQueue eventT currentEvent; //根据模拟参数中指定的顾客数生成所有顾客的到达事件，并存入事件队列 int i; currentEvent.time=0; currentEvent.type=0; for(i=0;i +(arrivalHigh-arrivalLow+1)*rand()/(RAND_MAX+1); //每个顾客的到达时间为前一顾客的到达时间加上随机生成的到达时间间隔 eventQueue.enQueue(currentEvent); } while(!eventQueue.isEmpty())//只要队列非空，就要处理事件，直到队列为空 {currentEvent=eventQueue.deQueue();//先从事件队列中取出一个事件 currentTime=currentEvent.time; //把模拟时钟直接拨到事件发生的时间 switch(currentEvent.type) //然后根据事件发生类型进行不同的处理 {case 0: //如果是到达事件 if(serverBusy!=noOfServer) //首先检查有没有空闲的服务台 {++serverBusy; //如果有空闲的，则分配服务台 currentEvent.time+=serviceTimeLow+ (serviceTimeHigh-serviceTimeLow+1)*rand()/(RAND_MAX+1); //离开时间=服务时间+当前时间 currentEvent.type=1; //服务完后，生成一个离开事件 eventQueue.enQueue(currentEvent); //入队，事件队列 } else waitQueue.enQueue(currentEvent); //否如果没有空闲的服务台，这位顾客要到等待队列排队，入队，等待队列 break; case 1: //若是离开事件 if(!waitQueue.isEmpty())//检查有没有顾客在排队，即等待队列是否为空 {currentEvent=waitQueue.deQueue();//若有顾客在排队，则为等待队列队头的顾客服务，即让等待队列队头元素出队 totalWaitTime+=currentTime-currentEvent.time; //把这位顾客的等待时间加入到总的等待时间，currentTime为当前时间，currentEvent.time为顾客进入到等待队列的时间，即事件发生的事件 currentEvent.time=currentTime+serviceTimeLow+ (serviceTimeHigh-serviceTimeLow+1)*rand()/(RAND_MAX+1); //currentEvent.time在这指离开时间=当前时间+随机数生成的服务时间 currentEvent.type=1; //服务完后，生成一个离开事件 eventQueue.enQueue(currentEvent); //入队，事件队列 } else--serverBusy; //若没有人排队，则服务台可以休息，所以正在工作的服务台-1 } } return totalWaitTime/customNum; //计算并返回平均等待时间 }
优先级队列的应用 - 多服务台排队系统的模拟 - 图文
