A Simple Discrete-Event Simulation: Part 14

Posted on September 22, 2016 by R.P. Churchill

Today I modified the entry component so it creates new entities according to a supplied schedule. This can be made as complex as we’d like but let’s keep it simple for now: the input parameters are the duration of each scheduled block (in minutes) and the array of arrivals itself.

The entry object keeps a running index into the schedule array, a new value of which is read every 30 minutes. The increment method generates new entities spread even across the time span. It does this by dividing the block duration by the number of arrivals plus one, and then generating a new arrival on each increment (one arrival leads to two spans which leads to an arrival at 15 minutes, two arrivals leads to three spans which leads to arrivals at ten and twenty minutes, three arrivals leads to four spans which lead to arrivals every 7.5 minutes). No arrivals happen at the beginning or end of the schedule block.

Here’s the code for the new entry component:

And here’s the array definition and the call to create the entry component.

This works as expected, as demonstrated by the output:


360.000000 minutes

Entry component 1 generates 0 new entities at time 0
Entry component 1 generates 0 new entities at time 30
entity 2 created at time 60
Entry component 1 generates 1 new entities at time 60
entity 2 updated at time 75
entity 2 terminated at time 77
entity 3 created at time 90
entity 4 created at time 90
entity 5 created at time 90
Entry component 1 generates 3 new entities at time 90
entity 3 updated at time 97.5
entity 3 terminated at time 99.5
entity 4 updated at time 105
entity 4 terminated at time 107
entity 5 updated at time 112.5
entity 5 terminated at time 114.5
entity 6 created at time 120
entity 7 created at time 120
entity 8 created at time 120
entity 9 created at time 120
Entry component 1 generates 4 new entities at time 120
entity 6 updated at time 126
entity 6 terminated at time 128
entity 7 updated at time 132
entity 7 terminated at time 134
entity 8 updated at time 138
entity 8 terminated at time 140
entity 9 updated at time 144
entity 9 terminated at time 146
entity 10 created at time 150
entity 11 created at time 150
entity 12 created at time 150
entity 13 created at time 150
Entry component 1 generates 4 new entities at time 150
entity 10 updated at time 156
entity 10 terminated at time 158
entity 11 updated at time 162
entity 11 terminated at time 164
entity 12 updated at time 168
entity 12 terminated at time 170
entity 13 updated at time 174
entity 13 terminated at time 176
entity 14 created at time 180
entity 15 created at time 180
entity 16 created at time 180
entity 17 created at time 180
entity 18 created at time 180
Entry component 1 generates 5 new entities at time 180
entity 14 updated at time 185
entity 14 terminated at time 187
entity 15 updated at time 190
entity 15 terminated at time 192
entity 16 updated at time 195
entity 16 terminated at time 197
entity 17 updated at time 200
entity 17 terminated at time 202
entity 18 updated at time 205
entity 18 terminated at time 207
entity 19 created at time 210
entity 20 created at time 210
entity 21 created at time 210
entity 22 created at time 210
entity 23 created at time 210
entity 24 created at time 210
Entry component 1 generates 6 new entities at time 210
entity 19 updated at time 214.28571428571428
entity 19 terminated at time 216.28571428571428
entity 20 updated at time 218.57142857142858
entity 20 terminated at time 220.57142857142858
entity 21 updated at time 222.85714285714286
entity 21 terminated at time 224.85714285714286
entity 22 updated at time 227.14285714285714
entity 22 terminated at time 229.14285714285714
entity 23 updated at time 231.42857142857142
entity 23 terminated at time 233.42857142857142
entity 24 updated at time 235.71428571428572
entity 24 terminated at time 237.71428571428572
entity 25 created at time 240
entity 26 created at time 240
entity 27 created at time 240
Entry component 1 generates 3 new entities at time 240
entity 25 updated at time 247.5
entity 25 terminated at time 249.5
entity 26 updated at time 255
entity 26 terminated at time 257
entity 27 updated at time 262.5
entity 27 terminated at time 264.5
entity 28 created at time 270
entity 29 created at time 270
Entry component 1 generates 2 new entities at time 270
entity 28 updated at time 280
entity 28 terminated at time 282
entity 29 updated at time 290
entity 29 terminated at time 292
entity 30 created at time 300
Entry component 1 generates 1 new entities at time 300
entity 30 updated at time 315
entity 30 terminated at time 317
Entry component 1 generates 0 new entities at time 330
Entry component 1 terminated at time 360

