Uvod v teorijo čakanja

Teorija čakalnih vrst je matematični študij čakalnih vrst ali čakanje v vrsticah. Čakalne vrste vsebujejo kupci (ali "predmeti"), kot so ljudje, predmeti ali informacije. Čakalne vrste se oblikujejo, če je omejenih virov za zagotavljanje storitev. Na primer, če je v trgovini z živili 5 blagajn, bodo nastale čakalne vrste, če več kot 5 strank hkrati želi plačati svoje izdelke.

Osnovno čakalni sistem je sestavljen iz postopka prihoda (kako stranke pridejo v čakalno vrsto, koliko strank je prisotnih v skupaj), čakalno vrsto, postopek storitve za spremljanje teh strank in odhode iz sistem.

Matematični čakalni modeli se pogosto uporabljajo v programski opremi in podjetju za določitev najboljšega načina uporabe omejenih virov. Modeli iz čakalnih vrst lahko odgovorijo na vprašanja, kot so: Kolikšna je verjetnost, da bo stranka čakala 10 minut v vrsti? Kolikšen je povprečni čas čakanja na stranko?

Naslednje situacije so primeri, kako je mogoče uporabiti teorijo čakalnih vrst:

• Čakanje v vrsti v banki ali trgovini
instagram viewer
• Čakanje, da predstavnik klicne stranke odgovori na klic, ko je klic zadržan
• Čakam, da pride vlak
• Čakanje, da računalnik opravi nalogo ali se odzove
• Čakanje na avtomatizirano avtopralnico za čiščenje linije avtomobilov

Modeli čakalnih vrst analizirajo, kako stranke (vključno z ljudmi, predmeti in informacijami) prejmejo storitev. Čakalni sistem vsebuje:

• Postopek prihoda. Postopek prihoda je preprosto, kako pridejo stranke. Lahko pridejo v čakalno vrsto samo ali v skupinah in lahko pridejo v določenih intervalih ali naključno.
• Obnašanje. Kako se stranke obnašajo, ko so na vrsti? Nekateri so morda pripravljeni počakati na svoje mesto v čakalni vrsti; drugi lahko postanejo nestrpni in odidejo. Drugi pa se lahko odločijo, da se bodo pozneje ponovno priključili čakalni vrsti, na primer, ko bodo zadržani s storitvijo za stranke in se bodo odločili poklicati nazaj v upanju, da bodo prejeli hitrejšo storitev.
• Kako servisirajo stranke. To vključuje dolžino servisa stranke, število strežnikov, ki so na voljo strankam, ne glede na to, ali se strankam postreže ena po ena ali v šaržah, in vrstni red, v katerem so stranke servisirane servisna disciplina.
• Službena disciplina se nanaša na pravilo, po katerem je izbrana naslednja stranka. Čeprav številni maloprodajni scenariji uporabljajo pravilo "prvi pride, prvi streže", lahko druge situacije zahtevajo druge vrste storitev. Strankam lahko na primer postrežejo po vrstnem redu ali glede na število izdelkov, ki jih potrebujejo za servisiranje (na primer na hitrem pasu v trgovini z živili). Včasih bodo najprej postregli zadnjo stranko, ki je prišla (na primer v kupu umazanih posod, kjer bo prva oprana).
• Čakalnica. Število strank, ki lahko čakajo v čakalni vrsti, je lahko omejeno glede na razpoložljivi prostor.

Kendallova notacija je skrajšan zapis, ki določa parametre osnovnega modela čakalnih vrst. Kendall-ova nota je napisana v obliki A / S / c / B / N / D, kjer vsaka črka pomeni različne parametre.

