Järjekorrateooria simulaator (M/M/1)

saabumis- ja teenindusintensiivsus ning järjekorra stabiilsus

Näidisarvutus — Järjekorrateooria simulaator (M/M/1)

Koormatus ρ	0,750
L-i M/M/1 ennustus	3,000
Tegelik saabumissagedus	3,0084
Keskmine aeg süsteemis W	1,012
Little'i seaduse ennustus L	3,045
Ajas keskmistatud L	3,044
Erinevus kahe viimase vahel	0,0006
Loendatud L-i standardviga	0,121

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

rho-kuristik 🖖

Valem L = ρ/(1−ρ) ei kasva sujuvalt. Sel on vertikaalne asümptoot kohal ρ = 1. Koormatuse nihkumisel 90% juurest 99% peale hüppab keskmine järjekorra pikkus 9 inimeselt 99-le ning täpselt läbilaskevõime piiril on see tõkestamata. See ongi „rho-kuristik“. 80% ja 85% koormatusega järjekorrad tunduvad peaaegu identsed, kuid viies koormatuse 95% peale, ooteajad paisuvad. Valemis W = 1/(μ−λ) on nimelt sama singulaarsus – nimetaja kahaneb nulli suunas, mitte lugeja ei kasva. Seepärast on reaalsed süsteemid nagu kõnekeskused ja haiglate erakorralise meditsiini osakonnad teadlikult varustatud töötama tunduvalt alla 100% piiri. See ülemises otsas asuv näiliselt raisatud vaba puhver hoiabki teid kuristikku langemast.

järjekorra tekitab juhuslikkus 🖖

Lühendis M/M/1 tähistavad kaks M-tähte sõna "Markovi": saabumised toimuvad juhuslikult (Poissoni jaotus) ja teenindusajad varieeruvad juhuslikult (eksponentsiaaljaotus) läbi ühe serveri. Põhiidee on üllatav. Järjekord võib tekkida isegi siis, kui server on keskmiselt kiirem klientide saabumisest. Kui kõik ilmuksid kohale kellavärgi täpsusega ja iga töö võtaks sama kaua aega, ei moodustuks vaba ressurssiga serveri taha kunagi saba. Ootamine tuleneb varieeruvusest, mitte ülekoormusest. Seadke λ väärtus tunduvalt allapoole μ väärtust ja järjekord tekib ja kaob ikkagi. Pannes mõlemad mustrid kellavärgi peale, ei lahku ülaltoodud graafik kunagi 0 ja 1 vahelt. Identsete vahede ja identsete tööde korral on server igal ühest väiksemal koormatusel alati enne järgmise kliendi saabumist lõpetanud.

Little'i seadus nõuab peaaegu eimiskit 🖖

Siin näidatud L ja W ei ole sõltumatud. Need rahuldavad tingimust L = λW ja samuti Lq = λWq. See samasus ei eelda peaaegu midagi. John Little tõestas selle 1961. aastal ja see vajab vaid järgmist: pikaajaline saabumisintensiivsus eksisteerib ja on lõplik ning samuti eksisteerib pikaajaline keskmine süsteemis viibimise aeg. Ei mingeid Poissoni saabumisi, eksponentsiaalset teenindust, sõltumatust, ühte serverit ega isegi jaotuse püsiseisundit. Ülaltoodud tabelist näete, mida see väärt on. Sisestage kumba tahes voogu kellavärgi või puhanguline muster ja valem ρ/(1−ρ) annab ühel juhul neli korda liiga suure ning teisel juhul viisteist korda liiga väikese tulemuse. Samal ajal püsivad λW ja sõltumatult loendatud L kõigi 405 läbitud seadistuse puhul üksteisest 0,011 kliendi kaugusel. Sama seos kehtib haiglapalatis, tehase poolelioleva toodangu ja kaupluse laovaru puhul. Keskmine sisu võrdub saabumisintensiivsuse ja sees veedetud keskmise aja korrutisega.

kaks keskmist, millest vaid üks kuulub kliendile 🖖

