Transcript document

DECISION MODELING WITH
MICROSOFT EXCEL
Chapter 15
QUEUING
Part 2
Copyright 2001
Prentice Hall Publishers and
Ardith E. Baker
MODEL 2: A FINITE QUEUE
(WATS LINES)
In this model, we attempt to select the appropriate
number of _______lines for St. Luke’s.
The telephone company can provide a great deal of
_______in these matters, since queuing models
have found extensive use in the field of _________
traffic engineering.
This problem is typically attacked by using the
_______model, “with blocked customers cleared.”
This is a _____________queue with s servers,
exponential interarrival times for the calls and a
general distribution for the ______________(length
of call).
“Blocked customers cleared” means that when an
_______finds all of the servers __________(all of the
lines busy), he or she does not get in a queue but
simply________.
Probability of j Busy Servers The problem of
selecting the appropriate number of _____(servers)
is attacked by computing the steady-state
______________that exactly j lines will be busy.
This will be used to calculate the steady-state
probability that all s _______are busy.
Clearly, if you have s lines and they are all busy, the
next _________will not be able to place a call.
The steady-state probability that there are exactly j
busy ________ given that s lines (servers) are
available is:
j /j!
(l/m)
P=
j
s
S
(l/m)k /k!
k=0
where l = _______rate (the rate at which calls arrive)
1/m = mean _______time (the average length of
a conversation)
s = number of _________(lines)
This expression is called the ____________Poisson
distribution or the ________loss distribution.
The value of Pj depends only on the _______of this
distribution.
Consider a system in which
l = 1 (calls arrive at the rate of 1 per minute)
1/m = 10 (the average length of a conversation
is 10 minutes)
Here, l/m = 10. Suppose there are five lines in the
system (s = 5) and we want to find the steady-state
probability that exactly two are busy (j = 2).
2 /2!
(l/m)
P2 = 5
(l/m)k /k!
S
k=0
2 /2•1
(10)
P2 =
1 + 101/1 + 102/2•1 + 103/3•2•1 + 104/4•3•2•1 + 105/5•4•3•2•1
P2 =
50
= 0.034
1477.67
On the average, two lines would
be busy 3.4% of the time.
An ___________way of obtaining Pj that is easy to
implement in a spreadsheet is as follows:
Pi = Pi-1 (l/m)/i
So, for example, once we know P2, we can ________
P3 as:
P3 = P2(10)/3
= (0.034)(10)/3
= 0.1133
Likewise, P4 is found as:
P4 = P3(10)/4
= (0.1133)(10)/4
= 0.2833
Each _________Pi-1 is multiplied by (l/m) and divided
by i to achieve the new Pi.
The more interesting question is: “What is the
___________that all of the lines are busy?” since in
this case, a potential caller would not be able to
place a call on the _______lines.
To find the answer to this question, we simply set
______(in our example s = 5) and we obtain
P5 = P4(10)/5
= (0.2833)(10)/5
= 0.564
Or on the average the system is totally _________
56.4% of the time.
Using the spreadsheet, the probability that a
customer _______with 5 servers is easily calculated.
We can then build a data table to determine this
probability for different _________of s.
Enter the values for s, ranging from 0 to 10.
Specify the formula (= F13) for the quantity that we
want to track (the prob. that a customer balks).
Highlight the
cell range
B22:C33
and click
Data – Table.
Specify $E$4 as the Column
Input and click OK.
Column D calculates the __________improvement in
this probability as servers are added.
It is clear that the marginal effect of adding more
servers__________.
Average Number of Busy Servers This quantity is
called the__________. If we define N as the average
number of busy servers, then
N = (l/m)(1 – Prob. that a customer will balk)
Assume for this model, l = 1 and 1/m = 10.
Thus, if 10 lines are_________, the probability that
all 10 are busy is 0.215 (from previous table).
It follows then that
N = (10)(1 – 0.215) = 7.85
After finding N, the server ____________can be
calculated by dividing N by s (the number of
servers). Thus, 7.85/10 = 78.5%. Each server is
busy 78.5% of the time and ______21.5% of the time.
MODEL 3: THE
REPAIRPERSON MODEL
Now we must decide how many repairpersons to
hire to _________20 pieces of electronic equipment.
Machines are _________on a first-come, first-served
basis and a _______repairperson treats each broken
machine.
The failed machines form a ________in front of the
multiple servers (repairpersons).
This is an ______model, but it differs from the bloodtesting model in that there is a _______number of
items (20) that can join the queue.
Queuing models in which only a ________number of
“people” are eligible to join the queue is said to have
a finite_______________________.
Models with an ______________number of possible
participants are said to have an __________calling
population.
Consider the model with 20 machines and 2 repairpersons. Assume that
when a machine is running, the time between
______________has an exponential distribution
with parameter l = 0.25 per hour.
Thus, the average ____between breakdowns is
1/l = 4 hours.
The time it takes to ______a machine has an
exponential distribution and the _______repair
time (1/m) is 0.50 hour.
This model is an M/M/2 model with a ____________of
18 items in the ______and a finite calling population.
In this case, the general equations for the steadystate probability that there are _______in the system
is a function of l, m, s, and N (the number of
_____________).
N!
Pn =
(l/m)n P0
n!(N – n)!
for 0 < n < s
N!
(l/m)n P0
(N – n)!s!sn-s
for s < n < N
Pn =
N
We also know that
SP
n=0
n=
1
We thus have N + 1 ________equations in the N + 1
variables of interest (P0, P1, …, Pn).
Although_____________, this makes it possible to
calculate values of Pn for any particular model.
There are, however, no simple ____________for the
expected number of jobs (broken machines) in the
system or for___________.
If the values for Pn are computed, then it is a simple
task to find a _____________value for the expected
number in the system. You must just calculate:
N
expected number in system = L =
S nP
n=0
n
A spreadsheet can be used to compute values of Pn.
NOTE: when you enter the value for the arrival rate
(l) in the “MMs” worksheet, you need to enter N*l
(the entire population’s arrival rate).
TRANSIENT vs STEADY-STATE
RESULTS: ORDER PROMISING
In this section, we will consider a situation in which
we are interested in the _________(not steady-state)
behavior of the system.
_____________processes can be viewed as complex
queuing systems.
In fact, queuing systems __________is probably the
most frequently used management science tool in
manufacturing.
SONOROLA company is concerned about when to
________a new customer order. The order is for 20
units of an item that requires __________processing
at 2 work stations.
The average _______to process a unit at each work
station is 4 hours. Each work station is ________for
8 hours every working day.
By considering when the last of the 20 units will be
___________, it is estimated that it will take 10.5
days to process the order.
The last unit must wait at Work Station 1 for the first
19 units to be completed, then it must be
_________at Work Station 1, then at Work Station 2.
Assuming that it does not have to wait when it gets
to Work station 2, we can calculate the following:
(10 units x 4 hrs/unit + 4 hrs + 4 hrs)  8 hrs/day = 10.5 days
However, this analysis is somewhat___________. It
ignores the ___________of the processing times and
the possibility of queuing at Work Station 2.
The 4-hour _____________time at each work station
was arrived at by __________many processing times
that were less than 4 hours with a few processing
times that were significantly ________than 4 hours
(due to equipment failures at a work station while
processing a unit).
Next, check to see whether the _____________of the
basic queuing model are met.
The output from Work Station 1 are the _________to
Work Station 2, and the time between arrivals is
_____________because the processing time at Work
Station 1 is exponential.
The service time at Work Station 2 is ___________
because it is the same as the ______________time.
The units are processed on a_________, first-served
basis at Work Station 2 and there is sufficient _____
capacity between the work stations so that the
queue size is_________.
However, the __________of an infinite time horizon
is not met. We are only interested in the ________of
the system until “________” 20 ends its processing.
Let’s apply the basic model anyway and use it as an
_________________.
The time it takes to process 20 units is
approximated as follows:
1. The last unit in the batch of 20 is estimated to
leave Work Station 1 after 20 x 4 = 80 hours.
2. This unit will then wait in the _______in front
of Work Station 2.
3. Finally, it will ________processing at Work
Station 2, at which time all 20 units will have
been completed.
The total time that the last unit spends at Work
Station 2 is W. Thus, our __________is 20 x 4 x W.
Remember, for the basic model, W = 1/(m – l), for
m > l.
The problem is that m and l are ______(1 unit per 4
hours).
A spreadsheet can be used to simulate the ______of
the 20 units through the 2 work stations.
Assume that raw material is always ____________at
Work Station 1 so that the next unit at Work station 1
can start as soon as the ___________unit is finished.
This means that for Work Station 1, the start time of
a unit is the __________of the previous unit.
The start time of a unit at Work station 2 is either the
stop time of ________on Work Station 1 or the stop
time of the previous unit on Work Station 2,
whichever is________.
The stop time of a unit is just the ____________plus
the _____________time. The finish time in days is
calculated by dividing the stop time at Work Station
2 of the last unit by the number of___________.
The finish time is calculated to be 10.5 days if every
unit takes exactly 4 hours at every work station.
To analyze the impact of __________time variability,
replace the _________processing time of 4 at Work
Station 1 in the spreadsheet with the appropriate
________distribution (exponential with a mean of 4).
In @RISK, enter =RiskExpon($B$1) to make the
_______time a random variable.
We would like to know the 99th ___________of this
random variable so that we could then promise the
order in that number of days and be _____sure that
it would actually be _____________on time.
The following @RISK output shows the 99th
percentile for cell F2 (the finish time in days) based
on 1000 sets of 40 random processing times.
To be 99% sure of having the order completed by the
_________date, set the due date to be 18.28 days
after the material becomes ____________at Work
Station 1.
The ____________that takes place at Work Station 2
has increased the _________(time from the start of
the order to its completion) by nearly 8 days
(18.28 – 10.5) over what it would be if there were no
__________in the processing times.
Here is a histogram of the finish time. Note that the
time can vary from 6.5 days up to 21 days.
THE ROLE OF THE
EXPONENTIAL DISTRIBUTION
The role of the ___________distribution in ________
queuing models is useful in understanding the use
of queuing models.
Most analytic results for queuing situations involve
the exponential distribution either as the distribution
of ___________times or service times or both.
The following three properties help to identify the
set of _______________in which it is reasonable to
assume that an exponential distribution will______.
1. _______________: In an arrival process, this
property implies that the ____________that an
________will occur in the next few minutes is
not influenced by when the last arrival
occurred.
This situation arises when
(a) there are many ___________who could
potentially arrive at the system
(b) each person decides to arrive
_____________of the other individuals
(c) each individual selects his or her time
of arrival completely at_________
2. ___________________: With an exponential
distribution, small values of the ________time
are common (as shown below).
Prob S<t
1.0
0.632
10
20
30
40
t
This graph shows the _____________that the
service time S is less than or equal to t if the
________service time is 10.
The graph showed that more than 63% of the
service times were _________than the average
service time (10).
Compare this to the ___________distribution
where only 50% of the service times are
___________than the average.
The practical implication is that an
exponential distribution can best be used to
model the distribution of _______________in a
system in which a large proportion of “jobs”
take a very ___________and only a few “jobs”
run for a long time.
3. Relation to the __________________: While
introducing the_____________, a relationship
between the exponential and Poisson
distributions was noted.
In particular, if the time between arrivals has
an ___________distribution with parameter l,
then in a specified period of time (say, T) the
number of arrivals will have a ___________
distribution with parameter lT.
Then, if X is the number of arrivals during the
time T, the probability that X equals a specific
number (say, n) is given by the equation
-lT(lT)n
e
Prob [X = n] =
n!
For any _____________integer value of n.
The _____________between the exponential and the
Poisson distributions plays an important role in the
theoretical ______________of queuing theory.
It also has an important practical________________.
By comparing the number of _______that arrive for
service during a specific period of time with the
number that the Poisson distribution_____________,
the manager is able to see if his or her choices of a
model and ____________values for the arrival
process are reasonable.
QUEUE DISCIPLINE
In addition to the _________distribution, service
distribution and number of servers, the queue
__________must also be specified to define a
queuing system.
So far, we have always assumed that arrivals were
served on a first-come, first-serve basis (often called
__________, for “first-in, first-out”).
However, this may not always be the case. For
example, in an elevator, the last person in is often
the first out (___________).
Adding the possibility of selecting a ________queue
discipline makes the queuing models more
____________.
These models are referred to as __________models.