Ch. 1 Basic Simulation Modeling.ppt

1、1,Ch. 1 Basic Simulation Modeling,2,Notas,http:/delta.cs.cinvestav.mx/lixo/teaching,3,Basic Simulation Modeling,The nature of simulation Systems, Models and Simulation Discrete-Event Simulation Simulation of a single-server queuing system Steps in a sound simulation study Advantages, disadvantages a

2、nd pitfalls of simulation,4,The Nature of Simulation,Conceptions Application areas Academic level Impediments,5,Conceptions,Simulation course is about techniques for using computers to imitate or simulate the operations of various kinds of real world facilities or processes System: the facility or p

3、rocess of interest Model: a set of assumptions about how the system works, which usually take the form of mathematical or logical relationships, constitute a model that is used to try to gain more understanding of how the corresponding system behaves. Analytic soulution: to obtain exact information

4、on questions of intresets. Simulation: use a computer to evaluate a model numerically, and data are gathered in order to estimate the desired true characteristics of the model.,6,Example,a manufacturing company contemplates building a large extension onto one of its plants, but is not sure if the po

5、tential gain in productivity would justify the construction cost.,7,Application areas,Designing and analyzing manufacturing systems evaluating military weapons systems or their logistics requirements determining hardware requirements or protocols for communication networks Determining hardware and s

6、oftware requirements for a computer system Designing and operating transportation systems such as airports, freeways, ports and subways Evaluating designs for service organizations such as call centers, fast-food restaurants, hospitals, and post offices Reengineering of business processes Determinin

7、g ordering polices for an inventory system Analyzing financial or economic systems,8,Academic level,Winter Simulation Conference (600-700 people every year) Is one of the three important operations-research techniques (in serveys related to the use of operations research techniques: math programming

8、, statistics, simulation) The second only to “math programming” among 13 techniques considered (in 1294 papers from the journal Interfaces from 1970 through 1992),9,Impediments,Models used to study large-scale systems tend to be very complex, and writing computer programs to execute them can be an a

9、rduous task indeed. (excellent software products) Large amount of computer time is sometimes required. (cheaper and faster computer) An unfortunate impression that simulation is just an exercise in computer programming, albeit a complicated one. (attitude, simulation methodology),10,Systems, Models

10、and Simulation,System is defined to be a collection of entities, e.g., people or machines, which act and interact together toward the accomplishment of some logical end. System depends on the objectives of a particular study. State of a system: collection of variables necessary to describe a system

11、at a particular time, relative to the objectives of a study. (the number of busy tellers, the number of customers in the bank, the time of arrival of each customer in the bank) discrete system: the state variables change instantaneously at separated points in time. (a bank, e.g., the number of custo

12、mers in the bank) continuous system: the state variables change continuously with respect to time. (an airplane moving through the air, e.g., position and velocity ),11,Continue.,Study on a system: try to gain some insight into the relationships among various components, or to predict performance un

13、der some new conditions being considered. Ways to study a system,12,System,Experiment with the actual system,Physical model,Analytical solution,Simulation,Experiment with a model of the system,Mathematical model,13,Example,One study on a bank to determine the number of tellers needed to provide adeq

14、uate service for customers who want just to cash a check or make a savings deposite, the system can be defined to be that portion of the bank consisting of the tellers and the customers waiting in line or being served. If the loan officer and the safety deposite boxes are to be included, the definit

15、ion of the system must be expanded in an obvious way.,14,Discrete Event Simulation,Definition Time-Advance Mechanisms Components and Organization of a Discrete -Event Simulation Model Components Logic Organization,15,Definitions,Discrete-event simulation concerns the modeling of a system as it evolv

16、es over time by a representation in which the state variables change instantaneously at separate points in time. Or the system can change at only a countable number of points in time. Event is defined as an instantaneous occurrence that may change the state of the system.,16,Example 1.1,Single-serve

17、r queuing system: a barbershop, to estimate the (expected) average delay in queue (line) of arriving customers State variables: the status of the server (busy or idle), the number of customers waiting in queue to be served, the time of arrival of each person waiting in queue. Events: the arrival of

18、a customer and the completion of service for a customer, which results in the customers departure.,17,Time-Advance Mechanism,Simulation clock: the variable in a simulation model that gives the current value of simulated time. to keep track of the current value of simulated time as the simulation pro

19、ceeds to advance simulated time from one value to another Advancing the simulation clock next-event time advance (mostly used) fixed-increment time advance (a special case of the first) Next-event time-advance approach simulation clock is initialized to zero the times of occurrence of future events

20、are determined.,18,Example 1.2,Notations: : time of arrival of the ith customer () : interarrival time between (i-1)st and ith arrivals of customers : time that server actually spends serving ith customer (exclusive of customers delay in queue) : delay in queue of ith customer : time that ith custom

