Programming and Computation: Arrival Patterns and Service Times

Chapter 07:(Arrival Patterns and Service Times)

7-1:: Congestion in Systems::

Question: What is queue? (M.Sc.- ’97,’99)

Answer:

Queue: Sometimes, in a system, there are more entities arrive than can be served at one time, and some entities must wait for service. The entities are then said to join a waiting line. The combination of all entities in the system- those being served, and those waiting for service- will be called a queue.

Question: What are the factors (characteristics) that affect congestion in systems? Explain with examples. (M.Sc.- 98)

Answer: Congestion in a system may be described in terms of three main factors (characteristics). These are:

(a) The arrival pattern, which describes the statistical properties of the arrivals.

(b) The service process, which describes how the entities are served.

The service process, in turn, is described by three main factors: the service time and the capacity and the availability. The service time is the time required to serve an individual entity. The service capacity, or, more simply, the capacity, is the number of entities that can be served simultaneously. The service may not be available at all times.

Question: Mention the congestion characteristics of a system. (’99)

Answer: The congestion characteristics of a system are given below:

Congestion in a system may be described in terms of three main factors (characteristics). These are:

(a) The arrival pattern, which describes the statistical properties of the arrivals.

(b) The service process, which describes how the entities are served.

Question: How can we express service process in terms of service time, capacity and availability? (’01)

Answer:

7-2: Arrival Patterns

q Question: How can we express the arrival pattern of a system? (’01)

Answer:

Usually the arrival pattern is described in terms of the inter-arrival time, defined as the interval between successive arrivals. For an arrival pattern that has no variability, the inter-arrival time is a constant. Where the arrivals vary stochastically, it is necessary to define the probability function of the inter-arrival times. Two or more arrivals may be simultaneous. If n arrivals are simultaneous, then n – 1 of them have zero inter-arrival times.

Following notation will be used for describing arrival patterns:

Mean inter-arrival time.

Mean arrival rate and they are related by the question

For describing arrival patters, to express the distribution in terms of the probability that an inter-arrival time is greater than a given time (t). We define

as the arrival distribution, so that:

is the probability that an inter-arrival time is grater than t.

Since the cumulative distribution function

is the probability that an inter-arrival time is less than or equal to t, it is related to the arrival distribution by

From its definition, the function

takes a maximum value of 1 at t=0 and it cannot increase as t increases.

7-3:: Poisson Arrival patterns::

Question: Describe Poisson distribution:

Answer: The Poisson distribution describes many random processes quite well and is mathematically quite simple. S.D. Poisson introduced the Poisson distribution in 1837. The Poisson probability mass function (pmf) is given by

where a>0.

One of the important properties of the Poisson distribution is that the mean and the variance are both equalsa to a, that is, E(n)=a=V(n)

The cumulative distribution (cdf) is given by

The probability mass function(pmf) and cumulative distribution function(cdf) with a=2 are shown below:

Example: A computer terminal repairperson is “beeped” each time there is a call for service. The number of beeps per hour is known to occur in accordance with a Poisson distribution with a mean of a=2 per hour. The probability of 3 (three) beeps in the next hour is given by,

with n=3 as follows:

Question: Explain Poisson arrival patterns. (’97,’99,’01)

Answer: There are certain situations where the arrivals are said to be completely random. This means that an arrival can occur at any time, but the mean arrival rate be some given value. If we assumed that the time of the next arrival is independent of the previous arrival, that is the probability of an arrival in an interval

is proportional to

is the mean number of arrivals per unit time, then the probability of an arrival in

. With these assumptions, it is possible to show that the distribution of the inter-arrival times is exponential. The probability density function of the inter-arrival time is given by

If follows that the arrival distribution is

Here

is the mean number of arrivals per unit time. The actual number of arrivals in a period of time t is a random variable. It can be shown that with an exponential distribution of inter-arrival times, the probability of n arrivals occurring in a period of length t is given by

