Next-Event SimulationDiscrete-Event Simulation:A First CourseSection 5.1: Next-Event SimulationSection 5.1: Next-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Next-Event SimulationSection 5.1: Next-Event SimulationMaking small modifications to our simple discrete-eventsimulations is non-trivialAdd feedback to ssq2Add delivery lag to sis2Next-event simulation is a more general approach todiscrete-event simulationSystem stateEventsSimulation clocksEvent schedulingEvent listSection 5.1: Next-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Next-Event SimulationDefinitions and Terminology – StateThe state of a system is a complete characterization of thesystem at an instance in timeConceptual model - abstract collection of variables and howthey evolve over timeSpecification model - collection of mathematical variablestogether with logic and equationsComputational model - collection of program variablessystematically updatedExample 5.1.1 State of ssq is number of jobs in the nodeExample 5.1.2 State of sis is current inventory levelSection 5.1: Next-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Next-Event SimulationDefinitions and Terminology - EventsAn event is an occurrence that may change the state of thesystemExample 5.1.3 For s sq, eve nts are arrivals or completion of ajobsWith feedback, the state may changeExample 5.1.4 For s is with deliv ery lag, events are demandinstances, inventory reviews, and arrival of ordersWe can define artificial eventsStatistically sample the state of the systemSchedule an event at a prescribed timeSection 5.1: Next-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Next-Event SimulationDefinitions and Terminology - Simulation ClockThe simulation clo ck represents the current value of simulatedtimeDiscrete-event simulations lack definitive simulated timeAs a result, it is difficult to generalize or embellish modelsExample 5.1.5 It is hard to reason about ssq2 because thereare effectively two simulation clocksArrival times and completion times are not synchronizedExample 5.1.6 In sis2, the only event is inventory reviewThe simulation clock is integer-valued and we aggregate alldemandSection 5.1: Next-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Next-Event SimulationDefinitions and Terminology -Event Scheduling & Event ListIt is necessary to use a time-advance mechanism to guaranteethat events occur in the correct orderNext-event time advance is typically used in discrete-eventsimulationTo build a next-event simulation:construct a set of state variablesidentify the event typesconstruct a set of algorithms that define state changes for eachevent typeThe event list is the data structure containing the time ofnext occurrence for each event typ eSection 5.1: Next-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Next-Event SimulationNext-Event SimulationAlgorithm 5.1.11Initialize - set simulation clock and first time of occurrencefor each event typ e2Process current event - scan event list to determine mostimminent event; advance simulation clock; update state3Schedule new events - new events (if any) are placed in theevent list4Terminate - Continue advancing the clock and handlingevents until termination condition is satisfiedThe simul ation clock runs asynchronously; inactive periods areignoredClear computational advantage over fixed-incrementtime-advance mechanismSection 5.1: Next-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Next-Event SimulationSingle-Server Service NodeThe state variable l(t) provides a complete characterization ofthe state of a ssql(t) = 0 ⇐⇒ q(t) = 0 and x(t) = 0l(t) > 0 ⇐⇒ q(t) = l (t) − 1 and x(t) = 1Two events cause this variable to change1An arrival causes l(t) to increase by 12A completion of service causes l(t) to decrease by 1Section 5.1: Next-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Next-Event SimulationSingle-Server Service NodeThe initial state l(0) can have any non-negative value,typically 0The terminal state can be any non-negative valueAssume at time τ arrival process stopped. Remaining jobsprocessed before terminationSome mechanism must be used to denote an event impossibleOnly store possible events in event listDenote impossible events with event time of ∞Section 5.1: Next-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Next-Event SimulationSingle-Server Service NodeThe simulation clock (current time) is tThe terminal (“close the door”) time is τThe next scheduled arrival time is taThe next scheduled service completion time is tcThe number in the node (state variable) is lSection 5.1: Next-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Next-Event SimulationAlgorithm 5.1.2Algorithm 5.1.2l = 0;t = 0.0;ta= GetArrival(); /* initialize the event list */tc= ∞;while ((ta< τ ) or (l > 0)) {t = min(ta, tc); /* scan the event list */if (t == ta) { /* process an arrival */l ++;ta= GetArrival();if (ta> τ )ta= ∞;if (l == 1)tc= t + GetService();}else { /* process a completion */l − −;if (l > 0)tc= t + GetService();elsetc= ∞;}}Section 5.1: Next-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Next-Event SimulationProgram ssq3In ssq3, number represents l(t) and structure t representstimethe event list t.arrival and t.completion (taand tcfromAlgorithm 5.1.2);the simulation clock t.current (t from Algorithm 5.1.2)the next event time t.next (min(ta, tc) from Algorithm 5.1.2)the last arrival time t.lastTime-averaged statistics are gathered with the structure areaZt0l(s) ds evaluated as area.nodeZt0q(s) ds evaluated as area.queueZt0x(s) ds evaluated as area.serviceSection 5.1: Next-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Next-Event SimulationWorld Views and SynchronizationPrograms ssq2 and ssq3 simulate exactly the same systemThe two have different world viewsssq2 naturally produces job-averaged statisticsssq3 naturally produces time-averaged statisticsThe programs should pro duce e xactly the same statisti csTo do so requires rngsSection 5.1: Next-Event Simulation Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Next-Event SimulationModel ExtensionsImmediate Feedbackelse