Seadke mõlemad mustrid kellavärgi peale ja lugege kahte tabelirida teineteise vastu. Järjekord, mille saabuv klient eest leiab, on 0,000. Vaatleja, kes sama järjekorda ajas loendab, saab tulemuseks 0,751. Iga klient siseneb tühja süsteemi. Server on hõivatud kolmveerand ajast. Mõlemad on õiged, sest L kaalub järjekorra pikkust aja järgi, samas kui saabuja vaade kaalub seda kliendi järgi. Mitte miski ei sunni kahte erinevat kaalumist kokku langema. Little'i seadus seob ajakeskmise kliendikeskmisega ega väidagi, et nad kattuvad. Poissoni saabumiste puhul langevad need kokku ja seepärast ongi seda erinevust lihtne märkamata jätta. Saabumine on igal hetkel võrdselt tõenäoline, seega kliendi vaade on kella aus valim. See on PASTA omadus, mis kuulub pigem saabumistele kui järjekorrale. Muutke saabumised puhanguliseks ja sama jooks annab kellakeskmise 21,482 vastu tulemuseks 27,011, sest puhang on aeg, mil saabub enamik kliente ja samas on saba kõige pikem.

Ülesanded täielikult lahendatud

Järjekord, kus on 3 saabumist tunnis ja 20% kasv 5 sammu
Kliendid saabuvad sagedusega 3 korda tunnis ja server teenindab 4 klienti tunnis. Server on neljandiku ajast jõude, mis kõlab mugavalt. Arvutage, milline järjekord sellest tekib ja seejärel, mida teeb sellega saabumiste 20% kasv.
1. Ahel on tasakaalus. Iga oleku sisenev voog võrdub väljuva vooga, mis annab Pₙ = (1 − ρ)ρⁿ. See on geomeetriline jaotus üle järjekorra pikkuse, kus ρ on serveri hõivatuse ajaosa. Siin ρ = 0,75.
  
  $P_{n} = (1 - ρ) ρ^{n}, ρ = \frac{λ}{μ} = \frac{3}{4} = 0.750$
2. Selle jaotuse keskväärtus on ρ/(1 − ρ). Vaadake, mis on nimetajas. Seal pole mitte vaba läbilaskevõime klientides tunnis, vaid vaba osa. Keskmiselt kolm inimest süsteemis serverist, mis on neljandiku päevast jõude.
  
  $L = n \geq 0 \sum n P_{n} = \frac{ρ}{1 - ρ} = \frac{0.750}{0.250} = 3.000$
3. Lahutage teenindatav klient, kes on kohal tõenäosusega ρ, ja ootama jääb 2,25 klienti.
  
  $L_{q} = L - ρ = 3.000 - 0.750 = 2.250$
4. Little'i seadus muudab populatsiooni ajaks ega vaja üldse eeldusi jaotuse kohta. Keskmine süsteemis viibijate arv on saabumisintensiivsuse ja süsteemis veedetud keskmise aja korrutis. Üks tund süsteemis, millest 45 minutit möödub järjekorras töö nimel, mille tegemiseks kulub 15 minutit.
  
  $W = \frac{L}{λ} = \frac{3.000}{3} = 1.000, W_{q} = \frac{L _{q}}{λ} = 0.750$
5. Nüüd tõstke λ väärtusele 3,6. Koormatus läheb 0,75 juurest 0,90 peale. See on 20% rohkem tööd ja ρ/(1 − ρ) kasvab 3 pealt 9 peale.
  
  $λ = 3.6 : ρ = 0.90, L = 9; λ = 3.96 : ρ = 0.99, L = 99$
Vastus

Tööriist trükib 75% koormatuse juures L = 3,000, L_q = 2,250, W = 1,000, W_q = 0,750. Õppetund peitub valemi ρ/(1 − ρ) nimetajas. Järjekorra suurust ei määra teie vaba ressursi hulk, vaid see, kui palju teil seda murdosana järel on. See murdosa ongi see, mida te koormuse lisamisel kulutate. Kakskümmend protsenti rohkem saabumisi kolmekordistab järjekorra. Veel 10% sinna otsa, kus ρ = 0,99, teeb selleks 99. Seepärast varisevadki haiglad, kiirteed ja kettakontrollerid suure koormatuse all kokku, selle asemel et sujuvalt aeglustuda. Fraas „meil on kasutusel vaid 90% läbilaskevõimest“ ei paku seega nii palju kindlustunnet, kui see kõlab.

