第3講離散事件系統(tǒng)仿真原理與程序

第3講離散事件系統(tǒng)仿真原理與程序第一頁，共46頁。主要內(nèi)容

（以排隊系統(tǒng)為例）3.1問題的提出3.2排隊系統(tǒng)的組成3.3事件調(diào)度法3.4系統(tǒng)的統(tǒng)計性能指標(biāo)3.5實體到達模式與泊松過程第二頁，共46頁。3.1問題的提出

排隊常常是件很令人惱火的事情……尤其是在我們這樣的人口大國。電話亭－1978年在北京15%的電話要在1小時后才能接通。在電報大樓打電話的人還要帶著午飯去排隊。銀行窗口，ATM醫(yī)院火車售票交通理發(fā)游樂場的游樂項目第三頁，共46頁。3.1問題的提出第四頁，共46頁。3.1問題的提出怎樣縮短排隊的等待時間？銀行的排隊叫號機。只是有序的組織了顧客，并沒有減少等待時間。如果能實現(xiàn)知道輪到自己需要等待多少時間，再選擇合適的時間來，豈不很好？第五頁，共46頁。3.1問題的提出例，單人理發(fā)館系統(tǒng),設(shè)上午9:00開門,下午5:00關(guān)門。

特點：顧客到達時間一般是隨機的,為每個顧客服務(wù)的時間長度也是隨機的。系統(tǒng)的狀態(tài)：服務(wù)臺的狀態(tài)(忙或閑)、顧客排隊等待的隊長也是隨機的。狀態(tài)量的變化只能在離散的隨機時間點上發(fā)生。第六頁，共46頁。3.2排隊系統(tǒng)的組成排隊系統(tǒng)的三個基本組成部分到達模式 指臨時實體按怎樣的規(guī)律到達。服務(wù)模式 指同一時刻有多少服務(wù)臺可以接納臨時實體，它們的服務(wù)要多少時間。排隊規(guī)則 服務(wù)臺完成當(dāng)前服務(wù)后，從隊列中選擇下一個實體服務(wù)的原則。排隊系統(tǒng)的基本結(jié)構(gòu)到達模式排隊服務(wù)機構(gòu)到達離去第七頁，共46頁。3.2排隊系統(tǒng)的組成M/M/1的含義到達時間間隔服從指數(shù)分布,用M表示服務(wù)時間的分布服從指數(shù)分布,用M表示單隊單服務(wù)臺第八頁，共46頁。3.2排隊系統(tǒng)的組成穩(wěn)態(tài)平均延誤時間

實體通過系統(tǒng)的穩(wěn)態(tài)平均滯留時間w穩(wěn)態(tài)平均隊長Q系統(tǒng)中穩(wěn)態(tài)平均實體數(shù)LL(t)=Q(t)+S(t)第九頁，共46頁。Externaldefinitionsforsingle-server#include<stdio.h>#include<math.h>#include"lcgrand.h"

/*Headerrandom-numbergenerator.*/#defineQ_LIMIT100/*Limitonqueuelength.*/#defineBUSY1/*Mnemonicsforserver'sbeingbusy*/#defineIDLE0/*andidle.*/第十頁，共46頁。Externaldefinitionsforsingle-server(continued)intnext_event_type,num_custs_delayed,num_delays_required,num_events,num_in_q,server_status;floatarea_num_in_q,area_server_status,mean_interarrival,mean_service,sim_time,time_arrival[Q_LIMIT+1],time_last_event,time_next_event[3],total_of_delays;FILE*infile,*outfile;voidinitialize(void);voidtiming(void);voidarrive(void);voiddepart(void);voidreport(void);voidupdate_time_avg_stats(void);floatexpon(floatmean);第十一頁，共46頁。3.3事件調(diào)度法事件（Event）