This distribution is called Poisson distribution and it is discrete. The exponential distribution is, of course, continuous, since the inter-arrival time can take any non-negative value. Because of this connection between the two distributions, a random arrival pattern is often called a Poisson arrival pattern.

7-6: Erlang Distribution

Question: Write short notes on Erlang distribution.

Answer:

Erlang distribution:

There is a class of distribution functions named after A. K. Erlang, who found these distribution to be representative of certain types of telephone traffic. An arrival pattern governed by this type of function has the following density function and arrival distribution

where k is a positive integer greater than zero. Figure(1) illustrates the Erlang arrival distribution for several values of k. putting k=1 in the above equation we get

,the exponential distribution. The standard deviation of the Erlang

distribution is T/k^1/2, so that the coefficient of variation is 1/k^1/2. The coefficient has a maximum value of 1 for the case of the exponential distribution, and it decreases as k increases. It follows that data represented by an Erlang distribution (k>1) cluster more closely to the mean value than exponentially distributed data, so that there are fewer low values and high values. Ultimately, as k tends to infinity, the Erlang distribution tends to the case of a constant arrival time, for which the arrival distribution is the step function shown in the above figure(1).

7.7 Hyper – exponential distribution:

Question: Describe Hyper-exponential distribution. /Explain Hyper-exponential distribution through a physical model. How can we generate Hyper-exponential distributed random number/variates?

Answer: The hyper-exponential distribution defines a class of distributions that have a standard deviation greater than their mean value. Consequently, they can be used to match data found to have a co-efficient of variation greater than 1. They represent the data where low and high values occurs more frequently than with an exponential distribution. The data distribution may in fact be bimodal, showing a peak on either side of the mean value. It is possible to give a physical analogy to explain the nature of the hyper-exponential distribution. Suppose that there are two parallel stages of processing as shown in the following figure (fig: 7-4). Both stages have exponential service times, one with a mean value of T/2s and other with, mean value of T/2(1-s), 0< s £1/2. When an entity in to be served, a random choice is made between the two stages; the probability of choosing the stage with mean of T/2s being s and the probability of choosing the other being (1-s). A second entity can not enter either stage until the preceding entity has been cleared. The equation for the resulting arrival distribution is found to be

The variance is

so the co-efficient of variation is

where

When s=1/2, the value of K is 1 and the distribution becomes the exponential distribution. Following figure illustrate some hyper-exponential arrival distributions for various values of K and the corresponding values of s are shown in the following figure (fig:7-5,Page-157):

The process described below can generate hyper-exponential distributed random numbers:

Step1: An exponentially distributed random number with mean value of 1 is generated from a uniformly distributed random number.

Step2: A second uniformly distributed random number is compound to s, if it is less then s, the exponentially distributed random number is multiplied by T/2s, otherwise, it is multiplied by T/2(1-s).

Question: Explain exponential distribution and describe the procedure to generate random variates for exponential distribution.

Answer: The exponential distribution has probability density function (pdf) given by

and cumulative distribution function (cdf) is given by

The parameter

can be interpreted as the mean number of occurrence per time unit. If inter-arrival time

had an exponential distribution with rate

, then

can be interpreted as the mean number of arrivals per time unit or the arrival rate. It can be expressed through following type of curve:

SHAPE

For any i,

so that 1/l or

is the mean inter-arrival time.

Random Variates Generation for exponential distribution:

The goal here is to develop a procedure for generating values

which have an exponential distribution. The inverse transformation technique can be utilized, because the cdf, F(t) is of such simple form that its inverse,

be easily computed. A step by step procedure for the inverse transformation techniques, illustrated by the exponential distribution, is as follows:

Step1: Compute the cdf of the desired random variable t. For the exponential distribution, the cdf is

Step2: Set F(t)=U on the range of t. For the exponential distribution, it becomes

on the range t ³0. Here R is a uniform distribution over the interval (0,1).