Again, there are a lot of ways to make this mechanism more complicated. We could define several types of arrivals, which would involve a more complex data structure and more involved calculations. We could define different ways to distribute the arrivals over each time span (which I will discuss next week). We could have this component generate entries for the entire simulation and then use a different data structure to define how arrivals are distributed over multiple locations where the entries actually occur. Conversely, we could have a separate entry component and arrival definition for each entry location, individually. The possibilities are endless.

The main thing to note is that, depending on how it’s implemented, the entry component may be less a part of the process being modeled then it is a meta-component of the simulation. The mechanisms can and usually do end up being co-mingled.

Posted in Simulation | Tagged , | Leave a comment

A Simple Discrete-Event Simulation: Part 13

Posted on September 21, 2016 by R.P. Churchill

Today I wanted to streamline the code in the activate method for the entities that apply the advance command. I started by breaking the code in the series of if statements out into separate methods, which at least makes things look cleaner.

I defined a standard function called errorUndefinedAdvanceState so I don’t have to continually redefine it for the default/error condition, but the fact that it’s external to the object means that you have to pass the identifying parameters in to it.

I also observed that using strings for the governing state variable is unnecessarily slow, though it does provide information for the programmer. If these were replaced by variables with similar names that were assigned numeric values (e.g., 0, 1, 2, etc…), then the operations would be much quicker.

My next thought was to build some sort of hash table that could be used by yet another standard, external function, but then you’d have to build the hash, process it externally, and possibly incur extra overhead and weirdness. If you’re going to include overhead that can’t be hidden from the programmer via a compiler which handles such mechanisms in the background, you might as well keep it as clear and simple as you can.

I then read up on the relative merits of compound if statements and switch statements. You can Google the discussion for yourself, but the most interesting finding was the idea of declaring an array of functions (see a decent discussion of the idea here), which are then called using the numeric state variable as an array reference.

This works great in theory, and I tried it by modifying the code above.

This method works…sort of–but not really. The problem stems from all of the properties and methods being inside an object (technically a closure). The mechanism calls the proper subroutine, but has lost track of the context, which means it can’t properly refer to the various properties (e.g., this.entityID) correctly. The problem has to do with the this keyword. The this keyword is supposed to identify the owner of the item in question, which usually means an object. In this case however, we’ve assigned the function to an array, and when we call it the context of the this is (most annoyingly) the array, and not the parent object. I tried some things like dereferencing using foolishness like this.this, using external variables to hold the correct context, and so on, but nothing seemed to work. I thought about using anonymous functions but that seemed to take me back to where I started. I like this idea, even if it only makes sense for cases where there are many options, but I’ll have to do some more research.

Posted in Simulation | Tagged , | Leave a comment

A Simple Discrete-Event Simulation: Part 12

Posted on September 20, 2016 by R.P. Churchill

Today I wanted to start constructing an Entry component. I created a very simple on that generates modeled entities are regular, defined intervals over the duration of the simulation run. Here’s the relevant code.

This generates the following output.

1440.000000 minutes

entity 2 created at time 0
Entry component 1 generates new entity at time 0
entity 2 updated at time 0
entity 2 terminated at time 2
entity 3 created at time 30
Entry component 1 generates new entity at time 30
entity 3 updated at time 30
entity 3 terminated at time 32
entity 4 created at time 60
Entry component 1 generates new entity at time 60
entity 4 updated at time 60
entity 4 terminated at time 62
entity 5 created at time 90
Entry component 1 generates new entity at time 90
entity 5 updated at time 90
entity 5 terminated at time 92
...
entity 48 created at time 1380
Entry component 1 generates new entity at time 1380
entity 48 updated at time 1380
entity 48 terminated at time 1382
entity 49 created at time 1410
Entry component 1 generates new entity at time 1410
entity 49 updated at time 1410
entity 49 terminated at time 1412

