Discrete Event Systems
Merging Continuous and Discrete Time modelling
There are many processes such as the flow of control through complex computer programmes (particularly if multiple CPUs are involved), flow of products and materials, orders and invoices through factories and businesses, movement of people through transport systems and so on which present problems of understanding and design in commmercial and industrial environments.
Typically these processes can be seen as a collection of discrete activities, each of which takes time, may require the use of shared resources, and which, on conclusion, trigger or permit another activity to start. The starting and stopping of the activities are seen as events. Their timing is typically irregular
The ideas may be familiar in Gannt Charts, PERT digrams and critical path investigations. Here we are concerned with the dynamic behaviour of such systems while they operate.
If you don't want to read all this but just get to my simulation tool McSimAPN click this link.
Methods of Discrete Event Simulation.
Discrete events are modelled as taking place at instants of time and when
they take place the model system instantaneously changes state.
a server (assistant) becomes busy with a customer.
a computer programme starts work on a procedure,
someone joins a group (set membership changes)
That state persists until a subsequent time when another event takes place to change it.
In starting work the end time is defined,
Some event modifies the time at which another event will take place,
One way to represent such activities in a computable model is to keep a list of event times (called an event chain ) with their corresponding actions, keeping the list updated (sort by time order, next at top of list) whenever something happens to define a future event.
Such modelling systems can be very powerful (Simscript, Simula, ModSim and others are examples). They are special programming languages with a set theoretic basis and can handle entities that have complicated attibutes and set memberships. They require code to be written to define the events and and state changes. In their operation computed time moves by irregular leaps and bounds to the time of the next event.
Petri Net Approach
An alternative is a Petri-Net approach, in which Tokens move from one place (holder, container) to another when key events called transitions move them which when the tokens they need are ready (and perhaps other conditions are met.
The listing of the tokens in the places is called a marking.
The idea was formalized by Carl Adam Petri in the early 1960s..
You can find out more at the PetriNet
or from texts such as
"Peterson, James L., Petri Net Theory and the modeling of systems, Prentice hall, 1982, ISBN 0-13-661983-5" .
Petri Net in McSimAPN
My choice of Petri Nets was somewhat accidental.
I was trying to make a minimalist programme to compute the behaviour of an automated factory having found that the original model used by the builders was seriously deficient.
I concluded that to represent the multiple processes where product was mated with tools and worked on, passed along conveyors and put through inspections and batching, I needed modules that had at least two input and two output connections to link them to places where the products and tools could reside between the process operations. The programme worked OK.
A couple of years later a friend pointed out that what I had was really a Petri Net,
and pointed out its use in the design and proving of computer programmes.
The McSim Petri Nets are timed, monochromatic PNs.
It models the processes by connecting blocks. The simplest essential block type is the place or container (block type C) which in my version always has some maximum nominal capacity for tokens.
"Monochromatic" because the tokens are indistinguishable (and they can't simultaneously belong to more than one set or place). However, in practice their location (place, in a container [C-block] or in an A- B- or D-block) is implicitly definitive of their type and behaviour.
Conservation Law: If you make sure that all tokens are either in circulation in containers or at least never destroyed, then they can be counted at any time to verify the model at least has that right.
"Timed" because the key component, the Activity block type, has an input transition which takes tokens from places (containers) into its own internal places with a defined delay/residence time. The tokens leave by a second transition when the delay time is reached and if the next place (or places) have enough room available, otherwise the second transition can be blocked.
A conveyor belt can be modelled by a set of the activity blocks with shared (end) containers but more flexibility comes from making it a special unit.
I have added a diverter (originally envisioned as an inspector or test equipment), so the block types are:
A: Activity/Action: a process that takes time (but zero time is allowed)
B: Belt (conveyor): Moves tokens along at a chosen rate
C: Container (place): Passive, Stores tokens or provides a constant value
D: Diverter: randomly delivers tokens to either of two places (containers)
Individual A, B and D blocks look after their own timing, waiting till the independent time variable reaches their own next event time
so no event chain is needed and the blocks can be used in conjunction with analogue computer blocks.
The overall effect is that a network of blocks stands for a network of physical (or computational) processes
and its behaviour in time is displayed in the movement and accumulation of tokens.
They can be timed randomly or regularly
and A- D-blocks can act instantaneously (zero time delay) to provide routing control.
Having previously made continuous system simuation languages (CSSL) I realized that I could merge one with the Discrete Event Simulation (DES) ideas by using Petri Nets blocks and letting them run till they each individually decided its time was ripe. No need for event chains.
I merged Petri Net modelling with the block structured continuous systems (analogue) modelling into McSimAPN so Activity Blocks (and conveyor Belts) and Diverters can link to integrators (which are naturally accumulators/containers) in both input and output directions as well as to Containers (places).
The idea of a token has been expanded to include any quantity by using real numbers and so the continuous systems components can interact with them, providing control loops, logical switching, measurements, aggregation, graphing.
The resulting modelling tool called McSimAPN (McCannSimulationAnalogPetriNet) is available for anyone to down load . It's less than 1MB, including help and demo files; no need to install; it runs as an executable file under Microsoft Windows up to 8.1 (so far, 2014).
It incorporates the following features in a single package:
- interactive operation, see results as the simulation runs, make
changes, see graphed results, flip switches on the fly.
- all graphic interface, assemble, run modify.
- simple block structure with set of components designed for flexibility,
hundreds of state variables allowed.
- stop and restart, save and come back to same point.
- models stored as text files, always editable by humans, but can be
parsed into spreadsheets for parameterized modelling.
- has option for VBA extension to insert user defined
programmable components for testing control systems etc.
- Needs no installation, just unZIP it and run.
- After unZip, start with the file "readmefirst.txt".
Design has concentrated on being able to compress a lot on to the screen and particularly to be interactive so that the network (equations, model) can be changed while in the middle of a run without any need to recompile or reset or restart. In that sense, it emulates a hardware electronic analogue computer, on which it is modelled. (While it was never recommended practice, we could hot wire links in analogue computers at anytime.) As a result, it has the block structured form of an analog machine or the early digital analog simulators, rather than the statement structured form of CSMP, ACSL and sucessors.
Although it is small and simple, McSimAPN is an effective simulation tool. It is not so fast at numerical integration as hard coded or purpose designed programmes but shows its advantages in ease of use since it runs in an essentially interpretive mode. The schema for the graphics (mimic diagrams) is functional rather than pretty. However, it is fun to play with and easy to learn and gets results quickly.
|Links in website:
About Dr McCann
Contact in UK
Business & Commerce
Toxic gas allocation
Production & Process
Crimp and Press
Glass to metal seals
Helium Leak Testing
Vacuum web coating