Simulation and modeling 2068

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/Elements 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.

The gap test is used to determine the significance of the interval between recurrence of the same digit. A gap of length x occurs between the recurrence of  some digit. It Counts the number of digits that appear between repetitions of a particular digit and then uses the Kolmogorov-Smirnov test to compare with the expected number of gaps. 

The probability of a particular gap length can be determined by a Bernoulli trail.

If we are only concerned with digits between 0 and 9, then

The theoretical frequency distribution for randomly ordered digits is given by

Discrete system is one in which the state variables changes only at a discrete set of time. For example: banking system in which no of customers (state variable) changes only when a customer arrives or service provided to customer i.e. customer depart form system.

Continuous system is one in which the state variables change continuously over time. For example, the head of the water behind a dam. During and for some time after a rainstorm, water flows into the lake behind the dam. Water is drawn from the dam for flood control and to make electricity. Evaporation also decreases the water level.

--> Discrete model is appropriate for system having discrete state and changes at particular time point and remains in that state for some time where as Continuous model is a appropriate for system with a continuous state that changes continuously over time.

--> Most discrete time system represents how discrete signals are transformed via difference equations where as Most continuous time system represent how continuous signals are transferred via differential equations.

--> A discrete simulation model is not always used to model a discrete system, nor is a continuous model always used to model a continuous system.

The multi server queue consists of multiple servers and a common queue for all items. When any item requests for the server, it is allocated if at-least one server is available. Else the queue begins to start until the server is free. In this system, we assume that all servers are identical, i.e. there is no difference which server is chosen for which item.

The total server utilization for N server system is 

ρ = λ/μN

    where, μ = service rate and  λ = arrival rate

                        Fig: Multi server queue

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.

Key features of Markov chains

1. The outcome of each experiment is one of a set of discrete state.

2. The outcome of the experiment depends only on the present state and not on the past state.

3. The transition probability remains constant from one to the next.

The congruence method (linear congruential method) produces a sequence of integers X₁, X₂, X₃,.......between zero and m-1 according to the following recursive relationship:

• The initial value X₀ is called the seed;
• a is called the constant multiplier;
• c is the increment
• m is the modulus

The selection of a, c, m and X₀ drastically affects the statistical properties such as mean and variance, and the cycle length.

Case 1:

     When , the form is called the mixed congruential method.

Case 2:
    When c = 0, the form is known as the multiplicative congruential method.

Case 3:

    When a = 1, the form is known as additive congruential method.

The random numbers corresponding to each random integer can be obtained as:                                        

          R_i = X_i/m, for i = 0, 1, 2, 3, …………..

Validation is concerned with building the right model. It is utilized to determine that a model is an accurate representation of the real system. It is usually achieved through the calibration of the model.

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.

Kendall’s notation is used for parallel server systems. The basic format of this notation is of form: A / B / c / N / K, where, A, B, c, N, K respectively indicate arrival pattern, service pattern, number of servers, system capacity, and Calling population.

The symbols used for the probability distribution for inter arrival time, and service time are, D for deterministic, M for exponential (or Markov) and Ek for Erlang.

E.g. 

a) M/D/2/5/∞ stands for a queuing system having exponential arrival times, deterministic service time, 2 servers, capacity of 5 customers, and infinite population.

b) M/D/2 means exponential arrival time, deterministic service time, 2 servers, infinite service capacity, and infinite population.

Given,

    X₀ = 37, 

    α = 7,

    c= 29 &

    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₀ = 37

R₀ = 37/100 = 0.37

X₁ = (α X₀ + c) mod m = (7*37+29) mod 100 = 288 mod 100 = 88

R₁ = 88/100 = 0.88

X₂ = (α X₁ + c) mod m = (7*88+29) mod 100 = 645 mod 100 = 45

R₂ = 45/100 = 0.45

X₃ = (α X₂ + c) mod m = (7*45+29) mod 100 = 344 mod 100 = 44

R₃ = 44/100 = 0.44

Therefore,

The sequence of random integers are 37, 88, 45, 44

The sequence of random numbers are 0.37, 0.88. 0.45, 0.44.

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:

Example:

                Fig: Manufacturing shop model

a. Replication of runs

This approach 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:

b. Simulation tools

Simulation tool is a software which is used for simulating hardware, software and network. It is a type of software based on the process of modeling a real world phenomenon with mathematical formula. This program allows the user to observe the operation without actually performing that operation . Its main importance is: how it actually supports the model building.