We didn’t have to add the newly created entities to the setOfEntities array, since in theory they should all be actively processed using the relevant discrete-event methods. However, there are times when it’s necessary to access groups of elements that share some characteristic. They could be in a given state, in a given location, awaiting a given condition, or be of a certain type. Having an external handle for groups of items allows common types of processing, including set operations. The SLX language, which inspired this project, implemented set containers and operations for these purposes.

We could also probably have set the entities to move forward in time right from when they were created, rather than having them be processed once at zero seconds after creation and again at two seconds after. That would have made this process a little cleaner.

You may notice that this code looks very much like that for the entity objects themselves, and there’s a reason for that. Any element that does anything (and in this example we’re putting intelligence into both the entities processed by the system and the components used to do the processing) will require the same discrete-event mechanics. This means that processing will stop and wait to continue after a defined period of time has elapsed or a defined condition has been met. The question is about the specific behaviors to implement.

In this case we’re creating entities that exist for a moment and then extinguish themselves. This isn’t very interesting, but the goal here is simply to create entities. We’ve created a really mindless way of doing this, but let’s think of some that are more interesting. Here are some ideas.

A schedule could be created which governs the creation of entities. It would have to incorporate information about time periods, entity characteristics, and so on. All of the entities could be created at the beginning of the simulation and be activated on their individual arrival times. The Entry component could create a separate event loop (using a separate puck), that generates the entities for the next scheduled period. Assuming that a schedule defines arrivals by half-hour block, one loop could run every half hour while another loop generates the arriving entities during the course of that half-hour. It may also be possible to just generate all the arriving entities on the half-hour, but have them wait to activate at different times over that interval. Care would have to be taken to ensure that display and record-keeping for the new arrivals only begins when it logically should.

As I’ve discussed previously, an element can have a number of things going on at any given time. It could simultaneously be waiting for time to elapse, a condition to be met, or be affected by some outside process based on its state, location, or group membership. As long as the code keeps everything straight the sky’s the limit.

To that end I’m thinking that the activation mechanism I’ve been using could stand a little clarification and standardization, if possible. The relevant bits of code tend to get lost when buried in the series of cascading if statements, so it might be a good idea to modularize this somehow. If that structure could be standardized and externalized it could make the objects’ code much clearer. It may also allow us to hide the flag for going into an unidentified state. What we’d want is to be able to declare the various activities as methods within each object, each of which is triggered by a certain state identifier, while ensuring that each object defines a new state (unless the object is to be extinguished). There would have to be a way to associate an element’s states with its method calls in an external function or object (method). I think that will be tomorrow’s project, and when that’s done we can return to implementing more interesting ways to have an Entry component generate entities.

Posted in Simulation | Tagged , | Leave a comment

A Simple Discrete-Event Simulation: Part 11

Posted on September 19, 2016 by R.P. Churchill

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.

Posted in Simulation | Tagged , | Leave a comment

Art, Waste, and a Rumination on Economics

Posted on September 15, 2016 by R.P. Churchill

I’m going to table the work on the discrete-event simulation today in order to discuss a public art critique I attended last night. The gallery featured a few pieces of the works of two artists, Jessica Burnam and Eric Celarier, the latter of whom I’ve known for some years. They both work with found materials and ruminate on what our technological society is leaving behind as waste.

One thing that jumped immediately to mind is a classic Poul Anderson story called “Epilogue,” from 1962, which describes how a new form of “life” re-evolved on Earth from the automated machines that survived a thermonuclear war. The machines were sophisticated on a technical level, collecting minerals from ocean water, depositing them at docks when full and returning to sea, able to effect self repair operations, and able to make additional copies of themselves. In the biological realm this would be the equivalent of a single-celled organism of some kind. The characters in the story surmise that the instructions for creating new copies were modified by the hard radiation from the war, but since the story takes place three billion years into the future it’s easy enough to imagine all sorts of reasons for such genetic drift. Anyway, the story involves the discovery of this new ecosystem by humans who have been transported forward in time, and their struggles to deal with it.

The story was germane in my mind because it suggests a mechanism by which the technology incorporated into the artists’ works can be transformed into the biological forms they have imagined.

