隊列的應用——單服務臺排隊系統(tǒng)的模擬研究

1、隊列的應用：單服務臺排隊系統(tǒng)的模擬一、三個模擬1.離散事件模擬系統(tǒng)在排隊系統(tǒng)中，主要有兩類事件：顧客的到達事件和服務完畢后顧客的離去事件，整個系統(tǒng)就是不斷有到達事件和離開事件的發(fā)生，這些事件并不是連續(xù)發(fā)生的，因此這樣的系統(tǒng)被稱為離散事件模擬系統(tǒng)。（1）事件處理過程當生成一個到達事件時，表示有一個新顧客到達。如果服務員沒空，就去隊列中排隊；否則就為這個顧客生成服務所需的時間t，表示服務員開始為它服務，所需的服務時間是t。經(jīng)過這段時間后會產(chǎn)生一個顧客離開事件，每當一個離開事件發(fā)生，就檢查有沒有顧客在排隊，如果有顧客在排隊，則讓隊頭顧客離隊，為它提供服務，如果沒有顧客排隊，則服務員可以休息。（2）如

2、何產(chǎn)生顧客到達事件和離開事件在一個排隊系統(tǒng)中，顧客的到達時間和為每個顧客服務的時間并不一定是固定的。但從統(tǒng)計上來看是服從一定的概率分布。假設到達的間隔時間和服務時間都滿足均勻分布，則可以用隨機數(shù)產(chǎn)生器產(chǎn)生的隨機數(shù)。以生成顧客到達事件為例子如顧客到達的間隔時間服從a,b之間的均勻分布，則可以生成一個a,b之間的隨機數(shù)x，表示前一個顧客到達后，經(jīng)過了x的時間后又有一個顧客到達。a,b之間的隨機數(shù)可以按照下面的過程產(chǎn)生：假如系統(tǒng)的隨機數(shù)生成器生成的隨機數(shù)是均勻分布在0到RAND_MAX之間，可以把0到RAND_MAX之間的區(qū)間等分成b-a+1個，當生成的隨機數(shù)落在第一個區(qū)間，則表示生成的是a，當落在

3、第二個區(qū)間，則表示生成的是a+1當落在最后一個區(qū)間，則表示生成的是b。這個轉換可以用rand()*(b-a+1)/( RAND_MAX+1)+a實現(xiàn)，rand表示系統(tǒng)的隨機數(shù)生成函數(shù)。2.離散的時間驅(qū)動模擬在得到了在x秒后有一個事件生成的信息時，并不真正需要讓系統(tǒng)等待x秒再處理該事件。在模擬系統(tǒng)中，一般不需要使用真實的精確事件，只要用一個時間單位即可，這個時間單位是嘀嗒tick，可以表示1秒，也可以表示1min1h.沿著時間軸，模擬每一個嘀嗒中發(fā)生了什么事件并處理該事件。模擬開始時時鐘是0嘀嗒，隨后每一步都把時鐘加1嘀嗒，并檢查這個時間內(nèi)是否有事件發(fā)生，如果有，則處理并生成統(tǒng)計信息。3.離散的

4、事件驅(qū)動模擬離散的時間驅(qū)動模擬連續(xù)地處理每個事件單位，如果在很長一段時間內(nèi)沒有任何事件發(fā)生，程序海必須檢查每個嘀嗒中是否有事件發(fā)生，這很浪費計算機的時間。因此，可以將事件按照發(fā)生時間排隊，當一個事件處理結束后，直接將時間撥到下一個事件的發(fā)生時間，處理下一事件，這就是事件驅(qū)動模擬。二、模擬一個單服務臺排隊系統(tǒng)1.原理模擬銀行中只有一個服務臺，顧客到達的時間間隔服從arrivalLow, arrivalHigh的均勻分布，服務時間長度服從serviceLow,serviceHigh的均勻分布，一共模擬custNum個顧客，要求統(tǒng)計顧客的平均服務時間。整個模擬由3個步驟組成：首先生成所有的顧客到達事