Step3: Solving, the equation F(t)=U for t in terms of U. For the exponential distribution the solution proceeds as follows:

This equation called random variate generator for the exponential distribution.

Step4: Generate (as needed) uniform random numbers

and compute the desired random variates by

One simplification that is usually employed in the above equation is to replace

to yield

which is justified since both

and

are uniformly distributed on (0,1).

7-8 Service times: Frequently, the service time of a process is constant; but where it varies stochastically, it must be described by a probability function. In describing service time, the following notation will be used:

Ts = Mean service time

m = Mean service rate

So(t) = Probability that service time is > t.

If the service time is considered to be completely random, it may be represented by an exponential distribution or, if the co-efficient of variation is found to differ significantly from 1, an Erlang or hyper-exponential distribution may be used. A common situation is that, although the service time should be a constant, there are random fluctuations due to uncontrolled factors. For example, a machine tool may be expected to take a fixed time to turn out a part, but random variations in the amount of material to be removed and the toughness of the material cause fluctuations in the processing time. The normal or Gaussian distribution is often used to represent the service time under these circumstances.

7-9 The Normal distribution: The normal probability density function is symmetric about its mean value and is completely characterized by its mean value m and standard deviation s.

A random variable X with mean m(-µ < m < µ) and variance

has a normal distribution if it has a probability density function (pdf):

The normal pdf is shown is the following figure.

Many methods have been developed for generating normally distributed random variates. Neither the cumulative distribution function nor its inverse can be expressed in terms of simple mathematical function because the inverse cumulative distributed function (cdf) cannot be written in closed form.

If the transformation

is made, the distribution is transformed to a form in which mean is 0 and standard deviation is 1. In this from the probability density function is,

It is customary to create generators that determine numbers distributed according to the function f (z) and derive the variable x that has mean m and standard deviation s by the transformation

. The variable z in usually called the standard normal variate. A very useful approximation method derives normally distributed random numbers by summing several uniformly distillated random numbers

according to the following formula:

The distribution of a sequence of members derived from this formula approaches a normal distribution with mean zero(0) and standard divination 1 as k approaches infinity. Quite small values of k give good accuracy. A convenient vales of k is k =12, in which case the formal takes the form,

This is a direct method of deriving normally distributed random numbers, based upon the properties of random numbers, rather than using inverse transformations method.

7-10 Queuing Disciplines

Question: Discuss different queuing disciplines and other associative terms. (M.Sc.- ’97,’01)

Answer: One of the factors for describing congestion is the queuing discipline that determines how the next entity is selected from a waiting line. The most common queuing discipline and some of the terms used in describing queues are as follows:

(a) A First-In, First-Out (FIFO) discipline occurs when the arriving entities assemble in the time order in which they arrive. Service is offered next to the entity that has waited longest.

(b) A Last-In, First-Out (LIFO) discipline, occurs when service is next offered to the entity that arrived most recently. It is the precise discipline for records stored on a magnetic tape that are read back without rewinding the tape.

(c) A random discipline means that a random choice is made between all waiting entities at the time service is to be offered. Unless specified otherwise, the term random implies that all waiting entities have an equal opportunity of being selected.

Reneging: It means that entities leave before there service is due to being, and when this occurs the rules for reneging must be specified. Reneging may depends on the waiting line length or the amount of time an entity has waited.

Balking: It means an entity refuses to join a waiting line.

Polling: When there is more than one line forming for the same service, the action of sharing service between the lines is called polling. The polling discipline needs to be specified by giving the order in which the lines are served, the number of entities served at each offering of service, and the time (if any) in transferring service between lines.

Priority: Some members of a waiting line may have priority, meaning that they have a right to be served ahead of all other members of lower priority. There may be several levels of priority and since there may be several members in the same priority class, a queuing discipline must be specified for member within a class. A typical situation is for service to be by priority, and first-in, first-out within priority class.