Mr. Celarier’s early works, from his “Wasteland” series, involved making rectangular “quilts” out of electronic circuit boards, which are then bound together in a border of additional leather rectangles using leather strips. One can imagine such pieces being repurposed by post-technological survivors using whatever materials they can find. This idea reminds me of the cover from the Kansas album Monolith.

I mentioned the Poul Anderson story to the artists, who were both intrigued by its ideas, but there’s something more important I didn’t get to, mostly because it requires a longer conversation. Mr. Celarier and I plan to do this in the near future.

As a process engineer and systems analyst I’m fascinated by economics, whether in making a piece of software or a manufacturing or business process work more efficiently or in the broader sense of economics as the study of choice under conditions of scarcity. Both artists stated that they are concerned that we are leaving incredible amounts of waste behind in a way that cannot help but cause major problems for the environment and for humanity. Mr. Celarier described working with a group for a full day cleaning no more than a quarter mile of a local river bank. He observed that the volume and types of items found were shocking. He also stated that he isn’t a scientist, politician, futurist, urban planner, or whatever, but as an artist he feels it’s important to at least comment on the situation.

The attendees were all very intelligent, creative, and thoughtful (this was evident from the Q&A exchanges) but seemed to be of a certain type. More accurately, they seemed to not be of one particular type, namely economists. Economists, good ones anyway, always consider the marginal costs of doing various things. Humans and societies make choices by evaluating the relative costs and benefits of taking one action over another. These costs and benefits don’t have to be measured in terms of money; other physical goods, leisure, reputation, emotional satisfaction, and other considerations can all be elements of exchange.

I often find it helpful to begin any analysis by asking why things are the way they are. Why do most cars have four wheels? Why are manhole covers round? Why are bases ninety feet apart on a baseball diamond? Finding the answers to such questions can turn up a lot of knowledge that might not be evident at first glance, and every component of a problem has to be examined from every possible angle. Just because you don’t consider a component or an effect doesn’t mean it’s not there.

If an artist asks, “why is there so much junk thrown away so that it ends up on a riverbank somewhere?” or, “Why are we discarding appliances when two thirds of them still work?” or, “Doesn’t the fact that the landfill in my hometown reached its full capacity and had to be closed mean we’re running out of space to put our trash?” those are all good questions. But, like Henny Youngman replied when he was asked, “How’s your wife?” “Compared to what?”

Compared to what, indeed.

I’m not going to attempt a comprehensive answer, but we can look at a lot of factors.

What does it cost the owner to throw something away? This can be evaluated in terms of the cost of the act, the foregone utility of the discarded item (if any), the utility not realized by replacing it with an improved item, transportation, storage space and costs, fines, and pollution. What if one part of an old machine breaks, it can’t be replaced, and the machine is now unusable? Isn’t the bulk of the still-working machine going to get tossed? What if an owner throws something away that he or she knows has ten or twenty dollars worth of gold in it, but that gold is not recoverable by any reasonable, safe, economical, environmentally friendly, available technology? Does anyone want the item or the materials in it? Is it worth the time and expense to find such a person? How much economic damage is the discarded item actually causing? What if the item is in a landfill? What if it’s on a river bank? Who bears the cost? How much energy does the recycling process consume? How much pollution does it generate?

What materials get recycled now without anyone having to be forced to do so? There is a huge market for scrap steel because the recovery, transportation, and reprocessing of scrap steel is less than making it new (while storing the unused scrap). Precious metals get recycled at a pretty high rate because it makes economic sense to do so. There is a thriving trade in moving old and wrecked cars from the United States down to Mexico, where it makes sense to recover the parts or make repairs.

What materials don’t get recycled unless people are forced to do so? Most operations to recycle household paper, aluminum, and glass are money-losing propositions. They have to be subsidized by government taxation and enforced by fines and worse.

Are we really running out of landfill space? Not only are we not running out of space (they really don’t take up that much surface area), quite a few are run on a private, for-profit basis, even as they improve their isolation, ability to recover valuable hydrocarbon gases, controlled decomposition of organic materials, and recoverability for use as parkland.

