4. Előadás: Sorbanállási modellek, I. Wayne L. Winston: Operációkutatás, módszerek és alkalmazások, Aula Kiadó, Budapest, 2003 könyvének 20. fejezete alapján.
1.1.
A sorbanállási elmélet alapfogalmai
A sorbanállási elmélet két legfontosabb alapfogalma a beérkezési folyamat, a kimeneti vagy kiszolgálási folyamat. Néhány példa sorbanállási rendszerekre: 1) Banki ügyfélkiszolgálás. Ekkor a beérkezési folyamatot a bankfiókba véletlenszerűen beérkező ügyfelek, a kiszolgálást a banktisztviselők által végrehajtott különböző banki tranzakciók, a kimeneti folyamatot pedig a bankfiókból távozó ögyfelek jelentik. 2) Pizza házhozszállítás. Ebben a sorbanállási rendszerben a beérkezési folyamatot a pizzarendelések beérkezése, a kiszolgálást a pizzák elkészítés és dobozokba helyezése, a kimeneti folyamatot pedig a pizzák kerékpárokkal, vagy motorokkal történő kiszállításai jelentik. 3) Autóbusz karbantartó műhely. Ebben a sorbanállási rendszerben a beérkezési folyamatot a karbantartásra beérkező autóbuszok, a kiszolgálást az autóbuszok karbantartása, a kimeneti folyamatot az autóbuszok újboli üzembehelyezései jelentik. A beérkezési folyamat esetén általában feltesszük, hogy minden adott pillanatban egyszerre csak egy ügyfél érkezhet a sorbanállási rendszerbe. Ez irreális lehet pl. egy étterem esetében. Ilyen sorbanállási rendszerekben megengedjük a többszörös beérkezéseket is. Azt is feltételezzük általában, hogy a beérkezési folyamatot nem befolyásolja, hogy éppen hány ügyfél tartózkodik a sorbanállási rendszerben. Emellett a feltételezés mellett a véletlen beérkezési folyamatot a két egymásutáni beérkezés között eltelt idő valószínűségeloszlásának a megadásával írhatjuk le. Van azonban két olyan eset is, amikor a beérkezési folyamat függhet a rendszerben lévő (várakozó) ügyfelek számától.
1
Az első ilyen eset az, amikor a sorbanállási rendszerbe nagyon kislétszámú alapsokaságból érkezhetnek csak be ügyfelek. Gondoljunk például egy olyan autóbusz karbantartó műhelyre, amelyik csak öt autóbusz karbantartásával foglalkozik. Ha véletlenül éppen mind az öt autóbusz karbantartás alatt áll, akkor a közeljövőben biztosan nem fog több autóbusz karbantartásra beérkezni és fordítva, ha mind az autóbusz kint van a forgalomban, akkor nagyon valószínű, hogy legalább az egyik közülük előbb, vagy utóbb karbantartásra fog jelentkezni. Az ilyen sorbanállási modelleket véges forrású modelleknek nevezzük. A második ilyen eset az, amikor amikor az ügyfeleknek a kiszolgálóhelyre való beérkezési sebessége csökken, amint a kiszolgálóhely túlzsúfolttá válik. Például, ha azt látjuk, hogy egy étterem kerthelyiségében minden asztalnál vendég ül, és már elég hosszú sor is várakozik megüresedő asztalra, akkor továbbmegyünk és keresünk egy másik, kevésbé zsúfolt kerthelyiséggel bíró éttermet. Ilyen esetben, azaz amikor az éppen érkező ügyfélnek nem sikerül belépnie a sorbanállási rendszerbe, azt mondjuk, hogy az ügyfél elveszett (a sorbanállási rendszer számára). A kimeneti vagy kiszolgálási folyamat leírásához alapvetően meg kell adni egy ügyfél véletlentől függő kiszolgálási idejének a valószínűségeloszlását. Általában feltesszük, hogy a kiszolgálási idő független a sorbanállók számától, tehát a kiszolgáló nem dolgozik gyorsabban, ha többen várnak rá. Ha egy sorbanállási rendszerben egynél több kiszolgáló van, akkor azok elrendezése szerint mek kell különböztetni párhuzamos kiszolgálóhelyeket és soros kiszolgálóhelyeket. Az előbbi esetben minden kiszolgálóhely ugyanazt a típusú kiszolgálást végzi és az ügyfeleknek csak egy kiszolgálóhelyen kell keresztülmenniük ahhoz, hogy a kiszolgálásuk befejeződjön. Például a banki kiszolgálóhelyek elrendezése általában párhuzamos. Ezzel szemben a kiszolgálóhelyek elrendezését akkor nevezzük sorosnak, ha az ügyfeleknek több kiszolgálóhelyen kell átmenniuk ahhoz, hogy befejeződjék a kiszolgálásuk. Erre tipikus példa egy szerelőszalag működése. A kiszolgálási folyamat másik fontos jellemzője az alkalmazott kiszolgálási szabály. Ez adja meg az ügyfelek kiszolgálásának a sorrendjét. A lehetséges kombinációk angol elnevezésének kezdőbetüivel azonosítva megkülönböztetünk FCFS First Come First Served kiszolgálási szabályt (gyakran nevezik FIFO First In First Out szabálynak is); LCFS 2
Last Come First Served kiszolgálási szabályt (hasonlóan úgy is nevezik, hogy LIFO Last In First Out szabály) valamint SIRO Service In Random Order kiszolgálási szabályt. Talán sokak számára igazságtalannak tűnik az LCFS szabály alkalmazása, ez azonban többnyire fizikai kényszerhelyzet hatására mégis kialakulhat. Ilyen például, amikor egy zsúfolt liftbe szállunk be, mikoris az fog először kiszállni a liftből, aki utoljára szállt be. Végül szólni kell a Magyarországon csak a legutóbbi időben alkalmazni kezdett kiszolgálási szabályról, amikor több, párhuzamosan működő kiszolgálóhelyhez az ügyfelek egyetlen sorban állnak és az éppen felszabaduló kiszolgálóhely mindig az éppen a sor elején álló ügyfelet fogadja. Enélkül, vagyis ha minden kiszolgálóhelyhez külön sor áll, az ügyfelek mindig igyekeznek a legrövidebb sort választani, amelynek a megtalálása nem minden estben triviális. Ha több sor van a sorbanállási rendszerben, akkor azt is rögzíteni kell, hogy az ügyfelek sorbanállás közben átmehetnek-e az egyik sorból a másikba, illetve bizonyos szabályokkal be lehet indítani egy vagy több gyors kiszolgálásra használt kiszolgálóhelyet is (nagy bevásárlóközpontok gyorspénztárai).
1.2.
A beérkezési és kiszolgálási folyamatok modellezésére használt legfontosabb valószínűségeloszlások
A beérkezési folyamat modellezése. Mivel feltettük, hogy egy adott időpillanatban csak egy beérkezés történhet, azért jelölhetjük ti -vel azt az időpontot, amikor az i-edik ügyfél megérkezik, i = 1, 2, . . . , n, . . .. Jelölje ηi = ti+1 − ti , i = 1, 2, . . . , n, . . . a
két egymásutáni ügyfélbeérkezés között eltelt véletlen időszakaszokat, melyekről feltéte-
lezzük, hogy egymástól független, folytonos és azonos eloaszlású valószínűségi változók, melyek eloszlása megegyezik valamely η valószínűségi változó eloszlásával. Ez a feltevésünk azt jelenti, hogy bármely két egymásután beérkező ügyfél beérkezési időpontjai közötti véletlen időtartam hossza független attól, hogy melyik napszakban, vagy a hét melyik napjában vagyunk, azaz az ügyfelek beérkezési folyamata stacionárius. Tegyük fel, hogy a közös η valószínűségi változónak G(t) = P (η ≤ t) a valószínűségi eloszlás-
3
függvénye és létezik a g(t) sűrűségfüggvénye, mellyel P (η ≤ c) =
Zc
g(t)dt és P (η > c) =
Z∞
g(t)dt.
c
0
Mérjük az egymásutáni ügyfélbeérkezések között eltelt időt mondjuk órában, és jelöljük 1 -val a két egymásutáni beérkezés között eltelt átlagos óramennyiséget: λ Z∞ 1 = tg(t)dt λ 0
Ekkor az óránkénti beérkezések számával mért it beérkezési gyakoriság értéke éppen λ lesz. Szoktuk ezt a beérkezési folyamat intenzitásának is nevezni. Az η valószínűségi változót leggyakrabban exponenciális eloszlásúnak választják, erre
λe−λt , g(t) = 0, különben,
ha t ≥ 0
1 , λ 1 D 2 (η) = , λ2 vagyis az eloszlás λ > 0 paramétere éppen a beérkezési folyamat intenzitását, azaz az E(η) =
óránként beérkező ügyfelek átlagos, vagy várható számát jelenti. Egy további szép (és karakterizáló) tulajdonsága az exponenciális eloszlásnak az úgynevezett örökifjú tulajdonság, amit úgy is mondhatunk, hogy az eloszlásnak „nincs emlékezete”: P (η > t + h | η ≥ t) = P (η > h) Az egymásutáni beérkezések között eltelő véletlen időre átfogalmazva ez azt jelenti, hogy ha tudni akarjuk a következő beérkezésig eltelő idő eloszlását, akkor nem számít, hogy mennyi idő telt el az előző beérkezés óta. Eszerint a jövőbeli beérkezések tulajdonságainak előrejelzéséhez nem kell feljegyeznünk, hogy milyen régen volt az utolsó beérkezés. Ez a megfigyelés jelentősen leegyszerűsíti a sorbanállási rendszerek elemzését. Egy ζ diszkrét valószínűségi változót λ > 0 paraméterű Poisson eloszlásúnak nevezünk, ha P (ζ = n) =
λn −λ e , n = 0, 1, . . . n! 4
Ekkor a valószínűségelméletből jól ismert, hogy E(ζ) = D 2 (ζ) = λ. Bizonyítható a következő állítás: 1.1. Tétel: Két beérkezés közt eltelt idő eloszlása akkor és csak akkor λ paraméterű exponenciális eloszlású, ha a beérkezések száma tetszőleges t hosszúságú időintervallumon λt paraméterű Poisson eloszlású. Az 1.1. Tétel értelmében, amennyiben ζt -vel jelöljük egy tetszőleges t hosszúságú időintervallumon történő beérkezések számát, akkor P (ζt = n) =
(λt)n −λt e , n = 0, 1, . . . n!
és ezért E(ζt ) = D 2 (ζt ) = λt, vagyis átlagosan λt beérkezés történik egy t hosszúságú időintervallumban, így λ jelentése a korábbiakban mondottakkal megegyező módon most is az időegység alatt történő beérkezések száma, vagy a beérkezési gyakoriság. A következő 1.2. tétel arra ad választ, hogy milyen egyszerűen megfogalmazható feltételek teljesülése esetén teljesül két egymásutáni beérkezés között eltelő időre, hogy az λ paraméterű exponenciális eloszlású? 1.2. Tétel: Ha teljesül a két egymást követő beérkezés között eltelő időre, hogy a) az egymást át nem fedő időintervallumokon történő beérkezések számai egymástól függetlenek, b) kis ∆t értékekre (és tetszőleges t-re), annak a valószínűsége, hogy a t és t + ∆t időpontok között egy beérkezés történik λ∆t + o(∆t), ahol o(∆t) („kis ordó” ∆t ) o(∆t) tetszőleges olyan mennyiség lehet, amelyre lim = 0. ∆t→0 ∆t Ezenkívül annak a valószínűsége, hogy t és t + ∆t között nem lesz beérkezés, 1 − λ∆t + o(∆t), és annak a valószínűsége, hogy t és t + ∆t között egynél több beérkezés lesz, o(∆t), akkor tetszőleges t hosszúságú időintervallum alatti beérkezések ζt száma Poisson eloszlású λt paraméterrel és bármely két egymást követő beérkezés közt eltelt idő exponenciális eloszlású λ paraméterrel. 5
1. Példa. Dick kocsmájában az óránként rendelt (korsó) sörök mennyisége Poisson eloszlást követ, óránként 30 korsó átlaggal. 1. Határozzuk meg annak a valószínűségét, hogy este 10 óra és éjfél között nem fognak 60-nál több sört rendelni! 2. Határozzuk meg a reggel 9 és délután 1 óra között rendelt sörök átlagát és szórását! 3. Határozzuk meg annak a valószínűségét, hogy két egymást követő rendelés 1 és 3 perc időtávolság között for megtörténni! Megoldás: 1. Az este 10 óra és éjfél között rendelt sörök mennyisége Poisson eloszlású lesz 2·30 = 60 paraméterrel. Ezért annak a valószínűsége, hogy 10 óra és éjfél között pontosan 60 sört fognak rendelni: 60 X 60k k=0
k!
e−60 ≈ 0, 534262.
2. Óránként λ = 30 sört rendelnek átlagosan és időszakunk t = 4 óra hosszú. Ezért a reggel 9 és délután 1 óra között rendelt sörök átlaga 4 · 30 = 120 sör. Az ugyanezen √ időszakban rendelt sörök szórása pedig 120 = 10, 95 sör. 3. Jelöljük η-val két egymást követő sörrendelés között eltelő idő véletlen tartamát most percben. Ekkor η exponenciális eloszlású, amely eloszlás λ paramétere pontosan egyenlő az időegységenként átlagosan megrendelt sörök számával. Mivel 30 = 0, 5 sör megóránként átlag 30 korsó sört rendelnek, ez percenként átlag 60 rendelését és kiszolgálását jelenti. Ezért η sűrűségfüggvénye: 0, 5e−0,5t , ha t ≥ 0. Így
P (1 ≤ η ≤ 3) =
Z3
0, 5e−0,5t dt = e−0,5 − e−1,5 ≈ 0, 38.
1
Ha a beérkezések között eltelt idő elszlása nem tekinthető exponenciálisnak, akkor gyakran használják az Erlang eloszlást. Egy η folytonos valószínűségi változó Erlang eloszlású, ha a g(t) sűrűségfüggvénye: R(Rt)k−1 e−Rt g(t) = , ha t ≥ 0. (k − 1)! 6
Itt R az un. arányparaméter, k pedig az un. alakparaméter. Parciális integrálással könnyen megmutatható, hogy E(η) =
k k és D 2 (η) = 2 . R R
Ha az arányparamétert az alakparaméter pozitív valós számszorosának vesszük, azaz R = kλ, akkor k = 1 esetén visszakapjuk az R = λ paraméterű exponenciális eloszlást, míg k értékének növelésével az Erlang eloszlás egyre jobban közelíti a normális eloszlást. Az is megmutatható, hogy a k alakparaméterű és kλ arányparaméterű Erlang eloszlás megegyezik annak az η1 + η2 + · · · + ηk valószínűségi változónak az eloszlásával, amelyre az ηi valószínűségi változók független, kλ paraméterű exponenciális eloszlásúak.
A kiszolgálási folyamat modellezése. Feltesszük, hogy a különböző ügyfelek kiszolgálási idői független valószínűségi változók és hogy az egyes ügyfelek kiszolgálási 1 időit a ξ valószínűségi változó írja le, amelynek a sűrűségfüggvénye f (t). Legyen az µ ügyfelek kiszolgálási időinek az átlaga. Nyilván 1 = µ
Z∞
tf (t)dt.
0
1 jelentése tehát az ügyfél kiszolgálásával eltöltött órák száma, így µ az ügyfelek óránµ kénti számát jelenti. Ezért µ-t kiszolgálsi gyakoriságnak is nevezhetjük. Például µ = 5 azt jelenti, hogy ha az ügyfelek folyamatosan érkeznének, akkor a kiszolgálóhely átlagosan 5 ügyfelet tudna kiszolgálni óránként, és az egy ügyfélre jutó átlagos kiszolgálási 1 idő óra lenne. Azt reméljük, hogy a kiszolgálási időtartamokat is megfelelően mo5 dellezhetjük exponenciális eloszlással. Ekkor ξ f (t) sűrűségfüggvénye az f (t) = µe−µt 1 exponenciális formát ölti és az ügyfél átlagos kiszolgálási ideje lesz. Nyilván való, hogy µ az exponenciális eloszlás örökifjú tulajdonsága a kiszolgálási folyamat elemzésekor is jól hasznosítható, hiszen nem kell tudni, hogy mikor kezdődött egy ügyfél kiszolgálása, a hátramaradó kiszolgálási idő ugyanolyan exponenciális eloszlású. Ha a kiszolgálási időre nem fogadható el, hogy exponenciális eloszlású lenne, akkor szokás azt is Erlang eloszlással is modellezni. 2. Példa. Egy hipermarket pénztáránál a kiszolgálási idő exponenciális eloszlású és átlagosan 4 percet vesz igénybe. 7
1. Amikor beállunk ehhez a pénztárhooz csak egyetlen vevő kiszolgálása folyik éppen. Mi a valószínűsége annak, hogy 6 percnél is többet kell majd várnunk arra, hogy megkezdődjön a mi kiszolgálásunk? 2. Ha feltesszük, hogy a vevők folyamatosan érkeznek a pénztárhoz kiszolgálásra, akkor mennyi annak a valószínűsége, hogy a pénztáros egy óra alatt legalább 20 vevőt is kiszolgál? Megoldás: 1 1 = . Mivel E(ξ) 4 az exponenciális eloszlás örökifjú tulajdonsága miatt teljesen mindegy, hogy az
1. A ξ kiszolgálási idő exponenciális eloszlásának a paramétere λ =
éppen kiszolgálás alatt álló vevő kiszolgálása hány perccel korábban kezdődött, azért 1 P (ξ ≥ 6) = 1 − F (6) = 1 − 1 − e−6/4 = √ ≈ 0, 2231. e3 2. A pénztár által egy óra, azaz hatvan perc alatt kiszolgált vevők η száma λt = 1 · 60 = 15 paraméterű Poisson eloszlású, ezért 4 P (η ≥ 20) = 1 −
19 X 15i i=0
i!
e−15 = 1 − 0, 8752 = 0, 1248.
Mind a beérkezési, mind a kiszolgálási folyamat fontos speciális esete a determinisztikus (nulla szórású) eset. Ekkor az egymásutáni beérkezések között eletelő idő hossza 1 1 mindig pontosan és a a kiszolgálási idők pegig mindig pontosan hosszúságúak leszλ µ nek. A várakozási időkkel kapcsolatban egy érdekes jelenség az úgynevezett várakozási idő paradoxona. Tegyük fel, hogy egy diákotthon előtt megálló buszok érkezési ideje 60 perc várható értékű exponenciális eloszlással írható le. Ha véletlenszerűen érkezünk a diákotthon előtti buszmegállóhoz, átlagosan mennyi időt kell várnunk a következő buszra? Ha úgy okoskodunk, hogy a két egymásután érkező busz érkezése közt eltelő 60 perces intervallumban egyenletes eloszlással érkezünk, akkor az átlagos várakozási időt nyilván 30 percre jósoljuk. Tudjuk azonban az exponenciális eloszlás örökifjú tulajdonságából, 8
hogy bármikor érkezünk is, mindig úgy vehetjük, mintha éppen akkortól kezdődne a következő busz érkezésének az „időszámítása”, tehát a várható várakozási idő 60 perc. A paradoxon nemcsak exponenciális eloszlású érkezési idők mellett áll fent. Tekintsünk egy olyan buszmegállót, amelybe átlagosan 60 percenként érkeznek a buszok. Legyen a beérkezési folyamat egy realizációja 30, 90, 90 és 30 perc távolságú beérkezési soro180 3 zat. Ekkor = valószínűséggel érkezünk egy 90 perces követési intervallum alatt 240 4 1 60 = valószínűséggel érkezünk egy 30 perces követési intervallum a megállóba és 240 4 alatt a megállóba. Ezért az átlagos hosszúságú követési intervallum, amelyben az utas 3 1 megérkezik a megállóba 90 + 30 = 75 perc. Ezért az átlagos várakozási időnk a 75 4 4 perc fele, azaz 37,5 perc lesz, ez pedig több, mint 30, amire az átlagos 60 perces követési távolságok mellett számítottunk volna. A sorbanállási rendszerek Kendall–Lee-féle jelölésrendszere. Kendall 1951-ben javasolta a sorbanállási rendszerek hat jellemzővel történő leírását: 1/2/3/4/5/6 Az első jellemző a beérkezési folyamat tulajdonságát adja meg: M
= A beérkezési időtartamok független, azonos exponenciális eloszlású valószínűségi változók,
D
= A beérkezési időtartamok determinisztikusak,
Ek
= A beérkezési időtartamok független, azonos Erlang eloszlású valószínűségi változók k paraméterrel,
GI
= A beérkezési időtartamok függetlenek, azonos eloszlásúak és valamely általános (general) eloszlásból származnak.
A második jellemző a kiszolgálási idő tulajdonságát adja meg:
9
M
= A kiszolgálási időtartamok független, azonos exponenciális eloszlású valószínűségi változók,
D
= A kiszolgálsi időtartamok determinisztikusak,
Ek
= A kiszolgálási időtartamok független, azonos Erlang eloszlású valószínűségi változók k paraméterrel,
G
= A kiszolgálási időtartamok függetlenek, azonos eloszlásúak és valamely általános (general) eloszlásból származnak.
A harmadik jellemző a párhuzamos kiszolgálóhelyek száma. A negyedik jellemző a sorbanállási szabályt írja le: FCFS
=
Az első beérkezőt szolgálják ki először (First Come, First Served)
LCFS
=
Az utolsó beérkezőt szolgálják ki először (Last Come, First Served)
SIRO
=
Véletlen sorrendben történő kiszolgálás (Service In Random Order) valószínűségi változók k paraméterrel,
GD
=
Általános kiszolgálási szabály (General queue Discipline)
Az ötödik jellemző a rendszerben lévő ügyfelek maximálisan megengedhető számát adja meg (beleértve a várakozó és az éppen kiszolgálás alatt álló ügyfeleket is). A hatodik jellemző megadja annak az alapsokaságnak a nagyságát, amelyből az ügyfelek származnak. Ha a potenciális ügyfelek számának nagyságrendje jóval nagyobb a kiszolgálóhelyek számának nagyságrendjénél, akkor az alapsokaság nagyságát végtelennek tekintjük. A jelölésrendszer illusztrálásaként az M/E2 /8/FCFS/10/∞ például egy olyan kórházat jelenthet, ahol 8 orvos dolgozik, a két beérkezés között eltelt idők exponenciális eloszlásúak, a kiszolgálási idők eloszlása 2 alakparaméterű Erlang eloszlás, a kiszolgálás érkezési sorrendben történik és a kórház 10 betegnyi kapacitással rendelkezik.
10
