數(shù)據(jù)、模型與決策(運(yùn)籌學(xué))課后習(xí)題和案例答案1

CHAPTER14

QUEUEINGMODELS

ReviewQuestions

14.1-1Customersmightbevehicles,machines,orotheritems.

14.1-2Itmightbeacrewofpeopleworkingtogether,amachine,avehicle,oranelectronicdevice.

14.1-3Meanarrivalrate=1/(meaninterarrivaltime).

14.1-4

14.1-5Themeanequalsthestandarddeviationoftheexponentialdistribution.

14.1-6Havingrandomarrivalsmeansthatarrivaltimesarecompletelyunpredictableinthesense

thatthechanceofanarrivalinthenextminutealwaysisjustthesameasforanyother

minute.Theonlydistributionofinterarrivaltimesthatfitshavingrandomarrivalsisthe

exponentialdistribution.

14.1-7Thenumberofcustomersinthequeueisthenumberofcustomerswaitingforserviceto

begin.Thenumberofcustomersinthesystemisthenumberinthequeueplusthenumber

currentlybeingserved.

14.1-8Queueingmodelsconventionallyassumethatthequeueisaninfinitequeueandthatthe

queuedisciplineisfirstcomefirstserved.

14.1-9Meanservicetime=1/(meanservicerate).

14.1-10Fortheexponentialdistribution,thestandarddeviationequalsthemean.Forthedegenerate

distribution,thestandarddeviationequalszero.FortheErlangdistribution,thestandard

deviation=—^(mean).

14.1-11Thethreepartsofalabelforqueueingmodelsprovideinformationonthedistributionof

servicetimes,thenumberofservers,andthedistributionofinterarrivaltimes.

14.2-1Incommercialservicesystems,outsidecustomersreceiveservicefromcommercial

organizations.Manyexamplesarepossible.

14-1

14.2-2Ininternalservicesystems,thecustomersreceivingserviceareinternaltotheorganization.

Manyexamplesarepossible.

14.2-3Intransportationservicesystems,eitherthecustomersortheserversarevehicles.Many

examplesarepossible.

14.3-1Whenthecustomersareinternaltotheorganizationprovidingtheservice,itismore

importanthowmanycustomerstypicallyarewaitinginthequeueingsystem.

14.3-2Commercialservicesystemstendtoplaceagreaterimportanceonhowlongcustomers

typicallyhavetowait.

14.3-3L=expectednumberofcustomersinthesystem

Lq=expectednumberofcustomersinthequeue

W=expectedwaitingtimeinthesystem

%=expectedwaitingtimeinthequeue

14.3-4Aqueueingsystemisinasteadystateconditionifitisinitsnormalconditionafteroperating

forsometime.

14.3-5W=%+(1/R)

14.3-6L=2lVandLq=ZWq