So why do we discard so many electronic circuit boards? We do so because it’s currently cheaper to stop using outmoded boards and put them in landfills than it is to keep using them or try to recycle them. If and when it becomes economical to send robots in to sort and reprocess landfill materials then you can bet there will be a stampede to do so. When the cost to recover junk from river banks becomes less than the damage it is actually causing then that will happen, too. Until then, we are clearly choosing to pursue other ends.

In short, if we’re discarding a circuit board, it’s because we think something else is more important.

Posted in Economy and Society | Tagged , , , | Leave a comment

A Simple Discrete-Event Simulation: Part 10

Posted on September 14, 2016 by R.P. Churchill

Today I defined some new entities that better illustrate the operation of the wait mechanism and the current events queue, which I have modified so it scans the list of current items repeatedly until no conditions are met. Here’s the modified version.

I then created an entity that simply advances to a time, sets a flag, and destroys itself. Note that the flag has to be implemented as an object so it can be passed by reference. Here’s the flag object (see note below) and two instantiations.

Here’s the entity that sets the flag.

I also created an entity that checks the flag and destroys itself when the condition becomes true.

Finally, I created two instantiations of each entity. The idea is for the entity4 types to wait for some period (times 45.0 and 63.7, respectively) and then set the flags which represent the entity5 unblock conditions, and for the entity5 types to check to see if their unblock conditions have been met (via the ceq.processCeq() call) each time a new future event is processed.

The output indicates that things appear to be working as intended.

104 minutes

entity 1 created at time 0
entity 2 created at time 0
entity 3 created at time 0
entity 4 created at time 0
entity 5 created at time 0
entity 6 created at time 0
entity 7 created at time 0
entity 8 created at time 0
entity 4 reports at time 0 executions: 0
entity 7 still blocked at time 0 flag value: false flag1: false flag2: false
entity 8 still blocked at time 0 flag value: false flag1: false flag2: false
entity 5 sets flag at time 0 flag value: false flag1: false flag2: false
entity 7 still blocked at time 0 flag value: false flag1: false flag2: false
entity 8 still blocked at time 0 flag value: false flag1: false flag2: false
entity 6 sets flag at time 0 flag value: false flag1: false flag2: false
entity 7 still blocked at time 0 flag value: false flag1: false flag2: false
entity 8 still blocked at time 0 flag value: false flag1: false flag2: false
entity 1 updated at time 11
entity 7 still blocked at time 11 flag value: false flag1: false flag2: false
entity 8 still blocked at time 11 flag value: false flag1: false flag2: false
entity 3 updated at time 12 position: -40
entity 7 still blocked at time 12 flag value: false flag1: false flag2: false
entity 8 still blocked at time 12 flag value: false flag1: false flag2: false
entity 2 updated at time 13
entity 7 still blocked at time 13 flag value: false flag1: false flag2: false
entity 8 still blocked at time 13 flag value: false flag1: false flag2: false
entity 3 updated at time 19.009999999999998 position: -35
entity 7 still blocked at time 19.009999999999998 flag value: false flag1: false flag2: false
entity 8 still blocked at time 19.009999999999998 flag value: false flag1: false flag2: false
entity 1 updated at time 21
entity 7 still blocked at time 21 flag value: false flag1: false flag2: false
entity 8 still blocked at time 21 flag value: false flag1: false flag2: false
entity 2 updated at time 26
entity 7 still blocked at time 26 flag value: false flag1: false flag2: false
entity 8 still blocked at time 26 flag value: false flag1: false flag2: false
entity 3 updated at time 26.019999999999996 position: -30
entity 7 still blocked at time 26.019999999999996 flag value: false flag1: false flag2: false
entity 8 still blocked at time 26.019999999999996 flag value: false flag1: false flag2: false
entity 1 updated at time 31
entity 7 still blocked at time 31 flag value: false flag1: false flag2: false
entity 8 still blocked at time 31 flag value: false flag1: false flag2: false
entity 3 updated at time 33.029999999999994 position: -25
entity 7 still blocked at time 33.029999999999994 flag value: false flag1: false flag2: false
entity 8 still blocked at time 33.029999999999994 flag value: false flag1: false flag2: false
entity 2 updated at time 39
entity 7 still blocked at time 39 flag value: false flag1: false flag2: false
entity 8 still blocked at time 39 flag value: false flag1: false flag2: false
entity 3 updated at time 40.03999999999999 position: -20
entity 7 still blocked at time 40.03999999999999 flag value: false flag1: false flag2: false
entity 8 still blocked at time 40.03999999999999 flag value: false flag1: false flag2: false
entity 1 updated at time 41
entity 7 still blocked at time 41 flag value: false flag1: false flag2: false
entity 8 still blocked at time 41 flag value: false flag1: false flag2: false
entity 5 terminated at time 45 flag value: true flag1: true flag2: false
entity 7 unblocks at time 45 flag value: true
entity 8 still blocked at time 45 flag value: false flag1: true flag2: false
entity 3 updated at time 47.04999999999999 position: -15
entity 8 still blocked at time 47.04999999999999 flag value: false flag1: true flag2: false
entity 1 updated at time 51
entity 8 still blocked at time 51 flag value: false flag1: true flag2: false
entity 2 updated at time 52
entity 8 still blocked at time 52 flag value: false flag1: true flag2: false
entity 3 updated at time 54.05999999999999 position: -10
entity 8 still blocked at time 54.05999999999999 flag value: false flag1: true flag2: false
entity 1 updated at time 61
entity 8 still blocked at time 61 flag value: false flag1: true flag2: false
entity 3 updated at time 61.069999999999986 position: -5
entity 8 still blocked at time 61.069999999999986 flag value: false flag1: true flag2: false
entity 6 terminated at time 63.7 flag value: true flag1: true flag2: true
entity 8 unblocks at time 63.7 flag value: true
entity 2 updated at time 65
entity 3 waiting at time 68.07999999999998 wait count: 4
entity 1 updated at time 71
entity 3 waiting at time 75.08999999999999 wait count: 3
entity 2 updated at time 78
entity 1 updated at time 81
entity 3 waiting at time 82.1 wait count: 2
entity 3 waiting at time 89.11 wait count: 1
entity 2 updated at time 91
entity 1 updated at time 91
entity 3 waiting at time 96.12 wait count: 0
entity 1 terminated at time 101
entity 3 terminated at time 103.13000000000001
entity 2 terminated at time 104