$L = \frac{ρ}{1 - ρ} blows up at ρ = 1 : + 20% λ ⟹ \times 3 queue$
Samad intensiivsused ilma juhuslikkuseta 5 sammu
Hoidke λ = 3 korda tunnis ja μ = 4 korda tunnis ning eemaldage igasugune juhuslikkus. Saabumised on täpselt kahekümne minuti tagant, iga töö võtab täpselt viisteist minutit. Koormatus on endiselt 0,750. Arvutage tekkiv järjekord ja vaadake, kui kaugel on ρ/(1 − ρ) sellest.

Ava see ülesanne tööriistas
1. Klient k saabub hetkel k/λ ja lahkub vaba serveri korral hetkel k/λ + 1/μ. Järgmine klient saabub hetkel (k + 1)/λ. Server lõpetab õigeaegselt alati, kui 1/μ ≤ 1/λ, mis on ümberkirjutatult ρ ≤ 1.
  
  $ρ = \frac{λ}{μ} = \frac{3}{4} = 0.750, \frac{1}{λ} = 0.3333 > \frac{1}{μ} = 0.250$
2. Seega kuni järjekord on stabiilne, ei oota keegi üldse. W_q = 0 ja W on pelgalt teenindusaeg 1/μ = 0,250 tundi. Viisteist minutit hoones, iga viimne kui minut sellest teeninduses.
  
  $\frac{k}{λ} + \frac{1}{μ} \leq \frac{k + 1}{λ} ⟺ \frac{1}{μ} \leq \frac{1}{λ} ⟺ ρ \leq 1 ⟹ W_{q} = 0$
3. Little'i seadus muudab selle populatsiooniks ega vaja selle tegemiseks mingit jaotust. L = λW = 3 × 0,250 = 0,750 ja L_q = 0. Kolmveerand klienti, mis on serveri hõivatuse ajaosa ja ei midagi muud.
  
  $W = \frac{1}{μ} = 0.250, L = λW = 3 \times 0.250 = 0.750, L_{q} = λ W_{q} = 0$
4. Nüüd ρ/(1 − ρ) = 0,750/0,250 = 3,000, mis on neli korda tõest suurem. See tegur pole nende arvude juhuslik kokkusattumus. M/M/1 annab ρ/(1 − ρ), samas kui kellavärk annab ρ, seega ülehindamine on iga koormatuse juures 1/(1 − ρ).
  
  $ρ 0.50 0.75 0.90 0.95 0.99 ρ / (1 - ρ) 1.000 3.000 9.000 19.000 99.000 ρ 0.500 0.750 0.900 0.950 0.990 1/ (1 - ρ) 241020100$
5. Koormatuse ρ = 0,99 juures on see tegur 100. M/M/1 paigutab süsteemi 99 inimest, aga täiesti regulaarne liiklus ainult 0,99.
  
  $\frac{ρ / ( 1 - ρ )}{ρ} = \frac{1}{1 - ρ}; ρ = 0.99 : 99.000 ⟷ 0.990$
Vastus

Tööriist trükib W = 0,250 ja Little'i seadus teeb sellest L = 0,750. See on vastuolus M/M/1 ennustusega 3,000, mis teeb veaks +299,6%. Järjekorda polnudki kunagi. Esimeses infoplokis mainitud ρ-kuristik koosneb täielikult varieeruvusest ning ilma selleta pole ka kohal ρ = 0,99 mingit kuristikku. Väljaspool seda lehekülge annab see tugeva argumendi vastuvõtuaegade kasuks. Nii läbilaskevõime lisamine kui ka varieeruvuse eemaldamine lühendavad järjekorda ja 1/(1 − ρ) ütleb, et teine tasub end kõige enam ära just seal, kus esimest on kõige raskem osta. 75% koormatuse juures vähendab täiesti regulaarne graafik järjekorda neli korda, 99% juures sada korda. Ükski reaalne kliinik ei saavuta kellavärgi täpsust ning samad intensiivsused koos puhanguliste saabumistega annavad tulemuseks hoopis 21,482.

$L_{D / D /1} = ρ = 0.750 ⟷ L_{M / M /1} = \frac{ρ}{1 - ρ} = 3.000, \frac{L _{M / M /1}}{L _{D / D /1}} = \frac{1}{1 - ρ} = 4$

Allikad (1)

Insight block 3 — how little L = λW assumes: J. D. C. Little, "A Proof for the Queuing Formula: L = λW." Operations Research 9(3), 383–387, 1961.

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.