Simulation and Modelling 2076 (new)

The line where the entities or customer wait is generally known as queue. The combination of all entities in system being served and being waiting for service will be called as queueing system.

Queue discipline refers to the rule that a server uses to choose the next customer from the queue when the server completes the service of the current customer. Common queue disciplines include first-in-first-out (FIFO); last-in-first-out (LIFO); service in random order (SIRO); shortest processing time first (SPT); and service according to priority (PR).

• First in first out :This principle states that customers are served one at a time and that the customer that has been waiting the longest is served first.
• Last in first out : This principle also serves customers one at a time, however the customer with the shortest waiting time will be served first. 
• Service in random order: A customer is picked up randomly from the waiting queue for service.
• Shortest job first: The next job to be served is the one with the smallest size (shortest service time).
• Priority: Customers with high priority are served first. 

The performance of a queuing system can be evaluated in terms of a number of response parameters, however the following four are generally employed.

• Average number of customer in the queue or in the system
• Average waiting time of the customer in the queue or in the system
• System utilization (Server utilization)
• The cost of waiting time and idle time

1. If  Ta and Ts be the inter arrival time and the mean service time then

• Arrival rate λ=1/Ta 
• Service rate μ=1/Ts
• Average number of customer in the system = λ/(μ - λ)
• Average number of customer in the queue = λ2/μ(μ - λ)
• Average waiting time in the system = 1/(μ - λ)
• Average waiting time in the queue = λ/μ(μ - λ)

2. The ratio of the mean service time to the mean inter arrival time is called traffic intensity. i.e.  u=Ts/Ta

3. Server utilization: It consists of only the arrival that gets served. It is denoted by and defined as

        ρ= λTs= λ/ μ (server utilization for single server).

        ρ= λTs= λ/ nμ (server utilization for n server). 

4. Probability of finding service counter free is (1 – ρ) i.e there are zero customers in the service facility.

The Chi Square test is used to test whether the distribution of nominal variables is same or not as well as for other distribution matches and on the other hand the Kolmogorov Smirnov (K-S) test is only used to test to the goodness of fit for a continuous data.

Kolmogorov Smirnov (K-S) test compares the continuous cdf, F(X), of the uniform distribution to the empirical cdf, SN(x), of the sample of N observations. By definition,

    F(x) = x, 0 <= x <= 1

If the sample from the random-number generator is R₁, R₂,......,R_N, then the empirical cdf, S_N(X), is defined by

    S_N(X) = (Number of R₁, R₂,......,R_N which are <= x)/N

As N becomes larger, SN(X) should become a better approximation to F(X), provided that the null hypothesis is true. The Kolmogorov-Smirnov test is based on the largest absolute deviation or difference between F(x) and S_N(X) over the range of the random variable. I.e. it is based on the statistic

    D = max | F(x) - S_N(x)|

The chi-square test uses the sample statistic

Where O_i is the observed number in the i^th class, E_i is the expected number in the i^th class, and n is the number of classes. For the uniform distribution, E_i ist the expected number in each class is given by: E_i = N/n, N is the total number of observation.

Now,

Given sequence of number,

    0.54, 0.73, 0.98, 0.11,0.68 and 0.45

Arranging the given number in ascending order:

    0.11, 0.45, 0.54, 0.68, 0.73, 0.98

Here, N = 6

Calculation table for Kolmogorov-Smirnov test :

i
1	0.11	0.17	0.06	0.11
2	0.45	0.33	-	0.28
3	0.54	0.5	-	0.21
4	0.68	0.67	0.07	0.18
5	0.73	0.83	0.1	0.06
6	0.98	1	0.02	0.15

Now, calculating

 = 0.1

 = 0.28

 = 0.28

Given, Critical value  = 0.565

Since the computed value, D = 0.28, is less than the tabulated critical value,  = 0.565, the hypothesis of no difference between the distribution of the generated numbers and the uniform distribution is not rejected.

Static mathematical model is the mathematical model that represents the logical view of the system in equilibrium state. Such models are time-invariant. It is generally represented by the basic algebraic equations.

For example:  Supply and demand relationship model of a market 

Consider a market model assuming the linear behavior of supply and demand with price.

• Demand for a product will be low when the price is high and will be high when the price is low.
• Supply for a product will be high when the price is high and will be low when the price is low.
• If conditions remain stable, the price will settle to the point at which demand equals supply.

The relations can be stated mathematically as:    

    Q = a – bP
    S = c + dP
    S = Q

where, S = supply, Q = demand and P = price

The linear market model is shown below:

Difference Between Stochastic and Deterministic Activities

• Stochastic model / activity has one or more random variable as inputs. Random inputs leads to random outputs. E.g. Simulation of a bank involves random inter-arrival and service times.
• Deterministic model / activity contains no random variables. They have a known set of inputs which will result in a unique set of outputs. E.g. Arrival of patients to the Dentist at the scheduled appointment time.

Simulation is the imitation of the operation of a real-world process or system over time. Simulation involves the generation of an artificial history of the system, and the observation of that artificial history to draw inferences concerning the operating characteristics of the real system that is represented.

Merits of Simulation

• New procedures or rules can be explored without hampering the ongoing real time system operations.
• New designs can be tested without acquiring resources.
• The hypotheses about certain phenomena can be tested for feasibility.
• Insights can be obtained about the variable interaction and their credit for system performance.
• It provides the better understanding of the operation of the system in easier way.
• A simulation study can help in understanding how the system operates rather than how individuals think the system operates.
• “what-if” questions can be answered. So it is useful in the design of new systems.