14.3-7L=Lq+(2///)

14.3-8Steady-stateprobabilitiescanalsobeusedasmeasuresofperformance.

14.4-1EachTechRepshouldbeassignedenoughmachinessothattheTechRepwillbeactive

repairingmachinesapproximately75%ofthetime.

14.4-2Theissueistheincreasednumberofcomplaintsaboutintolerablewaitsfbrrepairsonthe

newcopier.

14.4-3TheaveragewaitingtimeofcustomersbeforetheTechRepbeginsthetriptothecustomer

sitetorepairthemachineshouldnotexceedtwohours.

14.4-4Fouralternativeapproacheshavebeensuggested.

14.4-5AteamofmanagementscientistandJohnPhixittwillanalyzetheseapproaches.

14.4-6ThemachinesneedingrepairarethecustomersandtheTechRepsaretheservers.

14.5-12=expectednumberofarrivalsperunittime

〃=expectednumberofservicecompletionsperunittime

(1/2)=expectedinterarrivaltime

(1///)=expectedservicetime

p-utilizationfactor

14.5-2(1)Interarrivaltimeshaveanexponentialdistributionwithameanof(IM);(2)servicetimes

haveanexponentialdistributionwithameanof(I///);(3)thequeueingsystemhas1server.

14.5-3FormulasareavailableforL,W,%,Lq,Pn,P(W>t),andP(Wq=0).

14.5-4p<1

14-2

14.5-5Theaveragewaitingtimeuntilservicebeginsis6hours.

14.5-6Itwouldcostapproximately$300millionannually.

14.5-7TheM/G/lmodeldiffersintheassumptionaboutservicetime.Inthismodeltheservice

timescanhaveanyprobabilitydistribution.Itisnotevennecessarytodeterminetheformof

thisdistribution.Itisonlynecessarytoestimatethemeanandstandarddeviationofthe

distribution.

14.5-8TheM/D/lmodelassumesadegenerateservice-timedistribution.TheM/Ek/1model

assumesanErlangdistributionwithshapeparameterk.

14.5-9DecreasingthestandarddeviationdecreasesLq,L,W,and%

14.5-10Thetotaladditionalcostisaone-timecostofapproximately$500million.

14.6-1p=2/(s〃)whichistheaveragefractionoftimethatindividualserversarebeingutilized

servingcustomers.

14.6-2p<1

14.6-3Explicitformulasareavailableforallthemeasuresofperformanceconsideredfbrthe

M/M/lmodel.

14.6-4Threeterritoriesneedtobecombinedinordertosatisfythenewservicestandard.

14.6-5TheM/M/smodelhasagreatamountofvariabilityinservicetimes.TheM/D/smodelhas

novariability.TheM/Ek/smodelprovidesamiddlegroundbetweentheothertwowith

somevariabilityinservicetimes.

14.7-1Whenusingpriorities,moreimportantcustomersareservedaheadofotherswhohave

waitedlonger.

14.7-2Withnonpreemptivepriorities,onceaserverhasbegunservingacustomer,theservicemust

becompletedwithoutinterruptionevenifahigherprioritycustomerarriveswhilethis

serviceisinprocess.Withpreemptivepriorities,thelowestprioritycustomerbeingservedis

ejectedbackintothequeuewheneverahigherprioritycustomerentersthequeueingsystem.

14.7-3Exceptforusingpreemptivepriorities,theassumptionsarethesameasfortheM/M/lmodel.

14.7-4Exceptfbrusingnonpreemptivepriorities,theassumptionsarethesameasfortheM/M/s

model.

14.7-5p<1

14.7-6Priorityclass1consistsofprinter-copiersandpriorityclass2consistsofallothermachines.

14.7-7Two-personterritorieswouldbeneededtoreducewaitingtimestoacceptablelevels.

14.7-8Managementdecidedtochangetotwo-personterritories,withprioritygiventotheprinter-

copiersforrepairs.

14.8-1Givingarelativelyhighutilizationfactortotheserverprovidessurprisinglypoormeasures

ofperformanceforthesystem.

14.8-2Aspisincreasedabove0.9,LqandLgrowastronomically.

14-3

14.8-3Decreasingthevariabilityofservicetimesimprovestheperformanceofasingle-server

queueingsystemsubstantially.

14.8-4Cuttingthevariabilityofservicetimesinhalfprovidesmostoftheimprovementfrom

completelyeliminatingthevariability.

14.8-5Combiningseparatesingle-serverqueueingsystemsintoonemultiple-serverqueueing

systemgreatlyimprovesthemeasuresofperformance.

14.8-6Applyingprioritieswhenselectingcustomerstobeginservicecangreatlyimprovethe

measuresofperformanceforhigh-prioritycustomers.

14.8-7Applyingpreemptiveprioritiesimprovesthemeasuresofperformanceforcustomersinthe

toppriorityclassevenmorethanapplyingnonpreemptivepriorities.

14.9-1Whenchoosingthenumberofserversthereisatradeoffbetweenthecostoftheserversand

theamountofwaitingbythecustomers.

14.9-2Makingone'sownemployeeswaitcauseslostproductivity,whichresultsinlostprofit

whichisthewaitingcost.

14.9-3WaitingCost=CwLwhereCwisthewaitingcostperunittimeforeachcustomerinthe

queueingsystem,andListheexpectednumberofcustomersinthequeueingsystem.

14.9-4Arelativelyhighutilizationfactorfortheserversinaqueueingsystemcanactuallybemore

costlyandthereforenotadvisable.

14.10-1Previousone-personterritorieswerereplacedbylargerthree-personterritories.

14.10-2Queueingmodelswereusedtofindtheminimumnumberofserversthatwouldprovide

satisfactorymeasuresofperformanceforthequeueingsystem.

14.10-3Decisionsneededtobemadeonthenumberoftelephonetrunklines,telephoneagents,and

holdpositions.

14.10-4Thecity'sarresteeswerethecustomersinNewYorkCity.

14.10-5Morethan$750millioninannualprofitswereobtainedbythebusinesscustomersofAT&T.

14.10-6Aspecialkindofqueueingsystemwherethecustomers(theprinterstobeassembled)go

throughaseriesofservers(assemblyoperations)inafixedsequence.

Problems

14.1a)Ahospitalemergencyroomisaqueueingsystemwithpatientsasthecustomersandcare

providersastheservers.

b)Thequeueisthewaitingroomanditwouldoperateonapriorityprocedure.

c)Arrivalswouldberandomsincearrivaltimesarecompletelyunpredictable.