As an aside I was reading up on some things related to this mod and discovered that I’ve apparently been using the closure pattern and not the prototypal pattern for creating objects. As I understand it on first reading, the closure pattern carries the overhead of the entire object with each instantiation, while the prototypal pattern causes the method mechanisms to be instantiated only once while the created objects contain only the relevant data and a reference to the prototype mechanisms. This may be important because discrete event simulations can involve huge numbers of entities and we wouldn’t want to carry any more overhead than absolutely necessary. I’ll definitely have to look into this more going forward.

Posted in Simulation | Tagged , | Leave a comment

A Simple Discrete-Event Simulation: Part 9

Posted on September 13, 2016 by R.P. Churchill

It’s one thing when you place an entity back in the future events queue at a specific absolute or relative time, but it’s quite another if you want an entity to become active when a certain condition–or set of conditions–becomes true. Some way has to be found to represent all of the conditions that are causing wait states. Since any operation or any object may affect the value of one or more variables, and since there is no way to tell ahead of time which variables may be affected, the conditions have to be checked every time something happens.

The trick is to figure out what that something should be.

Here’s the first part of the solution. We’re going to start by creating a mechanism to store and process the condition checks in an organized way. Every item in this mechanism will be checked every time a new event is pulled from the future events queue. Every event pulled from the future event updates the current time, so we’re going to refer to the mechanism as the current events queue. Its structure, elements, and behavior are going to look very much like the future events queue in that it will be composed of a list of current event items, each of which is owned by an entity being modeled in the simulation. Here are the basic declarations.

You’ll notice that each current event item calls its parent’s checkBlockingCondition item, which implies that every modeled entity that wants to test for (one or more) wait conditions needs to implement a version of this function.

If you can imagine writing a statement of the form

you can think of the / statement as being replaced by whatever goes on in the checkBlockingCondition method. Since we don’t control the interpreter we have to create some external mechanisms as we are here.

