Discrete-event vs. discrete-time simulation

The time we experience in everyday life is continuous. Engineers simulating, e.g., the flight behavior of an aircraft, have to build a continuous-time model accounting for quite complex dynamics. To make the model amenable to numerical simulation, suitable discretization schemes have to be devised; indeed, nothing is continuous in the digital world of computers. The way in which this discretization is done influences the computational burden and accuracy of predictions obtained by running the model. Over the years, we all have noticed the improvement in weather forecasts due to more sophisticated models and numerical schemes, as well as dramatically faster computer hardware, allowing for fine discretizations. The knowledge involved in suitable discretizations of continuous systems is really cutting-edge.

Fig. 9.8 Sample path of a discrete-event queueing system.

Luckily, time discretization is often much more natural in many business models. In the inventory control problem of Example 9.26, there is really no need to model the exact timing of demand, if we review inventory in the evening and we receive shipments in the morning. The system will change its state only at naturally discrete-time instants, resulting in very simple dynamics:

i.e., inventory at the end of day t is just the inventory at the end of the day before, plus what we receive from suppliers on day t, minus demand on day t. We see that simulating such a system involves state changes at regular time steps. In other cases, system dynamics is not so easy and regularly paced. Consider again the queueing system of Section 9.2.1. Assume that there is only one server in the system and that its service time for each customer is random. If we model the arrival process by a Poisson process, we have to simulate the system in continuous time; according to this model, the time elapsing between successive arrivals is exponentially distributed, and the exponential distribution is a continuous one. A possible sample path of such a system is illustrated in Fig. 9.8, which shows how the main state variable, the queue length L(t), evolves in time. To be precise, L(t) counts the number of customers in the system, including the one currently being served. From this sample path, it is easy to figure out the sequence of events taking place:

• At time T₁ the first customer arrives; the server is idle, so service starts immediately.
• At time T₂ the second customer arrives; the server is busy, so this customers is enqueued; now there are two customers in the system.
• At time T₃ the first customer completes her service, and the second one starts being served; the number of customers in the system is decreased.
• At time T₄ the second service is completed; there is no one in the queue, and server gets idle.
• At time T₅ the third customer arrives, and so on.

We notice that the relevant state variable follows a piecewise constant path, whereby abrupt changes are due to occurrence of events. Queueing systems are the standard example of discrete-event dynamics. To simulate a discrete-event system we need the following ingredients:

• A system clock, whose current value is denoted by t_cl, representing simulated time.
• An ordered list of events – the clock is advanced to the earliest scheduled event.
• Data structures to represent the system state.
• A set of procedures to manage each type of event; events change the system state and possibly schedule the occurrence of later events.

In a standard queueing system, there are two natural events: the arrival of a new customer and the completion of a service. The way in which these events should be handled can be outlined as follows.

Arrival of a customer. When a customer arrives, we check the server state:

• If it is idle, we start service immediately; we also schedule the next completion time, by drawing a random variable T_s according to the chosen probability distribution and adding it to the current clock time t_cl; we insert a completion event in the sorted list of events, with clock time T_s + t_cl.
• If the server is busy, we insert the customer in the queue.

In any case, we schedule the next arrival by drawing an interarrival time T_a, and inserting an arrival event in the sorted list of events, with clock time T_a + t_cl.

Completion of a service. When a service is completed, we should check the queue:

• If it is empty, the state of the server is changed to idle.
• Otherwise, we pick the first customer in the queue, possibly according to some priority scheme, draw a random variable T_s accounting for service time, and insert a completion event in the sorted list of events, with time T_s + t_cl.

After the current event is processed, we pick the next one in the list, advance the clock t_cl accordingly, and process the event as prescribed.

Conceptually, discrete-event simulations are not so difficult for very simple systems. However, when there are many entities and resources in the system, with complicated interactions, suitable simulation languages and environments are needed. In particular, the collection of relevant statistics about waiting times, queue lengths, and resource utilizations can be awkward without suitable tools. Clearly, it takes some skill to implement a simulation model, but this kind of technicality should not hide some more relevant difficulties:

• Which system features are really important, and which can be neglected? Any model is a simplification of reality; too many details will make model building more difficult; even worse, data requirements will become unmanageable. There is no point in building a complex model if the data we feed are not reliable. This type of decision is more of an art than a science, as you can imagine.
• The output of any Monte Carlo simulation should be regarded as a random variable. Which statistical techniques should we use to analyze the output? How should we plan the simulation experiments? A good knowledge of inferential statistics is an essential ingredient of a serious and successful simulation study.