TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
MŰSZAKKIOSZTÁSI PROBLÉMÁK A KÖZÖSSÉGI KÖZLEKEDÉSBEN Készítette: Árgilán Viktor, Dr. Balogh János, Dr. Békési József, Dávid Balázs, Hajdu László, Dr. Galambos Gábor, Dr. Krész Miklós, Pap Imre, Tóth Attila (mind SZTE)
AZ ELKÉSZÍTETT DOKUMENTÁCIÓ TARTALMA
TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
I.
Elméleti háttér (Irodalom, célok)
II.
Matematikai modell (kidolgozott heurisztikák)
III.
JAVA implementáció
IV.
Felhasználói kézikönyv, használati eset példa
V.
Tesztadatok összeállítása, futtatások dokumentációja
VI.
Hivatkozások
VII. Melléklet: Forráskód
2
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
A FELADAT LEÍRÁSA
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
• Feladat –
napi műszakok kiosztása alkalmazottaknak hosszabb távra (több hét vagy hónap)
• Nagyméretű feladat –
egzakt módszerek lassúak gyakorlati életben hatékonyan alkalmazható heurisztikák
• Megtörtént – –
A módszer kidolgozása, program elkészítése JAVA nyelven, és mindezek dokumentációja.
3
A FELADAT ELMÉLETI HÁTTERÉNEK BEMUTATÁSA
TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
• A feladat –
Adott napi műszakokhoz dolgozók rendelése bizonyos korlátozó tényezők mellett, előre megadott tervezési időszakra (1-3 hónap) a költség minimalizálásával.
• A probléma NP-nehéz • Alkalmazási területek –
Repülőgép-személyzet (pilóták) ütemezése,
–
Nővérek ütemezése (nurse rostering),
–
Call centerek dolgozóinak munkabeosztása,
–
Tömegközlekedési vállalatok (buszvezetők).
4
A FELADAT ELMÉLETI HÁTTERÉNEK BEMUTATÁSA
TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
A megoldást szabályok korlátozzák: munkajogi, EU, szakszervezeti, stb.
Legfontosabb szabályok: –
Azonos napon egy dolgozó legfeljebb 1 műszakot kaphat.
–
Egy elvégzett műszak után legalább adott pihenőidőt kell hagyni (12 óra).
–
A heti összes munkaidő nem haladhatja meg az adott korlátot (48 óra).
–
Egy hónapban legalább adott számú szabadnapot kell biztosítani (4 nap).
–
Egymás követő munkanapok száma nem haladhat meg egy értéket (6 nap). 5
A PROGRAM ADATAI ÉS A CÉLFÜGGVÉNY
TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Műszakok tulajdonságai: – – –
Dátum Kezdési, befejezési időpont Tartalmazott munkaidő
• Dolgozók tulajdonságai – –
Szerződésben foglalt napi átlag munkaóra (esetünkben 8 óra) Elvárt munkaidő (alapbérként fizetett) = munkanapok száma * szerződés
• Cél –
Költség minimalizálása: A dolgozók alulfoglalkoztatásának és felül-foglalkoztatásának összege legyen minimális (mindkettő költséges a vállalatnak, előbbi esetben nem hatékony a kiosztás, utóbbi esetben a „túlóra” költsége.
• Alsó korlát –
A műszakok munkaidejének összegéből és az alkalmazottak elvárt munkaidejéből számolható : • abs(összes munkaidő - optimális emberszámmal lefedhető munkaidő)
6
A KIDOLGOZOTT ÉS MEGVALÓSÍTOTT HEURISZTIKUS ELJÁRÁS ISMERTETÉSE
TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
• IP-megoldás: –
a gyakorlatban lassú
• Heurisztika 1.
2. 3.
Inicializálás – Emberszámbecslés – Szabadnap minta generálás – Gráf felépítése Gráfszínezés Átszínezés Tabu Search használatával
7
TÁMOP-4.2.2.C-11/1/KONV-2012-0004
A KIDOLGOZOTT ÉS MEGVALÓSULT HEURISZTIKUS ELJÁRÁS ISMERTETÉSE
Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Inicializálás • •
•
Kezdeti emberszám becslése Szabadnapmintákat generálunk minden emberhez (6-1 minta) 1. nap
2. Nap
3. nap
4. nap
5. nap
6. nap
7. nap
1. buszvezető
0
0
0
0
0
0
1
2. buszvezető
1
0
0
0
0
0
0
3. buszvezető
0
1
0
0
0
0
0
4. buszvezető
0
0
1
0
0
0
0
5. buszvezető
0
0
0
1
0
0
0
6. buszvezető
0
0
0
0
1
0
0
7. buszvezető
0
0
0
0
0
1
0
Miért jó? –
Csak kezdeti fix szabadnapokat határozunk meg, amely biztosítja az előírt szabályokat és szabadságot hagy a későbbi optimalizáláshoz.
8
A KIDOLGOZOTT ÉS MEGVALÓSULT HEURISZTIKUS ELJÁRÁS ISMERTETÉSE
TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Gráf építése
• Gráf generálása – –
A gráf csúcsai: Műszakok A gráf élei: Kizárások
• Két csúcs között él van – –
Ha egyazon napon vannak Ha van elég pihenőidő közöttük
9
A KIDOLGOZOTT ÉS MEGVALÓSULT HEURISZTIKUS ELJÁRÁS ISMERTETÉSE
TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Gráfszínezés – – – –
Színek = emberek, a színezés = egy műszakkiosztást Jól ismert, gyakorlatban hatékony DSATUR gráfszínezési algoritmus Becsült emberhalmaz -> k-színezés Színezendő csúcs és választott szín választása mohó módon (First Fit) elősegítve az egyenletes munkaelosztást
10
A KIDOLGOZOTT ÉS MEGVALÓSULT HEURISZTIKUS ELJÁRÁS ISMERTETÉSE
TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
Tabu Search – – –
A kezdeti állapot iteratív javítása Tabu Search jellegű keresővel Állapottér: Egy állapot (konfiguráció) egy gráfszínezés Szomszédságok alapján javítás a kezdeti színezésen Átadás: A gráf egy csúcsa új színt kap (műszaki átadás)
Csere: A gráf két csúcsának a színét megcseréljük (műszakcsere)
11
TESZTFUTTATÁSOK EREDMÉNYEI
TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
A tesztelés során generált, illetve valós input adatokat használtunk:
• Generált tesztadatbázis: –
több méretben (25-től 200-ig napi műszakszám), véletlenszerűen generált adatok,
• Valós (Tisza Volán Zrt.): –
megközelítőleg 3000 műszakot tartalmaz.
Valamennyi tesztadaton elértük az alsó korlátot, kedvező futási időkkel. –
A legnagyobb méretű tesztadaton is 25 sec
12
TESZTFUTTATÁSOK EREDMÉNYEI
TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
• A heurisztika és az IP eredményei generált teszteseteken:
• A heurisztika és az IP eredményei a valós teszteseten:
13
TÁMOP-4.2.2.C-11/1/KONV-2012-0004 Nemzeti kutatóközpont fejlett infokommunikációs technológiák kidolgozására és piaci bevezetésére
KÖSZÖNÖM A FIGYELMET!