d)Theservicetimesinthiscontextwouldbetheamountoftimeittakesforapatientto

receivecare,whichwouldbehighlyvariable.

14.2

14-4

customerserver

a)shopperscheckoutclerk

b)firesfirefighters/firetrucks

c)carstollcollectors

d)bikesbicyclerepairpeople

e)shipslongshoremen/docks

0machinesoperator

g)loadshandlingequipment

h)cloggedpipesplumber

i)customorderscustomizedprocess

j)employeessecretary

14.3a)True.Theonlydistributionofinterarrivaltimesthatfitshavingrandomarrivalsisthe

exponentialdistribution.

b)False.Theprobabilityofanarrivalinthenextminuteiscompletelyuninfluencedbywhen

thelastarrivaloccurred.

c)True.Mostqueueingmodelsassumethattheformoftheprobabilitydistributionof

interarrivaltimesisanexponentialdistribution.

14.4a)False.Dependingonthenatureofthequeueingsystem,theexponentialdistributioncan

provideeitherareasonableapproximationoragrossdistortionofthetrueservice-time

distribution.

b)False.Themeanandstandarddeviationarealwaysequal.

c)True.Theexponentialanddegeneratedistributionsrepresenttworatherextremecases

regardingtheamountofvariabilityintheservicetimes.

14.5a)False.Thequeueiswherecustomerswaitbeforebeingserved.

b)False.Queueingmodelsconventionallyassumethatthequeueisaninfinitequeue.

c)True.Themostcommonisfirst-come-first-served.

14.6a)Abankisaqueueingsystemwithpeopleasthecustomers,andtellersastheservers.

b)%=1minute

%+(l/〃)=1+2=3minutes

Lq=AWq=(40/60perminute)(1minute)=0.667customers

L=AW=(40/60customersperminute)(3minutes)=2customers

14.7a)Aparkinglotisaqueueingsystemforprovidingparkingwithcarsasthecustomers,and

parkingspacesastheservers.Theservicetimeistheamountoftimeacarspendsina

space.Thequeuecapacityis0.

b)L=OP。+IP1+2尸2+3P3=0(0.2)+1(0.3)+2(0.3)+3(0.2)=1.5cars

Lq=0cars

W=L/A=1.5/2=0.75hours

Wq=Lq/2=0/2=0hours

14-5

c)Acarspendsanaverageof45minutesinaparkingspace.

14.8a)L=0(1/16)+1(4/16)+2(6/16)+3(4/16)+4(1/16)=2,whichrepresentstheaverage

numberofcustomersintheshop,includingthosegettingtheirhaircut.

b)

n#inqueueprobabilityproduct

00

10

20

310.250.25

420.06250.125

Lq=0.375whichrepresentstheaveragenumberofcustomersintheshopwaitingtogeta

haircut.

c)W=Lt九-2/4=0.5hours=30minutes

%=Lq//=0.375/4=0.094hours=5.625minutes

Thesequantitiesmeanthatcustomerswillbeintheshopanaverageofhalfanhour,