When priority is allowed, a factor that must be considered is what happens when a new arrival has a higher priority than the entity currently being served. If, new arrival with higher priority displace the entity being served, the new arrival is the said to interrupt or preempt the service.

Question: Define ‘reneging’ and ‘balking’ according to queuing discipline of a system. (’99)

Answer: The define of the terms ‘reneging’ and ‘balking’ according to queuing discipline of a system are given below:

Balking: It means an entity refuses to join a waiting line.

Question: You are given to simulate the bill reception counter of a bank. What will be your queuing discipline? Justify your choice. (’98)

Answer:

Here our queuing discipline should be FIFO (First-In-First-Out) where entities assemble in the time order in which they arrive. Service is offered next to the entity that has waited longest. Here we also consider reneging situation. Reneging means that entities leave before their service is due to being. Reneging may depend on the waiting line length or the amount of time an entity has waited. Multiple lines can be formed, where one for young peoples and other for old peoples. These two lines may be served from a single counter and this type of sharing service is called polling. Service is offered first for old peoples that means old peoples line has higher priority than young people line but service should not be preempted/interrupted by other entities.

7-11: Measures of Queues:

Question: Discuss different key parameters used as measures of queues.

(OR)

Question: Discuss any one of key parameters used as measures of queues. (M.Sc.- 97)

Answer: We can consider the following terms: mean inter-arrival time,

, mean service time

, together with the corresponding rates, mean arrival rates

and mean service rate

. The ratio of the mean service time of mean inter-arrival time is called the traffic intensity, denoted by u.

Traffic intensity

Here, prime is used, because there may balking or reneging, that is not all arriving entities will get served. It is therefore necessary to distinguish between the actual arrival rate and the arrival rate of the entities that get served. For this purpose, we define the quantity,

Server utilization,

Server utilization (for single server)

Here both the traffic intensity and server utilization can be greater than 1. If so, a single server cannot keep up with the flow of traffic. If more than one server is used, say n servers, server utilization is redefined to reflect the load on each individual server, as follows:

n Number of servers

Server utilization.

Two principle measures of queuing systems are the mean number of entities waiting and mean time they spend waiting. Both these quantities may refer to the total number of entities in the system, those waiting and those being served, or they may refer to the entities in the waiting line only. The probability that an entity will have to wait more than a given time, called delay distribution and will be denoted as follows:

: Probability that the time to complete service is greater than t.

: Probability that the time spent waiting for service to being is greater than t.

Question: What is queue? Give the equations for mathematical solutions for queuing problems.

Answer:

(1^st Part) Queue: Sometimes, in a system, there are more entities arrive than can be served at one time, and some entities must wait for service. The entities are then said to join a waiting line. The combination of all entities in the system- those being served, and those waiting for service- will be called a queue.

(2^nd Part) A number of problems involving queues can be solved mathematically. All solutions given here are for infinite populations of sources; that is, the arrival rates are not affected by the number of entities currently in the system. We give solutions for the case of a single server with Poisson arrivals and different service time distributions. The cases considered for hyper-exponential, exponential, Erlang, and constant service time distributions. The equations for mean number of entities in the system, when

are

In all cases, the total number of entities waiting for service and the mean times spent waiting, both for service to begin and for service to be competed, can be derived from L with the following formula:

7-14: Grade of Service:

Question: Write short notes on grade of service

Grade of service:

Answer: The grade of service places some limit, or limits, on the length of time an entity must wait for service measured either as the time for service to begin or to be completed. This is an a important characteristics of any system involving human beings, for example, a telephone system, or any computer-based terminal system. The limit might be absolute, but it is usually expressed in probability terms. The requirement, for example, might be that not more than 10% of the requests for service should have to more than three seconds.

To meet such criteria, it is necessary to know the probability of waiting a given length of time, and so waiting time probabilities are important outputs of simulation studies. As an illustration, following figure shows the probability of waiting longer than a given time for service to begin, in the case of a single server with Poison arrivals and an exponential service time distribution. The probability, denoted by