• Izraz opisuje, kdaj kupci pridejo v čakalno vrsto - zlasti čas med prihodi ali časi medsebojnega prihoda. Matematično ta parameter določa porazdelitev verjetnosti da sledijo časi medsebojnih prihodov. Ena pogosta porazdelitev verjetnosti, uporabljena za izraz A, je Poissonova porazdelitev.
• Izraz S opisuje, kako dolgo traja servisiranje stranke, ko zapusti čakalno vrsto. Matematično ta parameter določa porazdelitev verjetnosti, ki je ta servisni časi slediti. Poissonova distribucija se pogosto uporablja tudi za izraz S.
• Izraz c določa število strežnikov v sistemu čakanja. Model predvideva, da so vsi strežniki v sistemu enaki, zato jih je mogoče opisati z zgornjim izrazom S.
• Izraz B določa skupno število elementov, ki so lahko v sistemu, in vključuje predmete, ki so še v čakalni vrsti, in tiste, ki jih servisirate. Čeprav ima veliko sistemov v resničnem svetu omejeno zmogljivost, je model lažje analizirati, če se ta zmogljivost šteje za neskončno. Če je zmogljivost sistema dovolj velika, se običajno domneva, da je sistem neskončen.
• Izraz N določa skupno število potencialnih strank - tj. Število strank, ki bi lahko kdaj stopile v čakalni sistem - in ki se lahko štejejo za končne ali neskončne.
• Izraz D določa servisno disciplino sistema čakalnih vrst, na primer prvi-prvi-serviran ali zadnji-v-prvi.

Mali zakon, kar je prvi dokazal matematik John Little, navaja, da je lahko povprečno število elementov v čakalni vrsti izračunano z množenjem povprečne hitrosti, s katero predmeti prispejo v sistem, in povprečno količino, ki jo vnesejo preživite v njej.

• V matematičnem zapisu je maličev zakon: L = λW
• L je povprečno število elementov, λ je povprečna stopnja prispevkov elementov iz čakalnega sistema, W pa povprečna količina časa, ki ga predmeti preživijo v čakalnem sistemu.
• Little's zakon predvideva, da je sistem v stanju mirujočega stanja - matematične spremenljivke, ki označujejo sistem, se sčasoma ne spreminjajo.

Čeprav zakon Little potrebuje le tri vložke, je povsem splošen in ga je mogoče uporabiti za številne čakalnih sistemov, ne glede na vrsto elementov v čakalni vrsti ali način obdelave elementov v čakalna vrsta. Majhna zakonodaja je lahko koristna za analizo uspešnosti čakalne vrste v določenem času ali za hitro merjenje uspešnosti čakalne vrste.

Na primer: čevljarska družba želi ugotoviti povprečno število škatel za shranjevanje čevljev, ki so shranjene v skladišču. Podjetje ve, da je povprečna stopnja prispelih škatel v skladišče 1.000 škatel za shranjevanje na leto in da je povprečen čas, ki ga preživijo v skladišču, približno 3 mesece ali ¼ na leto. Tako je povprečno število škatel za shranjevanje v skladišču izraženo s (1000 škatel za čevlje na leto) x (¼ leto), ali 250 škatel za čevlje.

• Teorija čakalnih vrst je matematični študij čakalnih vrst ali čakanja v vrsticah.
• Čakalne vrste vsebujejo »kupce«, kot so ljudje, predmeti ali informacije. Čakalne vrste se oblikujejo, če je za zagotavljanje storitve omejenih virov.
• Teorijo čakalnih vrst lahko uporabimo v situacijah, od čakanja v vrsti v trgovini, do čakanja, da računalnik opravi nalogo. Pogosto se uporablja v programski opremi in poslovnih aplikacijah za določitev najboljšega načina uporabe omejenih virov.
• Kendallova nota se lahko uporabi za določitev parametrov sistema čakalnih vrst.
• Zakon Little je preprost, a splošen izraz, ki lahko hitro oceni povprečno število elementov v čakalni vrsti.

• Beasley, J. E. "Teorija čakalnih vrst."
• Boxma, O. J. "Stohastično modeliranje zmogljivosti." 2008
• Lilja, D. Merjenje zmogljivosti računalnika: Vodnik za praktikante, 2005.
• Little, J. in Graves, S. "Poglavje 5: Mali zakon." V Zgradba Intuicija: Vpogled v osnovne modele in načela upravljanja operacij. Springer Science + Business Media, 2008.
• Mulholland, B. "Mali zakon: Kako analizirati svoje procese (s prikrilnimi bombniki)."Process.st, 2017.