21、er completes service and departs : time of occurrence of ith event of any type (ith value the simulation clock takes on, excluding the value ),19,e0,e1,e2,e3,e4,e5,0,t1,t2,c1,t3,c2,A1,A2,A3,S1,S2,Time,20,Components and Organization of a Discrete -Event Simulation Model,Components (10) Systems state:

22、 The collection of state variables necessary to describe the system at a particular time Simulation clock: A variable giving the current value of simulated time Event list: A list containing the next time when each type of event will occur Statistical counters: Variables used for storing statistical

23、 information about system performance,21,Continue.,Initialization routine: A subprogram to initialize the simulation model at time 0 Timing routine: A subprogram that determines the next event from the event list and then advances the simulation clock to the time when that event is to occur Event ro

24、utine: A subprogram that updates the system state when a particular type of event occurs (there is one event routine for each event type) Library routines: A set of subprograms used to generate random observations from probability distributions that were determined as part of the simulation model,22

25、,Continue.,Report generator: A subprogram that computes estimates (from the statistical counters) of the desired measures of performance and produces a report when the simulation ends Main program: A subprogram that invokes the timing routine to determine the next event and then transfers control to

26、 the corresponding event routine to update the system state appropriately. The main program may also check for termination and invoke the report generator when the simulation is over.,23,Start,1. Set simulation clock=0 2. Initialize system stateand statistical counters 3. Initialize event list,0. In

27、voke the initialization routine1. Invoke the timing routine 2. Invoke event routine,1. Determine the next event type, say, i 2. Advance the simulation clock,1.Update system state 2.Update statistical counters 3.Generate future events and add toevent list,Repeatedly,Initialization routine,Main progra

28、m,Time routine,Event routine i,Generate random variates,Library routines,Is simulation over?,1. Compute estimates of interest 2. Write report,Stop,Report generator,1,0,2,i,No,Yes,24,Simulation of A Single-Server Queueing System,25,Components of a queueing system,Arrival process: Interarrivals: Ai Me

29、an interarrival time: E(A) Arrival rate: Service mechanism Service time: Si Number of servers: s Mean service time: E(S) Service rate: Queue discipline FIFO LIFO Priority* D. Gross, and C.M. Harris, Fundamentals of Queueing Theory, 3d ed., John Wiley, New York, 1998,26,Notation for queueing systems,

30、s servers in parallel and one FIFO queue feeding all servers A1, A2, are IID random variables S1, S2,are IID random variables The Ais and Sis are independent,1,2,s,. . .,FIGURE 1.71 A GI/G/s queue,27,GI/G/s queue,GI (general independent): the distribution of the Ais G (general): the distribution of

31、the Sis Symbols: M (exponential), Ek (k-Erlang), D (deterministic times) M/M/1: a single-server queueing system with exponential interarrival and service times and a FIFO discipline: the utilization factor of the queueing system,28,A departure customer,Server,Customer in service,Customers in queue,A

32、n arrival customer,FIGURE 1.4 A single-server queueing system.,29,Measures of Performance for Queueing Systems,: delay in queue of ith customer,: waiting time in system of ith customer,: number of customers in queue at time t,: number of customers in system at time t Q(t) plus number of customers be

33、ing served at time t,: steady-state average delay,: steady-state average waiting time,: steady-state time-average number in queue,: steady-state time-average number in system,30,e1, e2, , e13 : 13 successive events n=6 : delays in queue,Interarrival times: A1=0.4, A2=1.2, A3=0.5, A4=1.7, A5=0.2,A6=1

34、.6, A7=0.2, A8=1.4, A9=1.9, ,Service times: S1=2.0, S2=0.7, S3=0.2, S4=1.1, S5=3.7, S6=0.6, ,31,Measures of Performance for the example,: delay in queue of ith customer,: the expected proportion of the time that Q(t) is equal to i,: number of customers in queue at time t,The expected average delay i

35、n queue,The expected average number of customers in queue,32,t,Q(t),0,1,2,3,4,5,6,7,8,9,e1=0.4,e2=1.6,e3=2.1,e4=2.4,e5=3.1,e6=3.3,e7=3.8,e8=4.0,e9=4.9,e10=5.6,e11=5.8,e12=7.2,e13=8.6=T(6),FIGURE 1.5 Q(t), arrival times, and departure times for a realization of a single-server queueing system.,Arriva

36、ls,Departures,1,2,3,33,Measures of Performance for the example,The expected utilization of the server,34,t,B(t),0,1,2,3,4,5,6,7,8,9,e1=0.4,e2=1.6,e3=2.1,e4=2.4,e5=3.1,e6=3.3,e7=3.8,e8=4.0,e9=4.9,e10=5.6,e11=5.8,e12=7.2,e13=8.6=T(6),FIGURE 1.6 B(t), arrival times, and departure times for a realizatio

