|
A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. Bizonyára mindenkivel megesett már, hogy valahol sorban kellett állnia. Ha elég hosszú volt a sor, akkor talán olyan kérdéseken is eltöprengett, hogy vajon mennyi ideig fog várhatólag sorban állni, hány embert szolgálnak ki addig (ezt persze, ha egy sor van, meg is számolhatja, de ha már kettő, akkor nem ilyen könnyű eldönteni), vagy hogyha beállítanának még egy kiszolgálót, az mennyire csökkentené a várakozási időt. Ha nagyobb volt a beleérző képessége, akkor az is eszébe juthatott, hogy mennyit kell dolgoznia a kiszolgálónak, milyen hosszúak az egyfolytában foglalt, illetve üres periódusok. Ha pedig a sorbanállónak fejlett az üzleti érzéke, akkor azt is meggondolhatta, hogy megérné-e egy újabb kiszolgálót beállítani: mennyivel több lenne akkor az adott időn belül kiszolgált személyek száma, vagy ‐ ha a sor hossza korlátozott ‐ mennyivel kisebb lenne az esetleg ki nem szolgáltak aránya.
Ilyen és ezekhez hasonló kérdésekkel foglalkozik a sorbanállás, más néven tömegkiszolgálás elmélete.
1. A tömegkiszolgálási rendszer elemei
Nézzük meg, milyen jellemzői lehetnek egy tömegkiszolgálási rendszernek. A két legfontosabb dolog, amit meg kell vizsgálnunk, az az igények beérkezésének dinamikája és a kiszolgálásuk ideje. Ezek lehetnek előre pontosan meghatározottak, azaz determinisztikusak, illetve részben vagy teljesen véletlentől függőek, azaz sztochasztikusak. Teljesen determinisztikus tömegkiszolgálási rendszer például az a futószalag, ahol 1 percenként érkezik egy munkadarab, amelynek megmunkálása 0,9 percig tart. Érezhető, hogy az ilyen egyszerű rendszerek vizsgálata semmilyen elvi nehézséget nem okoz, és ezek kedvéért nem építettek volna fel egy egész elméletet. Az is látható, hogy ez a modell legtöbbször nem is írja le hűen a valóságot. Honnan tudjuk ugyanis, hogy egy munkadarab megmunkálása pontosan 0,9 percig tart? Általában csak azt tudjuk, hogy például a munka 0,8 percnél hosszabb, de 1 percnél rövidebb ideig tart, továbbá hogy az átlagos megmunkálási idő 0,9 perc. Így el is érkeztünk a sztochasztikus kiszolgálási időhöz. Ezt pontosabban úgy fogalmazhatjuk meg, hogy adva van egy eloszlás, amely a kiszolgálás idejét írja le; vagyis annak a valószínűsége, hogy a kiszolgálás -nél rövidebb ideig tart, egyenlő -szel.
Az igények beérkezésének dinamikáját, mint azt az előbbi példában tettük, általában az egymás utáni beérkezések között eltelt idővel írjuk le. Ha ez sztochasztikus, akkor ennek is az eloszlását adjuk meg. Annak a valószínűségét, hogy egy ilyen beérkezési időköz rövidebb, mint egy időintervallum, -vel jelöljük. Legtöbbször feltesszük, hogy a különböző beérkezési időközök ‐ például az 1. és 2. igény beérkezése között eltelt idő és a 2. és 3. igény beérkezése között eltelt idő ‐ egymástól független és azonos eloszlású valószínűségi változók.
A tömegkiszolgálási rendszer jellemzői még: a maximális lehetséges sorhossz (), a kiszolgáló egységek száma (), illetve a kiszolgálási sorrend. Ez utóbbi általában azt az elvet követi ‐ mint ahogy az a valós életben megszokott ‐, hogy aki korábban érkezik, azt hamarabb kiszolgálják (ezt az elterjedt angol rövidítéssel FIFO, azaz First In First Out elvnek hívják), de lehetnek ettől eltérő kiszolgálási módok is, például ha egynémely igényt soron kívül szolgálnak ki (erre is találhatunk példát az életben). Ha nincs lehetőség várakozásra, azaz , akkor elutasításos rendszerről beszélünk. Ilyen például egy telefonközpont, ahol ha nem ad vonalat a készülék, akkor újra be kell lépnünk a rendszerbe, vagyis le kell tennünk és újra próbálkozni. Alapesetnek tekintjük, és külön nem is említjük, ha nincs korlátozva a sor hossza () és egy kiszolgáló van.
Ha ismerjük a fentebb felsorolt adatokat, akkor számos, a rendszerre jellemző mennyiséget tudunk kiszámolni (legalábbis elvileg). Például megkérdezhetjük, hogy milyen valószínűséggel lesz sorbanálló egy adott pillanatban, vagy mennyi lesz az átlagos sorhossz, és így tovább. Ahhoz, hogy ezekre a kérdésekre választ adjunk, meg kell ismerkedni egy újabb fogalommal.
2. Születési-halálozási folyamatok
Tegyük fel, hogy elefántokat tenyésztünk, amelyek születnek és meghalnak az idő folyamán úgy ‐ ahogy az az elefántoknál szokásos ‐, hogy egyszerre csak egy elefántbébi születik, az is eléggé ritkán, szinte soha nem fordul elő, hogy nagyon rövid időn belül két elefánt születne. Cserébe a halálozások is ugyanilyen ritkák. Az is természetes, hogy az elefántok születési, illetve halálozási intenzitása (az, hogy mennyi elefánt születik, illetve hal meg egységnyi idő alatt) függ az állatok számától. Arra vagyunk kíváncsiak, hogy elég hosszú idő múlva milyen valószínűséggel lesz 0, 1, 2, elefántunk, vagyis milyen lesz az állatok számának az eloszlása.
Ezt a problémát általánosítva, és matematikailag kezelhető módon a következőképpen fogalmazhatjuk meg: Adott egy populáció, lehetséges nagysága , 1, 2, . Minden -hoz meg van adva egy születési és egy halálozási intenzitás. A populáció nagysága egyesével változhat, azaz ha valamikor ez az érték , és egy másik időpillanatban , akkor kell lennie olyan pillanatnak a kettő között, amikor a populáció nagysága volt. Ezen kívül teljesülnek az alábbi feltételek: jelöli egy esemény bekövetkezésének valószínűségét, értéke 0 és 1 közötti.
Az (kiolvasva: kis ordó ) egy szokásos matematikai jelölés, egy olyan -tól függő mennyiséget jelöl, amely -hoz képest nagyon kicsi, azaz -val osztva és -val tartva 0-hoz a hányados értéke 0-hoz tart. | |
Ezekből már az is következik, hogy több halálozás, több születés vagy születés és halálozás egyszerre egy kis idő alatt lehetetlen, abban az értelemben, hogy az ilyen típusú események valószínűsége nagyságrendű.
A fenti feltételeket teljesítő populáció nagyságát az időben leíró folyamatot születési-halálozási folyamatnak nevezzük. Ha minden -ra, akkor tiszta születési folyamatról, ha minden -ra, akkor tiszta halálozási folyamatról beszélünk.
Legyen annak a valószínűsége, hogy a időpillanatban (természetesen ) a populáció nagysága, vagyis az elefántok száma . Először vizsgáljuk meg ezeket a mennyiségeket. A annak az eseménynek a valószínűségét méri, hogy a időpontban 0 elefántunk van. Nézzük, hogy fordulhat ez elő. Háromféleképpen:
| * | -ben is 0 volt, és idő alatt nem született egy elefánt sem; |
| * | -ben 1 elefánt volt, és idő alatt nem született egy sem, de az az egy meghalt; |
A harmadik eset elég furcsán hangzik, de megmagyarázza az a tény, hogy minden ebben foglalt lehetőség együttes valószínűsége a feltételeink szerint . Az első eset valószínűsége: a másodiké | |
Ezeket összegezve megkapjuk -t: | |
(a , és a többi -t tartalmazó szorzat összege együttesen is csak ). Mindkét oldalból kivonva -t, osztva -val, majd -val tartva 0-hoz, a bal oldalon -nek szerinti deriváltját kapjuk, amelyre tehát ez teljesül: | | (1) |
A annak az eseménynek a valószínűségét méri, hogy a pillanatban darab elefántunk van (). Ez a következőképpen fordulhat elő:
| * | -ben elefánt volt, és idő alatt nem született, és nem halt meg egy elefánt sem; |
| * | -ben elefánt volt, és idő alatt egy született de nem halt meg egy sem; |
| * | -ben elefánt volt, idő alatt egy meghalt, de egy sem született; |
Az előbbi okoskodáshoz hasonlóan kaphatjuk a következőt: | | (2) |
Innen úgy lehetne továbblépni, hogy megoldanánk az (1)‐(2) ún. differenciálegyenlet-rendszert, azaz keresnénk olyan -változós , , , , függvényeket, amelyek kielégítik a deriváltakra vonatkozó egyenleteket. Ne ijedjen meg senki, ezt nem fogjuk megtenni, csak egy speciális, ám igen tanulságos esetben.
Legyen és minden -ra, azaz tekintsük az állandó intenzitású tiszta születési folyamatot. Ekkor a differenciálegyenletek: | |
Tegyük fel, hogy ,,a rendszer a 0-ból indul'': Ekkor (3)-ból következik, hogy , és ezt behelyettesítve (4)-be esetén (ezt könnyen lehet ellenőrizni deriválással). Tovább helyettesítve nagyobb -ra: . Ez egy nevezetes eloszlás, az ún. -paraméterű Poisson-eloszlás, és a folyamat neve -paraméterű Poisson-folyamat. Könnyen kiszámolhatja az olvasó, hogy egy -paraméterű Poisson-folyamat esetén annak a valószínűsége, hogy a populáció nagysága ideig nem változik, . Ennek az eloszlásnak is van neve, ez az exponenciális eloszlás. Az exponenciális eloszlás az egyik leggyakrabban előforduló folytonos eloszlás, definíciója a következő:
Definíció. Legyen egy úgynevezett valószínűségi változó, amelynek lehetséges értékei a nemnegatív valós számok. Az eloszlása -exponenciális, ha annak a valószínűsége, hogy legalább , megegyezik -vel, azaz , ahol természetesen .
Egy -exponenciális eloszlású valószínűségi változó várható értéke , azaz egy állandó intenzitású tiszta születési folyamat esetében átlagosan hosszúságú időközönként történik egy születés. Azt is be lehet látni, hogy a Poisson-folyamatok és az exponenciális változatlansági idők közötti kapcsolat kölcsönös: ha exponenciális eloszlású időközönként növekszik eggyel a populáció nagysága, akkor az egy Poisson-folyamat lesz.
Az elefántfarm eseténél azt kérdeztük, hogy mi lesz az elefántok számának eloszlása elég hosszú idő múlva. Ez azért természetes, mert míg az elején nagyon ingadozhat a létszám, joggal várhatjuk, hogy egy idő után a populáció beáll egy stabil állapotba, a kezdeti hullámzások kisimulnak. Természetesen a stabil állapotot nem úgy kell érteni, hogy mindig ugyanannyi elefántunk lesz, hanem hogy az eloszlás nem változik már az idővel, ún. stacionárius eloszlás lesz. Tehát azt kérdezzük, hogy létezik-e, és ha igen, akkor mennyi a következő határérték: Szerencsére a mi esetünkben létezik ez a határérték, és meg is tudjuk határozni. Tekintsük az (1)‐(2) differenciálegyenletrendszert, és tartsunk -vel a végtelenbe. Ekkor a deriváltak 0-hoz tartanak, mert nem függ -től, tehát az egyenletek így alakulnak: | |
A (6)-ot átrendezve: | | (7) |
Az (5)-öt és (7)-et egybevetve, azonnal következik, hogy Ebből pedig rekurzióval | | (8) |
Ha pedig tudjuk azt is, hogy a mennyiségek eloszlást alkotnak, vagyis , akkor meg tudjuk határozni -t, és így a -kat is.
3. A teljesen exponenciális tömegkiszolgálási rendszer
Teljesen exponenciális tömegkiszolgálási rendszer alatt a következőt értjük: a beérkezési időközök eloszlása -exponenciális, a kiszolgálási idő eloszlása pedig -exponenciális. Vagyis , . Ez azt is jelenti, hogy átlagosan hosszúságú időközönként érkeznek be az igények, és ha van kit kiszolgálni, akkor átlagosan hosszúságú időközönként távoznak.
Nézzük, hogyan változik a rendszerben lévő igények száma. Feltehetjük, hogy kezdetben egy igény sincs, ez nem változtat a lényegen, de a szemléletünknek sokkal kedvezőbb. Amikor beérkezik egy igény ‐ ez -exponenciális eloszlású időközönként történik ‐, akkor a rendszerben lévő igények száma 1-gyel nő; amikor egy igényt kiszolgálnak, és távozik ‐ ez az első kiszolgálás kezdete után, amíg van kit kiszolgálni, -exponenciális időközönként történik ‐, akkor 1-gyel csökken. Az, hogy egyszerre két igény jelenjen meg, vagy ugyanakkor jelenjen meg egy igény, amikor egy másikat éppen kiszolgáltak, elhanyagolható valószínűségű. Be lehet tehát látni, hogy a rendszerben lévő igények száma születési-halálozási folyamatot követ. Ha egy kiszolgáló van, és nincs korlátozva a sorhossz, akkor a a folyamat paraméterei a következők: (, 1, 2, ), (, 2, ).
Vagyis az előző részben kifejtettek alapján a rendszerben lévő igények számának stacionárius eloszlása: ha bevezetjük a jelölést. Ez a mennyiség olyan fontos szerepet játszik a tömegkiszolgálási rendszerek vizsgálatában, hogy külön nevet adtak neki: a rendszer terhelése. Be lehet látni, hogy a -k akkor és csak akkor alkotnak tényleg eloszlást (vagyis akkor teljesül, hogy az összegük 1), ha . Ez részben eléggé kézenfekvő, mert ha , azaz , a rendszerbe nagyobb intenzitással érkeznek az igények, mint ahogy kiszolgálják őket, akkor egyre több és több várakozó igény lesz, a sor hossza egyre nagyobb lesz, nem alakul ki stacionárius eloszlás. Tegyük ezért fel, hogy a rendszer terhelése kisebb, mint 1. Ekkor egy végtelen mértani sor összegzésével ki tudjuk számolni -t: | |
azaz , és így .
Ezek segítségével ki tudjuk számolni például a rendszerben tartózkodó igények várható értékét: | |
A végtelen sorok összegképletével könnyen kiszámolható, hogy .
Ha , az azt jelenti, hogy a rendszer kapacitása teljesen ki van használva, a beérkezések és a távozások egyensúlyban vannak. Azt várnánk tehát, hogy ha egyre jobban közelítünk alulról -val 1-hez (de persze nem érjük el, mert akkor nem létezne már a stacionárius eloszlás), akkor egyre hatékonyabb lesz a rendszer. Ez azonban nem így van, mert ilyenkor a végtelenbe tart, vagyis egyre hosszabb időt kell eltöltenie egy igénynek a rendszerben. Ez azért van így, mert a véletlen ingadozás miatt a forgalom időnként nagyon megugorhat, és a feszített kiszolgálás már nem tudja ezt ledolgozni.
Most nézzünk példákat olyan teljesen exponenciális rendszerekre, ahol az alapesettől eltérően , illetve (azaz 1-nél több kiszolgáló van, és a sor hossza korlátozott).
Képzeljünk el egy telefonközpontot, ahol vonal, vagyis kiszolgáló egység van, és nincs várakozás, azaz elutasításos a rendszer. Így a rendszerben tartózkodó igények száma 0, 1, 2, , lehet, és természetesen születési-halálozási folyamatot követ. A születési (beérkezési) intenzitás nem függ a kiszolgálástól, tehát és ha ; a halálozási (távozási) intenzitás pedig annál nagyobb, minél több kiszolgálás folyik, ez pedig megegyezik avval, ahányan a rendszerben vannak, tehát ha , 2, , és , ha . A stacionárius eloszlás (amely ebben az esetben mindig létezik, nem csak esetén, mert ilyenkor véges összeg): Eszerint | |
A -nek külön jelentősége van, ez a visszautasítás valószínűsége, vagyis azé, hogy nem ad vonalat a központ. Tegyük fel, hogy egy egészen kicsi központunk van 4 vonallal (). Percenként 3 hívás érkezik (), és egy beszélgetés hossza átlagosan 2 perc (, azaz ). Ekkor a visszautasítás valószínűsége: | |
vagyis az esetek kb. felében a központ nem ad vonalat, az pedig, hogy éppen senki nem telefonál, szinte soha nem fordul elő. Egy telefontársaság számára érdekes kérdés lehet, hogy ha növeljük a vonalak számát, akkor mennyire javul a központ teljesítménye, és ez milyen arányban van a plusz vonalak telepítési költségével. Ilyen problémát vizsgálunk a következő példában.
Nézzünk egy autószervízt, ahol szerelő dolgozik (ők a kiszolgáló egységek), és a garázson kívül, a szervíz udvarán autó várakozhat (). Ekkor a rendszerben 0, 1, 2, , igény lehet, a beérkezési, illetve távozási paraméterek pedig , ha , 1, , , különben; , ha , 2, , ; , ha , , és különben. A stacionárius eloszlás: | |
és | |
Ha például kétóránként érkezik egy autó (), az átlagos javítási idő szintén két óra (), egy szerelő van (), és 3 hely az udvaron (), akkor annak a valószínűsége, hogy egy javításra hozott autót el kell utasítani, illetve annak, hogy a szerelőnek nincs munkája: vagyis minden ötödik autót el kell utasítani. A főnök ezt soknak tartja, ezért felvesz egy másik szerelőt is. Nézzük, hogyan változnak akkor a valószínűségek: Azaz ilyenkor már csak minden ötvenedik autót kell elutasítani, cserébe viszont a szerelők az idejük harmadában nem dolgoznak.
Az eddigiekkel talán be tudtuk mutatni, hogy milyen egyszerűbb alkalmazásai lehetnek a sorbanállás elméletének. Természetesen ennél jóval bonyolultabb rendszerek is léteznek. Aki mélyebb részletekre kíváncsi, az olvassa el L. Kleinrock Sorbanállás, kiszolgálás (Bevezetés a tömegkiszolgálási rendszerek elméletébe) című könyvét (megjelent a Műszaki Kiadónál 1979-ben).
* |
PDF | MathML