Delphi-menetelm¨an l¨aht¨okohtana oli 1950-luvulla Yhdysvalloissa her¨annyt kysymys Neu-vostoliiton ydinaseuhan merkityksest¨a. Kysymyst¨a, montako atomiasetta tarvittaisiin lamauttamaan USA:n sotateollisuus, selvitettiin monikierroksisella asiantuntijakyselyll¨a, jonka pani toimeen RAND ja jonka nimi oli Project Delphi.
Menetelm¨ass¨a valitulle asiantuntijajoukolle selvitet¨a¨an ensin kiinnostuksen kohteena ole-vaa kysymyst¨a yleisesti. Sitten l¨ahetet¨a¨an kyselykaavake, jolla kukin asiantuntija toi-sistaan riippumatta ja nimett¨om¨an¨a ilmaisee k¨asityksens¨a, vapaamuotoisesti. Kyselyn tulokset analysoidaan ja laaditaan uusi strukturoitu kysely, joka kohdistuu erityisesti en-simm¨aisess¨a kyselyss¨a esiin tulleisiin mielipide-eroihin. Vastaajat ilmaisevat kantansa ja perustelunsa. Toista kysely¨a seuraa viel¨a kolmas, edelleen tarkentava vaihe. Siin¨a kyselyn kohteille esitet¨a¨an edellisen kyselyn tulokset ja n¨am¨a tiedossaan vastaajat saavat arvioida uudelleen kantaansa. T¨am¨an kierros voidaan viel¨a toistaa. Lopputulemana esitet¨a¨an sek¨a ryhm¨an mielipiteiden mediaani ja asiat, joista ryhm¨a on yksimielinen, ett¨a asiat, joita koskevat k¨asitykset hajoavat samoin kuin perusteet k¨asityseroille. – Menetelm¨an k¨aytt¨o on ymm¨arrett¨av¨asti jokseenkin hidasta ja j¨aykk¨a¨a.
12 Jonoteoriaa
Jonoteoria k¨asittelee ilmi¨oit¨a, jotka voidaan havainnollistaa asiakaspalvelumallilla. Yksi tai useampi palvelija k¨asittelee asiakkaita, jotka saapuvat satunnaisesti. Asiakkaan palve-lemiseen kuluva aika on satunnaissuure. Jos palvelija on jo ty¨oss¨a, h¨an ei voi ottaa asia-kasta vastaan. T¨all¨oin asiakas saattaa j¨a¨ad¨a odottamaan. Sama asiakas saattaa tarvita per¨akk¨ain useita palvelijoita, ja jokaiseen palveluun p¨a¨asy¨a on jonotettava (sarjajonotus).
Odotuspaikkojen m¨a¨ar¨a saattaa olla rajoitettu tai rajoittamaton. Ns.jonokuri saattaa olla mm. FCFS (ensiksi saapunutta palvellaan ensiksi), LCFS (viimeksi saapunutta palvellaan ensiksi) tai SIRO (satunnaisj¨arjestyksess¨a palveleminen).
Jonomallista voidaan laskea esim. tarkasteltavan j¨arjestelm¨an todenn¨ak¨oist¨a kapasiteettia, todenn¨ak¨oisyytt¨a sille, ett¨a systeemiin tuleva asiakas saa palvelun, asiakkaan todenn¨ a-k¨oisen jonotusajan tunnuslukuja, systeemiss¨a kerrallaan olevien asiakkaiden lukum¨a¨ar¨an tunnuslukuja ja kerrallaan k¨ayt¨oss¨a olevien palvelijoiden m¨a¨ar¨an tunnuslukuja.
Todellisia tilanteita, joissa jonoteorian tarkasteluilla on merkityst¨a, ovat mm. viestikanavat ja puhelinkeskukset, liikenne ja ty¨oteht¨avien jako.
12.1 Poisson-prosessi
Tarkastellaan ajan funktiona j¨arjestelm¨a¨a, joka voi olla eri tiloissa S, T, . . .. Oletetaan, ett¨a todenn¨ak¨oisyys sille, ett¨a systeemi siirtyisi aikav¨alin¨a [t, t+h] mist¨a hyv¨ans¨a tilasta S mihin hyv¨ans¨a tilaan T riippuu vainS:st¨a,T:st¨a jah:sta, mutta eit:st¨a eik¨a siit¨a, miss¨a tiloissa systeemi on ollut ennen siirtymist¨a¨an tilaan S. Oletetaan viel¨a, ett¨a kun h on tarpeeksi pieni, niin v¨alill¨a [t, t+h] tapahtuu enint¨a¨an yksi tilanmuutos. N¨aill¨a oletuksilla voidaan todistaa, ett¨a t:n kasvaessa todenn¨ak¨oisyydet
Pk(t) =P{systeemi on hetkell¨at tilassa Sk}
l¨ahestyv¨at vakioraja-arvoja Pk, riippumatta siit¨a, mik¨a oli systeemin tila alussa. T¨all¨oin my¨os suurilla t:n arvoilla derivaatat Pk(t) ovat nollia.
Esimerkki. Oletetaan, ett¨a systeemill¨a on tasan kaksi tilaa, S1 ja S2, ja ett¨a todenn¨ a-k¨oisyys sille, ett¨a tilassa S1 oleva systeemi siirtyisi ajan h kuluessa tilaan S2 olisi λh ja todenn¨ak¨oisyys sille, ett¨a tilassa S2 oleva systeemi siirtyisi ajan h kuluessa tilaan S2 olisi µh. Hetkell¨a t= 0 systeemi on tilassa S1. Merkit¨a¨an
P1(t) =P{systeemi on tilassaS1 hetkell¨a t}, P2(t) =P{systeemi on tilassa S2 hetkell¨a t}. Silloin
P1(t+h) =P1(t)(1−λh) +P2(t)µh
ja
P2(t+h) =P1(t)λh+P2(t)(1−µh).
Kun n¨aist¨a yht¨al¨oist¨a muodostetaan P1:n ja P2:n erotusosam¨a¨ar¨at ja annetaan h → 0, saadaan yht¨al¨opari
P1(t) =−λP1(t) +µP2(t), P2(t) =λP1(t)−µP2(t).
Koska P1(t) = 1−P2(t) kaikilla t, saadaan funktiolle P1 differentiaaliyht¨al¨o P1(t) =−(λ+µ)P1(t) +µ,
jonka toteuttavat funktiot
P1(t) = µ λ+µ
1 +Ce−(λ+µ)t
,
miss¨a C on vakio, jonka m¨a¨ar¨a¨a esim. P1(0). T¨ast¨a seuraa, ett¨a P2(t) = λ
λ+µ
1− µ
λCe−(λ+µ)t
.
Kun t→ ∞, niin P1(t) ja P2(t) l¨ahestyv¨at raja-arvoja
P1 = µ
λ+µ, P2 = λ
λ+µ.
Ajassa toisiaan seuraavien tapahtumien jono on Poisson-prosessi, jos se on edell¨a esite-tyn tilanmuutosprosessin kaltainen: aikav¨alill¨a [t, t+h] tapahtuvien tapahtumien m¨a¨ar¨a ei riipu t:st¨a, aikav¨alill¨a [t1, t2] tapahtuvien tapahtumien m¨a¨ar¨a ei riipu siit¨a, miten monta tapahtumaa on ollut jollakin toisella aikav¨alill¨a [t3, t4], ja pienill¨a h:n arvoilla todenn¨ a-k¨oisyys, ett¨a v¨alill¨a [t, t+h] tapahtuisi kaksi tai useampia tapahtumia on h¨avi¨av¨an pieni yhden tapahtuman todenn¨ak¨oisyyteen verrattuna. N¨aist¨a oletuksista seuraa, ett¨a kahden per¨akk¨aisen tapahtuman v¨aliaika noudattaa eksponenttijakaumaa, jonka tiheysfunktio on
f(t) =λe−λt, (t > 0).
T¨ass¨a λ on tapahtumisnopeus eli prosessin intensiteetti ja 1/λ per¨akk¨aisten tapahtumien v¨alisen ajan odotusarvo. Kiinte¨an¨a aikana t sattuvien tapahtumien m¨a¨ar¨a puolestaan noudattaa Poisson-jakaumaa parametrilla tλ. Jonotusilmi¨oiden tarkastelun yhteydess¨a oletetaan yleens¨a, ett¨a systeemin tilaan vaikuttavat tekij¨at kuten asiakkaan saapuminen tai palvelijan vapautuminen asiakkaasta ovat Poisson-prosesseja.
Tarkastellaan systeemi¨a, jolla on n mahdollista tilaa S1, S2, . . . Sn. Systeemi voi siirty¨a tilasta Sj johonkin toiseen tilaan Sk hetkin¨a t1, t2, . . .. Todenn¨ak¨oisyys, ett¨a systeemi olisi tilassa Sj hetkien ti ja ti+1 v¨alill¨a on pj(ti). Jos todenn¨ak¨oisyys, ett¨a tilassa Sj
mahdollisesti oleva systeemi siirtyisi tilaan Sk on Pjk ja sama jokaisena mahdollisena
siirtymishetken¨ati, niin todenn¨ak¨oisyydet pj(ti) m¨a¨ar¨aytyv¨at t¨aysin tilojen Sj todenn¨ a-k¨oisyyksist¨a pj(0) ennen hetke¨a t1; todenn¨ak¨oisyydet saadaan palautuskaavoista
pj(ti) = n k=1
pk(tj−1)Pkj.
Systeemin siirtyminen tilasta toiseen saattaa riippua ajan kuluessa satunnaisesti esiinty-vist¨a tapahtumista. Jos sellainen tapahtuma, joka siirt¨a¨a systeemin tilasta Sj tilaan Sk tapahtuu intensiteetill¨a λjk, niin todenn¨ak¨oisyys olla tilassa Sj kehittyy ajan kuluessa yht¨al¨on
dpj(t)
dt =
n k=1
λkjpk(t)−pj(t) n k=1
λjk
mukaisesti. Er¨ain ehdoin on voimassa, ett¨a t:n kasvaessa todenn¨ak¨oisyyksill¨a pj(t) on raja-arvo, kun t → ∞. N¨ain on esimerkiksi silloin, kun tilanmuutoksia aiheuttavat jonot ovat Poisson-prosesseja. Todenn¨ak¨oisyyksien raja-arvoja voi pit¨a¨a samalla niiden suh-teellisten aikaosuuksien mittoina, jonka kauan toiminnassa ollut systeemi on eri tiloissa.
T¨ass¨a kuvatunkaltaisia kysymyksi¨a tutkii stokastisten prosessien teoriaksi kutsuttu to-denn¨ak¨oisyyslaskennan osa-alue. T¨ass¨a esitellyt stokastiset prosessit kuuluvat verrattain yksinkertaisten,Markovin ketjuiksi kutsuttujen prosessien luokkaan.
12.2 Jonomalleja
Tarkastellaan seuraavia jonomalleja:
1. useita palvelijoita, ei jonotusmahdollisuutta, 2. yksi palvelija, ¨a¨arett¨om¨an pitk¨a jono,
3. yksi palvelija, rajallinen jono, 4. useita palvelijoita, rajaton jono, 5. useita palvelijoita, rajallinen jono.
12.2.1 Monta palvelijaa, ei jonoa
Tarkastellaan aluksi systeemi¨a, joka koostuun:st¨a palvelijasta. Systeemiin tulee asiakkaita Poisson-prosessina nopeudellaλ. Palvelijan vapautuminen asiakkaasta on Poisson-prosessi, jonka nopeus on µ (yhden asiakkaan palveluun kuluva aika on siis eksponentiaalisesti ja-kautunut ja sen odotusarvo on 1/µ).T¨am¨a merkitsee, ett¨a systeemiin tulee lyhyen¨a aikana h asiakas todenn¨ak¨oisyydell¨a λh ja ett¨a ”varattu” palvelija vapautuu ajan hkuluessa to-denn¨ak¨oisyydell¨aµh. Systeemill¨a on nytn+ 1 tilaaS0, S1,. . ., Sn, miss¨a Sj on tila, jossa tasan j palvelijaa on varattuna. Mahdolliset tilanmuutokset ovat
(i) Siirtyminen tilasta Sj tilaan Sj+1, j = 0, 1, . . . , n−1, kun systeemiin tulee uusi asiakas, jota voidaan palvella
(ii) Siirtyminen tilastaSj tilaanSj−1, j = 1,2, . . . , n, kun yksi palvelija vapautuu.
Olkoon
Pj(t) =P{systeemi on tilassa Sj hetkell¨a t}.
Silloin, jos h on pieni, on
P0(t+h) =P0(t)(1−λh) +P1(t)(1−λh)µh, josta saadaan (differentiaalikehitelm¨a!)
P0(t) =−λP0(t) +µP1(t).
Koska kaikilla j = 1, 2, . . ., n−1 siirtyminwen tilasta Pj−1 tilaan Pj edellytt¨a¨a yhden uuden asiakkaan saapumista ja sit¨a, ett¨a yksik¨a¨an toimessa olevista j−1:st¨a palvelijasta ei vapaudu, ja siirtyminen tilasta Pj+1 tilaa Pj edellytt¨a¨a, ett¨a systeemiin ei tule uutta asiakasta, mutta tasan yksi palvelija toimessa olevista j+ 1:st¨a vapautuu, on
Pj(t+h) =Pj(t)(1−λh)(1−jµh) +Pj−1(t)λh(1−(j−1)µh) +Pj+1(1−λh)(j+ 1)µh, josta seuraa
Pj(t) =λPj−1(t)−(λ+jµ)Pj(t) + (j+ 1)µPj+1(t).
Samoin saadaan ”kokonaan varattua” systeemi¨a koskeva yht¨al¨o
Pn(t+h) =Pn(t)(1−nµh) +Pn−1(t)λh(1−(n−1)µh), josta
Pn(t) =−mµPn(t) +λPn−1(t).
Kunt kasvaa, systeemi vakiintuu, ja kaikki todenn¨ak¨oisyydetPj(t) l¨ahestyv¨at raja-arvoja Pj. Samalla derivaatat Pj(t) tulevat nolliksi. Saadaan yht¨al¨oryhm¨a
⎧⎪
⎨
⎪⎩
−λP0+µP1 = 0,
λPj−1−(λ+jµ)Pj+ (j + 1)Pj+1 = 0 (j = 1, . . . n−1), λPn−1+µPn = 0.
Ensimm¨ainen n¨aist¨a yht¨al¨oist¨a antaa P1 = λ
µP0 =ρP0,
kun merkit¨a¨an λ/µ=ρ. Seuraavista yht¨al¨oist¨a saadaan j¨arjestyksess¨a P2 = 1
2ρ2P0, P3 = 1
3!ρ3P0, . . ., Pn = 1
n!ρnP0. Koska kaikkien todenn¨ak¨oisyyksien summa on 1, on
P0 = 1
1 +ρ+ ρ2
2! +. . .+ ρn n!
.
Sattumanvaraisena aikana saapuva asiakas saa palvelun, jos systeemi ei ole tilassa Sn, siis todenn¨ak¨oisyydell¨a 1−Pn. Systeemin kapasiteetti, siis sen aikayksik¨oss¨a todenn¨ak¨ oi-sesti palvelemien asiakkaiden m¨a¨ar¨a, on λ(1−Pn). Kunakin hetken¨a toiminnassa olevien palvelijoiden m¨a¨ar¨an odotusarvo on
n k=0
kPk = n k=1
1
(k−1)!ρkP0=ρ(1−Pn).
Esimerkki. Tutkitaan systeemi¨a, jossa v¨alitet¨a¨an sanomia kolmikanavaisella viestiv¨ ali-neell¨a. Sanomia tulee joka toinen minuutti ja niiden keskim¨a¨ar¨ainen kesto on yksi minuutti.
T¨ass¨a λ= 0,5 ja µ= 1, joten ρ = 0,5. LasketaanP0:
1/P0 = 1 +ρ+ρ2/2 +ρ3/6 = 1,646, joten P0 = 0,607. T¨ast¨a saadaan P1 = ρP0 = 0,304, P2 = ρ2
2 P0 = 0,075 ja P3 = ρ3 6 = 0,013. Tuleva viesti voidaan v¨alitt¨a¨a todenn¨ak¨oisyydell¨a 0,987 ja systeemin minuutissa v¨alitt¨amien puhelujen lukum¨a¨ar¨an odotusarvo on A = 0,987·0,5 = 0,494. Kerrallaan on k¨ayt¨oss¨a keskim¨a¨arin 0,494 linjaa.
Jos sanomia tulee keskim¨a¨arin kolme minuutissa, on λ = 3 ja ρ = 3. Samoin kuin edell¨a lasketaan nyt eri tilojen todenn¨ak¨oisyyksiksi P0 = 0,077, P1 = 0,231 ja P2 =P3 = 0,346.
Nyt kapasiteetti on A = λ(1−P3) = 1,962. Kunakin hetken¨a k¨ayt¨oss¨a on keskim¨a¨arin 1,962 linjaa. Jos puhelut olisivat kaikki tasan minuutin pituisia ja alkaisivat juuri edellisen p¨a¨attyess¨a, voitaisiin linjoja pitkin johtaa 3 puhelua minuutissa; t¨all¨oin kaikki linjat olisivat koko ajan k¨ayt¨oss¨a.
12.3 Yksi palvelija, rajaton jono.
Nyt systeemill¨a on ¨a¨aret¨on m¨a¨ar¨a tilojaS0, S1, S2. . . .Systeemi on tilassa S0, jos palvelija ei toimi eik¨a jonossa ole yht¨a¨an asiakasta. Systeemi on tilassa Sj, jos palvelija k¨asittelee asiakasta ja jonossa on j −1 asiakasta. Oletetaan taas, ett¨a asiakkaiden saapuminen on Poisson-prosessi, jonka intensiteetti on λ ja ett¨a asiakkaan k¨asittelyaika on eksponentiaa-lisesti jakautunut odotusarvolla 1/µ, ts. ett¨a ty¨on valmiiksi tulo on Poisson-prosessi, jonka intensiteetti on µ. Merkit¨a¨an λ/µ=ρ. Olkoon h pieni. Systeemi on hetkell¨a t+h tilassa S0, jos se oli hetkell¨a t tilassa S0 eik¨a yht¨a¨an asiakasta saapunut, tai jos se oli hetkell¨a t tilassa S1 ja palvelija sai asiakkaan palveltua v¨alill¨a [t, t+h] eik¨a yht¨a¨an uutta asiakasta saapunut. T¨ast¨a seuraa yht¨al¨o
P0(t+h) =P0(t)(1−λh) +P1(t)(1−λh)µh ja edelleen, kun h →0,
P0(t) =−λP0(t) +µP1(t).
Jos j >0 saadaan vastaavasti
Pj(t+h) =Pj−1(t)λh(1−µh) +Pj(t)(1−λh)(1−µh) +Pj+1(t)(1−λh)µh,
eli kun h→0
Pj(t) =λPj−1(t)−(λ+µ)Pj(t) +µPj+1
Antamalla nytt → ∞ saadaanPj(t)→0, ja rajatodenn¨ak¨oisyyksille Pj ehdot P1 =ρP0,
Pj+1 = 1
µ[(µ+λ)Pj −λPj−1], jotka toteutuvat, kun
Pj =ρPj−1 =. . .=ρjP0. T¨ast¨a seuraa, jos ρ <1,
1 = (1 +ρ+ρ2+. . .)P0 = 1 1−ρP0 ja
P0 = 1−ρ.
Tilan Sj todenn¨ak¨oisyys on sitenPj =ρj(1−ρ). – Jos ρ ≥ 1 eli λ ≥ µ, niin jono kasvaa kasvamistaan, eik¨a tilalla S0 ole positiivista todenn¨ak¨oisyytt¨a P0.
Systeemiss¨a, siis jonossa ja palveltavina kerrallaan olevien asiakkaiden m¨a¨ar¨an odotusarvo N saadaan normaalilla tavalla kaavasta
∞ k=1
kPk = (1−ρ) ∞ k=1
kρk.
Viimeinen summa lasketaan k¨aytt¨am¨all¨a avuksi derivointia: koska 1 +ρ+ρ2+. . .= 1
1−ρ, niin
1 + 2ρ+ 3ρ2+. . .=D 1
1−ρ
= 1
(1−ρ)2. T¨ast¨a seuraa
N = ρ
1−ρ.
Esimerkki. Itsepalveluruokalaan tulee asiakkaita keskim¨a¨arin kolme minuutissa. Yht¨a asiakasta palvellaan keskim¨a¨arin 15 s. Kuinka pitk¨a jono ruokalassa keskim¨a¨arin on?
Ratkaisu. T¨ass¨a λ = 3 ja µ = 4, joten ρ = 0,75. Edell¨a johdetun kaavan perusteella N = 0,75/0,25 = 3.
Periaatteessa samoin kuin systeemiss¨a kaikkiaan olevien asiakkaiden m¨a¨ar¨a johdetaan jo-nossa olevien asiakkaiden m¨a¨ar¨an odotusarvo J:
J = ∞ k=2
(k−1)Pk= ρ2 1−ρ.
Lasketaan viel¨a systeemiin tulevan asiakkaan palvelemiseen kuluvan ajan odotusarvo. Jos asiakas tulee jonoon systeemin ollessa tilassa Sj, eli kun palveltavana ja jonossa on j asiakasta, niin asiakkaan on odotettava keskim¨a¨arin aika (j+ 1)1
µ eli oma ja edell¨a olevien palveluaika. Jonotus- ja palveluajan odotusarvo T on siten
T =
∞ k=0
Pk(k+ 1)1
µ = 1
µ(1−ρ) = 1
µ−λ.
Edellisess¨a ruokalaesimerkiss¨a jonottamiseen ja palveluun kuluvan ajan odotusarvo on 1 minuutti.
12.3.1 Yksi palvelija, rajallinen jono
Oletetaan, ett¨a tilanne on muuten sama kuin edellisess¨a kohdassa, mutta ett¨a jo-noon mahtuu kerrallaan vain m jonottajaa. Asiakas, joka pyrkii systeemiin silloin, kun kaikki jonotuspaikat ovat t¨aynn¨a, joutuu poistumaan. Systeemill¨a on m+ 2 tilaa S0, S1, . . . , Sm, Sm+1 (systeemi on tilassa S0, jos palvelija on jouten eik¨a jonossa ole ke-t¨a¨an, ja tilassaSj, jos palvelija on varattu, ja jonossa on j−1 jonottajaa), joiden rajato-denn¨ak¨oisyyksilleP0, P1, . . . , Pm+1 saadaan palautuskaavat
−λP0+µP1 = 0
−λPj−1+ (λ+µ)Pj−µPj+1 = 0 (j = 1, . . . , m).
Saadaan taasPj =ρjP0 ja
P0 = 1
1 +ρ+. . .+ρm+1 = 1−ρ 1−ρm+2.
Systeemi pystyy palvelemaan asiakasta todenn¨ak¨oisyydell¨a 1−Pm+1 ja sen kapasiteetti on A=λ(1−Pm+1).
12.3.2 Monta palvelijaa, rajaton jono.
J¨arjestelm¨ass¨a on n palvelijaa. Silloin mahdollisia tiloja ovat S0, miss¨a kaikki palvelijat ovat joutilaina,S1, S2, . . . Sn, eli 1, 2,. . . npalvelijaa k¨ayt¨oss¨a ja jono tyhj¨a, jaSn+r, kaikki palvelijat k¨ayt¨oss¨a ja jonossar asiakasta. Tilojen rajatodenn¨ak¨oisyydetP0, P1, . . . Pn saa-daan samoin kuin jonottomassa tapauksessa (1):
Pj = ρj j!P0.
Niiss¨a tiloissa, joissa jono ei ole tyhj¨a, johdutaan kaavaan Pn+r= ρn+r
nr·n!P0 =κrPn,
miss¨a κ = ρ/n. Tilojen todenn¨ak¨oisyyksien summa voidaan normeerata ykk¨oseksi vain, jos κ <1. T¨all¨oin saadaan
T¨ast¨a voidaan laskea jonossa kerrallaan olevien asiakkaiden m¨a¨ar¨an odotusarvo J =
∞ r=1
rPn+r = κPn
(1−κ)2
samoin kuin kerrallaan toiminnassa olevien palvelijoiden lukum¨a¨ar¨an odotusarvo
K =
N¨aiden summa on kerrallaan systeemiss¨a olevien asiakkaiden m¨a¨ar¨an odotusarvo N: N = J +ρ. Asiakkaan jonotus- ja palveluaika riippuu systeemin tilasta asiakkaan saa-pumishetkell¨a. Jos systeemi on jossakin tiloista S0, S1, . . . , Sn−1, niin asiakkaan palvelun keskim¨a¨ar¨ainen aika on 1/µ. Jos systeemi on tilassa Sn+k, k > 0, niin odotukseen kuluu aikaa keskim¨a¨arin (k + 1) 1
nµ ja palveluun 1
µ. Jonotus- ja palveluajan odotusarvo T on siten
T¨am¨a on yleisesti jonotussysteemeiss¨a voimassa oleva Littlen kaava.
Esimerkki. Systeemiin tulee keskim¨a¨arin 5 asiakasta minuutissa. Palvelijan keskim¨a¨ a-r¨ainen palveluaika on 30 sekuntia. Montako palvelijaa olisi k¨aytett¨av¨a, jotta asiakkaan odotus- ja palveluaika olisi keskim¨a¨arin alle minuutin?
Ratkaisu. T¨ass¨a λ = 5 ja µ= 2, joten ρ = 2,5. Jotta jono ei kasvaisi rajatta, on oltava κ=ρ/n <1. Siis palvelijoiden lukum¨a¨ar¨an on oltava n≥3.
Koska n:n ratkaiseminen suoraan algebrallisesti ep¨ayht¨al¨ost¨a T < 1 on mahdotonta, haa-rukoidaan: Kun n = 3, niin κ = 2,5
3 = 5
6, ja edell¨a johdetuista kaavoista saadaan P0 = 0,04494. . . ja P3 = 0,1170. . .. T¨ast¨a lasketaan T = 1,2022. . . . Jos n = 4, niin κ = 5/8 ja P0 = 0,07369. . ., P4 = 0,1199. . . ja T = 0,6066. . .. Siis vaaditun tavoitteen saavuttamiseksi olisi k¨aytett¨av¨a nelj¨a¨a palvelijaa.
12.3.3 Monta palvelijaa, rajoitettu jono
Jos palvelijoita on n ja jonossa voi kerrallaan olla enint¨a¨an m asiakasta, niin systeemill¨a on tilat S0, S1, . . . , Sn, Sn+1, . . . Sn+m. Rajatodenn¨ak¨oisyyksille saadaan samoin kuin edellisess¨a tapauksessa ehdot
Pj = ρj
j!P0, j = 1, 2, . . . , n, Pn+k =κkPn, k = 1, 2, . . . , m.
N¨aist¨a lasketaan
P0 = 1
1 +ρ+ ρ2
2! +. . .+ ρn−1
(n−1)! + ρn n!
1−κm+1 1−κ
.
Nyt voidaan laskea systeemin ominaisuudet: todellinen kapasiteetti A = λ(1 −Pm+n), keskim¨a¨ar¨ainen jonotusaika jne. (Tapaus κ = 1 voidaan hoitaa erikseen.)
12.4 Sarjajonoista
Systeemit, joissa esiintyy useita per¨akk¨aisi¨a jonoja, ovat yleens¨a vaikeammin hallittavia.
Jos asiakkaiden saapuminen on Poisson-prosessi ja jos systeemi sallii rajattoman jonon joka vaiheessa ja jokaisen palvelijan palveluaika on eksponentiaalisesti jakautunut, niin systeemist¨a l¨ahtev¨at asiakkaat samalla nopeudella λ kuin siihen tulevatkin. T¨allaista sys-teemi¨a voidaan tarkastella yksinkertaisten jonotussysteemien jonona. Jos systeemi sallii vain rajoitettuja jonoja, tilanne mutkistuu.
Tarkastellaan aluksi yksinkertaista systeemi¨a, joka muodostuu kahdesta palvelijasta S1 ja S2. Asiakasta palvelee ensinS1ja sittenS2.Jonoa ei voi muodostaa kummankaan palvelijan eteen. Asiakkaita tulee systeemiin Poisson-prosessina nopeudella λ, ja kumpikin palvelija saa ty¨ons¨a valmiiksi Poisson-prosessina nopeudellaµ. Systeemin tilaa kuvaa lukupari (i, j), miss¨ai= 0, 1 tai 2 sen mukaan, onkoS1 vapaa, toimessa vai ”tukossa” sen t¨ahden, ett¨aS2 ei ole vapaa, ja j = 0, jos S2 on vapaa, j = 1, jos S2 on toimessa. Jos systeemi on hetkell¨a t tilassa (i, j) todenn¨ak¨oisyydell¨a pij(t), niin pienill¨a h p¨atee (h2-termit unohtaen)
p00(t+h) =p00(t)(1−λh) +p01(t)µh,
p01(t+h) =p01(t)(1−λh−µh) +p10(t)µh+p21(t)µh, p10(t+h) =p00(t)λh+p10(t)(1−µh) +p11(t)µh, p11(t+h) =p01(t)λt+p11(t)(1−2µh),
p21(t+h) =p11(t)µh+p21(t)(1−µh).
N¨aist¨a yht¨al¨oist¨a saadaan taas stabiilit todenn¨ak¨oisyydet pij muodostamalla
erotusosa-m¨a¨ar¨at sek¨a derivaatat ja asettamallapij = 0.Saadaan yht¨al¨oryhm¨a p01 −ρp00 = 0,
p10+p21+ (1−ρ)p01 = 0, ρp00+p11−p10 = 0, ρp01−2p11 = 0, p11−p21 = 0.
T¨ast¨a ratkaistaan helpostipij:t esim. p00:n avulla, ja ehdosta p00+p01+p10+p11+p21 = 1 saadaan
p00 = 2 A p01 = 2ρ
A p10 = ρ2+ 2ρ
A p11 =p21 = ρ2
A, miss¨a
A= 3ρ2+ 4ρ+ 2.
Systeemiss¨a olevien asiakkaiden m¨a¨ar¨an odotusarvo on
0p00+ 1(p01+p10) + 2(p11+p21) = 5ρ2+ 4ρ
A .
Esimerkki. Liukuhihnan varrella on kaksi ty¨opistett¨a. Koottavat esineet saapuvat hih-nalle Poisson-prosessina intensiteetill¨aλ = 10 kappaletta tunnissa. Kumpikin ty¨opiste saa ty¨ons¨a valmiiksi Poisson-prosessina keskim¨a¨arin viidess¨a minuutissa. Koottavia esineit¨a ei voi s¨ailytt¨a¨a ty¨opisteiden v¨aliss¨a, ja kaikki sellaiset esineet, joita ei voi heti ottaa ty¨on alle siirret¨a¨an toisille liukuhihnoille. T¨all¨oin µ= 60/5 = 12 ja ρ= 10/12 = 0,833. T¨ast¨a saadaan A = 7,417 ja p00 = 0,2697, p01 = 0,2247, p10 = 0,3183 ja p11 = p21 = 0,0936.
Todenn¨ak¨oisyys, ett¨a saapuva esine voidaan ottaa hihnalle, onp00+p01 = 0,4944. Systee-min todellinen kapasiteetti on siten 10×0,4944 = 4,94 esinett¨a tunnissa. Systeemiss¨a on kunakin hetken¨a ty¨on alla keskim¨a¨arin 0,917 esinett¨a.
Useista vaiheista koostuvien yleisten jonotussysteemien eksakti analysointi on yleens¨a vai-keaa. Siin¨a erikoistapauksessa, jossa jokaisen palvelijan eteen voi muodostua rajoittamaton jono, asiakkaiden saapuminen on Poisson-prosessi, jonka intensiteetti on λ ja i:nnen pal-velijanpalveluaika noudattaa eksponenttijakaumaa odotusarvolla 1/µi, voidaan kuitenkin kutakin palvelijaa tarkastella muista riippumatta. Todenn¨ak¨oisyys,ett¨ai:nnell¨a palvelijalla olisi palveltavana ja jonossa ni asiakasta,on
pni = (1−ρi)ρnii, miss¨a ρi = λ
µi.
Esimerkki. Tuotantolinja koostuu viidest¨a per¨akk¨aisest¨a palvelijasta. T¨oit¨a saapuu en-simm¨aiselle palvelijalle 20 tunnissa, ja k¨asittelyaika noudattaa eksponenttijakaumaa odo-tusarvolla 2 minuuttia. 90 % kunkin palvelijan tuotteista on hyvi¨a, ja ne siirret¨a¨an seu-raavalle palvelijalle. Loput heitet¨a¨an pois. Kuinka suuret varastot on asennettava kunkin palvelijan eteen, jotta kaikki hyv¨at tuotteet mahtuisivat 99 % todenn¨ak¨oisyydell¨a odotta-maan vuoroaan?
Ratkaisu. Jos λi tarkoittaa i:nnelle palvelijalle tulevien t¨oiden m¨a¨ar¨a¨a tunnissa, niin λ1 = 20 ja λi = 0,9i−1·20. Koska µ= 30, niin ρ1 = 0,667, ρ2 = 0,6, ρ3 = 0,54, ρ4 = 0,486 ja ρ5 = 0,4374. Todenn¨ak¨oisyys, ett¨a i:nnell¨a asemalla olisi enint¨a¨an Ni − 1 tuotetta jonossa, on
Ni
j=0
(1−ρi)ρji = 1−ρNi i+1.
ValitaanNi:t niin, ett¨a n¨am¨a summat ovat kaikki ≥0,99. T¨am¨a tapahtuu,kun Ni ≥ ln 0,01
lnρi .
Kunρi:t sijoitetaan t¨ah¨an, saadaanN1 ≥10,5,N2 ≥8,N3 ≥6,47,N4 ≥5,38 jaN5 ≥4,57.