LİRINCZ SÁNDOR* A sorbanállás elméletének lehetséges gazdasági alkalma alkalmazásai Possible economic applications of queuing theory Queuing models are helpful for determining how to operate a queuing system in the most effective way. The models enable finding an appropriate balance between the cost of service and the amount of waiting. This theory can be used to design queuing systems that minimize the total cost of service and waiting. Various examples of real queuing systems can be found in commercial, transportation, internal, social service systems. Every individual problem has its own special characteristics, so no standard procedure can be prescribe to fit every situation. The subject of the present investigation is to find practical economic applications of this theory in order to use them for economic college purposes. Two examples will be discussed: in the first the choice of the proper model will be the main task, in the second the number and the location of the servers will design the optimal queuing system.
Bevezetés Valódi sorbanállási rendszereket a gazdasági élet több fontos területén találhatunk. Például: • kereskedelmi kiszolgáló rendszerek, • szállítási rendszerek, • belsı ipari üzleti rendszerek, • szociális szolgáltatási rendszerek, • elektromos hálózatok. A sorbanállási rendszerek modelljeinek megadása a következı módon történik: érkezések közti idık eloszlása / kiszolgálási idık eloszlása / kiszolgálók száma. A leggyakoribb eloszlások típusainak betőjele: • M – exponenciális (MARKOV) eloszlás, • D – elfajult eloszlás, • E – ERLANG-féle eloszlás, • G – általános eloszlás. A kiszolgálók száma lehet egy vagy több azonos paraméterő berendezés. A sorbanállási feladatokban elıször meg kell határozni az eloszlások milyenségét, tehát kiválaszthatók a megfelelı képletek, majd a szükséges paraméterek: kiszolgáló berendezések száma (S), beérkezési ráta (λ), kiszolgálási ráta (µ).
*
BGF Kereskedelmi, Vendéglátóipari és Idegenforgalmi Fıiskolai Kar, fıiskolai docens.
312
LİRINCZ S.: A SORBANÁLLÁS ELMÉLETÉNEK LEHETSÉGES GAZDASÁGI ALKALMAZÁSAI
• • • •
Általában felmerülı kérdések: a rendszerben adott idıpontban lévı egyének száma (n), az egyes ügyfelek átlagos várakozási ideje (M(ts)), a kiszolgálók számának optimuma (S), a kiszolgálók optimális elhelyezésének meghatározása.
Sorbanállási feladatok megoldása Excel táblázatkezelı prog programmal A magyar gazdasági fıiskolákon az operációkutatás része a módszertani szigorlatnak. Egyre több intézményben alakulnak ki a vizsgáztatás számítógépen (csak részlegesen, vagy teljes egészében) történı lebonyolításának feltételei. A gazdasági matematika, statisztika, informatika, operációkutatás feladatainak megoldására leginkább a gépek nagy többségén megtalálható Excel program használata tőnik a legcélszerőbbnek. Egyéb speciális programok bemutatása, kezelésének gyakoroltatása nem látszik reálisnak az egyre csökkenı óraszámkeretek, illetve az egyre növekvı hallgatói létszám mellett. A Budapesti Gazdasági Fıiskola Kereskedelmi, Vendéglátó-ipari és Idegenforgalmi karán az operációkutatás tantárgy bevezetése óta oktatjuk a sorbanállástömegkiszolgálás alapfeladatainak elméletét, megoldását. A módszertani szigorlat számítógépes segédletének (újra)bevezetése során felmerül a kérdés, hogy az egyes fejezetek mely kérdéseihez, feladataihoz érdemes és lehetséges az Excel program használata. 1. példa Egy üzemben sok szerszámot a szerelıcsarnokban lévı nagy szerszámraktárból kell az adott munkához kivenni. Ennek következményeként a raktárablakok elıtt sorba állnak a munkások. Hány raktáros kell a szerszámok szétosztására, hogy a munkások idıvesztesége és a raktári alkalmazottak kihasználatlan ideje minimális legyen? (Adatok forrása [1]) Adatok a beérkezésekrıl (100-szor 10 perc) és számítási eredmények: Beérkezések száma / 10 perc
Megfigyelt gyakoriság %
Beérkezések számának átlaga
Elméleti Poisson-gyakoriság
5
1
0,05
0,1
6
0
0,00
0,3
7
1
0,07
0,7
8
2
0,16
1,5
9
1
0,09
2,5
10
3
0,30
3,9
11
5
0,55
5,6
313
BUDAPESTI GAZDASÁGI FİISKOLA – MAGYAR TUDOMÁNY NAPJA, 2002
Beérkezések száma / 10 perc
Megfigyelt gyakoriság %
Beérkezések számának átlaga
Elméleti Poisson-gyakoriság
12
6
0,72
7,3
13
9
1,17
8,7
14
10
1,40
9,7
15
11
1,65
10,1
16
12
1,92
9,9
17
8
1,36
9,1
18
9
1,62
7,9
19
7
1,33
6,5
20
5
1,00
5,0
21
4
0,84
3,7
22
3
0,66
2,7
23
1
0,23
1,8
24
1
0,24
1,2
25
1
0,25
0,7
Átlag/10 perc:
15,61
Korrelá Korreláció ció:
0,974802
Száz 10 perces periódus adatait feljegyezve kapjuk a második oszlop gyakoriságait. Ezután kiszámítjuk a beérkezések átlagos számát 10 perces idıszakonként. Ez az átlag: 15,61. Majd megpróbáljuk felmérésünk eredményeit egy használatos és kényelmes elméleti valószínőségi eloszláshoz illeszteni: M/M/S. A modellnek megfelelı POISSON-eloszlást nagyon jó közelítéssel érvényesnek tekinthetjük. Adatok a kiszolgálásról (1000 idıtartam) és számítási eredmények: Kiszolgálás idıtartama (mp)
314
Megfigyelt gyakoriság (%)
Megfigyelt kumulált gyakoriság (%)
Kiszolgálási idı átlaga
Elméleti exponenciális gyakoriság
0
18,7
18,7
0,0
0,0
15
16,1
34,8
2,4
22,5
30
14,0
48,8
4,2
39,9
45
10,4
59,2
4,7
53,4
60
7,8
67,0
4,7
63,9
75
6,9
73,9
5,2
72,0
90
5,1
79,0
4,6
78,3
LİRINCZ S.: A SORBANÁLLÁS ELMÉLETÉNEK LEHETSÉGES GAZDASÁGI ALKALMAZÁSAI
Kiszolgálás idıtartama (mp)
Megfigyelt gyakoriság (%)
Megfigyelt kumulált gyakoriság (%)
Kiszolgálási idı átlaga
Elméleti exponenciális gyakoriság
105
4,7
83,7
4,9
83,2
120
3,8
87,5
4,6
87,0
135
3,0
90,5
4,1
89,9
150
1,6
92,1
2,4
92,2
165
1,7
93,8
2,8
93,9
180
1,1
94,9
2,0
95,3
195
0,7
95,6
1,4
96,4
210
0,9
96,5
1,9
97,2
225
0,9
97,4
2,0
97,8
240
0,5
97,9
1,2
98,3
255
0,4
98,3
1,0
98,7
270
0,4
98,7
1,1
99,0
285
0,3
99,0
0,9
99,2
300
1,0
100,0
3,0
99,4
Átlag (mp):
58,9
Korreláció:
0,99883945
Ezer kiszolgálási idıt jegyeztünk fel negyedperces idıintervallumokat véve alapul. A gyakoriságok táblázatának segítségével a kiszolgálás átlagos hosszára 58,9 másodpercet kapunk. A modellnek megfelelı exponenciális eloszlást nagyon jó közelítéssel érvényesnek tekinthetjük. A következıkben tehát alkalmazhatjuk az M/M/S modell képleteit, és kiszámíthatjuk annak a valószínőségét, hogy nincs ügyfél a rendszerben, a sorbanállással eltöltött idı hosszát, a kiszolgálók tétlenséggel eltöltött idejét, illetve az elvesztegetett összidıt. Egy raktárossal a rendszer nem tudna hatékonyan mőködni, hiszen, ha λ értéke meghaladja µ értékét, akkor a várakozó sor egyre csak növekszik, a beérkezés gyorsabb a kiszolgálásnál. Egynél több raktáros esetében ez a probléma nem jelentkezik, ezért összehasonlíthatjuk az S = 2, 3, 4,… esetekben kapott összidıket. A képletek segítségével kapott eredményeket kiolvashatjuk az alábbi Excel táblázatból. λ = 15,61/10 perc = 1,561/perc µ = 58,9 mp = 0,98 perc ψ= λ/µ = 1,59
315
BUDAPESTI GAZDASÁGI FİISKOLA – MAGYAR TUDOMÁNY NAPJA, 2002
S=
p0=
M(ts)=
Raktáros üres idı (perc)
Munkás üres idı (perc)
Összidı (perc)
2
0,11
1,75
197
1312
1508
3
0,19
0,20
677
146
823
4
0,20
0,04
1157
28
1185
5
0,20
0,01
1637
6
1642
Következtetések • A négy különbözı eset végeredményét összehasonlítva azt tapasztaljuk, hogy három raktáros alkalmazása esetén kapjuk a feleslegesen elvesztegetett összidı minimumát. Utána jól láthatóan, egyébként logikusan is, egyre növekszik ez az összeg, tehát felesleges a további esetek figyelembe vétele. • A feladatot lehetne általánosítani azáltal, hogy a munkások, illetve a raktárosok munkabérét differenciáltan adjuk meg. Ezáltal az idıveszteséget forintosítani lehet. Az optimális megoldás ilyenkor természetesen változhat az adott órabérek függvényében. • Az Excel segítséget nyújt a számolásigényes sorbanállási kérdések megválaszolásában. • Az Excel segítségével új típusú kérdések is megfogalmazhatóak sorbanállási feladatok esetében: egy felmérés során kapott megfigyelési eredmények megfelelnek-e a tanult egyszerősítı feltételeknek vagy nem. • Kapcsolat létesíthetı a statisztika tárgyban tanult ismeretekkel (átlagolás, összegzés, korrelációszámítás, statisztikai próbák) az Excel segítségével.
Kiszolgáló berendezések optimális számának és térbeli elhelyezésé elhelyezésének kiszámítása 2. példa Egy ipari vállalat új egységet kíván létrehozni. Ebben egy vagy több szerszámraktárnak is lennie kell. A szerszámokat raktárosok adják ki a szerelıknek, és veszik vissza, amikor már nincs szükség rájuk. Minden egyes szerszámraktár egy sorbanállási rendszer, amelyben a kiadó a kiszolgáló, és a szerelık az ügyfelek. A tapasztalatok alapján úgy becsülhetı, hogy a kiszolgálási idı exponenciális eloszlású, ½ perc várható értékkel. A foglalkoztatni kívánt szerelık számából azt lehet következtetni, hogy a raktárnál percenként átlagban ketten fognak megjelenni véletlenszerően. Tehát az M/M/S modell alkalmazható. Ebben az esetben idıegységnek az órát választva µ=120. Ha csak egy szerszámraktár lenne akkor λ is 120 lenne, egyébként ennek a raktárok számával elosztott törtrésze, feltételezve, hogy a szerelık egyenletesen veszik igénybe a szerszámraktárakat. Egy raktáros órabére 10 euró, egy szerelıé 24 euró. A felújítási, elhasználódási stb. költségek minden egyes szerszámraktárnál 8 eurót tesznek ki óránként.
316
LİRINCZ S.: A SORBANÁLLÁS ELMÉLETÉNEK LEHETSÉGES GAZDASÁGI ALKALMAZÁSAI
Az új egységnek az alapterülete L alakú. Legalább egy, legfeljebb három szerszámraktár létesítése lehetséges. Az arányos lefedettség szempontja szerint, ha egy raktárt létesítünk, akkor azt a B helyre érdemes rögzíteni, két raktár esetében az A és C helyekre, három raktár esetén pedig az ábrán megjelölt A, B, C helyekre. Minden raktár foglalkoztathat egy vagy több raktárost. Az egység oldalhosszúságai 600 méter, illetve 300 méter. Tegyük fel, hogy a szerelık elektromobilon közlekednek, amelyek utazási sebessége 15 km/óra. (Adatok forrása [2].) A feladat eldönteni azt, hogy hány raktárt létesítsünk, illetve raktáranként hány raktárost alkalmazzunk, hogy az összköltség minimális legyen. A modell felállítása Vezessük be a következı jelöléseket: S – szolgáltató egységek száma k – kiszolgálók száma egy szolgáltató egységben λ – átlagos érkezési gyakoriság egy szolgáltató egységhez KeÖK – kiszolgáló egység önköltsége / idıegység KeK – kiszolgálási költség / idıegység SzeK – szolgáltatási költség / idıegység UeK – utazási költség / idıegység UI – utazási idı egy érkezésre oda-vissza VK – várakozási költség ÖK – összköltség A modell célfüggvénye nem más, mint az összes szolgáltató állomás idıegységre esı várható összköltségének várható értéke. M ÖK = s ⋅ KeÖK + k ⋅ KeK + M (VK ) + λ ⋅ UeK ⋅ M (UI ) ahol M x +M y M (UI ) = 2 v (x,y) – a szerelı koordinátái, v – haladási sebesség. Az utazási idı kiértékelésére feltesszük, hogy az egy raktárhoz rendelt szerelı egyenletesen oszlik el valamely területen, minden ügyfél visszatér az eredeti helyére, miután megkapta a szolgáltatást, és az utazás átlagos sebessége nem függ az utazási távolságtól. Azt is feltesszük, hogy az útvonalak egymásra merıleges egyenes szakaszokból tevıdnek össze, amelyek párhuzamosak a tekintett terület oldalaival. Az alkalmazott modell képleteinek felhasználásával, behelyettesítve az adatokat az alábbi eredmények születtek.
( )
( )
[
]
( )
317
BUDAPESTI GAZDASÁGI FİISKOLA – MAGYAR TUDOMÁNY NAPJA, 2002
A teljes költség értékei (euró/óra): S 1 1 1 2
λ 120 120 120 60
k 1 2 3 1
M(ÖK) ∞ 175,20 178,26 164,00
S 2 3 3
λ 60 40 40
k 2 1 2
M(ÖK) 161,64 147,60 166,38
Következtetések • Az abszolút minimumot, tehát a leggazdaságosabb üzemeltetést akkor érjük el, ha három szerszámraktárt létesítenek, mindegyikben egy raktárossal. • Az utazási idı, amely egy szolgáltató állomáshoz való oda-és visszautazással telik el, olykor igen fontos szerepet játszik. Ez a modell viszont arra az esetre is alkalmazható, ha a kiszolgáló utazik az ügyfélhez és még más esetekben is. • Az utazási idı várható értékének kiszámítása viszonylag nehéz, idıigényes. Ezért ilyen típusú feladatok végigszámolása esettanulmány feldolgozásakor vagy fakultáció keretén belül ajánlott. A sorbanállási elmélet egy újabb lehetséges hasznosítása a sorbanállási rendszerek irányításának kifejlesztése, mint például a kiszolgálók számának dinamikus változtatása a rendszerben lévı ügyfelek számának függvényében. Természetesen ezek a lehetıségek már túlmutatnak a gazdasági fıiskolák lehetıségein, ezért tanulmányozásuk csak meglévı szoftver bemutatásán keresztül képzelhetı el.
Irodalom [1] KAUFMAN, FAURE: Bevezetés az operációkutatásba, Mőszaki Könyvkiadó, Budapest, 1969. [2] HILLIER, LIEBERMAN: Introduction to operations research, 7th ed., McGrawHill, 2001.
318