37、n of a single-server queueing system.,Arrivals,Departures,1,35,Intuitive Explanation,36,0,0,0,0,0,0,0,0,Computer Representation,System state,Statistical counters,Sever status,Total delay,Area under Q(t),Area under B(t),Clock,Event list,Initialization time = 0,System,(a),Numberin queue,Times of arriv

38、al,Time of last event,0.4,A,D,Number delayed,37,1,0,0.4,0.4,1,0,0,0,Computer Representation,System state,Statistical counters,Sever status,Total delay,Area under Q(t),Area under B(t),Clock,Event list,Arrival time = 0.4,System,(b),Numberin queue,Times of arrival,Time of last event,1.6,A,D,0.4,2.4,Num

39、ber delayed,38,1,1,1.6,1.6,1,0,0,1.2,Computer Representation,System state,Statistical counters,Sever status,Total delay,Area under Q(t),Area under B(t),Clock,Event list,Arrival time = 1.6,System,(c),Numberin queue,Times of arrival,Time of last event,2.1,A,D,0.4,2.4,1.6,1.6,Number delayed,39,1,2,2.1,

40、2.1,1,0,0.5,1.7,Computer Representation,System state,Statistical counters,Sever status,Total delay,Area under Q(t),Area under B(t),Clock,Event list,Arrival time = 2.1,System,(d),Numberin queue,Times of arrival,Time of last event,3.8,A,D,0.4,2.4,1.6,1.6,2.1,2.1,Number delayed,40,1,1,2.4,2.4,2,0.8,1.1

41、,2.0,Computer Representation,System state,Statistical counters,Sever status,Total delay,Area under Q(t),Area under B(t),Clock,Event list,Departure time = 2.4,System,(e),Numberin queue,Times of arrival,Time of last event,3.8,A,D,1.6,3.1,2.1,2.1,Number delayed,41,1,0,3.1,3.1,3,1.8,1.8,2.7,Computer Rep

42、resentation,System state,Statistical counters,Sever status,Total delay,Area under Q(t),Area under B(t),Clock,Event list,Departure time = 3.1,System,(f),Numberin queue,Times of arrival,Time of last event,3.8,A,D,2.1,3.3,Number delayed,42,0,0,3.3,3.3,3,1.8,1.8,2.9,Computer Representation,System state,

43、Statistical counters,Sever status,Total delay,Area under Q(t),Area under B(t),Clock,Event list,Departure time = 3.3,System,(g),Numberin queue,Times of arrival,Time of last event,3.8,A,D,Number delayed,43,1,0,3.8,3.8,4,1.8,1.8,2.9,Computer Representation,System state,Statistical counters,Sever status

44、,Total delay,Area under Q(t),Area under B(t),Clock,Event list,Arrival time = 3.8,System,(h),Numberin queue,Times of arrival,Time of last event,4.0,A,D,3.8,4.9,Number delayed,44,1,1,4.0,4.0,4,1.8,1.8,3.1,Computer Representation,System state,Statistical counters,Sever status,Total delay,Area under Q(t

45、),Area under B(t),Clock,Event list,Departure time = 4.0,System,(i),Numberin queue,Times of arrival,Time of last event,5.6,A,D,3.8,4.9,4.0,4.0,Number delayed,45,1,0,4.9,4.9,5,2.7,2.7,4.0,Computer Representation,System state,Statistical counters,Sever status,Total delay,Area under Q(t),Area under B(t)

46、,Clock,Event list,Departure time = 4.9,System,(j),Numberin queue,Times of arrival,Time of last event,5.6,A,D,8.6,4.0,Number delayed,46,1,1,5.6,5.6,5,2.7,2.7,4.7,Computer Representation,System state,Statistical counters,Sever status,Total delay,Area under Q(t),Area under B(t),Clock,Event list,Arrival

47、 time = 5.6,System,(k),Numberin queue,Times of arrival,Time of last event,5.8,A,D,4.0,8.6,5.6,5.6,Number delayed,47,1,2,5.8,5.8,5,2.7,2.9,4.9,Computer Representation,System state,Statistical counters,Sever status,Total delay,Area under Q(t),Area under B(t),Clock,Event list,Arrival time = 5.8,System,

48、(l),Numberin queue,Times of arrival,Time of last event,7.2,A,D,4.0,8.6,5.6,5.6,5.8,5.8,Number delayed,48,1,3,7.2,7.2,5,2.7,5.7,6.3,Computer Representation,System state,Statistical counters,Sever status,Total delay,Area under Q(t),Area under B(t),Clock,Event list,Arrival time = 7.2,System,(m),Numberin queue,Times of arrival,Time of last event,9.1,A,D,4.0,8.6,5.6,5.6,5.8,5.8,7.2,7.2,Number delayed,49,1,2,8.6,8.6,6,5.7,9.9,7.7,Computer Representation,