Eötvös Loránd Tudományegyetem Természettudományi Kar
Ferenczi Dóra Sorbanállási problémák BSc Szakdolgozat
Témavezet®:
Arató Miklós
egyetemi docens Valószín¶ségelméleti és Statisztika Tanszék
Budapest, 2014
Tartalomjegyzék
1. Sorbanállási rendszerek jellemzése
5
1.1. Jelölések bevezetése . . . . . . . . . . . . . 1.1.1. A sorbanállási rendszerek jellemz®i 1.1.2. Hatékonyság mér®számai . . . . . . 1.1.3. Kendall jelölésrendszere . . . . . . 1.2. Születési-halálozási folyamatok . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
5 5 6 6 7
2. Az M/M/1 típusú sorbanállási rendszer
12
3. Prioritásos M/M/1 rendszer
19
3.1. A megszakításos rendszer . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. A kivárásos rendszer . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4. Az M/M/1/K rendszer
19 20
21
4.1. A rendszer f®bb jellemz®i . . . . . . . . . . . . . . . . . . . . . . . . . . .
5. Sorbanállási rendszerek alkalmazásai 5.1. Egyszer¶bb feladatok megoldása . . . . . . . . . . . . . . . . . . . . . . . 5.2. Kórházi sorok vizsgálata . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
22
26 26 31
Köszönetnyilvánítás
"Az élet egy folyamatos sorban állás, várakozva a következ® nagy ugrásra." Ezúton szeretnék köszönetet mondani témavezet®mnek, Arató Miklósnak, hogy gyelemmel kísérte a szakdolgozatom készülését, és hasznos tanácsokkal látott el közös munkánk során. Köszönöm családomnak és barátaimnak, hogy mellettem álltak, támogatásukra és biztatásukra mindig számíthattam. Végül,de nem utolsó sorban hálával tartozom gimnáziumi tanáromnak, Fonyó Lajosnak, hogy megszerettette velem a matematikát.
3
Bevezet®
A sorbanálláselmélet több tudományterület határán fekv®, az alkalmazott matematikához tartozó viszonylag atal tudományág, amely a hétköznapokban is gyakran el®forduló problémával, a várokozás vizsgálatával foglalkozik. Segítségével kiszámíthatjuk, hogy meddig kell várakoznunk a bankban vagy a postán, illetve mikor kerülünk sorra a boltban a pénztárnál. Módszerei hatékonyan alkalmazhatók az operációkutatás, hírközlési és telekommunikációs, valamint számítógép rendszerek területén felmerül® problémák matematikai modellezésére. Az elmélet a telefonhálózatok fejlesztésével párhuzamosan fejl®dött es lényegi elemévé vált a klasszikus távközlési hálózatok tervezésének. Bármilyen szolgáltatást vizsgálva nagyon fontos tényez®ként jelenik meg a hozzá kapcsolódó várakozás, ugyanis az ezzel töltött id® mértéke a felhasználók elégedettségét nagy mértékben befolyásolja, kedvez®tlen esetben pedig negatív képet adhat az adott kiszolgálóegységr®l. Ugyanakkor a szolgáltatók számára is fontos a szolgáltatás egyensúlyi állapotának vizsgálata. A kiszolgálórendszer nem megfelel® méretezése ugyanis a szolgáltatók számára is felesleges kiadásokat generálhat. A számítógéprendszerek rohamos fejl®désének hatására, egyre nagyobb gyelem irányult a bonyolult rendszerek elemzését lehet®vé tev® sztochasztikus folyamatok egyre szélesebb körben történ® alkalmazására. Manapság, az óriási információáradat korában észrevehet®en nagy igény mutatkozik mind komplexebb matematikai megközelítések bevezetésére, melynek következtében a leíró véletlen folyamatok is egyre összetettebbek lesznek. Célunk tehát a kiszolgálási id®k és szabályok ismeretében olyan módszerek bemutatása, melyek segítségével csökkenthet®ek a várokozási id®k.A felhasználók egy sztochasztikus folyamat szerint érkeznek a kiszolgálókhoz, várakozási idejüket pedig egy valószín¶ségi változó határozza meg. Ezen sztochasztikus folyamatok alapján alakul ki a várakozási sor, melynek átfutási ideje egy minél hatékonyabb kiszolgálást biztosító rendszerrel nagy mértékben csökkenthet®. Látható tehát, hogy a sorbanállási elmélet nem csak a hétköznapokban, de különböz® tudományterületeken is tág környezetben alkalmazható, segítségével hasznos információkhoz juthatunk a minél hatékonyabb kiszolgálási rendszerek kialakításához.
4
1. fejezet
Sorbanállási rendszerek jellemzése
1.1. Jelölések bevezetése
Egy sorbanállási rendszer megfelel® jellemzéséhez azonosítanunk kell egy sztochasztikus folyamatot, amely megadja számunkra a beérkez® igényekr®l szóló információkat.
De níció
Legyen adva egy (Ω, A, P ) valószín¶ségi mez® és egy tetsz®leges T (index)halmaz. Egy sztochasztikus folyamat minden t ∈ T indexhez hozzárendel egy valószín¶ségi változót. megjegyzés: A dolgozatom folyamán végig Sztrik János egyetemi jegyzetében található jelöléseket alkalmazom. [1], [2], [3] . 1.1.1. A sorbanállási rendszerek jellemz®i
Egy sorbanállási rendszer leírásához ismernünk kell a kiszolgálás szabályait, illetve struktúráját, melyeket az alábbi mennyiségek írnak le: : az igény kiszolgálóegységben töltött id®tartamának hossza, melyek független, azonos eloszlású valószín¶ségi változók
•
kiszolgálási id®
•
befogadóképesség
•
rendszerid®
•
csatornák száma
•
kiszolgálási sorrend
: a várakozó sor maximális hossza
: a várakozással és a kiszolgálással töltött együttes id® : a rendelkezésre álló kiszolgálóegységek
: az a szabály, amely szerint a várakozók sorra kerülnek A leggyakrabban használt kiszolgálási formák a következ®k: 5
1.
First Come First Served
, azaz az érkezés sorrendjében történ® kiszolgálás
2.
Last Come First Served
: az a kiszolgálási sorrend, amikor az utolsónak érkez®t
szolgálják ki el®ször. •
: a beérkez® igények esetleges csoportokba sorolása, melyeken a kiszolgálás sorrendje múlik prioritás
1.1.2. Hatékonyság mér®számai
A sorbanállási rendszerek hatékonyságának és teljesítményének vizsgálatához az alábbi rendszerjellemz®ket kell meghatároznunk: •
igények várakozási ideje
•
várakozó igények száma
•
foglaltsági intervallum
,amely megmutatja a csatorna id®egységre es® kihasználtsá-
gát •
pillanatnyi munkahátralék
Ezek mindegyike egy valószín¶ségi változó, így a vizsgálatok során ezek eloszlásfüggvényét igyekszünk meghatározni. A teljesítmény mérésének legalapvet®bb eszköze a torlódás vizsgálata. Jelölje % a forgalmi intenzitást, amelyet az átlagos kiszolgálási id® és az átlagos beérkezési id® hányadosaként számolhatunk ki. Ha ez a mennyiség nagyobb, mint 1, akkor arra a következtetésre juthatunk, hogy az igények gyorsabban érkeznek, mint ahogy az adott csatorna ki tudná szolgálni ®ket. Egy másik gyakran használt teljesítménymér® eszköz a rendszer átbocsátóképessége. Ez nem más, mint az id®egység alatt átlagosan kiszolgált igények száma. 1.1.3. Kendall jelölésrendszere
A sorbanállási rendszerek könnyebb osztályozhatósága érdekében vezessünk be néhány, a vizsgálatok során gyakran használt jelölést. A/B/m/K/N/D,
ahol A a beérkezési id®közök eloszlásfüggvénye,azaz
6
A(t) = P(beérkez® igények között eltelt id® 6 t) B a kiszolgálási id®k eloszlásfüggvénye, vagyis
B(t) = P(kiszolgálási id® 6 t), m a kiszolgálók száma, K a rendszer befogadóképessége, azaz az igények maximális száma, N az igények számossága,továbbá D a kiszolgálás elve.
Amennyiben a fent említett eloszlások exponenciálisak, az M jelölés használatos.Továbbá, ha a befogadóképesség és az igényforrás számossága végtelen, akkor ezeket a jelöléseket elhagyjuk. Így például az M/M/1 szimbólum, egy egy kiszolgálós Poisson beérkezéssel és exponenciális kiszolgálási id®vel jellemzett rendszert jelöl. 1.2. Születési-halálozási folyamatok
A sorbanállási rendszerek modellezésére a születési-halálozási folyamatok hatékonyan használhatók. A folyamatban a születések megfelelnek az érkez® igényeknek, míg a halálozást a rendszerben lév® igények kiszolgálása jelenti. A sorbanállási példákban nagy hangsúlyt fektetünk arra, hogy az X(t) (vagyis a sor hossza a t pillanatban) mely pillanatokban ugrik egyet, mintsem magára az X(t) értékére [4]. Példának okáért tekintsünk egy orvosi rendel®t,mint kiszolgálóegységet. Minden egyes id®pontot, amikor egy páciens belép az utcáról a várószobába, úgy tekintünk, mint egy igény beérkezését a sorbanállási rendszerbe; másrészt ezt a beérkezést úgy is fel lehet fogni, mint egy populáció új tagjának születését, ahol a populációt a jelenlev® páciensek alkotják. Hasonlóképpen, amikor egy páciens elhagyja a rendel®t, ezt mint a sorbanállási rendszerb®l való távozást tekintjük, a születési-halálozási folyamatban ez a populáció egy tagjának halálával ekvivalens.
De níció A születési-halálozási folyamat egy olyan Markov-folyamat, melyben minden állapotból csak a szomszédos állapotokba valósulhat meg átmenet. Tehát ha a folyamat a t pillanatban az n állapotban van, akkor véletlen hosszúságú várakozási id® után vagy az n + 1 vagy az n − 1 állapotok valamelyikébe megy át. Ahhoz, hogy egy X(t) Markov-folyamat, melynek állapotterét a 0,1,2,... számok alkotják születési-halálozási folyamat legyen, ki kell elégíteni a következ® feltételeket: 1. P (X(t + h) = k + 1|X(t) = k) = λk h + o(h); 2. P (X(t + h) = k − 1|X(t) = k) = µk h + o(h); 7
3. P (X(t + h) = k|X(t) = k) = 1 − (λk + µk )h + o(h); 4. P (X(t + h) = m|X(t) = k) = o(h) |m − k| > 1 5. µ0 = 0, λ0 > 0, µi , λi > 0, i = 1, 2, .... A h egy tetsz®leges intervallumot jelöl, míg o(h) egy olyan mennyiség, amelyre h → 0 esetén o(h) → 0.A λk mennyiségek a születési-intenzitások, µk számok pedig halálozásih intenzitások, melyek függetlenek az id®t®l. Annak valószín¶sége, hogy a rendszer a t id®pillanatban a k állapotban van: Pk (t) = P (Xt = k) A t + h id®pillanatban a X(t) k állapotban van akkor és csak akkor, ha az alábbi feltételek teljesülnek: 1. t id®pillanatban a folyamat a k állapotban van és a (t, t + h) id®intervallumban változás nem következik be; 2. t id®pillanatban a folyamat a k − 1 állapotban volt és a k -ba történt átmenet; 3. t id®pillanatban a folyamat a k + 1 állapotban volt és a k -ba történt átmenet; 4. (t, t + h) alatt 2 vagy több átmenet történt. Az els® három feltétel egymást kizáró, míg a negyedik eset valószín¶sége o(h). Mivel a Pk (t) mennyiségek valószín¶ségek, teljesül, hogy Pk (t) ≥ 0, továbbá
∞ P
Pk (t) = 1.
k=0
A konstans λ születési intenzitással rendelkez® folyamatokban el®forduló születések sorozatát Poisson-folyamatnak nevezzük. A Poisson-folyamat központi szerepet tölt be a sorbanállási rendszerek vizsgálatában. A folyamatot, mint igények beérkezését tekintjük valamilyen kiszolgálási rendszerbe, tehát a λ paraméter az érkez® igények átlagos intenzitását fogja jelenteni.[3] Tegyük fel, hogy a rendszer, a 0 állapotból indul a t = 0 id®pillanatban: 1 ,ha k = 0 Pk (0) = 0 ,ha k = 6 0
Ez a feltétel lesz a kezdeti feltételünk, Pk (t) mennyiségek pedig annak a valószín¶ségét jelentik, hogy k igény érkezik a rendszerbe a (0, t) id®intervallumban. Mivel átlagosan λ igény érkezik be egységnyi id® alatt, ezért egy t hosszúságú intervallum alatt szükségképpen átlagosan λt igénynek kell beérkeznie, ami azt is jelenti egyben, hogy a t id® alatt beérkez® igények várható értéke λt. Ez a megállapítás könnyen igazolható. Jelöljük egy pillanatra K -val a t hosszúságú intervallum alatt beérkez® igények számát. Ekkor: E(K) =
∞ X k=0
kPk (t) = e
−λt
∞ ∞ ∞ X X X (λt)k (λt)k (λt)k −λt −λt k =e k = e λt k k! (k − 1)! k! k=0 k=1 k=0
8
Mivel tudjuk, hogy ex = 1 + x + x2 + ..., azt kapjuk, hogy E(K) = λt [3] Vegyük sorra, hogy melyek azok a fontos tulajdonságok, melyek miatt a Poissonfolyamat alkalmazható a sorbanállás elméletében.[5] 1. A Poisson-folyamat homogén, vagyis X(s, s + t)-vel jelölve a t hosszúságú (s, s + t) intervallum alatt történ® beérkezések számát, P (X(s, s + t) = k) =
(λt)k e−λt k!
nem függ attól, hogy hol helyezkedik el az intervallum, azaz független az intervallum s kezd®pontjától. 2. A beérkezések számára vonatkozó szórás és várható érték megegyezik, mindkett® a λt képlettel számolható. 3. Ha tekintünk két Poisson-folyamatot λ1 és λ2 paraméterekkel, akkor a két folyamat összeolvasztásával nyert folyamat szintén Poisson-folyamat lesz, méghozzá λ1 + λ2 paraméterrel. 4. Poisson-folyamat esetén a beérkezési id®közök független exponenciális eloszlású valószín¶ségi változók. 5. Az exponenciális eloszlás esetén a beérkezés valószín¶sége független attól, hogy a legutolsó beérkezést®l számítva mennyi id® telt már el. Tehát egy exponenciális eloszlású valószín¶ségi változó jöv®je független a múltbeli viselkedését®l, az eloszlás id®ben állandó marad. Sajnos a születési-halálozási folyamatok id®t®l függ® megoldása nehezen kezelhet®, amint bonyolultabb születési-halálozási λk , µk intenzitásokat veszünk. Továbbá, még ha a Pk (t) függvényeket meg is tudnánk határozni, nem világos, mennyire segít minket ez a függvényhalmaz abban, hogy jobban át tudjuk tekinteni a sorbanállási rendszer viselkedését. Ezért természetes, hogy azt kérdezzük, vajon a Pk (t) valószín¶ségek t növekedésével megállapodnak-e végül, megsz¶nik-e id®beli változásuk, beáll-e stacionárius állapot. Egy születési-halálozási folyamat egyensúlyi eloszlása a következ® zárt alakban írható: P k = P0
k−1 Y i=0
λi , µi+1
k = 0, 1, 2, .... 1
P0 = 1+
∞ k−1 P Q k=1 i=0
9
. λi µi+1
Vizsgáljuk meg a Pk stacionárius valószín¶ségek létezésének feltételeit. Azt kell megnézni, hogy ezek a mennyiségek valóban valószín¶ségeloszlást alkotnak-e. Ehhez szükséges, hogy a P0 > 0 legyen. Ez az egyenletekben szerepl® születési és halálozási együtthatókra ró ki feltételt. Megköveteljük, hogy a rendszer alkalomadtán üres is legyen. Az, hogy ez feltétele a stabilitásnak rögtön ésszer¶nek látszik. A felmerül® lehet®ségek osztályozásához de niáljuk az alábbi két összeget: ∞ k−1 X Y λi S1 := , µ i+1 k=0 i=0
S2 :=
∞ X
λk
k=0
1 k−1 Q i=0
. λi µi+1
Ekkor három eset lehetséges. Azt mondjuk, hogy a születési-halálozási folyamat minden állapota 1. ergodikus, ha S1 < ∞ , S2 = ∞ ; 2. rekurrens nulla, ha S1 = ∞ , S2 = ∞ ; 3. átmeneti, ha S1 = ∞ , S2 < ∞. A sorbanállási rendszerek vizsgálata során szükségünk lesz egyensúlyi állapotban valamely születési-halálozási folyamat állapotára a születési és halálozási pillanatokban. Jelölje Nsz a születés és Nh a halálozás id®pontjában a rendszer állapotát, továbbá legyen Πk = P (Nsz = k) és Dk = P (Nh = k) k = 0, 1, 2, .... Ekkor: (λk h + o(h))Pk λ k Pk Πk = lim P = P ∞ ∞ h→0 λj h + o(h))Pj λj Pj j=0
továbbá
j=0
(µk+1 h + o(h))Pk+1 µk+1 Pk+1 Dk = lim P = P . ∞ ∞ h→0 µj h + o(h))Pj µ j Pj j=0
λ
Mivel teljesül, hogy Pk+1 = k Pk µk+1 ezért
j=0
k = 0, 1, ...
λk P k Dk = P ∞ λi Pi i=0
10
k = 0, 1, ...
Teljesül továbbá, hogy egyensúlyi állapotban az átlagos születési intenzitás egyenl® az átlagos kihalási intenzitással, ugyanis ¯= λ
∞ X i=0
λi Pi =
∞ X
µi+1 Pi+1 =
i=0
∞ X k=0
11
µ k Pk = µ ¯.
2. fejezet
Az M/M/1 típusú sorbanállási rendszer
Az M/M/1 rendszer a legegyszer¶bb, nemtriviális végtelen-forrású rendszer, azaz olyan rendszer, melyben végtelen hosszúságú sorok is létrejöhetnek, feltesszük továbbá, hogy az igényeket az érkezés sorrendjében szolgálják ki. Az M/M/1 típusú rendszerben a beérkezési folyamat λ paraméter¶ Poisson folyamat, vagyis az igények λ paraméter¶ exponenciális eloszlás szerint érkeznek a rendszerbe, a kiszolgálási id®k pedig µ paraméter¶,szintén exponenciális eloszlású valószín¶ségi változók. Feltesszük, hogy a beérkezési id®közök valamint a kiszolgálási id®k függetlenek egymástól. A továbbiakban jelölje X(t) a rendszerben tartózkodó igények számát. Azt mondjuk, hogy a rendszerünk a k állapotban van, ha X(t) = k . Mivel a fellép® valószín¶ségi változók exponenciális eloszlásúak, vagyis emlékezet nélküliek, az X(t) folytonos idej¶ Markov-lánc lesz. Vizsgáljuk meg a rendszer állapotváltozásainak valószín¶ségeit egy adott h id®tartam alatt: ∞ X pk,k+1 (h) = (λh+o(h))(1−(µ(h)+o(h)))+ (λh+o(h))k (µ(h)+o(h))k−1
k = 0, 1, 2, ....
k=2
Az összeg els® tagja annak a valószín¶sége, hogy a rendszerben egy igény érkezett, és nem szolgáltak ki egyet sem. Az összeg második tagja pedig annak a valószín¶ségét adja, hogy a rendszerbe 2 vagy több igény érkezett, és a beérkezettnél eggyel kevesebb került kiszolgálásra. Ez a valószín¶ség azonban o(h)-val egyenl®, így eredményül kapjuk, hogy: pk,k+1 (h) = λh + o(h).
Annak valószín¶sége, hogy a rendszer a k állapotból a k − 1 állapotba lépett h id®tartam után, a következ® módon számolható: pk,k−1 (h) = (µh + o(h))(1 − (λ(h) + o(h))) +
∞ X k=2
12
(λh + o(h))k−1 (µ(h) + o(h))k = µh + o(h)
Észrevehetjük tehát, hogy egy olyan születési-halálozási folyamattal van dolgunk, amit a születési és halálozási intenzitások alábbi megválasztásával jellemezhetünk: λk = λ,
k = 0, 1, 2, ...,
µk = µ,
k = 1, 2, 3....
Ez azt jelenti, hogy esetünkben az összes születési intenzitás λ, valamint az összes halálozási intenzitás µ. Az így nyert intenzitásokat behelyettesítve a születési-halálozási folyamat egyensúlyi állapotára vonatkozó képletbe, a következ®t kapjuk: k−1 Y
Pk = P0
i=0
azaz,
k λ Pk = P 0 , µ
λ , µ
k ≥ 0.
Az ergodikusság feltétele általánosságban (és így annak is, hogy egy Pk > 0 stacionárius megoldást kapjunk) S1 < ∞ és S2 = ∞; esetünkben az els® feltétel: S1 =
∞ X Pk k=0
=
P0
∞ k X λ
µ
k=0
< ∞.
Ez a sor akkor és csak akkor lesz konvergens, ha λ/µ < 1.
A második feltétel jelen esetben az alábbi alakba írható: S2 =
∞ X k=0
∞
X1 µ 1 = ( )k = ∞ Pk λ λ λ( ) k=0 P0
Ez akkor teljesül, ha λ/µ ≤ 1. Tehát arra a megállapításra juthatunk, hogy az ergodikusság szükséges és elégséges feltétele az M/M/1 sor esetén egyszer¶en λ < µ. Ez alapján P0 valószín¶ségek kiszámolhatóak a következ® képlet segítségével: P0 = 1+
1 ∞ P k=1
λ k µ
.
Mivel a fenti számolás alapján az ergodikusság feltétele λ < µ volt, ezért a fenti sor konvergens, azaz: P0 =
1
1+
λ/µ 1−λ/µ
13
=1−
λ . µ
A kihasználtsági tényez® % = µλ vagy 1. A stabilitás feltétele miatt a 0 ≤ % < 1 egyenl®séget meg kell követelni. Ez biztosítja, hogy P0 > 0 legyen. Így Pk = (1 − %)%k ,
k = 0, 1, 2, ...,
amely valóban valószín¶ségi eloszlás, nevezetesen a geometriai eloszlás. Ahhoz, hogy alkalmazni tudjuk a sorbanállás elméletet a gyakorlatban is, nézzük meg, hogy tudjuk kiszámolni a rendszer legf®bb jellemz®it.
A rendszerben tartózkodó igények átlagos száma N=
∞ X
kPk = (1 − %)%
∞ X
k=0
= (1 − %)%
k=1
∞ X ∂%k k=1
k%k−1 =
∂%
= (1 − %)%
∂ 1 % = ∂% 1 − % 1−%
A rendszerben eltöltött átlagos id® A rendszerben töltött átlagos id® meghatározásához a rendszerben tartózkodó igények száma közvetlenül felhasználható: T =
% 1 1/µ N =( )( ) = λ 1−% λ 1−%
A T id® függ a % kihasználtsági tényez®t®l. T értéke % = 0 esetén egyetlen igény átlagos kiszolgálási ideje, azaz ha a sorbanállással nem telik el id®, akkor átlagosan 1/µ lesz a tejesen rendszerid®. Azonban ha % közeledik 1-hez, a rendszerben tartózkodó igények száma és az igények rendszerben töltött átlagos ideje is meredeken n®. Vegyük észre, hogy % = 1 esetén a rendszer instabilan viselkedik, ugyanis % < 0 volt az ergodikusság feltétele. Meglep® azonban, hogy a rendszerbeli igények átlagos száma és az átlagos rendszerben töltött id® megromlik, ha % → 1 alulról. M/M/1 sor esetén azt tapasztalhatjuk, hogy nagy ára van annak, ha ki akarjuk használni a rendszer kapacitását. Ezen jelenség magyarázta, hogy a folyamat véletlen jellegének következtében id®nként a forgalom jelent®sen megugorhat, és ilyenkor id®legesen túlterhel®dik a kiszolgálócsatorna. Igaz marad azonban, hogy a kiszolgálócsatorna az id® P0 hányadában üres, de ez az átlagos üresjárati id® nincs egyenletesen elosztva kicsiny id®intervallumokra, csupán a hosszú m¶ködési szakaszokon érvényesül. Tehát a beérkezési id®köz és a kiszolgálási id® változékonysága okozza a rossz viselkedést % = 1 közelében.
14
A várakozó igények átlagos száma A kiszolgálási folyamat egy igényre nézve két f® részb®l áll. El®ször az igény arra vár, hogy sorra kerüljön(addig nyilván az el®tte lév®eket szolgálják ki), majd az ® kiszolgálása következik. ∞ ∞ ∞ Q=
X
(k − 1)Pk =
k=1
X
X
kPk −
k=1
Pk = N − % =
k=1
%2 1−%
A szerver kihasználtsága U s = 1 − P0 =
ahol P0 =
λ = %, µ
1 λ 1 λ
+ Eδ
,
a képletben Eδ a kiszolgáló átlagos foglaltsági periódushossza, λ1 a tétlenségi id® várható értéke. Mivel a szerver addig tétlen, amíg igény nem érkezik, az pedig exponenciális eloszlású λ paraméterrel. Így 1−%=
melyb®l Eδ =
1 λ
1 λ
+ Eδ
,
1 % 1 1 = N= . λ1−% λ µ−λ
Egy igény várakozási idejének eloszlása Jelölje Pk (t) - mint korábban is - annak valószín¶ségét, hogy a t pillanatban a rendszer a k állapotban van, Rk (t)) pedig annak valószín¶ségét, hogy egy a t pillanatban érkez® igény a rendszert a k állapotban találja. Megmutatjuk, hogy olyan sorbanállási rendszernél, amelybe az igények Poisson-folyamat szerint érkeznek, Pk (t) = Rk (t)
Legyen A(t, t + ∆t) az az esemény, hogy egy beérkezés történik a (t, t + ∆t) id®intervallumban. Ekkor: Rk (t) := lim P (X(t) = k|A(t, t + ∆t)) , ∆t→0
ahol X(t) jelöli a rendszerbeli igények számát a t id®pontban. Használjuk fel a feltételes valószín¶ség de nícióját. Ez alapján kapjuk, hogy: P (X(t), A(t, t + ∆t)) P (A(t, t + ∆t)|X(t) = k)P (X(t) = k) = lim ∆t→0 ∆t→0 P (A(t, t + ∆t) P (A(t, t + ∆t)
Rk (t) = lim
15
korábban láttuk, hogy Poisson-folyamat esetén (az emlékezetnélküliség miatt) az A(t, t + ∆t) esemény nem függ a t pillanatban a rendszerben tartózkodó igények számától (és magától a t id®t®l sem), ezért P (A(t, t + ∆t)|X(t) = k) = P (A(t, t + ∆t)) ,
így Rk (t) = P (X(t) = k).
Azt kaptuk tehát, hogy annak valószín¶sége, hogy egy beérkez® igény a rendszert a k állapotban találja, megegyezik azzal a valószín¶séggel , hogy a rendszer a k állapotban van. Világos, hogy ha egy tetsz®leges pillanatban egy igény érkezik, P0 lesz annak a valószín¶sége, hogy nem kell várakoznia, hisz ekkor a rendszer üres. Minden más esetben várakozni kényszerül. Tegyük fel, hogy az érkezés pillanatában n igény tartózkodik a rendszerben. Ekkor az érkez® igénynek meg kell várnia, míg a kiszolgálás alatt álló igény kiszolgálása befejez®dik és az el®tte álló n − 1 igény elhagyja a rendszert. Feltettük, hogy a kiszolgálások egymástól függetlenek és µ paraméter¶ exponenciális eloszlásúak. Köztudott, hogy az exponenciális eloszlás emlékezetnélküli, így a kiszolgálás alatt lev® igény eloszlása független attól mióta folyik a kiszolgálás, ezért a várakozási id® Γ vagy Erlang - eloszlású µ és n paraméterrel. Az Erlang-eolszlás s¶r¶ségfüggvénye a következ® alakot ölti: n−1 fn (x) =
µ(µx) e−µx , (n − 1)!
x ≥ 0.
Ha fW -vel jelöljük egy tetsz®leges igény várakozási idejének s¶r¶ségfüggvényét, akkor a teljes valószín¶ség tételét felhasználva az alábbi összefüggés adódik: fW (x) =
∞ X (µx)n−1 n=1
(n − 1)!
−µx n
% (1 − %) = (1 − %)%µ
µe
∞ X (µx%)k k=0
k!
e−µx = (1 − %)%µe−µ(1−%)x
Tehát x = 0fW (x) = (1 − %)%µe−µ(1−%)x
fW (0) = 1 − %
x>0
Ez alapján felírható a várakozási igény eloszlásfüggvénye: FW (x) = 1 − % + % 1 − e−µ(1−%)x = 1 − %e−µ(1−%)x .
Melyb®l az átlagos várakozási id®: Z∞ W =
xfW (x)dx =
% 1 = %Eδ = N . µ(1 − %) µ
0
16
Rendszerben való tartózkodási id® eloszlása Az el®z®höz hasonló számolással kaphatjuk a megfelel® eloszlást, azonban ebben az esetben egy igény akkor hagyja el a rendszert, ha ®t kiszolgálták, vagyis az Erlang-eloszlásunk paraméterei most µ és n + 1 lesznek. A s¶r¶ségfüggvény: fT (x) =
∞ X
(1 − %)%
n n (µx)
n!
n=0
−µx
µe
−µx
= µ(1 − %)e
∞ X (%µx)n n=0
n!
= µ(1 − %)e−µ(1−%)x
Az eloszlásfüggvény pedig: FT (x) = 1 − e−µ(1−%)x .
Látható tehát, hogy a tartózkodási id® exponenciális eloszlású, méghozzá µ(1−%) = µ−λ paraméterrel. Ezért az átlagos rendszerbeli tartózkodási id®: T =
1 1 = . µ(1 − %) µ−λ
Megállapítható néhány összefüggés a meghatározott mennyiségek között: T =W+
1 % 1 1 1 = + = = = Eδ. µ µ(1 − %) µ µ(1 − %) µ−λ
Vegyük észre továbbá, hogy: (∗)
λT = λ
1 % = = N. µ(1 − %) 1−%
valamint (∗∗)
λW = λ
%2 % = = Q. µ(1 − %) 1−%
A (*) és a (**) összefüggéseket Little-formuláknak nevezzük. Érdemes kiszámolni annak valószín¶ségét is, hogy legalább k igény tartózkodik a rendszerben: P P∞ i k P [rendszerben lév® igények száma> k ]= ∞ i=k pi = i=k (1 − %)% = %
17
A Little-törvényr®l A rendszerben tartózkodó igények átlagos száma, és az általuk a rendszerben töltött átlagos id® fontos mennyiségek a sorbanállás szempontjából. A Little-törvény összekapcsolja ezeket a mennyiségeket a beérkezési intenzitás segítségével. A törvény bizonyítása John Dutton Conant Little, amerikai matematikustól származik, melyet 1961-ben publikál [6]. A Little - törvény azt mondja, hogy állandó körülmények között, a sorbanállási rendszerben tarózkodó igények átlagos száma, megegyezik a beérkezési intenzitás és az átlagos rendszerben eltöltött id® szorzatával [7]. Tehát a már korábban bevezetett jelöléseket felhasználva: N = λT
Megköveteljük a háttérben rejt®z® sztochasztikus folyamat stacionárius voltát, azonban nem vesszük gyelembe, hogy hány kiszolgálóegységünk van, egy sorban, esetleg több sorban várakoznak az igények, milyen a kiszolgálási id® vagy várakozási id® eloszlása. Ebb®l adódóan ez a képlet rendkívül egyszer¶ és hasznos. A képlet legalább két mennyiségét általában könny¶ meghatározni (becslésekkel, meg gyelésekkel), és a harmadik paraméter ezekb®l már egyszer¶en adódik. Tekintsük a következ® példát [7]: Meg szeretnénk határozni, hogy egy kórház szülészetén hány ágyra van szükség, hogy az ott dolgozók megfelel®en el tudják látni a munkájukat.Korábbi évek tapasztatai alapján tudjuk, hogy a vizsgált városban átlagosan öt gyerek születik naponta. Az esetek 90 százalékában az újszülöttek két nap után hazamehetnek, a fennmaradó 10 százalékban, azonban valamiféle komplikáció következtében kénytelenek egy hétig a kórházban maradni. Tehát átlagosan 0, 9 · 2 + 0, 1 · 7 = 2, 5 napot maradnak a gyerekek a kórházban. A Little-törvény segítségével az adatok alapján megjósolható, hogy átlagosan hány anyuka tartózkodik a szülészeten naponta. A beérkezési intenzitás most λ = 5 (naponta), a rendszerben töltött várakozási id® 2, 5 nap. Ebb®l következ®en a "várakozó sor" átlagos hossza: N = 12, 5. Azt kaptuk, hogy átlagosan 12.5 anyuka tartózkodik a kórházban, tehát legalább 13 ágyra szüksége van az adott kórháznak ahhoz, hogy mindenkit el tudjanak látni.
18
3. fejezet
Prioritásos M/M/1 rendszer
A prioritásos M/M/1 rendszer,az M/M/1 rendszer egy olyan módosítása, amelyben a beérkez® igényeknek többféle típusát különböztetjük meg. Az egyszer¶ség kedvéért olyan rendszerrel foglalkozunk, melyben a beérkez® igényeknek két típusa lehetséges, de a modell kiterjeszthet® több különböz® típusú igény esetére is. Általában az alacsonyabb sorszámú igények élveznek prioritást a magasabb sorszámú igényekkel szemben. Az igények továbbra is független Poisson-eloszlás szerint érkeznek, az egyes típusú λ1 , míg a kettes típusú λ2 paraméterrel. Tegyük fel, hogy az egyes típusuktól eltekintve a kiszolgálási intenzitás paramétere µ. Jelölje a továbbiakban ρi a λi /µ mennyiséget. Ekkor a prioritásoknak két különböz® fajtáját különböztethetjük meg ([2],[5]). 3.1. A megszakításos rendszer
Megszakításos rendszer esetén az egyes típusú igények abszolút prioritást élveznek a kettes típusú igényekkel szemben. Ez azt jelenti, hogy egy egyes típusú igény érkezésekor, a kettes típusú igény kiszolgálása azonnal megszakad, és a m¶velet az egyes típus kiszolgálásával folytatódik. Kettes típusú igény már csak akkor kerül újra kiszolgálásra, ha nincs a rendszerben több egyes típusú. Ekkor a kettes típusú igények kiszolgálása ott folytatódik, ahol megszakításra került. Jelöljük most Ni -vel az i típusú igények számát, továbbá Ti -vel az i típusú igények rendszerben tartózkodásának idejét. Határozzuk meg ezen mennyiségek várható értékét. Mivel az egyes típusú igények abszolút prioritással bírnak, ezért E(T1 ) =
1/µ 1 − ρi
E(N1 ) =
ρi 1 − ρi
továbbá
19
Ez azért lehetséges, mert a prioritás miatt az egyes típusú igények kiszolgálását a rendszerben lév® kettes típusú igények nem befolyásolják. Mivel típustól függetlenül a kiszolgálási intenzitás megegyezik, így a rendszerben tartózkodó igények a kiszolgálás sorrendjét®l független. Így ez az érték megegyezik azzal, amikor az érkezési sorrend szerint történik a kiszolgálás. Az M/M/1 rendszernél levezetett képletek felhasználásával: E(N1 ) + E(N2 ) =
ρ1 + ρ2 1 − ρ1 − ρ2
Haználjuk fel az egyes típusú igényekre kapott képletet.Ekkor: E(N2 ) =
ρi ρ2 ρ1 + ρ2 − = 1 − ρ1 − ρ2 1 − ρi (1 − ρ1 )(1 − ρ1 − ρ2 )
A Little-törvény alkalmazásával adódik, hogy: E(T2 ) =
1/µ E(N2 ) = λ2 (1 − ρ1 )(1 − ρ1 − ρ2 )
3.2. A kivárásos rendszer
A prioritások második típusa az úgynevezett relatív prioritás. Ebben az esetben az egyes típusú igényeknek majdnem abszolút prioritása van, ami azt jelenti, hogy az egyes típusú igény érkezésekor a kettes típusú igény kiszolgálása nem szakad meg, de ahogy annak kiszolgálása befejez®dik,az egyes típusúak kiszolgálása következik függetlenül attól, hogy a soron következ® igény kettes típusú volt. Az egyes típusú igények átlagos tartózkodási idejére a következ® képlet írható fel: E(T1 ) = E(N1 )
1 1 1 + + ρ2 µ µ µ
Az utolsó tag azt jelöli, hogy amikor egy érkez® egyes típusú igény kettest típusút talál kiszolgálás közben, akkor mindaddig várnia kell, amíg annak kiszolgálása be nem fejezodik. A Poisson-folyamat szerinti érkezésnek köszönhet®en annak a valószín¶sége, hogy az egyes típusú beérkez® igény kettes típusút talál megegyezik a kettes típusú igényekre vonatkozó kihasználtsággal, amely ρ2 . Alkalmazzuk a Little-törvényt, azaz: E(N1 ) = λ1 E(T1 ),
amib®l:
(1 + ρ2 )/µ 1 − ρ1 (1 + ρ2 )/ρ1 E(N1 ) = 1 − ρ1 E(T1 ) =
20
4. fejezet
Az M/M/1/K rendszer
AZ M/M/1/K rendszer egy véges befogadóképesség¶ rendszer. Ez azt jelenti, hogy a várakozó igények száma korlátozva van, méghozzá oly módon, hogy ha a rendszerbe érkez® igények száma meghaladja a meghatározott maximumot, akkor az ezen felül érkez® igények kiszolgálás nélkül kénytelenek távozni. Tegyük fel, hogy a rendszerben egyszerre K igény tartózkodhat, melybe beleszámoljuk az éppen kiszolgálandó igényt is. Az igények érkezése továbbra is Poisson-folyamat szerint történik. A változás abban rejlik, hogy csak azok az igények léphetnek be a rendszerbe, amelyek érkezésekor kevesebb, mint K igény van ott. Egy telefonközpont esetében például megoldást jelent a "várakozó üzemmód", amikor a beérkez® igények korlátos várakozó sort alkotnak ([3]). Mivel a bemen® igények száma korlátozott, ezért a beérkezéseket leíró Poisson-folyamatot is korlátoznunk kell. Ekkor a beérkezési intenzitások a következ® alakot öltik: λ ,ha k < K λk = 0 ,ha k > K
A kiszolgálási intenzitást leíró paraméter pedig változatlan marad: µk = µ,
k = 1, 2, ..., K.
Mivel a rendszer állapottere véges, ez garanciát ad arra, hogy mindig ergodikus. Továbbá teljesül, hogy: k−1 Y
k λ λ Pk = P 0 = P0 , µ µ j=0
21
ha k ≤ K.
Természetesen az is igaz, hogy: Pk = 0, ha k > K,
hiszen csak K igény tartózkodhat a rendszerben. Már csak a P0 valószín¶ség kiszámítására van szükség: " P0 = 1 +
K X λk k=1
#−1 =
µ
1 − λ/µ 1 − (λ/µ)K+1
A két eredmény összevetésével végül azt kapjuk, hogy: Pk =
1−λ/µ ( λ )k 1−(λ/µ)K+1 µ
,ha 0 6 k 6 K ,egyébként
0
Látható, hogy ha K = 1, akkor egy M/M/1/1 rendszert kapunk, ahol tehát nincs várakozás ([3]). Ekkor: Pk =
,ha k = 0
1 1+λ/µ
,ha k = 1 = K
λ/µ
1+λ/µ 0
, egyébként
AZ M/M/1 rendszer vizsgálatakor már láttuk, hogy a rendszer kihasználtsága, azaz Us = 1 − P0 , továbbá Eδ az a mennyiség, amely megmutatja, hogy átlagosan mennyi ideig foglalt az adott kiszolgálóegység.
4.1. A rendszer f®bb jellemz®i
A rendszerben tartózkodó igények átlagos száma N=
λ/µ(1 − (K + 1)(λ/µ)K + K(λ/µ)K+1 ) (1 − (λ/µ)(1 − (λ/µ)K+1 )
A várakozó igények átlagos száma K K K X X X Q= (k − 1)Pk = kPk − Pk = N − Us k=1
k=1
k=1
A tartózkodási és várakozási id® jellemz®inek meghatározásához azt kell tudni, hogy beérkez® igény milyen állapotban találja a rendszert. A Bayes-formula felhasználásával
22
látható, hogy: Πk =
λPk K−1 P
=
λPi
Pk 1 − Pk
i=0
Az M/M/1 rendszer vizsgálatakor már láttuk, hogy a feltételes tartózkodási és várakozási id®k Erlang-eloszlást követnek, ebben az esetben (k + 1, µ) és (k, µ) paraméterrel, amennyiben a rendszerben k igény tartózkodott az új igény rendszerbe érkezésének pillanatában. Azt kapjuk, hogy: T =
K−1 X k=0
K−1 K−1 X k + 1 ρ k P0 X 1 k+1 N Πk = = (k + 1)Pk+1 = µ µ 1 − Pk λ(1 − PK ) k=0 λ(1 − PK ) k=0
Amib®l következik, hogy W =T−
1 N 1 = − µ λ(1 − PK ) µ
Nézzük meg, hogy ebben az esetben is teljesül-e a Little formula? A rendszerbe történ® átlagos beérkezés λ = λ(1 − PK ), éppen ezért: λT = λ(1 − PK ) λW = λ
N =N λ(1 − PK )
N 1 λ − = N − = N − ρ(1 − PK ) = N − US = Q λ(1 − PK ) µ µ
A tartózkodási id® s¶r¶ségfüggvénye és eloszlásfüggvénye A teljes valószín¶ség tételéb®l adódik, hogy K−1 X
(µx)k −µx Pk e fT (x) = µ k! 1 − PK k=0
Ez alapján az eloszlásfüggvényt a s¶r¶ségfüggvény integrálásával tudjuk kiszámítani: FT (x) =
K−1 X Z x k=0
1
! K−1 k X X (µt)k −µt Pk (µx)i −µx Pk µ e dt = 1− e = k! 1 − PK i! 1 − PK i=0 k=0 =1−
K−1 X
k X (µx)i
k=0
i=0
i!
! e−µx
Pk 1 − PK
Bonyolultabb formulákkal kellett számolnunk, mint az M/M/1 rendszer esetében, azonban ha K → ∞, akkor fT (x) = µ(1 − ρ)e−µ(1−ρ)x
23
Most vizsgáljuk meg a várakozási id® s¶r¶ségfüggvényét is: fW (0) = K−1 X
fW (x) =
µ
k=0
P0 1 − PK
(µx)k−1 −µx Pk e (k − 1)! 1 − PK
Ez alapján az eloszlásfüggvény: K−1
X P0 + FW (x) = 1 − PK k=0 =1−
1−
k−1 X (µx)i
i!
i=0
K−1 X
k−1 X (µx)i
k=1
i=0
i!
! e−µx
! e−µx
Pk = 1 − PK
Pk 1 − PK
Vegyük észre, hogy PK valószín¶ségek kitüntetett szereppel bírnak az egyes képletekben. Mit is jelent ez a valószín¶ség? PK nem más, mint annak az esélye,hogy a rendszerhez érkez® igény nem tud csatlakozni a sorhoz, mert nincs hely. Ezt a valószín¶séget a szakirodalom igényvesztési valószín¶ségnek nevezi, és általában PB -vel jelöli. A Bayes-formulát felhasználva tudjuk kiszámítani, hogy: λPK
PB =
K P
λPK
k=0
Ha jobban megvizsgáljuk ezt az összefüggést, látható, hogy PB valószín¶ség függ ρ-tól is, tehát K PB (K, ρ) =
ρ
K P
ρk
k=0
A fenti képletet átalakítva adódik, hogy PB (K, ρ) =
ρρK−1 K−1 P
=
ρk + ρρK−1
ρPB (K − 1, ρ) 1 + ρPB (K − 1, ρ)
k=0
1
Induljunk ki a PB (1, ρ) = kezdeti valószín¶ségb®l. Ekkor az igényvesztés többi 1+ρ valószín¶ségét meghatározhatjuk rekurzív módon. Mivel ez a sorozat ρ < 1 esetén 0-hoz tart, ezért rekurzióval biztosan található olyan K , melyre PB (K, ρ) < P ∗ ,
ahol P ∗ egy el®re megadott korlát az igényvesztés valószín¶ségére. 24
K meghatározásához azonban a
ρK (1 − ρ) < P ∗ egyenl®tlenséget kell megoldanunk, 1 − ρK+1
ami bonyolult feladat. Ehelyett azonban választhatunk egy közelít® megoldást, melynek lényege, hogy egy M/M/1 rendszer esetén kiszámítjuk, hogy mi lesz annak a valószín¶sége, hogy a rendszerben legalább K igény tartózkodik, majd ennek segítségével közelítjük a szükséges értéket. Mivel ∞ ρK (1 − ρ) X k PB (K, ρ) = < ρ (1 − ρ) = ρK , K+1 1−ρ k=K
vagyis ρK < P ∗
Amennyiben a fenti egyenl®tlenség teljesül, igaz lesz az is, hogy PB (K, ρ) < P ∗ K érték megtalálásához logaritmizáljuk mindkét oldalt: Klnρ < lnP ∗ K>
lnP ∗ lnρ
Tehát tényleg találhatunk megfelel® K -t a közelít® módszer segítségével.
25
5. fejezet
Sorbanállási rendszerek alkalmazásai
A sorbanállási rendszereknél leggyakrabban feltett kérdések a következ®k: • Az id® mekkora hányadában szabad a kiszolgálóhely? • Mennyi a sorbanálló ügyfelek átlagos száma? • Mennyi az ügyfél sorban eltöltött idejének várható értéke? • Mennyi a rendszerben eltöltött átlagos id®tartam? • Hány új kiszolgálóhelyet kell létesíteni ahhoz, hogy az átlagos várakozási id® bizo-
nyos arányban lerövidüljön? • Hogyan lehet a rendszer hatékonyságát javítani?
5.1. Egyszer¶bb feladatok megoldása
Néhány feladaton keresztül vizsgáljuk meg, hogy a tárgyalt sorbanállási rendszerek mellett ezek a mennyiségek hogyan is számíthatóak ki.
1. feladat Egy postán egyetlen ablaknál történik az ügyintézés. Az ügyfelek Poisson-folyamat szerint érkeznek, óránként átlagosan tízen, a kiszolgálási id® pedig exponenciális eloszlású 5 perc várható értékkel. a) Átlagosan hány ügyfél tartózkodik a hivatalban? b) Átlagosan mennyi id®t tölt el egy ügyfél a hivatalban a várakozással és kiszolgálással együtt? 26
c) Átlagosan mennyi id® telik várakozással? d) Ha véletlen id®pontban érkezünk a postára, mennyi a valószín¶sége, hogy legfeljebb ketten állnak el®ttünk?
Megoldás Az érkezési intenzitás 10 ügyfél óránként, a kiszolgálási pedig 12 ügyfél óránként, azaz a paramétereink most λ = 10 és µ = 12. a) E(N ) =
λ 10 = =5, azaz átlagosan 5 ügyfél tartózkodik a postán. µ − λ 12 − 10 1
1
b) E(T ) = = =0,5 , azaz átlagosan fél órát tartózkodnak az egyes ügyfelek µ − λ 12 − 10 a postán. c) E(W )=
λ 1 10 1 5 = = , azaz átlagosan 25 percet kell várakozással tölteniük. µ µ − λ 12 2 12 λ
λ λ
λ λ2
d) P (legfeljebb ketten állnak el®ttünk)=π0 +π1 +π2 = 1 − +(1 − ) +(1 − ) ≈ µ µ µ µ µ 0, 4213.
2. feladat Tekintsük az el®z® feladatunkat azzal a módosítással, hogy most három ablak is nyitva van, a kiszolgálás ideje pedig 6 perc várható érték¶. a) Tegyük fel, hogy véletlenszer¶en érkezünk meg a postára. Mekkora a valószín¶sége, hogy sorba kell állnunk? b) Átlagosan hány ügyfél tartózkodik a hivatalban? c) Átlagosan mennyi id®t tölt egy ügyfél a hivatalban? d) Átlagosan mennyi id®t kell az ügyfeleknek várakozással töltenie? e) Mi történne, ha az egyik ablak bezárna? És ha két ablak zárna be? Megjegyzésként megemlítem, hogy most az M/M/n rendszer használatára van szükségünk, amelyben a a beérkezési intenzitásλ paraméter¶ és állandó, viszont ebben az esetben n darab kiszolgálóegység áll rendelkezésre.
Megoldás a) Akkor kell sorba állnunk, ha mind a három ablak foglalt. Ez akkor fordul el®, ha legalább három ügyfél van a hivatalban. Ennek valószín¶sége: 27
5 1 − (π0 +π1 +π2 )=1 − ( 17 +
6 17
+
18 ) 85
≈ 0, 1411
b) Ebben az esetben nem használható az M/M/1 rendszerre levezetett formula, azonban kis módosítással már alkalmazhatóvá válik: ∞ ∞ ∞ ∞ ∞ k 5 6 P P P P P λ 6 E(N )= kπk = kπk = π1 + kπk = µλ π0 + k 29 3µ π0 = 17 + k 92 12 = + 30 17 17 k=0
9 5 12 2 17 30
∞ P k=2
k=1
12 k−1 30
= 176 + 179
k=2
∞ P k=1
12 k−1 30
k=2 6 9 − 1 = 17 + 17
1
(1− 12 30 )
2
k=2 − 1 = 22 17
c) A postán eltöltött átlagos id® meghatározásához felhasználhatjuk a Little-formulát: E(N )=λ E(T ) ⇒ E(T )=
1 1 E(N )= 12 λ
22 17
≈ 6, 47 perc
d) A várakozással eltöltött átlagos id® meghatározásához ismét felhasználhatjuk a Littleformulát: 1 1 8 E(Nω )= λ E(Tω ) ⇒ E(Tω )= E(Nω ) = 12 ≈ 0, 47 perc 85 λ
Meg gyelhetjük, hogy a várakozási id®, és a postán töltött összid® különbsége éppen 6 perc, ami pont az átlagos kiszolgálási id®, tehát jól számoltunk. e) Ha az egyik ablak bezárna, akkor a rendszer maximális teljesít®képessége 2µ azaz 20 f®/óra lenne,vagyis a 12 f®/óra érkezési intenzitás mellett még m¶köd®képes maradna. Ha két ablak zárna be, akkor a maximális teljesít®képesség 10 f®/óra lenne, ami kevesebb, mint az érkezési intenzitás, tehát a rendszer összeomlana.
3. feladat Tekintsünk egy M/M/1 típusú rendszert,és tegyük fel, hogy a beérkez® igényeknek két különböz® típusa lehet. A kiszolgálási id® exponenciális eloszlású 5 perc várható értékkel minden ügyfél esetében. Az 1. típusú ügyfelek közül óránként 4, míg a 2. típusú ügyfelek közül óránként 5 érkezik a kiszolgálóegységbe. Tegyük fel továbbá, hogy az 1. típusú ügyfelek prioritást élveznek a 2. típusú ügyfelekkel szemben. a) Átlagosan mennyi id®t töltenek az egyes ügyfelek a rendszerben, ha az 1. típusú igények abszolút prioritást élveznek a 2. típusú igényekkel szemben? b) Átlagosan mennyi id®t töltenek az egyes ügyfelek a rendszerben, ha az 1. típusú igények relatív prioritást élveznek a 2. típusú igényekkel szemben?
Megoldás A feladat alapján a rendszerünk paraméterei most: λ1 =4, λ2 =5 valamint µ=12. 28
a) A rendszerben tartózkodó 1. típusú ügyfelek átlagos száma: 4/12 ρ1 = 1−4/12 E(N1 )= 1−ρ = 21 1 Az 1. típusú ügyfelek rendszerben töltött átlagos ideje: 1/µ 1 1 E(T1 )= 1−ρ = µ−λ = 12−4 =7,5 perc 1 1
A rendszerben tartózkodó 2. típusú ügyfelek átlagos száma: ρ2 = E(N2 )= (1−ρ1 )(1−ρ 1 −ρ2 )
5/12 (1−4/12)(1−4/12−5/12)
= 25
A 2. típusú ügyfelek rendszerben töltött átlagos idejének kiszámításához használható a Little - formula: 2) E(T2 )= E(N = 5/2 = 12 , azaz 30 perc. λ2 5 b) Ebben az esetben, ha az érkez® 1.típusú igény 2. típusút talál kiszolgálás közben, akkor meg kell várnia, hogy a kiszolgálás befejez®djön. A rendszerben tartózkodó 1. típusú ügyfelek átlagos száma: 17 2 )ρ1 E(N1 )= (1+ρ = 24 1−ρ1 Az 1. típusú ügyfelek rendszerben töltött átlagos ideje: 1) E(T1 )= E(N = 17 , azaz 10,625 perc. λ1 96 A 2. típusú ügyfelek rendszerben töltött átlagos ideje: 1−4(1−9) 1 (1−ρq −ρ2 ))/µ E(T2 )= (1−ρ = (1−4)(1−9) = 11 , azaz 27,5 perc. (1−ρ1 )(1−ρ1 −ρ2 ) 24 Szeretnék említést tenni a dolgozatban ugyan részletesen nem tárgyalt rendszerr®l, nevezetesen az M/G/1 sorbanállási rendszerr®l. Az M/G/1 rendszerben szintén egy kiszolgálóegység van, a beérkezési folyamat Poisson-típusú, azonban a kiszolgálási id® eloszlása tetsz®leges lehet [3]. A formulák levezetése nélkül nézzük meg a rendszer jellemz®inek kiszámítási módját. A sorban tartózkodó igények átlagos száma: E(Q) =
λ2 σ 2 + (λ/µ)2 2 · (1 − λ/µ)
A rendszerben tartózkodó igények átlagos száma: E(N ) = E(Q) +
29
λ µ
A várakozással töltött átlagos id®: E(W ) =
E(Q) λ
A rendszerben eltöltött átlagos id®: E(T ) = E(W ) +
1 µ
Ezeket a formulákat felhasználva tekintsük a következ® feladatot:
4. feladat Egy M/M/1 modellel leírható sorbanállási rendszert alkotó gép esetében, a készül® munkadarabok átlagosan 30 percig várakoznak a rendszerben. A gép idejének 25 százalékában nem dolgozik, mert az egyes munkadarabok megérkezésére vár. Mennyivel csökkenne a munkadarabok rendszerben töltött átlagos várakozási ideje, ha a kiszolgálási id® szórását a jelenlegi érték negyedére csökkentenénk? Megoldás Tekintsük el®ször a jelenlegi rendszert és számoljuk ki a szükséges paramétereket a megadott információkból! Annak valószín¶sége, hogy a rendszer üres: P0 = 1 −
λ = 0, 25 µ
A rendszerben töltött átlagos id®: E(T )=
1 =30 perc. µ−λ
Továbbá: E(T )=
1 1/µ 1/µ 1 30 1 = = = = = óra µ−λ µ/µ − λ/µ 1 − λ/µ P0 60 2
Ekkor 1/µ 1 1 1 = , melyb®l = , azaz µ = 8. 0, 25 2 µ 8
Tehát a gépek 8 munkadarabot készítenek el óránként. Ezt az eredményt felhasználva: P0 =1 −
λ λ =1 − =0, 25 miatt λ = 6. µ 8
Azaz óránként 6 munkadarab érkezik a rendszerbe. Az exponenciális eloszlás tulajdonsága, hogy szórása és várható értéke megegyezik. Mivel a feladatban a kiszolgálási id®nek csak a szórása csökken, ezért ez a feltétel a továbbiakban 30
nem teljesül, azaz a kiszolgálási id® nem exponenciális eloszlású. A kiszolgálási id® várható értékének és szórásának ismeretében azonban alkalmazható az /M/G/1 rendszer. 1
1
= . Ekkor: Jelen esetben µ = 4µ 32 A várakozó igények átlagos száma 2 1 2 62 32 + 68 λ2 σ 2 + (λ/µ)2 153 E(Q) = = = . 6 2 · (1 − λ/µ) 128 2 · (1 − 8 )
A sorban eltöltött átlagos id®: E(W ) =
E(Q) 153/128 51 = = λ 6 256
A rendszerben töltött átlagos id®: E(T )=E(W ) +
1 51 = + 1 = 83 óra, azaz 19, 45 perc. µ 256 8 256
Azt kaptuk tehát, hogy a rendszerben eltöltött várakozási id® 10, 54 perccel csökkenne. 5.2. Kórházi sorok vizsgálata
A sorbanállás megjelenik az egészségügyben is. A betegek számára az egészségügyi ellátás egyik igen fontos tényez®je a szolgáltatás nyújtásához kapcsolódó várakozás. A várakozással töltött, elvesz® id® mértéke a betegnek az ellátással kapcsolatos elégedettségét jelent®sen befolyásolja, és kedvez®tlen esetben az ellátóról negatív kép alakulhat ki.A kiszolgálórendszer nem megfelel® méretezése ugyan akkor a szolgáltató számára felesleges többletköltséget generálhat, amely tovább rontja az intézmény pénzügyi helyzetét. Miért kell sorokban várakoznunk? Tekintsünk egy kórházi várótermet, amely óránként átlagosan ötven beteget képes befogadni, de még akkor is kialakulhat várakozó sor, ha az szám óránként harmincötre csökken. A rendszer kulcsszava az átlagos. A valóságban ugyanis a páciensek véletlenszer¶ id®pontokban érkeznek, és egyesek ellátási ideje tovább tarthat, mint másoké. Más szóval az érkezési és kiszolgálási id®kben változékonyság gyelhet® meg. Ebb®l adódik, hogy a várótermek id®legesen telítetté válhatnak, és a páciensek várakozni kényszerülnek, de el®fordulhat olyan eset is, amikor a váróterem üresjáratba kerül, azaz épp nincs ellátásra váró beteg. Az egészségügyi ellátást leíró sorbanállási modell megalkotásához a következ® jellemz®ket kell sorra vennünk, amelyek karakterizálják a rendszerünket. Figyelembe kell venni a beérkezési folyamatot, az érkezések egyediségét, a sorok jellemz®it, a kiszolgálás szabályait, a kiszolgálási és távozási folyamat jellemz®it. 31
Az egészségügyi ellátás vizsgálatakor az egyszer¶ség kedvéért végtelen forrású sorbanállási rendszereket tekintünk, azaz olyan modellt, amelyben a betegek száma nincs korlátozva. Így könnyebben kezelhet®vé válik a sor hosszával és a rendszer kapacitásával kapcsolatos esetlegesen felmerül® problémák megoldása. Minden egyes kiszolgálóegységre adott egy kapacitás, amely meghatározza, hogy hány pácienst képes ellátni az adott kiszolgálóegység.A kórházakat tehát az M/M/1/K rendszer segítségével reprezentálhatjuk. Az egyik legfontosabb jellemz® a beérkez® beteg száma és annak id®beli eloszlása. Felmerülhet a kérdés, hogy az elméletb®l ismert eloszlásokkal tudjuk-e jellemezni a kórházi ellátás beérkezési és kiszolgálási id®it. A valóságban bonyolultnak t¶nik a helyzet, hiszen az érkezési intenzitások a nap különböz® szakaszaiban eltér®ek lehetnek. El®fordulhatnak napszaki ingadozások, reggel általában több beteggel találkozhatunk a várótermekben, mint egy kés® délutáni id®pontban, ezek azonban a betegek orvoshoz fordulási szokásainak ismeretében becsülhet®k. Mind az elméleti megfontolások, mind a valós adatsorokon végzett vizsgálatok([8]) azt igazolják, hogy a betegek érkezése Poisson-folyamatot követ, vagyis az adott beteg érkezési ideje nem függ az el®z®ekt®l. A kórházi menedzsment célja, hogy az egyes napszakokra a legmegfelel®bb megoldást találja esetleg elcsúsztatott munkarenddel, vagy forgalmasabb id®szakokban beállított többlet személyzet segítségével. Az elemzéshez meg kell határozni azokat a beérkezési id®szakokat, amelyekben a beérkezési folyamat jellemz®i azonosak.Így az egyes id®tartamokon belül feltételezzük a beérkezési id®közök exponenciális eloszlását. Els® körben tegyük fel tehát, hogy az igények λ paraméter¶ Poisson-folyamat szerint érkeznek a rendszerbe úgy, hogy minden igény prioritása azonos, kiszolgálásuk során a FIFO elv érvényesül. A kiszolgálás történjen µ paraméter¶ Poisson-folyamat szerint, és tegyük fel, hogy egyszerre legfeljebb K igény tartózkodhat a rendszerben. Ekkor a stacionárius megoldás a következ® módon írtható fel: P0 =
1 − λ/µ 1 − (λ/µ)K+1
k λ Pk = P0 µ Kórházak összevonásának vizsgálata
A számolások elvégzéséhez az ötletet a 2007-es norvég kórházreform szolgáltatta [11]. Tekintsünk most két kórházat λ paraméter¶ Poisson-folyamat szerinti beérkezési és µ paraméter¶ Poisson-folyamat szerinti kiszolgálási id®kkel. 32
Kérdés: Mikor lenne hatékonyabb megoldás a két kórház összevonása? A két kórház összevonásával a beérkezések Poisson-folyamatának paramétere: λ1 + λ2 , a kiszolgálás Poisson folyamatának paramétere pedig µ1 + µ2 és így egy M/M/2/2K rendszert kapunk. Ekkor: 1
P0 = 1+
K P k=1
2
k λ µ
k λ Pk = 2P0 µ
Egy M/M/m/K rendszer állapotgiagrammja:
Számoljunk ki néhány valószín¶séget az egyes kórházak esetén külön-külön, majd az összevont kórházak paramétereit használva. Tekintsünk két kórházat, ahol id®egység alatt átlagosan 4 beteg érkezik, azaz λ = 4. A kórházak maximális sorhossza legyen 5, és tegyük fel, hogy mindkét kórházban egy rendel® üzemel. A kiszolgálás szintén Poisson-folyamat szerint történik, µ = 5 paraméterrel. El®ször tekintsük a kórházakat külön-külön, ekkor az M/M/1/K jellemz®i alapján kell a számításokat végezni.Tehát: 33
1 − λ/µ 1 − 4/5 = = 0, 27105 K+1 1 − (λ/µ) 1 − (4/5)6 k λ 1 − 4/5 4 1 − λ/µ = 0, 21684 = P1 = K+1 1 − (λ/µ) µ 1 − (4/5)6 5 2 1 − 4/5 4 P2 = = 0, 17347 1 − (4/5)6 5 3 4 1 − 4/5 = 0, 13878 P3 = 6 1 − (4/5) 5 4 1 − 4/5 4 P4 = = 0, 11102 1 − (4/5)6 5 5 1 − 4/5 4 P5 = = 0, 08881 6 1 − (4/5) 5 P0 =
Vizsgáljuk meg az eredményeket az összevonás után. Most az M/M/2/2K rendszerrel számolunk, azaz az érkezési intenzitás λ0 = λ1 + λ2 = 8, a kiszolgálás paramétere µ0 = µ1 + µ2 = 10, továbbá a sor maximális hossza 10.Ekkor: 1
P0 = 1+2
10 P k=1
= 0, 12283 8 k 10
λ 8 P1 = 2P0 = 2 · 0, 12283 · = 0, 19653 µ 10 2 8 = 0, 15722 P2 = 2 · 0, 12283 · 10 3 8 P3 = 2 · 0, 12283 · = 0, 12578 10 4 8 P4 = 2 · 0, 12283 · = 0, 10062 10 5 8 P5 = 2 · 0, 12283 · = 0, 08050 10 6 8 P6 = 2 · 0, 12283 · = 0, 06440 10 7 8 P7 = 2 · 0, 12283 · = 0, 05152 10 8 8 P8 = 2 · 0, 12283 · = 0, 04121 10
34
P9 = 2 · 0, 12283 · P10 = 2 · 0, 12283 ·
8 10
9
8 10
10
= 0, 03297 = 0, 02637
Little tételének segítségével felírhatjuk az átlagos várakozási id®t, és a sorban tartózkodó betegek átlagos számát. A sorban tartózkodó igények száma ugyanis egyenl® a beérkezési intenzitás és az átlagos várakozási id® szorzatával. E(N )=λE(T ), ahol
E(N ) =
K X
iPi
i=1
Ez alapján külön tekintve a kórházakat: E(N ) = 0, 21684 + 2 · 0, 17347 + 3 · 0, 13878 + 4 · 0, 11102 + 5 · 0, 08881 = 1, 86825 E(T ) =
1, 86825 = 0, 46706 4
Az összevont kórházak esetén is hasonló számolással adódik, hogy: E(N ) = 0, 19653 + 2 · 0, 15722 + 3 · 0, 12578 + 4 · 0, 10062 + 5 · 0, 08050 + 6 · 0, 06440+ +7 · 0, 05152 + 8 · 0, 04121 + 9 · 0, 03297 + 10 · 0, 02637 = 3, 33044
E(T ) =
3, 33044 = 0, 416305 8
A számítások során ktív adatokat használtam. Habár messzire men® következtetések nem vonhatóak le a kapott eredményekb®l, látható, hogy az összevont kórház esetén a várakozási id® valamelyest lecsökkent, tehát ha a két kórházba azonos számú beteg érkezik naponta, akkor érdemes a két kórház helyett egy összevont kórházat m¶ködtetni. Hasonló meggondoláshoz vezethet az a probléma is, ha az orvosok nem külön-külön fogadják a betegeket, hanem egyetlen várakozó sor kerül kialakításra. Azaz, ha nem kellene szakorvoshoz bejelentkezni, bizonyos mértékben csökkenhetne a várakozási id® a kórházakban.
35
Mi is az igazság?
A szakdolgozatom célja az volt, hogy betekintést nyújtson a sorbanállás matematikai hátterébe. Láthattuk, hogy a különféle rendszerek jól leírhatóak a valószín¶ségszámítás eszközeivel. Felmerülhet azonban a kérdés, hogy a valóságban mennyire alkalmazhatóak a kapott eredmények. A sorbanállást mindenki gy¶löli, de senki sem úszhatja meg. Ejtsünk néhány szót a mindennapokban leggyakrabban el®forduló jelenségr®l, a pénztáraknál való sorbanállásról. A pénztárakhoz véletlenszer¶en érkeznek a vev®k és ott szintén nem pontosan meghatározott id®t töltenek. Ez függ a vásárolt áruk jellegét®l és mennyiségét®l, a kért számlától, a zetési módtól, és jelent®sen befolyásolhatja egy leesett vonalkód vagy a nyilvántartási rendszer pontossága. A probléma kézenfekv®: az egyes napszakokban hány pénztárt kell nyitva tartanunk ahhoz, hogy a kialakuló várakozási sorok elfogadható méret¶ek legyenek. A kiszolgálás gyorsítására adódik még egy lehet®ség, az úgynevezett expressz sorok bevezetése. Ez azt jelenti, hogy a kevesebb tételt vásárlók számára külön pénztárakat jelölünk ki, itt a kiszolgálás várhatóan gyorsabban zajlik. Kérdés, hogy legyenek-e ilyen pénztárak, ha igen akkor hány. Amint látható, a zikai probléma jól megfogalmazható, de megoldása sok véletlen tényez®t®l függ. Több matematikus is foglalkozott a problémával,s legideálisabb megoldásnak az úgynevezett amerikai sort találták ([9],[10]). Itt a vev®k nem több külön sorba állnak be, hanem egyetlen hosszúba - ahonnan szétosztják ®ket a soron következ® szabad pénztárhoz. Ez a rendszer már Németországban is megszokott a reptereken, pályaudvarokon és postákon. A várakozási id® igazságosabb elosztásához vezet a vev®k között. Még ha az amerikai sor hosszabbnak is t¶nik és pár embert elriaszt: általában mégis gyorsabban halad. Ezzel a rendszerrel nem fordulhat el®, hogy az egyik áruházi dolgozó az egyik kasszánál unatkozik, míg a következ®nél hárman várják, hogy az elöl álló vev® kihalássza a pénz a pénztárcájából. Összességében igazságosabb a kiszolgálás és kevesebb az elpazarolt munkaid®. Alexander Herzog német matematikus szerint az áruházi sorok két szempontból is bosszantóak. El®ször is érdekes a kérdés, hogyan állhatunk a legintelligensebben sorba. A nem túl kielégít® válasza: két 36
hosszabb sor esetén majdhogynem mindegy, melyik mellett döntünk, ugyanis a kiszolgálási folyamat egyenetlenségei sokkal fontosabbak mint a sorok hosszának különbsége. A rövidebb sorban is csak az esetek felében szolgálnak ki valóban gyorsabban. Le kell szögezni, hogy az amerikai sor csak az ésszer¶en méretezett rendszerekben megoldás.Ha túl sok vev® jönne, ezzel a rendszerrel is sokáig kellene várniuk. Mindent összevetve, lehet®ség lenne olyan módszert találni, amivel lecsökkenthetnénk a várakozó sorok hosszát. A probléma azonban abból adódik, hogy szupermarketeket kevésbé foglalkoztatja a bosszankodó vásárlók lelki világa, ugyanis a vev®k várakozással töltött ideje a vállalkozásoknak elvben nem kerül pénzébe. Amikor a hosszabb várakozást vagy egy újabb pénztár nyitását veszik fontolóra, az üzemeltet®k többnyire a vev® ellenében és az alacsonyabb személyi kiadások mellett döntenek - mert a vev®k bosszúságát nem lehet csak úgy veszteségre átszámítani. A vásárlók a pénztárhoz érve tehát próbálkozhatnak különböz® taktikák bevetésével a gyors kiszolgálás reményében, ám a rengeteg küls® tényez® jelent®sen megnehezítheti a dolgukat.
37
Irodalomjegyzék
[1] Sztrik János, Bevezetés a sorbanállási elméletbe és alkalmazásaiba, Debreceni tem (2004) http://irh.inf.unideb.hu/ jsztrik/education/08/index.html [2] Sztrik János, A
(2004)
sorbanállási elmélet alapjai Debreceni Egyetem
[3] L. Kleinrock, Sorbanállás, kiszolgálás - Bevezetés méletébe, M¶szaki könyvkiadó, Budapest (1979) [4] Samuel Karlin - Howard M. Taylor, (1985) [5] Ivo Adan,Jacques Resing,
Egye-
a tömegkiszolgálási rendszerek el-
,
Sztochasztikus folyamatok
Gondolat,Budapest
Queueing Theory Department of Mathematics and Com-
puting Science Eindhoven University of Technology
2001
[6] John D.C. Little, A Proof of the Queuing Formula, Operational Research, Volume 9, Issue 3 (1961) 383-387 [7] John D.C. Little and Stephen C. Graves, Little's Law, Massachusetts Institute Technology, http://web.mit.edu/sgraves/www/papers/Little's20Law-Published.pdf [8] Kim-Horvitz-Young-Buckley, Analysis of capacity management of the intensive unit in a hospital, European Journal of Opertional Research 115 (1999) 41-46. [9] Rafael
Hassin,
To
Queue
or
not
to
http://www.math.tau.ac.il/ hassin/main.pdf
[10] Alexander Herzog, Spiegel (2008)
,
,
queue
Tel
Aviv
of
care
University
,
(2006) ,
Wartenschlagen Theorie Technischen Universität Clausthal
[11] Magnussen-Hagen-Kaarboe, Centralized or decentralized? A case study of Norwegian hospital reform , Social Science Medicine (2007)
38