Demerits of Simulation

• Building model requires specialization which is the art learned through experience.
• In some cases, the results of the simulation may be so complex to interpret.
• It may be time consuming and expensive.

If the future states of a process are independent of the past and depend only on the present , the process is called a Markov process. A discrete state Markov process is called a Markov chain. A Markov Chain is a random process with the property that the next state depends only on the current state.

Markov chains are used to analyze trends and predict the future. (Weather, stock market, genetics, product success, etc.

Formally,

A Markov chain is a sequence of random variables X₁, X₂, X₃, ... with the Markov property, namely that, given the present state, the future and past states are independent.

The conditional probability above gives us the probability that a process in state i_n at time n moves to i_n+1 at time n + 1. We call this the transition probability for the Markov chain. If the transition probability does not depend on the time n, we have a stationary Markov chain, with transition probabilities

Now we can write down the whole Markov chain as a matrix P:

Example:

Weather Problem:

• raining today  ⇒ 40 % rain tomorrow

                                ⇒ 60 % no rain tomorrow

• not raining today  ⇒ 20 % rain tomorrow

                                      ⇒ 80 % no rain tomorrow

What will be probability if todays is not raining then not rain the day after tomorrow?

Markov chain diagram:

Transition matrix:

Thus, the probability of not rainy the day after tomorrow is 0.76.

Arrival defines the way customers enter the system. Mostly the arrivals are random with random intervals between two adjacent arrivals. Typically the arrival is described by a random distribution of intervals also called Arrival Pattern. Arrivals may occur at scheduled times or at random times. When at random times, the inter arrival times are usually characterized by a probability distribution and most important model for random arrival is the poisson process. In schedule arrival interarrival time of customers are constant.

The non-stationary Poisson process is a Poisson process for which the arrival rate varies with time. More specifically, it can be defined as follows:

The counting process N(t) is a non-stationary Poisson process if:

a) The process has independent increments.

b) 

    Where, λ(t) = the arrival rate at time t

                dt = differential sized interval

Validation is a process of comparing the model and its behavior to the real system and its behavior. Calibration is the iterative process of comparing the model with real system, revising the model if necessary, comparing again, until a model is accepted (validated).

Naylor and Finger proposed three step approach for validation of model. These steps are as follows:

1. Face validity

3. Input-Output Transformations

Given,

    X₀ = 27, 

    α = 17,

    c= 43 &

    m=100

We have,

        X_i+1 = (α X_i + c) mod m

        Mixed Congruential Method: c ≠ 0

        & R_i =X_i/m,

The sequence of random numbers are calculated as follows:

X₀ = 27

R₀ = 27/100 = 0.27

X₁ = (α X₀ + c) mod m = (17*27+43) mod 100 = 502 mod 100 = 2

R₁ = 2/100 = 0.02

X₂ = (α X₁ + c) mod m = (17*2+43) mod 100 = 77 mod 100 = 77

R₂ = 77/100 = 0.77

X₃ = (α X₂ + c) mod m = (17*77+43) mod 100 = 1352 mod 100 = 52

R₃ = 52/100 = 0.52

X₄ = (α X₃ + c) mod m = (17*52+43) mod 100 = 927 mod 100 = 27

R₄ = 27/100 = 0.27

Therefore,

The sequence of random integers are 27, 02, 77, 52, 27 & so on.

The sequence of random numbers are 0.27, 0.02, 0.77, 0.52, 0.27 & so on.

Replication of run is used to obtain independent results by repeating the simulation. Repeating the experiment with different random numbers for the same sample size n gives a set of independent determinations of the sample mean  .The mean of the means and the mean of the variances are then used to estimate the confidence interval.

Suppose the experiment is repeated p times with independent random values of n sample sizes. Let x_ij be the i^th observation in j^th run and let the sample mean and the variance for the j^th run is denoted by  and  respectively. Then for j^th run, the estimates are

Combining the result of p independent measurement gives the following estimate for the mean and variance s² of the populations as:

Replication of runs are necessary for running experiments based on scenarios with stochastic parameters. It is used to obtain independent results by repeating the simulation. If replications are not used, a single run of an experiment will not produce statistically significant results and will not allow for proper calculation of statistical data.

Non-uniform random variate generation is concerned with the generation of random variables with certain distributions. Such random variables are often discrete, taking values in a countable set, or absolutely continuous, and thus described by a density. 

The block diagram for given problem using GPSS is given below:

Code for simulating the given problem using GPSS:

        GENERATE  10, 0

          TRANSFER  0.1  A   B

    A    ADVANCE  6, 2

    B    ADVANCE 10, 2

    A    TRANSFER  0.1  ACC   REJ

    B    TRANSFER  0.1  ACC   REJ

    A    ACC TERMINATE   1

           REJ TERMINATE   1

    B     ACC TERMINATE   1

            REJ TERMINATE   1

    START 100

a) System and its environment.

• A system is defined as a collection of object join in some regular interaction or interdependency for achievement of a common goal. We can also define a system as organized set of inter-related idea or principles. All system have input, output and feedback and maintain a basic level of equilibrium.
• A system boundary is the line that separate the system and its environment.
• The external components which interact with the system and produce necessary changes are said to constitute the system environment. In modeling systems, it is necessary to decide on the boundary between the system and its environment. This

b) Simulation run statistics