Since we’re going to process the entire list of current event items every time we pull the next future event item we modify the main activity loop as follows.

Before continuing I’ll observe that this first implementation raises some issues. The way this is set up we make one pass through the current events queue, processing every event whose conditions are met. If we have a large number of conditions to check, which means a large number of variables may be changed, what is to say that a condition might become true and then untrue again before the relevant current event item is processed again? If it happens within the course of processing a single item it might not be a big deal (and is frankly unlikely to happen anyway), but if it happens across the processing of multiple items it might be a big deal, indeed. Perhaps ceq.processCeq() needs to be exited and called anew each time an item’s condition is found to be true. There are a lot of ways to do this but I’m going to park this thought for the moment. First we want to get something working.

To that end, here is an entity declaration that implements a conditional wait state. It’s been structured to allow for many different wait conditions, though only one can ever be active at one time.

What this entity actually does is trivial, and there are many simpler ways to do it. This happens to be the one I chose for testing. Here is the setup of the globalExecutionCount mechanism.

What happens is that the other entities call bumpGlobalExecutionCount() every time they are pulled off the future events queue, incrementing the global counter. When the current events queue is processed, before pulling the next event, the waiting entity tests to see if the global counter is evenly divisible by five, and writes out a message when it is.

The program now generates the following output:

104 minutes

entity 1 created at time 0
entity 2 created at time 0
entity 3 created at time 0
entity 4 created at time 0
entity 4 reports at time 0 executions: 0
entity 1 updated at time 11
entity 3 updated at time 12 position: -40
entity 2 updated at time 13
entity 3 updated at time 19.009999999999998 position: -35
entity 1 updated at time 21
entity 2 updated at time 26
entity 3 updated at time 26.019999999999996 position: -30
entity 1 updated at time 31
entity 3 updated at time 33.029999999999994 position: -25
entity 2 updated at time 39
entity 3 updated at time 40.03999999999999 position: -20
entity 1 updated at time 41
entity 3 updated at time 47.04999999999999 position: -15
entity 1 updated at time 51
entity 2 updated at time 52
entity 3 updated at time 54.05999999999999 position: -10
entity 1 updated at time 61
entity 3 updated at time 61.069999999999986 position: -5
entity 2 updated at time 65
entity 3 waiting at time 68.07999999999998 wait count: 4
entity 1 updated at time 71
entity 3 waiting at time 75.08999999999999 wait count: 3
entity 2 updated at time 78
entity 1 updated at time 81
entity 3 waiting at time 82.1 wait count: 2
entity 3 waiting at time 89.11 wait count: 1
entity 2 updated at time 91
entity 1 updated at time 91
entity 3 waiting at time 96.12 wait count: 0
entity 1 terminated at time 101
entity 3 terminated at time 103.13000000000001
entity 2 terminated at time 104

Here we see that the current events list is scanned as expected–once–when the global count is zero–whereupon the item takes itself out of the current events queue. Once that happens there’s nothing left to repeat the test.

This is actually what I intended. wait…until conditions are supposed to only happen once. When the condition becomes true, the modeled entity goes back to or on to some other behavior, which may be governed by bumping forward in time on the future events queue or waiting for a new condition on the current events queue. Before long I’ll come up with a better demonstration case, but the basic mechanism appears to work as far as it’s been tested.

I’ll also note that it’s possible to have multiple mechanisms in place simultaneously. Each modeled entity can create multiple current end future events queue items at the same time, and can be doing one thing while waiting for another. The SLX simulation language allows for different subentities it calls pucks (like a hockey puck). Each modeled entity can spawn multiple subentities, each of which can implement arbitrarily complex behavior. We’ll get into some examples of this as we go.

A similar thing happens in business process systems. An entity may enter a process and proceed through many stages, sometimes kicking off multiple subprocesses. Imagine that an order for a widget comes in. Different “pucks” may have to be sent to create a new customer or look up and existing one, pull items from inventory, do something in manufacturing or shipping, send a bill, wait for payment, pursue payment if it is not received by the expected date, and handle questions, change orders, clarifications, and cancellations. The BPMN standard discusses the diagramming and documentation of these ideas, but it is up to different business tools to implement them in different ways.

