第3讲离散事件系统仿真原理与程序

第3讲离散事件系统仿真原理与程序第一页，共46页。主要内容

（以排队系统为例）3.1问题的提出3.2排队系统的组成3.3事件调度法3.4系统的统计性能指标3.5实体到达模式与泊松过程第二页，共46页。3.1问题的提出

排队常常是件很令人恼火的事情……尤其是在我们这样的人口大国。电话亭－1978年在北京15%的电话要在1小时后才能接通。在电报大楼打电话的人还要带着午饭去排队。银行窗口，ATM医院火车售票交通理发游乐场的游乐项目第三页，共46页。3.1问题的提出第四页，共46页。3.1问题的提出怎样缩短排队的等待时间？银行的排队叫号机。只是有序的组织了顾客，并没有减少等待时间。如果能实现知道轮到自己需要等待多少时间，再选择合适的时间来，岂不很好？第五页，共46页。3.1问题的提出例，单人理发馆系统,设上午9:00开门,下午5:00关门。

特点：顾客到达时间一般是随机的,为每个顾客服务的时间长度也是随机的。系统的状态：服务台的状态(忙或闲)、顾客排队等待的队长也是随机的。状态量的变化只能在离散的随机时间点上发生。第六页，共46页。3.2排队系统的组成排队系统的三个基本组成部分到达模式 指临时实体按怎样的规律到达。服务模式 指同一时刻有多少服务台可以接纳临时实体，它们的服务要多少时间。排队规则 服务台完成当前服务后，从队列中选择下一个实体服务的原则。排队系统的基本结构到达模式排队服务机构到达离去第七页，共46页。3.2排队系统的组成M/M/1的含义到达时间间隔服从指数分布,用M表示服务时间的分布服从指数分布,用M表示单队单服务台第八页，共46页。3.2排队系统的组成稳态平均延误时间

实体通过系统的稳态平均滞留时间w稳态平均队长Q系统中稳态平均实体数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事件调度法事件（Event）

引起系统状态发生变化的行为，系统是由事件来驱动的。“顾客到达”为一类事件 顾客到达→引起系统状态：服务员的“状态”——从闲变到忙（如果无人排队)；或者另一系统状态——排队的人数发生变化（队列人数增加)。“顾客离去”为一类事件 服务完毕后离开系统→服务台“状态”由忙变成闲。第十二页，共46页。3.3事件调度法定义系统事件类型: 类型1顾客到达事件 类型2顾客接受服务事件（本程序未考虑）类型3顾客服务完毕并离去事件定义程序事件:仿真运行到150个时间单位(例如分钟)结束。假定已经得到到达时间间隔随机变量的样本值为:系统初始状态:思考：请列出该排队系统的事件表。第十三页，共46页。3.3事件调度法事件表第十四页，共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系统的统计性能指标假设仿真目的是要估计服务n个顾客后的顾客平均队长Q(n)及平均排队等待时间d(n)： 其中为第i个顾客排队等待时间，Q(t)为t时刻排队等待的顾客数，T为完成n个顾客服务所耗时间，d(n)、Q(n)表示估计值，、表示平均值。为计算方便 其中为时间区间上排队人数乘以该时间区间长度 ，即，其中是第i个任何一类事件发生的时间。

m为在区间上发生的事件总数，其中为仿真初始时间。第二十页，共46页。3.4系统的统计性能指标

与等价的图示第二十一页，共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实体到达模式与泊松过程平稳泊松过程 在(t,t+s)内到达的实体数k的概率为:

N(t)表示在(0,t)区间内到达实体的个数

λ为到达速率第三十页，共46页。3.5实体到达模式与泊松过程定理 如果{N(t),t≥0}是具有速率λ的泊松过程，那么其相应的到达时间间隔A1,A2…是具有均值1/λ的IID指数随机变量。平稳泊松过程到达时间间隔服从指数分布,其密度函数为： 其中为到达时间间隔均值。第三十一页，共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