Seuraava artikkeli auttaa sinua: Miten jonoteoriaa voidaan käyttää koneoppimisessa?
Olemme kaikki elämässämme olleet jonoissa joko ostaaksemme päivittäistavaroita lähimmästä supermarketistasi tai nostamassa rahaa pankkiautomaatista. Jos olet rationaalinen ihminen, on täytynyt herätä kysymys: miten nämä organisaatiot laskevat kuinka monta kassatiskiä/pankkiautomaattia pitäisi riittää tehokkaaseen asiakkaiden käsittelyyn? Vastaus tulee kuuluisasta matemaattisesta käsitteestä “The Queuing Theory”. Tässä artikkelissa keskustelemme jonoteorian matemaattisesta muotoilusta syvällisen toiminnan kanssa ja tämän käsitteen soveltamisesta tosielämässä. Näiden ohella yritämme ymmärtää sen soveltuvuutta koneoppimiseen. Tässä artikkelissa käsiteltävät aiheet ovat seuraavat.
Sisällysluettelo
- Lempeä johdatus jonoteoriaan
- Jonoteorian matemaattinen toiminta
- Jonotusmallit
- Jonoteorian sovellukset
Aloitetaan johdannosta jonoteorian käsitteeseen, joka antaa korkean tason yleiskatsauksen tästä käsitteestä.
Lempeä johdatus jonoteoriaan
Jonoteoria keskittyy ymmärtämään, kuinka rivit tai jonot toimivat ja miten niiden tehokkuutta voidaan lisätä. Tässä tutkimuksessa on tiettyjä näkökohtia, kuten ihmisten käyttäytyminen, kun heidän on odotettava ostoksen tekemistä tai palvelun saamista, millainen jonoorganisaatio siirtää ihmisiä rivien läpi tehokkaasti ja myös sen määrittäminen, kuinka monta ihmistä jonossa voidaan käsitellä. tietty aika.
Jonoteoria on pohjimmiltaan kustannusanalyysin työkalu. Suurin osa yrityksistä ei voinut toimia niin, ettei kenenkään asiakkaiden tarvinnut jonottaa, joko siksi, että se olisi kohtuuttoman kallista tai koska heillä ei ole niin paljon asiakkaita.
(GIF-linkki)
Yllä oleva gif on täydellinen esimerkki järjestelmän viasta. Tämän seurauksena yritykset käyttävät jonoteoriaa toiminnan järjestämisessä tavalla, joka tasapainottaa asiakkaiden palvelukustannusten ja jonossa jonotuksen aiheuttaman haitan välillä. Jonoteoriassa on neljä päätekijää, jotka auttavat johtamaan tuloksia:
- Menetelmä, jolla asiakkaat saapuvat jonoon.
- Jonon luonne tarkoittaa, millä tavalla jono toimii.
- Palvelun tarjoamistapa.
- Jonon sijainnista poistumismenetelmä.
Ymmärretään matemaattinen muotoilu, jota tarvitaan yllä olevien vastausten saamiseksi.
Etsitkö täydellistä arkistoa tietotieteessä käytettävistä Python-kirjastoista, katso tästä.
Jonoteorian matemaattinen toiminta
Jonoteoria käyttää todennäköisyysteorian tietoa prosessin eri vaiheiden laskemiseen. Se käyttää pääasiassa eksponentiaalista ja Poissonin todennäköisyysjakaumaa. Katsotaanpa, kuinka jonoteoria hyödyntää näitä todennäköisyyksiä.
Eksponentiaaliset ja Poissonin todennäköisyysjakaumat
Jonoteoriassa eksponentiaalinen jakauma nopeusparametrilla ja eksponentiaalisella satunnaismuuttujalla lasketaan saapumisajalle Poisson-pisteprosessissa. Tämän jakauman avulla voidaan mallintaa asiakkaiden saapumisaikoja tai palveluaikoja useista syistä.
- Eksponentiaalinen funktio on tiukasti laskeva satunnaismuuttujan funktio, mikä tarkoittaa, että saapumisten välinen aika on todennäköisemmin pieni kuin suuri saapumisen jälkeen.
- Eksponentiaalisessa jakaumassa on ominaisuus, joka tunnetaan nimellä “ei muistia”, eli aika seuraavaan saapumiseen ei riipu siitä, kuinka paljon aikaa on jo kulunut. Koska asiakkaiden toiminta on riippumatonta, tämä on intuitiivisesti järkevää mallille, joka mittaa asiakkaiden tuloja.
Poisson-jakauma liittyy eksponentiaaliseen jakaumaan, koska sitä käytetään määrittämään todennäköisyys sille, että tietty määrä saapumisia tapahtuu tietyllä aikakehyksellä.
Kun saapujia ei ole, Poisson-jakauma antaa eksponentiaalisen arvon, joka on yhtä suuri kuin todennäköisyys, että saapumisaika on suurempi kuin eksponentiaalisen jakauman satunnaismuuttuja. Jakson nollan saapumiskertoimet korreloivat tietynpituisen saapumisajan todennäköisyyksien kanssa. Saapumisaika tarkoittaa asiakkaiden saapumisen välistä ajanjaksoa.
Joskus eksponentiaaliset ja Poisson-todennäköisyysjakaumat eivät selitä muuttujien jakautumista selkeästi, jolloin käytetään Erlang-jakaumaa.
Kun eksponentiaalinen jakauma yleistetään, se muodostaa Erlang-jakauman. Satunnaismuuttuja, jota kutsutaan Erlangin satunnaismuuttujaksi, on mitta tietyn tapahtuman ja seuraavan tapahtuman riippumattoman eksponentiaalisen satunnaismuuttujan välisestä ajanjaksosta. Tämä yleistys saadaan aikaan ottamalla eksponentiaalijakaumaan kaksi uutta parametria.
- Shape-parametri yleistää jakauman muodon, jota merkitään “k”
- Skaalausparametri on eksponentiaalisen jakauman nopeusparametrin käänteisluku.
Mutta missä aiomme käyttää näitä todennäköisyysjakaumia? Vastaus on jonon syöttö- ja tulostusprosessin laskemisessa.
Syöttöprosessi
Syöttöprosessi laskee asiakkaiden saapumisen alustamalla jokaisen asiakkaan ajan. Tätä aikaa käytetään sitten edelleen satunnaisriippumattoman muuttujan laskemiseen eksponentiaaliselle funktiolle. Oletetaan, että tietyllä hetkellä ei voi tapahtua enempää kuin yksi saapuminen. Jos useampi kuin yksi saapuminen voi tapahtua tietyllä hetkellä, joukkosaapuminen sallitaan.
Rajallisen lähdemallin tulot otetaan väestöstä ja bulking-malli on sellainen, jossa asiakkaat saapuvat, mutta eivät tule sisään. Eksponentiaalisen jakelun ei-muistitoiminto tulee peliin, koska kunkin asiakkaan toiminta on riippumatonta toisesta.
Tulostusprosessi
Palveluprosessi kuvaa jonojärjestelmän tulostusprosessia. Asiakkaan palveluajan määrittämiseksi määritämme todennäköisyysjakauman. Palvelimia on kaksi järjestelyä, rinnakkain ja sarja.
- Samanaikaisesti, jos kaikki palvelimet tarjoavat samantyyppistä palvelua, asiakkaan tarvitsee kulkea vain yhden palvelimen kautta vastaanottaakseen palvelua.
- Sarjassa asiakkaan tulee kulkea useiden palvelimien läpi saadakseen palvelua.
Tässä prosessissa eksponentiaalinen jakauma ei selitä palveluaikoja tarkasti monia eri palveluvaiheita vaativana palveluna, se vaatii paljon joustavampaa todennäköisyysjakaumaa, minkä vuoksi tässä prosessissa käytetään Erlang-jakaumaa.
Jonotusalat
Jonokuri kuvaa, kuinka saapujat otetaan palveluun. On tavallista, että uusi tulokas sijoitetaan jonon loppuun, eikä sitä palvella ennen kuin kaikki saapujat on käsitelty. Jonotuksen peruslajeja on kolme:
- Ensin tullut-ensin-palvelija -kuri (FCFS) -kuri
- Viimeisenä saapuvaksi palvellaan ensin (LCFS) -kuri
- Palvelu satunnaisessa järjestyksessä (SIRO).
Valitusta kurinalaisuudesta riippuen asiakkaiden odotusajat vaihtelevat merkittävästi. Esimerkiksi kukaan ei halua saapua aikaisin LCFS-alalle. Yleisesti ottaen kurilla ei ole vaikutusta itse jonoon, koska saapujat saavat jatkuvasti palvelua kurinalaisuudesta riippumatta. Jonotus riippuu kahdesta tekijästä.
- Liikenteen intensiteetti ilmaistaan saapuvien keskimääräisenä aikayksikköä kohti, joka on otettu keskimääräiseksi palveluajaksi. Tämä tarjottu kuorma on mitta siitä, mitä asiakkaat haluavat.
- Liikenteen intensiteetin perusteella lasketaan palvelimien lukumäärä kuormaa kohti, jota kutsutaan käyttökertoimeksi
Kendall-Leen merkintä
Kun kaikkien jonon ominaisuuksien kuvaamisesta tulee erittäin sanallista, käytetään paljon yksinkertaisempaa merkintää nimeltä Kendall-Lee.
Kendall-Leen notaatio antaa yhteensä kuusi lyhennettä vinoviivalla kirjoitetuille ominaisuuksille.
- Ensimmäisen ja toisen ominaisuuden todennäköisyysjakaumien perusteella ensimmäinen ja toinen ominaisuus kuvaavat saapumis- ja palveluprosesseja. Ensimmäisen ja toisen ominaisuuden osalta
- M edustaa eksponentiaalista jakaumaa
- E edustaa Erlang-jakaumaa
- G edustaa yleistä jakaumaa
- Kolmas ominaisuus määrittelee samanaikaisesti toimivien palvelimien lukumäärän, joita kutsutaan myös rinnakkaispalvelimiksi.
- Neljäs kuvaa jonokuria sen annetun lyhenteen mukaisesti.
- Viides kuvaa järjestelmään mahtuvien asiakkaiden enimmäismäärää.
- Kuudes on asiakkaiden määrä, joista järjestelmä voi saada ammentaa.
Esimerkiksi pankissa jonomalli esitetään muodossa M/M/5/F CF S/20/, joka voidaan dekoodata eksponentiaalisilla saapumisajoilla, eksponentiaalisilla palveluajoilla, FCFS-jonokurilla ja 20 asiakkaan kokonaiskapasiteetilla, ja ääretön väestöallas, josta ammentaa.
Puhutaanpa erilaisista käytetyistä jonomalleista.
Jonotusmallit
Voimme nyt analysoida erilaisia malleja jonoteorian toimivuuden aiemman tiedon perusteella.
M/M/1/GD/∞/∞ jonojärjestelmä
M/M/1/GD/∞/∞-järjestelmässä on eksponentiaaliset saapumisajat, eksponentiaaliset palveluajat ja yksi palvelin. Tämä järjestelmä voidaan mallintaa syntymän ja kuoleman prosessiksi.
Prosessi, jossa järjestelmän tila millä tahansa aikavälillä on positiivinen kokonaisluku. Tässä prosessissa on kaksi tärkeää todennäköisyyttä, syntymätodennäköisyys ja kuoleman todennäköisyys.
- Syntymätodennäköisyys on todennäköisyys, että saapuminen tapahtuu jonkin aikaa
- Vastaavasti kuoleman todennäköisyys on todennäköisyys, että palvelu valmistuu jonkin aikaa.
Siksi syntymällä ja kuolemalla on samankaltainen merkitys saapumisella ja palvelun päättymisellä. Syntymä lisää tilaa yhdellä, kun taas kuolema vähentää tilaa yhdellä. Siksi näiden kahden todennäköisyyden on oltava toisistaan riippumattomia.
M/M/1/GD/c/∞ jonojärjestelmä
Tällä jonojärjestelmällä on eksponentiaaliset saapumis- ja palveluajat kahdella eri eksponentiaalisella nopeudella λ ja µ vastaavasti. Järjestelmä toimii hyvin samalla tavalla kuin syntymä-kuolema -järjestelmä, paitsi että kun järjestelmässä on “c”-asiakas, ylimääräiset saapujat eivät pääse sisään, eikä niitä sen jälkeen enää lasketa.
Esimerkiksi tyypillinen asiakas ei vaivautuisi jonottamaan pikaruokaravintolassa, jos jonot ovat liian pitkät. Sen sijaan asiakas kävisi toisessa ravintolassa.
M/M/s/GD/∞/∞ jonotusjärjestelmä
Tällä jonojärjestelmällä on eksponentiaaliset saapumis- ja palveluajat kahdella eri eksponentiaalisella nopeudella λ ja µ vastaavasti. Tässä järjestelmässä on ‘s’-palvelimia, jotka ovat valmiita palvelemaan yhtä asiakasriviä, kuten ehkä pankista löytyisi. Jos järjestelmässä olevien asiakkaiden määrä on pienempi kuin palvelimien lukumäärä, palvellaan jokaista asiakasta. Jos asiakkaiden määrä on suurempi kuin järjestelmän palvelimien määrä, niin ”asiakkaita palvellaan ja loput asiakkaat ovat jonossa.
M/G/∞/GD/∞/∞ ja GI/G/∞/GD/∞/∞ jonojärjestelmät
Nämä järjestelmät ovat ainutlaatuisia, sillä niissä on ääretön määrä palvelimia, mikä tarkoittaa, että asiakkaan ei koskaan tarvitse odottaa jonossa palvelun alkamista. Ajattele tätä itsepalveluna, joka on samanlainen kuin verkkokaupoissa.
M/G/s/GD/s/∞ jonotusjärjestelmä
Tässä järjestelmässä, jossa asiakas saapuu ja näkee, että kaikki palvelimet ovat varattuina, asiakas poistuu järjestelmästä kokonaan ilman palveluita. Tässä tapauksessa jonoa ei luoda, ja sanomme, että estetyt asiakkaat on tyhjennetty.
Jonoteorian sovellukset
Jonoteoriaa hyödynnetään useilla toimialoilla, joihin olemme osa jokapäiväistä elämää. Katsotaanpa muutamia suosittuja käyttötapauksia, joiden kautta voimme ymmärtää sen soveltuvuuden koneoppimiseen.
A. Jonoteoriasovellukset odotusajan ennustamisessa
- Jonoteoria asiakaspalvelussa
Asiakaspalvelussa hyödynnetään M/M/S-jonomallia. Tässä mallissa on saapumisaikoja, eksponentiaalisia palveluaikoja ja palvelimia. Täällä asiakkaita kutsutaan soittajiksi, palvelimet ovat puhelinoperaattoreita. Nämä jonot koostuvat soittajista, jotka odottavat, että järjestelmäresurssit palvelevat tilaa.
- Jonoteoria pankkiautomaatissa
Pankkiautomaatissa käytetään M/M/1-jonomallia, jossa asiakkaita palvelevat saapumisajat, eksponentiaalinen palvelu ja yksi palvelin. Täällä palveluaika ja saapumisaika jakautuvat eksponentiaalisesti. Tässä mallissa käytetään yhtä jonoa ja yhtä palvelinta.
- Jonoteoria kirjastohallinnossa
Jonottamisen tarkoituksena kirjastoissa on helpottaa kirjojen, tiskipalveluiden ja liitännäispalvelujen kiertoa. Kirjaston perustehtäviä ovat pinon ylläpito, jäsenhallinta, kirjastoaineiston valinta ja aineiston hankinnan suunnittelu.
B. Jonoteorian sovellukset dynaamisessa ajoituksessa
- Jonoteoria prosessoreissa
Prosessori ajoittaa tehtävän priorisoinnin perusteella. Esimerkiksi älypuhelimessasi on käynnissä 10 erilaista sovellusta ja ne ovat kaikki jonossa sen mukaisesti, mutta prosessori päättää, mikä sovellus toimii taustalla, jotta RAM-muistin käyttö ei vaikuta. Tässä prosessori käyttää prioriteettipohjaista jonotuskuria taustasovellusten jonoon.
- Jonoteoria tietokonejärjestelmässä
Töiden saapuminen tietokonejärjestelmään käyttäytyy saapumisprosessina ja suoritusaika on Poisson-prosessi. Työt suoritetaan saapumisjärjestyksessä, joten FCFS:ää käytetään saapumisen jonotuskurina. Jos tietokone on varattu työn saapuessa, se asetetaan jonoon.
Yllä mainittujen käyttötapausten ohella tällä teorialla on sovelluksia myös seuraaviin tehtäviin:
- Työntekijöiden tehokkuuden parantaminen
- Palvelun laadun parantaminen
- Koko myymälän myynnin parantaminen
- Asiakasuskollisuuden lisääminen
- Viestinnän tehostaminen
- Käyttökustannusten vähentäminen
- Aikataulut sairaaloissa
Koneoppimisen alalla jonoteoriaa käytetään yleisesti odotusajan ennustamisessa. Yllä olevia sovelluksia voidaan myös harkita ja mallintaa koneoppimisperiaatteilla parempien tulosten saavuttamiseksi.
Lopullinen tuomio
Usein syntyy jono, kun palvelun nykyinen kysyntä ylittää kyseisen palvelun nykyisen kapasiteetin. Tämä artikkeli sisältää joitakin peruskäsitteitä jonoteoriasta ja sen sovelluksista. Käsittelimme myös jonoteorian tärkeitä käyttötapauksia ja ymmärsimme sen soveltuvuuden koneoppimisalueelle.
