Management Science Chapter 11 pp507 520
Management Science Chapter 11 pp507 520
Management Science Chapter 11 pp507 520
::,i
CONTENTS
1I.1 STRUCTURE OFA WAITING 11.4 SOME GENERAL
LINE SYSTEM RELATIONSHIPS FOR \\ : -'
Single-Server Waiting Line LINE MODELS
Distribution of Arrivals 11.5 ECONOMIC ANALYSIS t:
Distribution of Service Times WAITINGLINES
Queue Discipline
11.6 OTHER WAITING LINE
Steady-State Operation
MODELS
I1.2 SINGLE.SERVER WAITING
11.7 SINGLE-SERVETI WAITD" -
LINEMODELWITH LINE MODEL WITH POIS'
POISSON ARRIVALS AND
EXPONENTIAL SERVICE
ARRIVALS AND ARBITR] i
SERVICE TIMES
TIMES
Operating Characteristics i. : -".'
Operati ng Characteri stics
M/GIIModel
Operating Characteristics for the
Constant Service Times
Burger Dome Problem
Managers' Use of Waiting Line 11.8 MULTIPLE-SERVER IICI] :.-
Models WITH POISSON ARRN 1-:
Improving the Waiting Line ARBITRARY SERVICE T.]. :
Operation AND NO WAITING LI\E
Excel Solution of Waiting Line Operating Characteristic' : - .'
Model M/G/k Model with Bio; r.. :
Customers Cleared
11.:1 MULTIPLE-SERVER
WAITING LINE MODEL WITH 11.9 WAITING LINE MODELS
POISSON ARRIVALS AND WITH FINITE CALLING
EXPONENTIAL SERVICE TIMES POPULATIONS
Operati ng Characteristics Operating Characieristic. : -
Operating Characteristics for the M/Mll Model with a Fir,::.
Burger Dome Problem Calling Population
l*r-j
T::l'i"'l:Hil:::..}1:1""*:'J,""T1["":",i:,'Hfrf,J#il;:"$1il*:ff
:*ffi
"l;':il*ir#i*Id'*,"'s*fi
,ffi ::':,-:
L.li.*:;l'::,i$is:::,ffi
to determine wavs
t9 kSen -11#H;rriuno uno make better
decisions
;l;;r;;r;;ed developed to help
mana-
Models have been
'-ttdlry#:::f*rum*"dlii:i
concerningtr,"op"'utio''i;;;"fi
AT CITIBANK*
ATMWAITING TIMES
U S^'^:itibankinC
as averase nu 1be1 :t :,-T:"J:;':;:":1' #tlTtl
franchise :l line. average.ti.Tt .? lTi
The New York City Each .urtom., hut
*o': :;";'";io-u*rtine"""n-s' probabilitv ,n"t ^.iirrr!
operates teller and the il;;;;todetermine, the
t""t"t'pto"J"""ln"-o' ryt:-1y'T*tc to wait wou[ fe]1 ::ffir;il';t eact' banking
of performing a variety to rec'
"
.,.'*rd terrti'it"p^tle number of AIMs
machines
et t"111' a waiting
':-i is of banking t'"t#i"' "f1 customers who
center. -rusv Midtown Manhattan
t: )n iin" is to'm"Jil' t*i"J' "*"ing For examPle' "l:,Ti'.#';f" 172 .ur,o*.,.
' J ATY'
" f,k
of the center had
seek service at one number T.i:l:
,.;;; o..or.'"totwaiting line
rn oto"t tJ'*itt"
- a""i'ion" r.|er hour. A multlpte-sErYi'"'^.' tn
tt'ra
'o1-th" center
banking showed that 88%
of AIMs ,"'i"'" " selectedinformation about lllo.i'** 'x ervrt
locations' t;;;;;;t nee-ded
ser- .l1l: ::- :l; .:i'l T'it::
H;;;;;; -"'ldbetwee
ootential *#;; ilt and general-customer
characteristics such
age Yaittime
waiti'i'j'i:lt';';;;;;i (continuefi
'ic''
5*S Choprer I 'l Woiring Line Models
of
waiting line model, we consicter the waiting
a
tr,: 5
I::llX':*""0.":1.^1*y"s B urgei Dome
vYaLurE L-f
*.
s hambr.s*;,
*:^"":"?:::-f:, }:*::r:rant. "w"u
; l;;;;;;?;.";,r".,"i,i1,. _,
1eu
""r"br.g... _'
iil 1T Burger Dome would; ttk"
f :::::ll ^11*, Alrhough shakes,as "h
;;r";;;;;;;#;;;;--
*XY:::ions. ,;
Thus, customers wait in line to place and receive
their orders.
Burger Dome is concerned that the methods currently
used to serve custor:- i:
resulting in excessive waiting times and a possibre
loss oi sales. Managemenr-.,._-
conduct a waiting rine stuoy to help determine
the best approach to ."0u.. wairi:: _ - n
and improve service.
s,
,h: Burger Dome resrauraniis served U! a sugre order_fili
:H,T::,"^l,1lig placement,
l3l.l1l1,:l "'*er u,r payment, il ;";;"dd.'ffiJ;"ffi:"l;,,-;
:fl:: :Y.l:"n be served ;@;r).^*, ffi ;,*tl,ri!lir?; #T#?:: ili'i. ;
Iinp i" .1'^,-,-
line is shown :- Di ^----- i i r
in Figure
;iil ;;.d ;;;ffi ;":,'*JJl" - *
I 1. I .
System
If*ffir
I
:
I
Customer *+
i
tf\,
,'-\ /*\
lLl
i:{ \--,'}{ \*-/}f LJ
^ r--, ll -*ffi
\r
Arrivals
I
i
I
Waiting Line
}
I ll
oraernttins
i i Customer
I
it;
:
Leaves
I
! after 0rder
t
Is Filled
!!
qfiQ
I
'l
.l Structure of o Woiiing Line System
we cannot
situations, the arrivals occvr randomly and independently of other arrivals, and
predict when an arrival will occur. In such cases, analysts have found that the Poisson
probability distribution provides a good description of the arrival pattern.
time
The poisson probabiliiy function provides the probability of x arrivals in a specific
period. the probability function is as follows:l
where
x : the number of arrivals in the time period
), : the mean ntmber of arrivals per time period
e :2;71828
The mean number of arrivals per time period, tr, is called the arrival rate. Values of
e-^
can be found using a calculator or by using Appendix C'
that
Suppose that Burger Dome analyzed data on customer arrivals and concluded
period, the arrival rate would
the arrival rate is 45 customers per hour. For a one-minute
be .tr : 45 customers + 60 minutes : 0.75 customers per minute. Thus, we
can use the
following Poisson probability function to compute the probability of r customer arrivals
during a one-minute Period:
TirT-!:^il:r-:T-:Fa:-:i:::::':-:ll-:T:t ::;-1---li:: ::T'::---TT1T iT,,iXTIrTT::-:- ::i:e--:*:^ :f-:: ::*l
zs
p(0) : ::lfti-:e'0.75:0.4124
16.75;ou-o
-o.zs
P(l) :
16.751r"
: o"7se-0'15 : 0'1s(0l724) : 0'3543
?
1s (o.s62s)(0.4124)
t0.7 512 e-o
P(2): :0.1329
"
The probability of nO customers in a one-minute period is 0.4724, the probability of one
customer in a one-minute period is 0.3543, and the probability of two customers
in a one-
minute period is O.I32g. Table 11.1 shows the Poisson probabilities for customer arrivals
during a one-minute Period.
The waiting line models that will be presented in Sections 11.2 and 11 .3 use the Poisson
probability distribution to describe the customer arrivals at Burger Dome' In practice, you
should record the actual number of arrivals per time period for several days or weeks
Poisson
and compare the frequency distribution of the observed number of arrivals to the
probabilily distribution to determine whether lhe Poisson probability distribution provides
a reasonable approximation of the arrival distribution'
rThe term xl, xfactorial, is defined os x! : x(x- 1)(x - 2) . . . {2)(1). For exomple, 4l : (4)(3)(2)(l) = 24. For the
l')!
ol the qetrii'i' trrlrc\
Inpractice.youshouldcollectdataonactualservicetimcs.todecl,ej]nine\\llcl1.}t|thu
ir r r.u'onubi"'"pp'"*'*''ion
exponenrial probability disirilu,ion
your aPPlication'
,i*tp p"tlod Jt
Waiting un'operation'
",
svstem reaches ,n"'l'"'*' of a waiting line'
"tuav't'ut"
sieady-state op"'utiuJ"nJ'u"ioit'i"t
j { i:5 ' :'' =
H*ilTfflx.TH:f:J#:?'.;!iLir',iHtf,"#l$,*.ffi;Iffi
;;u",'; ;;1""1, 0.':l"1ol','ir::T""t:H;,lJf,'.ooi, ,o nuyluseti i. c'-'tct'nt'tL
rn';r:iing tri rc
trr.e
can be
nrobabilitY distribufior Jt.i *.. ,1"-* [lin'tn*urus
,"'rlo,"" manageme0t rvith holpitrl
nroblem inlroduced
characteristic, uni
.io, provide
: .-,te models are R,,,n", Dome,s operating titarrti-
' ::.il on assumPtiotls
?oisson arrit'als
;JJ:;,";*; *f:::ff:[loo,o*-';*used to-derive the rormula" l"]-'n' orrc'i.rtrrls
05 - qi
The mathematlcal
nential sen'ice
s f w aiti g ;:::'::t"J'L li l":I[:] ],I : l:
',;1en
-
\pphing
:ne model, dota
anY teri st i c o
" "
orovide the rheoretrcal
"'"*' n
:H:
developmen' :l:11.:i:i;i.r*"it""'"orut operating 'h'tl1rcter:stir
can provros il;;;;;;;' (,[ rhc lr)r ilrula'
"
been developed
: -. collected on the il;;;;;"ihave deveroprnenr
. -: jsltmptions of the
-.e reasonable'
:# ffittn,$:. x,:x:"'::
1Jig*er*tBxeg LlEa:tgactu:r-?sti*s erating crr*Lacrerislii:s
|:'nU'\. \\h-."
*"J:.,1"#::.1""H]ilf;*:;l"fJ:,::fi'#J[;ff:1'1x'..^fi';.,i.:
per time period 1the"
a'rival rarej
of arrivals
I : the mean number
per tirne period
(the service rale)
p: the mean numbe'
of *it"'
rtiilillfr
;rl* Chopter I I Woiiing Line Models
T&*tS Tx. X POISSON PROBABILITIES FoR THE NUMBER oF CUSTOMER ARRI\ 1., ,:
where
p. : the mean number of units that can be served per time period
e :2.71828
' The mean number
of units that can be served per time period, p, is called the seryice p&u
Suppose that Burger Dome studied the order-filling process and found that a i -: I
employee can process an average of 60 customer orders per hour. on a one-minute :,:
the service rate would be p : 60 customers + 60 minutes : I customer per r.: "
-',
A property of the exponen- For example, with p, : 1, we can use equation (11.3) to compute probabilities S:-r r
t i al p rob ab il ity di s tributi on
the probability that an order can be processed in 1/2 minute or less, 1 minute or le..
is that there is a 0.63.21 -:-.
2 minutes or less. These computations are
probability that the random
variable takes on a value
less than its mean. In wait- P(servicetime < 0.5 min.) : 1- e-1(0s) : 1 - 0.6065 : 0.393_<
ing line applications, the P(servicetime < l.0min.) - 1- r*t(1.0) : I - 03679: 0.6321
exp one ntial p ro b ab ility
distribution indic ate s that P(servicetime < 2.0min.) - 1- e-1(2.0) : 1 - 0.1353 : 0.g6+-
approximately 63Vo of the Thus, we would conclude that there is a 0.3935 probability that an order can be prG-;,
service times are less than
in 1/2 minute or less, ao.632l probability trat it can be processed in I minute or 1ess. ,-,:",,-_
the mean sentice time and
approximately 379o of the 0.864'l probability that it can be processed in 2 minutes or less.
service times are greater In several waiting line models presented in this chapter, we assume that the :, -
than the mean sen)ice time. ability distribution for the service time follows an exponential probability distribr-: r
:
5r? Chopter 'l 1 Woiting Line Models
Equatians (1 1.4) through l. The probability that no units are in the system:
( 1 1.10) do not provide
,3
4. The average time a unit spends in the waiting line: rI
Thevaluesofthearrivalratelandtheserviceratepareclearlyimportantcomponents
(11.9) shows.that the ratio of the
in determining the operating characteristics. Equation unit has to wait
probability that an
arrival rate to the ,**i*.uti ,\/p, provides the lnving
to as the utilization factor fot
because the service f""iii, i; ;';;. Hence, ,\/p is referred
the service facilitY.
(11.4) through (11'10) are
The operating characteristics presented in equations
applicableonlywhentheserviceratep"iss.reallrthanthearrivalratetr-inotherwords,
the waiting line will continue to grow with-
when tr/p < 1. If this condition does not eiist,
not have sufficient capacity to handle the arriving
out limit because the service facility does
(11'10)' we must have p)
units. Thus, in using equations (t 1'+) through
'1"
w:wc,+f;:z+ ! : 1
4 minutes
rw
r 0.75 : O.75
p 1
Equation(11.10)canbeusedtodeterminetheprobabilityofanynumberofcustomers
inthesystem.ApplyingthisequationprovidestheprobabilityinformationinTablell'2.
.EA*E.*t:.STHEPRoBABILITYoFnCUSToMERSINTHESYSTEMFoRTHEBURGER"
DOME WAITING LINE PROBLEM
,,i ririlltlilililllill
5i4 Chopter I I Woiring Line Models
;; il;;;the il ; .
;iiil:T::Ttr'::.:Yl1-':9:n"to;-p.oi.,r,"",ui,ing1irreoperation.Tabil
0.1335 probability rhar seven or more
.urro,o"rJi. ,;t"'i"fi:"5:1.:.
;;";J;;,t# :;;H;#,::i. ,,
r,ier,'p'"i"ulity
some Ii:::TYX_,::[i:",',
.:,*: long {-o,,
waiting lines if it continu",
that Burger Dome
'' ,
&'
t service rate bv making a creative
H:fi:rl: design change or b.,
- :-
Add one or more servers so that
more customers can be served
simulr--,
P.robability of no customers
in the system
Average number of cusromers 0.400
initJ ,"uiilrg rir.
Average number of customers 0.900
..'-
in the syste#
urslvul
Average fime in rhe waiting 1.500
Average time in the svstem
f;- 1.200 minr:::",
Probability that an arriving customer has to 2.000 mini,:=.
Probability that seven or more wait 0.600
custorners are in the system
0.02s
service Times 5I 5
1 I .2 Singleserver woiting Line Model with Poisson Arrivols ond Exponentiol
have im-
The information in Table 11.3 indicates that all operating characteristics
time a customer
proved because of the increased service rate. In particular, the
average
and the average time a
ip"no, in the waiting line has been reduced from 3 to 1.2 minutes,
4 to 2 minutes. Are any other alter-
customer spends in the system has been reduced from
service rate? If so' and if the
natives available that Burger Dome can use to increase the
equations (11'4) through (11' 10)
mean service rate p caflbe identified for each alternative,
the revised operating characteristics and any improvements
in
;;ru;r;d;;#;t" be compared to the
change can
the waiting line system. The added cosi of any proposed
the proposed
service improvements to help the manager determine whether
: .s \ou "o11"rponiirg
service improvements are worthwhile'
. available is to add one
lether a As mentioned previously in Alternative 2, another option often
,,. .€n'ice rate simultaneously' The
,. or more servers so that orders for multiple customers can be filled
model to the multiple-server waiting line model
:,mpany's
,:i .for its extension of the single-server waiting lini
is the topic of the next section.
WAITING LINE
: WORKSHEET FOR THE BURGER DOME SINGLE-SERVER
riiiiXiiiiriirii
Sinsle-Server Waiting Line Model
Assumptions
Poisson ArriYals
iH,l,,{ n**ti"i service Times
senice Rate I
ODeratins Characteristics
ffi
I
::i* Chopter 1 1 Woiting Line Models
values is on the right. The arrival rate and the service rate are entered in cej-, :
The formulas for the waiting line's operating characteristics are placed in celr. _
The worksheet computes the same values for the operating characteristics rh.: , :
earlier. Modiflcations in the waiting line design can be evaluated by enre::: ,
arrival rates and/or service rates into cells 87 and 88. The new operating ; .
of the waiting line will be shown immediately. The Excel worksheet in Fr;--:
template that can be used with any single-server waiting line model with pc:, -
and exponential service times.
The assumption that arrivals follow a pois- the system should be able to r.-' ,
arrivals will follow an exponential probability ing times even when the sen'rce ::-:
distribution, with a mean time between arrivals the arrival rate. A contribution c,: ;,
of 1/2e or 0.05 hour.
) Many individuals believe
that whenever the
models is that they can point o.: _:
waiting line operating chara;:.- :
k
service rate trr, is greater than the arrival rate ),, when the g, > ,[ condition appe-: ] -.
A multiple-server waiting line consists of two or more seryers that are i>:*r;:
identical in terms of service capability. For multiple-server systems, there j:: -,
cal queueing possibilities: (l) arriving customers wait in a single waiting L:r
"pooled" or "shared" queue) and then move to the first available server foi
--
or (2) each server has a "dedicated" queue and an arriving customer selecls c.:,.
lines to join (and typically is not allowed to switch lines). In this chapter, ri e ::,_
-
system design with a single shared waiting line for all servers. operating ci:-- :
for a multiple-server system are typically better when a single shared queue. .-:,-"::
multiple dedicated waiting lines, is used. The single-server Burger Dome oper.:- r ".:
iilllilil
1I '3 Multipl+serverWoiting Line Modelwith Poisson Arrivols ond Exponentiolservice Times j II
FISURE T }"S THE BURGER DOME TWO-SERVER WAITING LINE
System
!r
Customer
ffi,iffi ffi
Waiting Line
Leaves
After Order
Is Filled
-**
i=fi:3H,::,ff.H*7::H,
l. The probability that no units are in the system:
Po= :{}.t,ti}
p,W;94{(,H
l. The average number of units in the waiting line:
(i/p)kip
to:1t:ffil4',ro
r _
{'i1.,1}i
{:tr.t:t 3i
Chopter
'l Woiting Line Models
:iH 1
Lo
Wn:
i
5. The average time a unit spends in the system:
,-:*(i)(#h),.
?. The probability of n units in the system:
r,; $1$i'
nt.
,u f-bf ,t s'&
i-
n.
.Y
{ti
i,t ::irltl,rll.lli'r::
: i:1:r! r'::lrr:r,
Alu\'
P*: toi+:>r[
T)FTPo
To illustrate the multiple-server waiting line model, we return to the Burger-'\ l': 'nu
wants to e
fast-food restaurant waiting line problem. Suppose that management
!rir'
TABTE I I
, "4 VALUES OF PO FOR MULIIPLE.SERVER wAITING LINES wITH PoISSoN
ARRIVALS AND EXPONENTIAL SERVICE TIMES
:
we use equations (l 1.1 1) through ( I r. 1g) for the k 2-sewer system. For an
arrival
:
rate of .tr 0.75 customers per minute and a service rate of p,:
1 customer per minute for
each server, we obtain the operating characteristics:
L: Lr+
i: 0.tz2i. :g.1'tzjcusromer
T
wq:
L,: 0.1227
: 0.1636 minute
T 0.75
I
w: wq* v: 0.1636 +
1
I
1.1636 minures
Try Problem lSfor practice using equations (11.17) and (l1.lg), we can compute the probabiiities
in determining the operat- of r: :_;,;
the system. The results from these computations are summarized
ing characteristics for a in Table l tr :
ttvo - s erv er w aiting line.
we can now compare the steady-state operating characteristics of the :..
system to the operating characteristics of the original single-server system i..5..;
Sectron \\ 2.
i. The average time a customer spends in the system (waiting time plus s-
-
is reduced from I4z : 4 minutes to I4l : 1.1636 minutes.
2. The average number of customers in the waiting line is reduced from I =
customers to In :
0.1227 customers.
3. The ayeruge time a customer spends in the waiting line is
Wq: 3 minutes to Wr: 0.1636 minutes.
4. The probability that a customer has to wait for service is reduced
to P* : 0.2045.
clearly the two-server system will substantially improve the operating chri.:y:,*
tics of the waiting line' The waiting line study provides ihe ope.atin! characteris::
mM1
can be anticipated under three configurations: the originat single-server system.
i ,,r*1r,t
server system with the design change involving direct submission of paper order :.-:
ur
kitchen, and a two-server system composed of two order-filling employees. After ; _ r. .*rrr
ing these results, what action would you recommend? In thisiase, Burger Dome , - -nuryi
the following policy statement: For periods when customer arrivals are expected
ic : :::jluun,
45 customers per hour, Burger Dome wil open two order-processing servers ;,..: rilmil,
employee assigned to each.
By changing the arrival rate I to reflect arrival rates at different times of the
then computing the operating characteristics, Burger Dome's management can
rrilril