引起系統(tǒng)狀態(tài)發(fā)生變化的行為，系統(tǒng)是由事件來驅(qū)動的?！邦櫩偷竭_”為一類事件 顧客到達→引起系統(tǒng)狀態(tài)：服務(wù)員的“狀態(tài)”——從閑變到忙（如果無人排隊)；或者另一系統(tǒng)狀態(tài)——排隊的人數(shù)發(fā)生變化（隊列人數(shù)增加)?！邦櫩碗x去”為一類事件 服務(wù)完畢后離開系統(tǒng)→服務(wù)臺“狀態(tài)”由忙變成閑。第十二頁，共46頁。3.3事件調(diào)度法定義系統(tǒng)事件類型: 類型1顧客到達事件 類型2顧客接受服務(wù)事件（本程序未考慮）類型3顧客服務(wù)完畢并離去事件定義程序事件:仿真運行到150個時間單位(例如分鐘)結(jié)束。假定已經(jīng)得到到達時間間隔隨機變量的樣本值為:系統(tǒng)初始狀態(tài):思考：請列出該排隊系統(tǒng)的事件表。第十三頁，共46頁。3.3事件調(diào)度法事件表第十四頁，共46頁。main()/*Mainfunction.*/{/*Openinputandoutputfiles.*/infile=fopen("mm1.in","r");outfile=fopen("mm1.out","w");/*Specifythenumberofeventsforthetimingfunction.*/

num_events=2;/*Readinputparameters.*/fscanf(infile,"%f%f%d",&mean_interarrival,&mean_service,&num_delays_required);/*Writereportheadingandinputparameters.*/fprintf(outfile,"Single-serverqueueingsystem\n\n");fprintf(outfile,"Meaninterarrivaltime%11.3fminutes\n\n",mean_interarrival);fprintf(outfile,"Meanservicetime%16.3fminutes\n\n", mean_service);fprintf(outfile,"Numberofcustomers%14d\n\n",num_delays_required);Mainfunction第十五頁，共46頁。/*Initializethesimulation.*/

initialize();/*Runthesimulationwhilemoredelaysarestillneeded.*/while(num_custs_delayed<num_delays_required){/*Determinethenextevent.*/

timing();/*Updatetime-averagestatisticalaccumulators.*/

update_time_avg_stats();/*Invoketheappropriateeventfunction.*/switch(next_event_type){case1:

arrive();break;case2:

depart();break;}}Mainfunction(continued)第十六頁，共46頁。Mainfunction(continued)

/*Invokethereportgeneratorandendthesimulation.*/

report();fclose(infile);fclose(outfile);return0;}第十七頁，共46頁。voidinitialize(void)/*Initializationfunction.*/{/*Initializethesimulationclock.*/sim_time=0.0;/*Initializethestatevariables.*/server_status=IDLE;num_in_q=0;time_last_event=0.0;/*Initializethestatisticalcounters.*/num_custs_delayed=0;total_of_delays=0.0;area_num_in_q=0.0;area_server_status=0.0;/*Initializeeventlist.Sincenocustomersarepresent,thedeparture(servicecompletion)eventiseliminatedfromconsideration.*/time_next_event[1]=sim_time+expon(mean_interarrival);time_next_event[2]=1.0e+30;}FunctionInitialize第十八頁，共46頁。voidtiming(void)/*Timingfunction.*/{inti;floatmin_time_next_event=1.0e+29;next_event_type=0;/*Determinetheeventtypeofthenexteventtooccur.*/for(i=1;i<=num_events;++i)if(time_next_event[i]<min_time_next_event){min_time_next_event=time_next_event[i];next_event_type=i;}/*Checktoseewhethertheeventlistisempty.*/if(next_event_type==0){/*Theeventlistisempty,sostopthesimulation.*/fprintf(outfile,"\nEventlistemptyattime%f",sim_time);exit(1);}/*Theeventlistisnotempty,soadvancethesimulationclock.*/sim_time=min_time_next_event;}FunctionTiming第十九頁，共46頁。3.4系統(tǒng)的統(tǒng)計性能指標(biāo)假設(shè)仿真目的是要估計服務(wù)n個顧客后的顧客平均隊長Q(n)及平均排隊等待時間d(n)： 其中為第i個顧客排隊等待時間，Q(t)為t時刻排隊等待的顧客數(shù)，T為完成n個顧客服務(wù)所耗時間，d(n)、Q(n)表示估計值，、表示平均值。為計算方便 其中為時間區(qū)間上排隊人數(shù)乘以該時間區(qū)間長度 ，即，其中是第i個任何一類事件發(fā)生的時間。

m為在區(qū)間上發(fā)生的事件總數(shù)，其中為仿真初始時間。第二十頁，共46頁。3.4系統(tǒng)的統(tǒng)計性能指標(biāo)

