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

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

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

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

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

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

/*Headerrandom-numbergenerator.*/#defineQ_LIMIT100/*Limitonqueuelength.*/#defineBUSY1/*Mnemonicsforserver'sbeingbusy*/#defineIDLE0/*andidle.*/第十頁(yè)，共46頁(yè)。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);第十一頁(yè)，共46頁(yè)。3.3事件調(diào)度法事件（Event）

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

/*Invokethereportgeneratorandendthesimulation.*/

report();fclose(infile);fclose(outfile);return0;}第十七頁(yè)，共46頁(yè)。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第十八頁(yè)，共46頁(yè)。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第十九頁(yè)，共46頁(yè)。3.4系統(tǒng)的統(tǒng)計(jì)性能指標(biāo)假設(shè)仿真目的是要估計(jì)服務(wù)n個(gè)顧客后的顧客平均隊(duì)長(zhǎng)Q(n)及平均排隊(duì)等待時(shí)間d(n)： 其中為第i個(gè)顧客排隊(duì)等待時(shí)間，Q(t)為t時(shí)刻排隊(duì)等待的顧客數(shù)，T為完成n個(gè)顧客服務(wù)所耗時(shí)間，d(n)、Q(n)表示估計(jì)值，、表示平均值。為計(jì)算方便 其中為時(shí)間區(qū)間上排隊(duì)人數(shù)乘以該時(shí)間區(qū)間長(zhǎng)度 ，即，其中是第i個(gè)任何一類事件發(fā)生的時(shí)間。

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

與等價(jià)的圖示第二十一頁(yè)，共46頁(yè)。Flowchartofarrivalroutine第二十二頁(yè)，共46頁(yè)。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第二十三頁(yè)，共46頁(yè)。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)第二十四頁(yè)，共46頁(yè)。Flowchartfordepartureroutine第二十五頁(yè)，共46頁(yè)。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第二十六頁(yè)，共46頁(yè)。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)第二十七頁(yè)，共46頁(yè)。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);}第二十八頁(yè)，共46頁(yè)。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;}第二十九頁(yè)，共46頁(yè)。3.5實(shí)體到達(dá)模式與泊松過程平穩(wěn)泊松過程 在(t,t+s)內(nèi)到達(dá)的實(shí)體數(shù)k的概率為:

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

λ為到達(dá)速率第三十頁(yè)，共46頁(yè)。3.5實(shí)體到達(dá)模式與泊松過程定理 如果{N(t),t≥0}是具有速率λ的泊松過程，那么其相應(yīng)的到達(dá)時(shí)間間隔A1,A2…是具有均值1/λ的IID指數(shù)隨機(jī)變量。平穩(wěn)泊松過程到達(dá)時(shí)間間隔服從指數(shù)分布,其密度函數(shù)為： 其中為到達(dá)時(shí)間間隔均值。第三十一頁(yè)，共46頁(yè)。FunctionExponfloatexpon(floatmean)/*Exponentialvariategenerationfunction.*/{/*Returnanexponentialrandomvariatewithmean"mean".*/return-mean*log(lcgrand(1));}第三十二頁(yè)，共46頁(yè)。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};第三十三頁(yè)，共46頁(yè)。Random-numbergenerateForexample:lcgrand(1)floatlcgrand(intstream){ ...... zi=zrng[stream]; ......}第三十四頁(yè)，共46頁(yè)。SimulationOutputandDiscussionSingle-serverqueueingsystemMeaninterarrivaltime1.000minutesMeanservicetime0.500minutesNumberofcustomers1000Averagedelayinqueue0.430minutesAveragenumberinqueue0.418Serverutilization0.460Timesimulationended1027.915minutes第三十五頁(yè)，共46頁(yè)。SimulationOutputandDiscussionTheresultsarefunctionsoftheinputparameters:ThemeaninterarrivaltimeThemeanservicetimeThen=1000stoprule andalsodeterminedbythenumberstherandom-numbergenerated(withanother“seed”or“stream”).第三十六頁(yè)，共46頁(yè)。AlternativeStoppingRulesTwotypesofterminationWhenthenumberofcustomersdelayedbecameequalto1000. Thefinalvalueofthesimulationclockisarandomvariable.Aftersomefixedamountoftime. Thenumberofcustomersdelayedisarandomvariable. Theideacanbeimplementedintheprogramsbymakingchangstothefollowingroutines:ThemainprogramTheinitializationroutineThereportgenerator第三十七頁(yè)，共46頁(yè)。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);第三十八頁(yè)，共46頁(yè)。AlternativeStoppingRulestime_next_event[next_event_type]: next_event_type=1,2,3 1——arrive(); 2——depart(); 3——report();//theloopkeepsrepeatingitselfaslong asthetypeofeventjustexecutedisnot3;aftera type3eventischosenforexecution,theloopends andthesimulationstops.第三十九頁(yè)，共46頁(yè)。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第四十頁(yè)，共46頁(yè)。/*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)第四十一頁(yè)，共46頁(yè)。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