includingthetimetogetahaircut,andwillhavetowaitanaverageof5.625minutes

beforetheirhaircutwillbegin.

d)W-Wq=().5-0.094=0.406hours=24.375minutes

14.9Theutilizationfactorprepresentsthefractionoftimethattheserverisbusy.Theserveris

busyexceptwhentherearezeropeopleinthesystem.P()istheprobabilityofhaving0

customersinthesystem.Hence,p=1-P().

14.10a)L-勿(4-/1)=30/(40-30)=3customers

l/(//-2)=1/(40-30)=0.1hours

%=〃[;/(〃-團(tuán)]=30/[40(40-30)]=0.075hours

Lq=4%=30(0.075)=2.25customers

Po=l-p=1-0.75=0.25

Pi=(l-p)p=(1-0.75)(0.75)=0.188

2

P2=Q-M=(l-0.75)(0.75)=0.141

Thereisa1-PO-P1-P2=1-0.25-0.188-0.141=42%chanceofhavingmorethan2

customersatthecheckoutstand.

14-6

b)(M/M/lmodel)

BCDEGH

3DataResults

4X=30(meanarrivalrate)L=3

5P二40(meanservicerate)Lq=2.25

6s=1(#servers)

7W=0.1

8Pr(W>t)=4.54E-05Wq=0.075

9whent=1

10P=0.75

11Prob(Wq>t)=3.405E-05

12whent=1nPn

1300.25

1410.1875

1520.140625

c)L=A/(//-2)=30/(60-30)=1customer

W==1/(60-30)=0.033hours

%=W-孫=30/[60(60-30)]=0.017hours

Lq==30(0.017)=0.5customers

Po=l-p=1-0.75=0.5

Pi=(l-p)p=(1-0.75)(0.75)=0.25

P2=Q-M=(1-0.75)(0.75)2=0.125

ThereisaX-P^P^-P^=1-0.5-0.25-0.125=12.5%chanceofhavingmorethan2

customersatthecheckoutstand.

d)(M/M/smodel)

BCDEGH

3DataResults

4A.=30(meanarrivalrate)L=1

5N=60(meanservicerate)Lq=0.5

6s=1(#servers)

7W=0.03333

8Pr(W>t)=9.3576E-14wq=0.01667

9whent=1

10p=0.5

11Prob(Wq>t)=4.6788E-14

12whent=1nPn

1300.5

1410.25

1520.125

e)Themanagershouldadoptthenewapproachofaddinganotherpersontobagthegroceries.

14-7

14.11a)Pa=\-p=1-0.5=0.5

Pi=(l-p)p=(l-0.5)(0.5)=0.25

2

P2=(l-p)/r=(l-0.5)(0.5)=0.125

3

P3=(1-9=(l-0.5)(0.5)=0.0625

4

P4=(l-p)/=(l-0.5)(0.5)=0.03125

PO+P1+P2+P3+P4=O.5+O.25+O.125+O.O625+O.O3125=O.96875or96.875%ofthetime.

b)96.875%ofthetimetherearefewerthan4inthesystem.(M/M71model)

BCDEGHI

3DataResults

4X=2(meanarrivalrate)L=1

5p=4(meanservicerate)Lq=0.5

6s=1(#servers)

7w=0.5

8Pr(W>t)=0.13533528Wq=0.25

9whent=1

10P=0.5

11Prob(Wq>t)=0.06766764

12whent=1nPnCumulative

1300.50.5

1410.250.75

1520.1250.875

1630.06250.9375

1740.031250.96875

14.12a)Tractor-trailertrain(M/M/lmodel):

BCDEGHI

3DataResults

4X=4(meanarrivalrate)L=4

55(meanservicerate)Lq=3.2

6S=1(#servers)

7w=1

8Pr(W>t)=0.36787944Wq=0.8

9whent=1

10P=0.8

11Prob(Wq>t)=0.29430355

12whent=1nPnCumulative

1300.20.2

1410.160.36

1520.1280.488

1630.10240.5904

1740.081920.67232

Thetraindoesnotmeetanyofthecriteria.Theaveragetimeismorethanhalf-an-hour(W

=1hour),itisnomorethananhourlessthan80%ofthetime(Pr(W>1)=36.8%),and

therearethreeloadsorfewerlessthan80%ofthetime(尸0+P1+P2+尸3+P4=67.2%).

14-8

b)Forklifttruck(M/M/smodel):

