Models - Operations Research Models and Methods

Models

Queuing

Model Classes

General

Markov

Non-Markov

Networks

	Model Classes
	Markov Systems

When the interarrival and service times have exponential probability distributions, the system is a Markov Queuing System. The exponential distribution satisfies the Markovian assumption in that it has no memory. For example, if we are waiting for an arrival to occur whose time is exponentially distributed, the expected time for the arrival to occur does not depend on how long we have already waited. Although this may seem odd, there are situations where the assumption is valid, and the assumption of exponential distributions is necessary to obtain closed form solutions for statistical measures. With the assumption of exponential distributions, we say that the arrival and service processes are Poisson.

Notation

A 5-field notation specifies the parameters of the system.

M/M/s/K/N

The first field indicates the probability distribution for time between arrivals and the second field indicates the probability distribution for time for service. The letters M mean that the arrival and service processes are Poisson. The third field, s, is the number of servers. The fourth field, K, is the maximum number of customers allowed in the system, and the fifth field, N, is the size of the calling population. When K and N are infinite, only the first three fields are used. When K is finite but N is infinite, the first four terms are used. We will not have the case when K is infinite but N is finite.

Example: A Manufacturing Station

A rework station in a computer manufacturing facility consists of three workers repairing computers with manufacturing defects. The average repair time for a machine is 30 minutes, or equivalently, the rate of repair is 2 per hour. Because of the wide variety of possible defects, the probability distribution for repair time can reasonably be approximated by an exponential distribution. Machines arrive at the station at a rate of 5 per hour. Arrivals occur independently, so we can justify that the time between arrivals has an exponential distribution with a mean of 12 minutes.

We would like to answer a variety of questions about his situation. For example, how many machines on the average will be waiting for repair? How much time will a machine spend in the repair facility? How often will the workers be idle? With the assumption of exponential distributions (Poisson processes) for interarrival and repair times, we can use the formulas of queuing analysis to answer these and many other interesting analysis and design questions.

The display generated for the example case using the Excel Queuing add-in is shown below. Two other cases that demonstrate the effects of a finite queue and a finite population. The add-in provides user defined Excel functions that compute the steady-state results. The first six rows of the display give the parameters of the system. The remaining rows show selected steady state results. We use P(n) as a substitute for in the display.

The column for Q_Sample provides answers to the questions originally posed. How many machines on the average will be waiting for repair? This is given by the mean number in the queue or 3.51. The mean number in service (or actually being repaired) is 2.50, so the total number in the system is 6.01. This is an interesting number because it represents the average inventory due to the repair operation.

How much time will a machine spend in the repair facility? This is given by the mean time in the system as 1.20 hours. The time dimensions are the same as those assumed for the arrival and service rates. The system time is broken into time in the queue (0.70 hours) and time in service (0.50) hours. These numbers are interesting because they describe the cycle time for the repair process.

How often will the workers be idle? The efficiency result indicates that on the average the repair workers are busy 83.3% of the time. The state probabilities indicate that all three workers are idle simultaneously 4.5% of the time (P(0)), all three are busy 70% of the time (1 - P(0) - P(1) - P(2)), and the system is never full since in this case there is no limit to the length of the queue.

The entry for P(Wait >= Critical Wait) shows the probability that the time in the queue is greater than a specified value. In the display the critical value is 0.5 hours.

The column for Q_2 shows the results for a finite queue case. With a finite queue there is the possibility that an arrival will discover that the system is full. For the example this occurs when there are 8 already in the system. When the system is full, the arrival balks and does enter. The probability of this is P(8) or 0.0615. This is an important measure for a system because it indicates the proportion not served. It also appears as the Probability that the system is full. When balks occur the Throughput Rate is smaller than the arrival rate, as indicated for the example.

Column Q_3 illustrates a finite population system. In this case the arrival rate is the rate for each individual of the population. The actual arrival rate into the system depends on the state since customers already in the system cannot arrive. For the example there are 8 in the population, so the arrival rate into the system when it is empty (state 0) is 0.0625*8 = 5. Since K and N are equal in this case there is no balking. When there are 8 customers in the system, none can arrive. The Throughput Rate for the finite population case is smaller that the other two. This is due to reduction in arrival rate as the number in the system increases.