Simulation and modeling 2067

Model

• Model is a computerized program that defines the mechanics of the considered system.
• During system modeling, the focus is on the system components, system structure, relationships among the components of the system and the behavior of the modeled system.
• Model must have state which may change on each time step.
• Model represents the system for the purpose of studying the system.

Types of Model

1. Physical Model

    Physical model is the smaller or larger physical copy of an object being modeled. The physical model helps in visualization of the object taken into consideration in an effective way. It is also used to solve equations with the particular boundary conditions.

Two types of physical model:

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.

Characteristics of Queueing System

The key elements of queuing systems are customer and server. Customer refers to anything that arrives at a facility and requires service. E.g. people, machines, trucks, emails. Servers refers to any resource that provides the requested service. E.g. receptionist, tellor, CPU, washing machine etc.

1. Calling Population

The population of potential customers those require service from system is called calling population. It may be finite or infinite. System having large calling population is usually considered as infinite. For e.g. customers at banks, restaurant. And System having less and countable population is usually considered as finite. For e.g. a certain number of machines to be repaired by a service man.

    In finite population model, arrival rate depends on the number of customers being served and waiting. But in infinite population model, arrival rate is not affected by the number of customer being served and waiting.

2. Arrival Process

The arrival process for infinite-population models is usually characterized in terms of interarrival times of successive customers. 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.

3. Service Process

Service process can be measured by the number of customers served per some unit of time or the time taken to complete the service. Once entities have entered to the system they must be served. The service can be provided in single or batch. if it is batch, as in the case of arrival the batch size can be fixed or random. Service time may be of constant duration or of random duration.

Markov Service process: A Markov service process is a special service process in which entities are processed one at a time in FCFS order and service times are independent and exponential. Aswith the case of Markov arrivals, a Markov service process is memoryless, which means that the expected time until an entity is finished remains constant regardless of how long it has been in service.

4. Queueing Discipline and Queueing Behaviour

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.

Queue behavior refers to the actions of customers while in a queue waiting for service to begin. Different queue behaviours are:

• Balk/Balking: It means leaving the queue when the customer see the line is too long.
• Renege/Reneging: Leave after being in the line when they see that the line is moving too slowly.
• Jockey/Jockeying: Move from one to a shortest line. 

5. Number of Servers: 

Servers represent the entity that provides service to the customer. A system may consist of single server or multiple servers.
- A system with multiple servers is able to provide parallel services to the customers.

Independent test determines whether a random number generator is producing independent random number in a sequence. Test for independence includes the three types of tests as given below:

1) Autocorrelation Test tests the correlation between numbers and compares the sample correlation to the expected correlation of zero.

2) Gap test Counts the number of digits that appear between repetitions of particular digit and then uses the Kolmogorov-Smirnov test to compare with the expected size of gaps,

3) Poker test: Treats numbers grouped together as a poker hand. Then the hands obtained are compared to what is expected using the chi-square test.

Now,

The probabilities associated with each of the given combination is given by

P (four different digits) = ⁴C₄ * (10/10) * (9/10) * (8/10) * (7/10) = 0.504

P (one pair) = ⁴C₂ * (10/10) * (1/10) * (9/10) * (8/10) = 0.432

P (two pair) = (⁴C₂/2)*(10/10) * (1/10) * (9/10) * (1/10) = 0.027

P (three digits of a kind) = ⁴C₃ * (10/10) * (1/10) * (1/10) * (9/10) = 0.036

P (four digits of a kind) = ⁴C_{4 *} (10/10) * (1/10) * (1/10) * (1/10) = 0.001

Now the calculation table for the Chi-square statistics is:

 = 25. 183

and Given  _{α, N} = _{0.05, 4}= 9.49

Here the calculated value of chi-square is 25.183 which is greater than the given tabulated value of chi- square so we reject the null hypothesis of independence between given numbers.

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.

Advantages 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.

Disadvantages 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.

Pseudo random numbers are the random numbers that are generated by using some known methods (algorithms) so as to produce a sequence of numbers in [0,1] that can simulates the ideal properties of random numbers. They are not completely random as the set of random numbers can be replicated because of use of some known method.

Every new number is generated from the previous ones by an algorithm. This means that the new value is fully determined by the previous ones. But, depending on the algorithm, they often have properties making them very suitable for simulations.

When generating pseudo-random numbers, certain problems or errors can occur. Some examples include the following:

1. The generated numbers might not be uniformly distributed.
2. The generated numbers might be discrete valued instead of continuous valued.
3. The mean of the generated numbers might be too high or too low.
4. The variance of the generated numbers might be too high or too low.
5. There might be presence of correlation between the generated numbers.

The important considerations that should be made while generating pseudo random numbers are as follows:

1. The method used to generate random number should be fast because the simulation problem requires a large set of random numbers which can increase time complexity of the system.
2. The method used should be portable to different platform and programming languages so as to generate same results wherever it is executed.
3. The method should have long cycle.
4. The random numbers should be replicable. It means that the same set of random numbers should be generated with same starting point.
5. The generated random numbers should approximate the uniformity and independence properties.

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 methods used for generating non-uniform random variate are inverse transformation technique and acceptance/rejection technique.

