A Simple Discrete-Event Simulation: Part 11

Now that we have a couple of basic mechanisms in place for building discrete-event simulations let’s apply them to some actual components we can use to represent something real. A very simple system might consist of the following four components strung together in series. The idea is that entities would be introduced into this system at an entry point, wait in a queue to be processed in some way, and then exit the system. Entities can travel between these items via paths, which can be logical or spatial. Queues and processes may incorporate paths.

A system must be simulated from a certain viewpoint, of which the model depicted here is one possibility. At one extreme, all of the intelligence can be in the fixed components shown, while the entities are entirely passive. Conversely, all of the intelligence can be in the entities while the fixed components are entirely passive. Each element can have its own characteristics whether it is active or passive. The question then becomes, in an object-oriented or architectural sense, which elements have code or calculations associated with them. As a practical matter it’s very likely that the logic will be distributed across elements in a hybrid fashion.

Let’s look at each element in turn. I’m not sure there’s a standard vocabulary to describe these concepts, but I try to be internally consistent with the names I use. I use the term component to refer to the entries, queues, processes, exits, and paths which make up the model environment. I use the term element to include both components and the entities which are processed. In theory this could include any part of the computing or interface aspects of the simulation as well.

Entity: Entities move through a system and are processed by it. They can be items in a manufacturing process, people, vehicles, items being shipped or inspected, inventory in a warehouse, or almost anything else. The key feature that entities have in common is that they move or are moved. That said, elements can have characteristics of entities and components (usually processes but sometimes queues), so the delineations are not always clear-cut. You can easily imagine a warehouse where active machine entities manipulate passive inventory entities. Similarly, many pieces of luggage can be placed on a cart and transported somewhere.

Entry: Entities are introduced into a simulation at defined points. The entities can all be generated at the beginning of the simulation and enter it over time, or they can be created on the fly as needed. They can be created on a defined and fixed schedule, on an entirely random basis, or on a hybrid basis. In the latter case a specific number of entities are generated in each time interval, but the specific times may vary or the number may be allowed to vary within a defined range. Any combination is possible. Moreover, the characteristics of entities entering the system can also vary on a completely scheduled, random, or hybrid manner. Sub-entities may be generated or forked off almost anywhere, at any time, for any reason, but always derive from a parent entity that entered the model at a defined point.

Queue: Queues are holding areas or containers where entities wait to be processed. They may be modeled explicitly as a container or implicitly as a section of path where entities wait to be processed In the latter case the extent of the queue is determined based on which entities have come to a stop at the end of a line (queue) of entities. Queues may require a certain amount of time to be traversed (that is, their representation may have a spatial component) or may make entities instantly available for processing at the instant they enter (as in the case of a logical queue). Many type of queues are possible. The most common is probably the FIFO (first-in, first-out) queue, but many other types are possible. These may include LIFO (last-in, first-out; which may also be referred to as a stack), random (think of a parking lot where the order of exit is driven by an external mechanism not related to the order of entry; this may not be explicitly random), double-ended (dequeue–or deque, for short), and other types.

Process: Processes are stations where operations are performed on entities. The most salient feature of processes is usually that they take a certain amount of time to complete. Beyond that they may cause changes to the entities being processed, consume or require other resources (staff, utilities, supplies), may process entities in different ways (randomly or based on an entity’s characteristics or type), may process entities differently based on the time of day or the status of other parts of the system, and may incorporate spatial features that take time to traverse in addition to the processing performed. In the case of physical entities transferring from queues to processes, a pull-up time can also be defined, as can an exit time. If processes are thought of as specific objects or stations (e.g., a tollbooth, workstation, or worker) then groups of similar processes working in parallel might be referred to using a term appropriate to the situation (e.g., plaza, bank, or team). The entire simulated system might, if representing something contiguous like an airport or border crossing, be referred to as a facility.

Exit: Entities don’t always leave simulations, but when they do it is usually at a defined exit point. Exit points are often a good place to capture statistics (e.g., processes visited, total processing time, total transit time, errors or rework, etc.) and free up computing resources.

Note that I often mention randomness in these descriptions. A simulation that does not include random variations (assuming it also does not incorporate user intervention), generates a deterministic result. This means that a given set of inputs always generates the same output. A simulation that does include random variations is a stochastic system. Analyses involving stochastic systems usually involve performing a large number of runs and evaluating the results statistically. Systems that involve user intervention may be referred to as interactive or dynamic, though there seems to be a somewhat formal definition for a dynamical system. For now we can leave those as separate topics.

Tomorrow I’ll begin extending the code to represent these elements. Interestingly, I’ll also have to come up with a way to represent the state of the model in a visual way, which can be thought of as a view. We already have the model, and the method of controlling the simulation is present implicitly, though it will be made explicit over time. Thus we have an example of a classic model-view-controller software pattern. I bring this up because there are cases where the view of the state of the simulation involves its own overhead beyond that which may strictly be needed to model the system. For example, entities may transfer between entries, queues, processes, and exits instantaneously, but it may be desirable to depict those operations as animations, which necessarily involve some finite amount of time, so the operations within the simulation are comprehensible to the viewer. For another example, an entity may be told to traverse a given path to a new component, but the details for doing so aren’t given. That operation may involve a whole new layer of complexity, though the details may be handled by existing mechanisms.

Finally, while I’ve discussed the possibility of using defined paths to go from one component to the next, the method of movement can actually be represented in many ways. Entities may move across defined points in a grid, or may move in an even more free-form way in a defined space, based on a different set of rules. For the foreseeable future I am going to be examining fairly straightforward, path-based systems. This will support the modeling of vast classes of systems.

This entry was posted in Simulation and tagged , . Bookmark the permalink.

Leave a Reply