BCDEGHI

3DataResults

4X=4(meanarrivalrate)L=1.5

56.66666667(meanservicerate)J=0.9

6S=1(#servers)

7W=0.37500

8Pr(W>t)=0.06948345Wq=0.22500

9whent=1

10P二0.6

11Prob(Wq>t)=0.04169007

12whent=1nPnCumulative

1300.40.4

1410.240.64

1520.1440.784

1630.08640.8704

1740.051840.92224

Theforklifttruckmeetsallthecriteria.Theaveragetimeislessthanhairan-hour(W=

0.375hours),itisnomorethananhourmorethan80%ofthetime(Pr(W>1)=6.9%),

andtherearethreeloadsorfewermorethan80%ofthetime(尸0+P1+P2+P3+&=92.2%).

c)Tractor-trailertrain:L($20)+$50=(4)($20)+$50=$130/hour

Forklifttruck:L($20)+$150=(1.5)($20)+$150=$18()/hour

d)Whiletheforklifttruckhashigheroverallcosts,itdoesabetterjobofmeetingthe

additionalcriteria.

14.132=Z7W=8/120=0.0667perminute

〃=1/W+4=1/120+0.0667=0.075perminute

(M/M/lmodel)

BCDEGH

3DataResults

4X=0.06666667(meanarrivalrate)L=8

50.075(meanservicerate)q=7.111111111

6s=1(#servers)

7w=120

8Pr(W>t)=0.99170129Wq=106.6666667

9whent=1

10p二0.888888889

11Prob(Wq>t)=0.88151226

12whent=1nPn

1300.111111111

14.14a)Thecustomersaretruckstobeloadedorunloadedandtheserversarethecrews.The

systemcurrentlyhas1server.

14-9

b)4membercrew(M/M/lmodel):

BCDEGH

3DataResults

4X=1(meanarrivalrate)L=0.333333333

54(meanservicerate)q=0.083333333

6s=1(#servers)

7w=0.33333

8Pr(W>t)=0.04978707wq=0.08333

9whent=1

10p=0.25

11Prob(Wq>t)=0.01244677

12whent=1nPn

1300.75

c)3membercrew(M/M/lmodel):

BCDEGH

3DataResults

4X=1(meanarrivalrate)L=0.5

5N=3(meanservicerate)L=0.166666667

6S=1(#servers)

7w=0.5

8Pr(W>t)=0.13533528wq=0.166666667

9whent=1

10p=0.333333333

11Prob(Wq>t)=0.04511176

12whent=1nPn

1300.666666667

d)2membercrew(M/M/lmodel):

BCDEGH

3DataResults

4九=1(meanarrivalrate)L=1

52(meanservicerate)q=0.5

6s=1(#servers)

7w=1

8Pr(W>t)=|0.36787944wq=0.5

9whent=1

10p=0.5

11Prob(Wq>t)=|0.18393972

12whent=1nPn

13I00.5

e)Aonepersonteamshouldnotbeconsideredsincethatwouldleadtoautilizationfactorof

p=1whichdoesnotenabletheqeueuingsystemtoreachasteady-stateconditionwitha

manageableloadfortheteam.

14-10

f&g)Totalcost=($20)(#oncrew)+($30)(Lq)

TC(4members)=($20)(4)+($30)(0.0833)=$82.50/hour

TC(3members)=($20)(3)+($30)(0.167)=$65/hour

TC(2members)=($20)(2)+($30)(0.5)=$55/hour

Acrewof2peoplewillminimizetheexpectedtotalcostperhour.

14.15a)1/R=1minute(M/M/lmodel):

BCDEGH

3DataResults

4X=0.5(meanarrivalrate)L=1

5尸1(meanservicerate)Lq=0.5

6s=1(#servers)

7W=2

8Pr(W>t)=0.082085Wq=1

9whent=5

10P=0.5

11Prob(Wq>t)=0.0410425

12w