Posted in Simulation | Tagged , | Leave a comment

A Simple Discrete-Event Simulation: Part 8

Posted on September 12, 2016 by R.P. Churchill

Today I automated the generation of entity IDs.

First we create a basic counter.

Then we change the entity declarations to remove the explicit assignment of IDs as we have been doing.

That was pretty mindless, so let’s also add a new type of entity, following the form of the original one. Here’s the original. It just advances its own clock and reinserts itself back into the future events queue.

Here’s the new one. It also updates its clock and inserts itself back into the future events queue, but in this case it implements a more interesting (though still mindlessly simple) behavior. It increments a location property which itself gets incremented, until it reaches a final offset, whereupon it counts down through a five-step wait process. Then it stops reinserting itself back into the future events queue.

In reality we would always create entities that carry out more interesting behaviors.

Having to rely on passive garbage collection to officially deallocate or “destroy” objects in JavaScript is kind of annoying but it is what it is. Doing demos in this language makes it easy to post working demos.

Here’s how the entities are initialized.

Here is the output generated:

104 minutes

entity 1 created at time 0
entity 2 created at time 0
entity 3 created at time 0
entity 1 updated at time 11
entity 3 updated at time 12 position: -40
entity 2 updated at time 13
entity 3 updated at time 19.009999999999998 position: -35
entity 1 updated at time 21
entity 2 updated at time 26
entity 3 updated at time 26.019999999999996 position: -30
entity 1 updated at time 31
entity 3 updated at time 33.029999999999994 position: -25
entity 2 updated at time 39
entity 3 updated at time 40.03999999999999 position: -20
entity 1 updated at time 41
entity 3 updated at time 47.04999999999999 position: -15
entity 1 updated at time 51
entity 2 updated at time 52
entity 3 updated at time 54.05999999999999 position: -10
entity 1 updated at time 61
entity 3 updated at time 61.069999999999986 position: -5
entity 2 updated at time 65
entity 3 waiting at time 68.07999999999998 wait count: 4
entity 1 updated at time 71
entity 3 waiting at time 75.08999999999999 wait count: 3
entity 2 updated at time 78
entity 1 updated at time 81
entity 3 waiting at time 82.1 wait count: 2
entity 3 waiting at time 89.11 wait count: 1
entity 2 updated at time 91
entity 1 updated at time 91
entity 3 waiting at time 96.12 wait count: 0
entity 1 terminated at time 101
entity 3 terminated at time 103.13000000000001
entity 2 terminated at time 104

Posted in Simulation | Tagged , | Leave a comment

A Simple Discrete-Event Simulation: Part 7

Posted on September 8, 2016 by R.P. Churchill

Today we’ll do some more streamlining.

We’ll start by adding a new function to the futureEventsQueue object.

Then, instead of having to specify the “absolute” (vs. “advance”) flag in the initialization of a new entity object, we know we’ll be inserting it into the future events queue at a specific time (which might, in fact, be the current time, but that is a different discussion). Look for the streamlined and specific newItem call in place of the more general insertItem call.

Again the output is unchanged so we’re still pretty sure we haven’t broken anything.

Posted in Simulation | Tagged , | Leave a comment

A Simple Discrete-Event Simulation: Part 6

Posted on September 7, 2016 by R.P. Churchill

Now that I’m sure the basics are working the way I’d like I want to see if I can streamline things some more.

The first thing to do is recognize that the next item being pulled off the future events queue can always be referred to the same way. If we make the item a global variable then we can always have code refer to it by a known name without having to pass the reference around all over the place. This cleans things up quite a bit.

We’ll start by creating a variable called feqCurrent, which is intended to hold a futureEventItem object.

Next, we’ll copy the insertExistingItem method in the futureEventsQueue object so it eliminates the need to pass in a reference to an feqItem, because it refers to the global variable instead.

We’ll follow that up by streamlining the advance function in the same way.

Then we’ll do the same to the activate function in the entity object.

Finally, we’ll do the same thing to the main event processing loop.

The output remains the same as before, so we assume we haven’t broken anything.

Posted in Simulation | Tagged , | Leave a comment