Hi, sam420-ga:
The assumption that "customers arrive according to a Poisson process"
implies that their interarrival times are exponentially distributed
and independent. See Thm. 3.2 here and the comment following:
[Properties of the Poisson Process]
http://www.sics.se/~andersa/report/node16.html
Thus the exercise describes a basic queuing model called M/M/n.
The two captial M's stand for "Markovian" and denote that the
interarrival and service times are independently and exponentially
distributed. The little "n" stands for the number of servers, so
we are comparing an M/M/1 queue and an M/M/5 queue in this case.
Both systems have equal capacity, an ability to serve 30 average
customers per hour. The first arrangement features a single high
capacity server, and the second arrangmement divides that capacity
among five servers.
What requires some initiative on our part is to guess exactly what
needs to be calculated. The exercise asks simply, which system
would you prefer?
The information provided allows us to determine how long on average
it takes for a customer to be served, including time spent waiting.
While there might be other considerations to choose between the two
systems in practice, such as cost and reliability, no information
is given about these aspects, so we will ignore them and focus on
the average time a customer spends in the system.
We shall refer to the following concise summary of formulas for the
basic M/M/n queuing models:
[Note on Queuing Theory]
http://williams.cs.ncat.edu/queueing.htm
The formulas for a single server queue are especially easy to use,
and will motivate the discussion of a multiple server queue. We are
told that on average the customers arrive at a rate of 25 per hour.
In the M/M/1 case we have a single server that can process customers
at an average rate of 30 per hour. The single server will then be
"busy" precisely 25/30 = 5/6 of the time. The queue "buffers" work
which arrives while the server is busy, but as long as the average
rate at which the work arrives is less than the average rate at which
the server can do the work, the queue will eventually empty and allow
the server to sit idle for a positive fraction of time.
The figure p = 5/6 here is called the "utilization" of the system,
and in a one processor queue it is simple the ratio of the rate at
which work arrives to the rate at which the system can perform it.
Note that in the single high capacity server case, the average length
of time needed to serve a customer is just:
s = (1/30) hour = 2 minutes
The average of total time customers spend in the system is greater
than that time being served, because of the positive possibility of
waiting in the queue before reaching the server.
In M/M/n queues average time waiting in the queue T_w is often stated
in terms of a "stretch factor" F(n,p), depending only on the number n
of servers and the utilization p, times the average service time s:
T_w = F(n,p) * s
and thus the average total time in the system, including service time:
T_q = T_w + s = [1 + F(n,p)] * s
For an M/M/1 system, the formulas are simply these:
F(1,p) = p/(1-p)
T_w = ps/(1-p)
T_q = T_w + s = s/(1-p)
Note that as p tends to 1 from below, all these expressions go to
infinity. In the particular case p = 5/6 and s as above:
T_q = (1/5) hour = 12 minutes
What I like about the "stretch factor" F(n,p) is that it is non-
dimensional (a "pure" number, it has no units), as are its arguments
n and p. It provides a fairly clean basis for comparison between
the two queuing systems, M/M/1 and M/M/5, having equal capacity
and facing equal demand.
Let's first "recalibrate" our definitions for the M/M/5 case. We
now assume five servers, each of which can handle an average of 6
customers per hour. So now the average length of time required to
actually serve a customer is five times longer than before:
s = (1/6) hour = 10 minutes
In terms of capacity for work, this is exactly offset by having five
servers. The M/M/5 system can process five customers "in parallel"
so 5 per 10 minutes is still 30 customers per hour. Therefore if we
have actually an average of 25 customers per hour arriving, the
utilization is still 25/30 = 5/6.
The corresponding formula for the stretch factor is more complicated,
and we shall not attempt a detailed derivation but only refer to the
reference notes cited above:
[SUM (np)^k/k! FOR k = 0 to n-1]
K(n,p) = --------------------------------
[SUM (np)^k/k! FOR k = 0 to n]
1 - K(n,p)
C(n,p) = --------------
1 - p*K(n,p)
F(n,p) = C/[n(1-p)]
with T_w = F(n,p) * s and T_q = [1 + F(n,p)] * s like before.
It remains only to evaluate these with n = 5, p = 5/6:
K(5,5/6) = 0.79038602027555444608087190400487...
C(5,5/6) = 0.61408249747371373199293960367961...
F(5,5/6) = 0.73689899696845647839152752441553...
and thus, in the final comparison:
T_q = 17.369 minutes (approx.)
Thus a single fast server would produce shorter average times in
the system for the customer in this case, namely 12 minutes for the
M/M/1 queue system versus roughly 17.369 minutes for the M/M/5 queue
system of equal capacity. The customers would spend slightly more
time waiting in line with the single-server queue, but this delay is
more than made up by the rapid service once the front of the queue
has been reached.
A longer discussion of queuing theory formulas and their applications
may be found here:
[Queuing Analysis]
(see esp. 4.5 Single-Server Queues and 4.5 Multi-Server Queues)
http://www.site.uottawa.ca/~jyzhao/courses/ceg4183/ch04_ceg4183.pdf
Note in particular that the expression K(n,p) is called the Poisson
ratio function, while C(n,p) is the Erlang C function. The latter
has an interesting interpretation as the probability that all servers
are busy. Thus for a single server queue C(1,p) = p.
regards, mathtalk-ga
Search Strategy
Keywords: "Poisson process"
://www.google.com/search?hl=en&lr=&ie=UTF-8&oe=UTF-8&q=%22Poisson+process%22&btnG=Google+Search
Keywords: "queuing theory" markovian utilization waiting
://www.google.com/search?hl=en&ie=UTF-8&oe=UTF-8&q=%22queuing+theory%22+markovian+utilization+waiting&btnG=Google+Search
Keywords: "queuing theory" "M/M/n" utilization waiting
://www.google.com/search?hl=en&ie=UTF-8&oe=UTF-8&q=%22queuing+theory%22+%22M%2FM%2Fn%22+utilization+waiting&btnG=Google+Search |