5、件，按到達時間排成一個隊列；其次，服務員一旦有空，就為隊頭元素服務，在提供服務前先檢查該顧客等待了多少時間，記入累計值；最后，在所有顧客服務完以后，返回累計值除以顧客數(shù)的結果。2.偽代碼totalWaitTime=0;設置顧客開始到達的時間currentTime=0;for(i=0;i當前時間）直接將時鐘撥到事件發(fā)生的時間； else 收集該顧客的等待時間；生成服務時間；將時鐘撥到服務完成的時刻；返回 等待時間/顧客數(shù)3.代碼分析4-6代碼分析 鏈接隊列類的定義template class linkQueue private:struct node/定義一個結點結構體 elemType dat

6、a; /存儲數(shù)據(jù)部分node* next; /存儲指向下一個數(shù)據(jù)的指針部分node(const elemType &x,node*N=NULL) /定義一個node，它包含數(shù)據(jù)部分和指針部分 data=x;next=N; /給data和next賦值 node():next(NULL) /什么參數(shù)都沒有，就令為空node()/析構函數(shù)，釋放空間;node*front,*rear; /結點的隊頭和隊尾public:linkQueue() front=rear=NULL; /空隊列，隊頭和隊尾都為空linkQueue();/析構函數(shù)，釋放空間bool isEmpty() return front=N

7、ULL; /判隊列空void enQueue(const elemType &x); /進隊 elemType deQueue();/出隊elemType getHead() return front-data; /返回隊頭元素值;4-7代碼分析 析構函數(shù)的實現(xiàn)template linkQueue :linkQueue()node*tmp; /定義一個跟隨指針，確保能夠找到頭結點while(front!=NULL) /當頭結點不為空，進行下列循環(huán)tmp=front; /tmp指向頭結點front=front-next; /頭結點指向下一位delete tmp; /刪除tmp所指結點4-8代碼分

8、析 鏈接隊列類中enQueue和deQueue運算的實現(xiàn)template void linkQueue :enQueue(const elemType &x) /進隊if(rear=NULL) /如果隊尾為空front=rear=new node(x); /則隊頭=隊尾=新結點elserear-next=new node(x); /否則隊尾的后繼指針指向新結點rear=rear-next; /更新隊尾，現(xiàn)在隊尾為新添加的結點template elemType linkQueue :deQueue()/出隊node *tmp=front; /定義一個指針指向隊頭 elemType value=f

9、ront-data; /隊頭元素值用value保存front=front-next; /隊頭往后移一個，隊頭更新if(front=NULL) rear=NULL;delete tmp; /刪除原來的隊頭return value; /返回原來隊頭元素值4-10代碼分析 模擬類simulator的定義class simulator int arrivalLow; /到達間隔時間下限int arrivalHigh; /到達間隔時間上限int serviceTimeLow; /服務時間下限int serviceTimeHigh; /服務時間上限int customNum; /模擬的顧客數(shù)public:

10、simulator();int avgWaitTime() const; /平均等待時間（常數(shù)）;4-11代碼分析 構造函數(shù)的實現(xiàn)simulator:simulator()cout arrivalLow arrivalHigh; /計算機讀入輸入的參數(shù)cout serviceTimeLow serviceTimeHigh; cout customNum;srand(time(NULL); /初始化隨機數(shù)發(fā)生器4-12代碼分析 avgWaitTime函數(shù)的實現(xiàn)int simulator:avgWaitTime() constint currentTime=0; /當前時間int totalWai

11、tTime=0; /總的等待時間int evenTime; /顧客到達時間，根據(jù)到達時間入隊linkQueue customerQueue; /定義一個鏈接隊列，存放顧客到達時間，生成到達事件int i;for(i=0;icustomNum;+i) /生成所有的到達事件currentTime+=arrivalLow+(arrivalHigh-arrivalLow+1)* rand()/(RAND_MAX+1);customerQueue.enQueue(currentTime);/循環(huán)體的含義是生成所有顧客的到達時間，并按照到達時間的次序存入隊列currentTime=0;while(! cu

12、stomerQueue.isEmpty() evenTime=customerQueue.deQueue();/隊頭元素if(evenTimecurrentTime) totalWaitTime+=currentTime-evenTime;/判斷顧客的到達時間和當前時間，如果到達時間比當前時間要小，說明顧客已經(jīng)等待了一段時間，則統(tǒng)計總的等待時間 else currentTime=evenTime; /如果到達時間不小于當前時間，說明顧客還沒到達，還沒入隊，可以將時鐘直接撥到事件發(fā)生的時間。 currentTime+=serviceTimeLow+ (serviceTimeHigh-serviceTimeLow+1)*rand()/(RAND_MAX+1); /隨機生成服務時間return totalWaitTime/customNum; /返回平均等待時間4-13代碼分析 simulator類的使用#include stdafx.h#include simulator.h