與等價的圖示第二十一頁，共46頁。Flowchartofarrivalroutine第二十二頁，共46頁。voidarrive(void)/*Arrivaleventfunction.*/{floatdelay;

/*Schedulenextarrival.*/time_next_event[1]=sim_time+expon(mean_interarrival);

/*Checktoseewhetherserverisbusy.*/if(server_status==BUSY){

/*Serverisbusy,soincrementnumberofcustomersinqueue.*/++num_in_q;

/*Checktoseewhetheranoverflowconditionexists.*/if(num_in_q>Q_LIMIT){

/*Thequeuehasoverflowed,sostopthesimulation.*/fprintf(outfile,"\nOverflowofthearraytime_arrivalat");fprintf(outfile,"time%f",sim_time);exit(2);}

/*Thereisstillroominthequeue,sostorethetimeofarrivalofthearrivingcustomeratthe(new)endoftime_arrival.*/time_arrival[num_in_q]=sim_time;}FunctionArrive第二十三頁，共46頁。else{/*Serverisidle,soarrivingcustomerhasadelayofzero.(Thefollowingtwostatementsareforprogramclarityanddonotaffecttheresultsofthesimulation.)*/delay=0.0;total_of_delays+=delay;/*Incrementthenumberofcustomersdelayed,andmakeserverbusy.*/++num_custs_delayed;server_status=BUSY;/*Scheduleadeparture(servicecompletion).*/time_next_event[2]=sim_time+expon(mean_service);}}FunctionArrive(continued)第二十四頁，共46頁。Flowchartfordepartureroutine第二十五頁，共46頁。voiddepart(void)/*Departureeventfunction.*/{inti;floatdelay;/*Checktoseewhetherthequeueisempty.*/if(num_in_q==0){/*Thequeueisemptysomaketheserveridleandeliminatethedeparture(servicecompletion)eventfromconsideration.*/server_status=IDLE;

time_next_event[2]=1.0e+30;}

FunctionDepart第二十六頁，共46頁。else{/*Thequeueisnonempty,sodecrementthenumberofcustomersinqueue.*/--num_in_q;/*Computethedelayofthecustomerwhoisbeginningserviceandupdatethetotaldelayaccumulator.*/

delay=sim_time-time_arrival[1];total_of_delays+=delay;/*Incrementthenumberofcustomersdelayed,andscheduledeparture.*/++num_custs_delayed;time_next_event[2]=sim_time+expon(mean_service);/*Moveeachcustomerinqueue(ifany)uponeplace.*/for(i=1;i<=num_in_q;++i)time_arrival[i]=time_arrival[i+1];}}FunctionDepart(continued)第二十七頁，共46頁。FunctionReportvoidreport(void)/*Reportgeneratorfunction.*/{/*Computeandwriteestimatesofdesiredmeasuresofperformance.*/fprintf(outfile,"\n\nAveragedelayinqueue%11.3fminutes\n\n",total_of_delays/num_custs_delayed);fprintf(outfile,"Averagenumberinqueue%10.3f\n\n",area_num_in_q/sim_time);fprintf(outfile,"Serverutilization%15.3f\n\n",area_server_status/sim_time);fprintf(outfile,"Timesimulationended%12.3fminutes",sim_time);}第二十八頁，共46頁。Functionupdate_time_avg_statsvoidupdate_time_avg_stats(void)/*Updateareaaccumulatorsfortime- averagestatistics.*/{floattime_since_last_event;/*Computetimesincelastevent,andupdatelast-event-timemarker.*/

time_since_last_event=sim_time-time_last_event;time_last_event=sim_time;/*Updateareaundernumber-in-queuefunction.*/area_num_in_q+=num_in_q*time_since_last_event;/*Updateareaunderserver-busyindicatorfunction.*/area_server_status+=server_status*time_since_last_event;}第二十九頁，共46頁。3.5實體到達模式與泊松過程平穩(wěn)泊松過程 在(t,t+s)內(nèi)到達的實體數(shù)k的概率為:

N(t)表示在(0,t)區(qū)間內(nèi)到達實體的個數(shù)

