Handout #5

Handout #7

Date:

Remember:

A/B/c/N/K

Where

A = Interarrival Times

B = Service Times

c = Number of Servers

N = System Capacity

K = Size of the population

A & B can be represented by distributions, and c, N, and K are integers.

Common symbols for A & B:

M = Exponential or Poisson

D = Constant or deterministic

E_k = Erlang of Order k

G = Arbitrary or General

There are two types of systems:

Serial � Servers are arranged serially, so when a job finishes service, it goes to the next server.

Parallel � Servers are arranged in parallel, so a job has a choice of one or more servers.

You were given queuing notation for parallel server systems previously.

Example 1

Given a queuing system where the interarrival times of jobs are exponentially distributed with a mean of two per hour and service times are exponentially distributed with a mean of three jobs per hour.� Assume one server.

What is the notation for this queuing system?

What is the average time between arrivals?

l = �� per hour

�� jobs/hour � �� hour/2 jobs = �� hours between arrivals

What is the average service time?

m = �� per hour � �� hour/�� jobs = �� hours per job = �� minutes

What is the server utilization?

r = l/m = ��

What is the probability of 0, 1, 2, 3 and 4 or more jobs in the system?

P_n = (1 - r) rⁿ

P_n = ��

P₀ = (1 - r) r⁰ = ��

P₁ = (1 - r) r¹ = ��

P₂ = (1 - r) r² = ��

P₃ = (1 - r) r³ = ��

P_>4 = 1 - � P_i, for i = 0..3

P_>4 = 1 � (P₀ + P₁ + P₂ + P₃) = ��

What is the probability that the server is busy?

Probability that the server is busy + Probability that the server is not busy = 1

1 � Probability that the server is not busy = ��

What is the long time average of the number of jobs in the system?

L = l/(m - l) = ��

What is the average time an arrival spends in the system?

w = L/l = ��

What is the average number in the queue?

L_Q = l²/ [m (m - l)] = ��

Example 2.

Suppose instead that the exponential distributed service time has a mean of one job every forty minutes (instead of the three jobs per hour stated previously).

What is the average time between arrivals?

��

l = �� per hour

�� jobs/hour � �� hour/�� jobs = �� hours between arrivals

What is the average service time?

m =� �� job per �� minutes = �� job per �� hour � �� hour/job

What is the server utilization?

r = l/m = ��

What is the problem with this?

Server utilization, r, must be less than 1.

r = l/m < 1

How can we ensure a steady state system?

Increase the number of servers, c.

r = l/(cm)

l/(cm) < 1

l/m < c

�� < c, so c has to be at least �� .� There must be �� servers.

Increasing the number of servers to c = �� , what is the utilization?

r = l/(cm) = ��

What is the notation for this queuing system?

��

What is the probability of zero jobs in the system?

What is the probability that all the servers are busy?

��

What is the time average length of the queue?

L_Q = [r�P(L(t) � c)] / (1 - r) = [(2/3)(8/15)] / [1-(2/3)] = ��

What is the time average number of jobs in the system?

L = L_Q + l/m = ��

What is the long-run average time spent in the system per job?

w = L/l = ��

What is the long-run time spent in the queue per job?

w_Q = w � 1/m = ��

Example 3

Assume that a single server queuing system has problems which cause random system shut-downs.� Let these shut-downs occur according to a Poisson process at a rate of 1.5 per hour.� Also assume that down times have been observed over a period of time and that the systems can be up and running on an average time of 30 minutes with a standard deviation of 20 minutes.

What is the notation for this queuing system?

�� , note that the mean of the service times is known, not the distribution.

What are the "arrivals"?

The arrivals are the occurrences of downtimes.

What is the average time between arrivals?

l = �� per hour

�� downtimes/hour � 1 hour/2 downtimes = � hours between arrivals of downtimes

What is the "service"?

The service, and the service time is the time to get the system back up.

What is the average service time?

m = �� per hour � 1 hour/2 services = 1/2 hours per service = �� minutes

standard deviation = s = �� minutes

variance = s² = (�� minutes)² = 400 minutes² = (400 minutes²) (1 hour/60 minutes)

= (400 minutes²) (1 hour²/3600 minutes²) = �� hours²

What is the busy time of the staff to get the systems up and running?

r = l/m = ��

What is the long-run time-average number of shut-downs of the system?

�� shut-downs

Example 4

Suppose now that jobs arrive to a single server queuing system according to a Poisson process at the rate of one per hour.� Also assume that the jobs must go through three stages, each one independently and exponentially distributed with a service time of fifteen minutes.� A job must go through all three stages before another job can be serviced.

What is the notation for this queuing system?

��

What is the average time between arrivals?

l = �� per hour

�� job/hour � �� hour/�� jobs = �� hours between arrivals

What is the average service time?

m = 1 job per �� minutes = 1 job per 45 minutes = 1 job per 3/4 hours = 1/(3/4) = 4/3 jobs/hour = �� hours/job

What is the server utilization?

r = l/m = ��

What is the long-run time-average number of jobs in the queue?

�� jobs

Example 5

Assume now that the service times for a single-server queuing system have no variability (service times are constant).� The arrivals are Poisson distributed at a rate of 30 per hour.� The time to service a job is a constant 90 seconds.

What is the notation for this queuing system?

��

What is the average time between arrivals?

l = �� per hour = 30 per 60 minutes = 1 per 2 minutes

1 jobs/2 minutes � �� minute/job

What is the average service time?

m = �� seconds/job = 3/2 minutes/job = �� jobs/minute

What is the server utilization?

r = l/m = ��

What is the long-run time-average number of jobs in the system?

�� jobs

What is the long-run average time spent in queue per job?

�� minutes

What is the long-run average time spent in system per job?

�� minutes

What is the long-run time-average number of jobs in the queue?

�� jobs