[Lecture Notes by Prof Yuen and possibly others 2000-2001]

SIMULATION
----------

Simulation is different from building virtual machines. Let us use the
car movement example to illustrate. The state variables relevant for
studying the movement of a car are for our simple example

  position
  velocity
  accelerator setting
  steering wheel setting

If we know these values at time t, we can compute position and velocity
at time t+dt; the "driver" can then choose new settings for accelerator/
steering wheel, which will then determine position/velocity at t+2dt, etc
and the computer can follow the movement of the car continuously for the
period of our study

Now what do you do with these values? If our objective is to build a
virtual car machine, then we would display the car's movement on a screen
(with background scene like race track, street with traffic, beautiful
scenery, etc), and provide an input interface through which the user can
pretend to be controlling the accelerator/steering wheel of a car. But our 
objective in simulation is quite different; it is to estimate certain
important variables' values under particular conditions. For example, 
we might wish to answer the question "if we steer left and right for
the same amount of total time, but left in a large number of short 
periods, and right in a small number of long periods, does the car end
up veering left, veering right or straight?"

For such a study, we dont need to build a virtual machine; in fact, a
virtual machine may not be reliable for answering the question, since
the "driver" may not do the right amount of steering as the question
requires; we simply follow the virtual car numerically, and produce the
answer purely by computation. This allows us to try out all kinds of
different scenarios and see what happens. Further, the results of many
similar but somewhat different scenarios could be summarized to produce
some kind of "collective wisdom". For example, right handed people might
have a slight bias of turning the wheel leftwards, while left handed
people do the opposite. Under various conditions, do right handers tend
to veer the car leftwards and left handers veer rightwards? You could
run the virtual car many times with various accelerator and steering
settings over the period, and see what differences arise from the left
and right biases.

The car example is a very simple one, and in fact you can use a mathematical
formula to compute the position/velocity values given the accelerator/
steering setting functions as input, so that it wont really be necessary
to run simulation programs fo the purpose. Actual application of simulation
programs tend to be more complex situations involving objects and events
that do not have such simple, mathematically expressable behaviour. The
name "discrete simulation" or "discrete event simulation" is used for such
application, in contrast to the more mathematical, often using differential
equations relating variables and rates of change, simulation.

For example, a supermarket would know that on average x customers arrive
between 2 and 3 pm on saturdays, and each buys goods requiring y minutes
average to check through; so is it enough to have xy/60 cashiers? Of course 
you know you need more than that, since (a) on particular saturdays, the 
number of customers might be more than x, and each might buy more than
y minutes' checkout goods (b) there might be moments when nobody is
checking out, while overcrowding occurs in the other moments; but exactly
how many cashiers should be rostered? xy/60 + 1? +2? when should be extras
start the shift to produce most benefit?

Simulation can be used to study such situations. The program uses a random
number generator to control the creation of customer objects that reflect
the known customer behaviour: if x customers arrive in the 2-3pm period,
then the average gap between successive customers is 60/x minutes, but
the gap varies randomly - it might be 0 if two customers arrive together
or twice the average; for each customer object, the checkout time requirement
is a random number that fluctuates around the average y, while the time
taken choosing the goods is another random number z that is related to y
in some average way (more goods takes more time to pick up, but some people
take long time to choose little shopping, while others do it very quickly).
In any case, there are certain variables for each customer object that
affect the behaviour of the objects themselves as well as other objects
like the busyness of cashiers and length of checkout queues.

A customer object goes through state changes. Upon arrival at time T, it 
is in the "choosing goods" phase; at time T+z (z, as I said just now, is
a random number related to y) it is in the "queuing up" phase, and the 
duration of the phase depends on the number of customer objects now in
the queue and their checkout time requirements (sum of the y values of
all the objects, s); at time T+z+s the particular customer goes into
"checkout phase", and at time T+z+s+y it goes into "leave" state. How
quickly or slowly a customer object moves through these phases depends
on its own variables and the variables of other customer objects, as well
as on the number of checkout counters open, plus some decision about which
queue to join (shortest queue? but that might sometimes take longer as
it depends on the amount of goods customers in the queues are buying;
are their "express counters" for customers with few things? are some
cashiers more efficient than others and so more popular with customers?
you can set all sorts of conditions that affect the simulation)

In any case, you can churn the computer program through a number of
similar but somewhat different scenarios, with each simulation run
producing a different number of customers, arrival patterns, buy patterns,
queuing experiences, etc, and then produce estimates of average condition,
worse cases, best cases, etc, and look at the results to see how best
to manage your supermarket. You could see how much floor space to have
from the total number of customers in the shop, how much space to have
near the checkout counters from the length of the queues, the size of
the trolleys from the amounts of goods customers buy, typical mix of
shopping, size/weight of typical goods mix, etc. 

To write such simulation programs, you need computer languages that make
it easy for you to describe the objects with particular relevant variables,
like simulating a university class would require quite different
variables to be captured (e.g., to determine how many entrances an LT
should have, you need to know the sizes of the students' bags and how
quickly they have to leave in order to go to the next class...), and events
that change the state of an object. For example, when a customer joins a
queue, the state of the custome changes, and so does the state of the queue;
if a language allows you to write Customer A Join Queue B, automatically
resets their states and scheduling a new event Customer A Reaches Head of
Queue B at time T+s, then your work in writing the simulation program
would be much simplified.