Acceptance/Rejection Method

The rejection method for obtaining samples of random numbers forms a given non-uniform distribution works by generating uniform random numbers repeatedly and accepting only those numbers that meet certain conditions.

The rejection method is applied when the probability density function, f(x), has a lower and upper limit to its range, 'a' and 'b', respectively, and an upper bound 'c'. The method can be specified as follows:

1. Find the maximum value c of f(x) on a ≤ x ≤ b.

        f(X)  ≤ c ∀ x ∈ [a, b]

2. Compute two values μ₁, μ₂ of the uniformity distributed variables, both defined on [a, b] = [0, 1].

3. Compute x₀ = a + μ₁(b - a)

4. Compute y₀ = c μ₂

5. If y₀ ≤ f(x₀), accept x₀ as desired output; otherwise reject x₀ and repeat the process with two next values μ₁ &  μ_2.

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.

Applications of Markov Chain

1. Physics: Markovian systems appear extensively in thermodynamics and statistical mechanics, whenever probabilities are used to represent unknown or unmodelled details of the system, if it can be assumed that the dynamics are time-invariant, and that no relevant history need be considered which is not already included in the state description.

2. Internet applications: The Page Rank of a webpage as used by Google is defined by a Markov chain. It is the probability to be at page i in the stationary distribution on the following Markov chain on all (known) web pages

3. Statistics: Markov chain methods have also become very important for generating sequences of random numbers to accurately reflect very complicated desired probability distributions, via a process called Markov chain Monte Carlo (MCMC) And many more.

4. Queuing theory: Markov chains are the basis for the analytical treatment of queues (queuing theory). Agner Krarup Erlang initiated the subject in 1917. This makes them critical for optimizing the performance of telecommunications networks, where messages must often compete for limited resources (such as bandwidth).

Given,

    X₀ = 29, 

    α = 9,

    c= 49 &

    m=100

We have,

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

The sequence of random integers are calculated as follows:

X₀ = 29

X₁ = (α X₀ + c) mod m = (9*29+49) mod 100 = 310 mod 100 = 10

X₂ = (α X₁ + c) mod m = (9*10+49) mod 100 = 139 mod 100 = 39

X₃ = (α X₂ + c) mod m = (9*39+49) mod 100 = 400 mod 100 = 0

CSMP or Continuous System Modelling Program is an early scientific computer software designed for modelling and solving differential equations numerically. This enables real-world systems to be simulated and tested with a computer.

1. Data statements which assign numerical value to parameters, constant and initial conditions. For example one data statement called INCON can be used to set the initial value of integration function block.

2. Control statements which specify options in the assembly and execution of program and choice of inputs. For e.g. If printed output is required, control statements with PRINT and PRDEL are used followed by the names of variables to form the outputs.

Example program in CSMP

TITILE AUTOMOBILE SUSPENSION SYSTEM

*

  PARAM D=(5.656,16.968,39.592,56.56)     //initial

  *

X2DOT=(1.0/M)*(K*F-K*X-D*XDOT)

XDOT=INTGRL(0.0,X2DOT)                         //dynamic

X=INTGRL(0.0,XDOT)

 *

CONST M=2.0,F=1.0,K=400.0

TIMER DELT=0.005,FINTIM=1.5, PRDEL=0.05     //terminal

PRINT X, XDOT, X2DOT

 END 

STOP 

Iterative calibration means to validate the model with the real system, look out for the places for betterment of the models and revising the model to form next better model repeatedly until a satisfiable model is not achieved. The initial model is developed and is calibrated using Naylor-Finger calibration steps with the real system. It is then revised and a first revision model is generated. The first revision model is then calibrated with the real system. It is revised to form a second revision model. This process is continued until the model becomes acceptable.

Naylor and Finger formulated a three step approach:-

1. Build a model that has high face validity.

2. Validate model assumptions.

3. Compare the model input-output transformations to corresponding input-output transformations for the real system.

The following figure shows the relationship of the model calibration to the overall validation process.

The comparison of the model to reality is carried out by verity of test. Some test are subjective and other are objective.

• Subjective test usually involve people, who are knowledgeable about one or more aspects of the system, making judgments about the model and its output.
• Objective test always require data on the system's behavior plus the corresponding data produced by the model.

a. GPSS

- GPSS (General Purpose Simulation System) is a highly structured and special purpose simulation language based on process interaction approach and oriented toward queuing systems.
- The system being simulated is described by the block diagram using various GPSS blocks.
- Each block represents events, delays or other actions that affect the transaction flow.
- GPSS model is developed by converting the block diagram into block statements and adding the control statements.

The general blocks used in GPSS block diagram is shown in figure below:

b. Server Utilization

Server/System utilization is the percentage of the time that all servers are busy. System utilization factor (ρ ) is the ratio of average arrival rate (λ) to the average service rate (μ).

ρ = λ/μ in the case of a single server model

ρ = λ/μn in the case of a “n” server model

The system utilization can be increased by increasing the arrival rate which amounts to increasing the average queue length as well as the average waiting time, as shown in fig below. Under the normal circumstances 100% system utilization is not a realistic goal.