λ為到達速率第三十頁，共46頁。3.5實體到達模式與泊松過程定理 如果{N(t),t≥0}是具有速率λ的泊松過程，那么其相應(yīng)的到達時間間隔A1,A2…是具有均值1/λ的IID指數(shù)隨機變量。平穩(wěn)泊松過程到達時間間隔服從指數(shù)分布,其密度函數(shù)為： 其中為到達時間間隔均值。第三十一頁，共46頁。FunctionExponfloatexpon(floatmean)/*Exponentialvariategenerationfunction.*/{/*Returnanexponentialrandomvariatewithmean"mean".*/return-mean*log(lcgrand(1));}第三十二頁，共46頁。Random-numbergenerate Thedefaultseedsforall100streamsstaticlongzrng[]={1,1973272912,281629770,20006270,1280689831,2096730329,1933576050,913566091,246780520,1363774876,604901985,1511192140,1259851944,824064364,150493284,242708531,75253171,1964472944,1202299975,233217322,1911216000,726370533,403498145,993232223,1103205531,762430696,1922803170,1385516923,76271663,413682397,726466604,336157058,1432650381,1120463904,595778810,877722890,1046574445,68911991,2088367019,748545416,622401386,2122378830,640690903,1774806513,2132545692,2079249579,78130110,852776735,1187867272,1351423507,1645973084,1997049139,922510944,2045512870,898585771,243649545,1004818771,773686062,403188473,372279877,1901633463,498067494,2087759558,493157915,597104727,1530940798,1814496276,536444882,1663153658,855503735,67784357,1432404475,619691088,119025595,880802310,176192644,1116780070,277854671,1366580350,1142483975,2026948561,1053920743,786262391,1792203830,1494667770,1923011392,1433700034,1244184613,1147297105,539712780,1545929719,190641742,1645390429,264907697,620389253,1502074852,927711160,364849192,2049576050,638580085,547070247};第三十三頁，共46頁。Random-numbergenerateForexample:lcgrand(1)floatlcgrand(intstream){ ...... zi=zrng[stream]; ......}第三十四頁，共46頁。SimulationOutputandDiscussionSingle-serverqueueingsystemMeaninterarrivaltime1.000minutesMeanservicetime0.500minutesNumberofcustomers1000Averagedelayinqueue0.430minutesAveragenumberinqueue0.418Serverutilization0.460Timesimulationended1027.915minutes第三十五頁，共46頁。SimulationOutputandDiscussionTheresultsarefunctionsoftheinputparameters:ThemeaninterarrivaltimeThemeanservicetimeThen=1000stoprule andalsodeterminedbythenumberstherandom-numbergenerated(withanother“seed”or“stream”).第三十六頁，共46頁。AlternativeStoppingRulesTwotypesofterminationWhenthenumberofcustomersdelayedbecameequalto1000. Thefinalvalueofthesimulationclockisarandomvariable.Aftersomefixedamountoftime. Thenumberofcustomersdelayedisarandomvariable. Theideacanbeimplementedintheprogramsbymakingchangstothefollowingroutines:ThemainprogramTheinitializationroutineThereportgenerator第三十七頁，共46頁。AlternativeStoppingRules/*Externaldefinitionsforsingle-serverqueueingsystem,fixedrunlength.*/#include<stdio.h>#include<math.h>#include"lcgrand.h"/*Headerrandom-numbergenerator.*/#defineQ_LIMIT100/*Limitonqueuelength.*/#defineBUSY1/*Mnemonicsforserver'sbeingbusy*/#defineIDLE0/*andidle.*/intnext_event_type,num_custs_delayed,num_events,num_in_q,server_status;/*num_delays_required

*/ floatarea_num_in_q,area_server_status,mean_interarrival,mean_service,sim_time,time_arrival[Q_LIMIT+1],time_end,time_last_event,

time_next_event[4],total_of_delays;FILE*infile,*outfile;voidinitialize(void);voidtiming(void);voidarrive(void);voiddepart(void);voidreport(void);voidupdate_time_avg_stats(void);floatexpon(floatmean);第三十八頁，共46頁。AlternativeStoppingRulestime_next_event[next_event_type]: next_event_type=1,2,3 1——arrive(); 2——depart(); 3——report();//theloopkeepsrepeatingitselfaslong asthetypeofeventjustexecutedisnot3;aftera type3eventischosenforexecution,theloopends andthesimulationstops.第三十九頁，共46頁。main()/*Mainfunction.*/{/*Openinputandoutputfiles.*/infile=fopen("mm1alt.in","r");outfile=fopen("mm1alt.out","w");/*Specifythenumberofeventsforthetimingfunction.*/

num_events=3;/*Readinputparameters.*/fscanf(infile,"%f%f%f",&mean_interarrival,&mean_service, &time_end);/*Writereportheadingandinputparameters.*/fprintf(outfile,"Single-serverqueueingsystemwithfixedrun");fprintf(outfile,"length\n\n");fprintf(outfile,"Meaninterarrivaltime%11.3fminutes\n\n",mean_interarrival);fprintf(outfile,"Meanservicetime%16.3fminutes\n\n",mean_service);fprintf(outfile,"Lengthofthesimulation%9.3fminutes\n\n",time_end);

/*Initializethesimulation.*/initialize();Mainfunction第四十頁，共46頁。/*Runthesimulationuntilitterminatesafteranend-simulationevent(type3)occurs.*/

do{timing();/*Determinethenextevent.*/update_time_avg_stats();/*Updatetime-averagestatisticalaccumulators.*/switch(next_event_type){/*Invoketheappropriateeventfunction.*/case1:arrive();break;case2:depart();break;

case3:report();break;}/*Iftheeventjustexecutedwasnottheend-simulationevent(type3),continuesimulating.Otherwise,endthesimulation.*/}while(next_event_type!=3);fclose(infile);fclose(outfile);return0;}Mainfunction(continued)第四十一頁，共46頁。voidinitialize(void)/*Initializationfunction.*/{/*Initializethesimulationclock.*/sim_time=0.0;/*Initializethestatevariables.*/server_status=IDLE;num_in_q=0;time_last_event=0.0;/*Initializethestatisticalcounters.*/num_custs_delayed=0;total_of_delays=0.0;area_num_in_q