Munkaidő-beosztás tervezési algoritmusok összehasonlítása
A kézzel történő munkaidő beosztás készítése egy rendkívül körülményes feladat a szerteágazó követelményrendszer miatt, ami ráadásul nem is ellentmondásmentes. Például sok dolgozó közel ugyanabban az időszakban szeretne nyaralni menni, miközben a munkáltatónak biztosítania kell az üzleti tevékenység folytonosságát. Továbbá a munkáltatók érdeke a foglalkoztatási költség minimalizálása. Az automatizált munkaidő tervezés célja az optimális beosztás megtalálása az adott követelmények mentén, miközben figyelembe veszi a munkajogi előírásokat. Sajnos ez egy NP-nehéz probléma, amit napjainkban is aktívan kutatnak.
Gyakori megközelítések közé tartoznak az egészértékű programozás és annak különféle vállfajai. Ez a megközelítés lineáris egyenletek segítségével fejezi ki a megkötéseket és a célfüggvényt, amire optimalizálni kell a feladatot, és előnye, hogy garantáltan megtalálja az optimális beosztást. Hátránya a memória éhsége és hosszú futási ideje.
Egy másik megközelítés a beosztás tervezésre a progresszív algoritmus, ami időben előre haladva készíti el a beosztást. A keresési tér nagyságrendekkel csökken ennél az algoritmus típusnál az időben előre haladó karakterisztika miatt. Ennek ára, hogy a követelmények kielégítése limitációkba ütközik.
E dokumentum részletesen taglalja az említett két megközelítést és összehasonlítja őket a Scheduling Benchmarks[1] nevű tudományos célokra létrehozott adathalmazon. Továbbá összehasonlítja a publikusan elérhető eddigi legoptimálisabb megoldásokkal is.
A dolgozat további lehetőségeket is taglal a fent említett két módszeren kívül. A progresszív módszer több módon is továbbfejleszthető, különös tekintettel az erőforrás szűkösség kezelésében. Az egészértékű programozási megvalósításban javulást eredményezhet az előzetes beosztások használata triviális esetekre. Továbbá a megerősítéses, illetve a mély tanulási algoritmusok is működő alternatívát nyújthatnak önállóan és hibrid megközelítésekben is.
[1] E. K. Burke and T. Curtois, “New approaches to nurse rostering benchmark instances” European Journal of Operational Research, pp. 71-81, 2014.
szerzők
-
Pintér Benedek
Mérnök informatikus szak, mesterképzés
mesterképzés (MA/MSc) -
Molnár Máté Lajos
Mérnök informatikus szak, mesterképzés
mesterképzés (MA/MSc)
konzulens
-
Dr. Kővári Bence
docens, Automatizálási és Alkalmazott Informatikai Tanszék