Diz 48 cz

Z DCEwiki
Přejít na: navigace, hledání

Pokročilé metody a modely pro problémy z oblasti rozvrhování lidských zdrojů[editovat]

Autor: Bäumelt Zdeněk


Disertační práce 2015


Tato disertační práce je zaměřena na návrh modelů a algoritmů pro efektivní řešení problémů týkajících se rozvrhování v oblasti lidských zdrojů. Na základě provedené analýzy aktuálního stavu souvisejících prací v této oblasti byly identifikovány dva následující kombinatorické problémy, jimž v literatuře není věnována dostatečná pozornost.

Prvním z nich je problém rozvrhování lidských zdrojů, kde je velká variabilita požadavků na pracovní sílu. Na rozdíl od známého problému rozvrhování zdravotních sester (Nurse Rostering Problem, NRP), kde jsou pouze směny ranní, odpolední a noční, jsou v tomto problému uvažovány desítky až stovky různých směn za účelem přesnějšího pokrytí požadavků na pracovní sílu. Tento problém je nazván jako Employee Timetabling Problem with a High Diversity of shifts (ETPHD). Není překvapivé, že exaktní metody, jako je např. celočíselné programování, jsou pro řešení ETPHD nepoužitelné. Pro řešení tohoto problému byla navržena transformace založená na mapování směn na typy směn. Tato transformace umožnila návrh třífázového algoritmu (MSA). Cílem prvních dvou fází je získat počáteční řešení, kde jsou již dány přibližné pozice bloků směn. Toto se ukázalo podstatné pro poslední fází, kdy je počáteční řešení zlepšováno. Pro ověření výkonnosti MSA byla navržena křížová metodika ohodnocení. Základní myšlenkou je porovnání výkonosti více algoritmů na různých kombinatorických problémech. V našem případě bylo pro experimenty použito 30 reálných ETPHD instancí ze společnosti z oblasti letecké dopravy a dále také 5 standardních NRP instancí z oblasti rozvrhování rozvrhování sester. Experimenty vyhodnocené touto metodikou ověřily, že naše výsledky jsou v drtivé většině případů lepší či alespoň stejně dobré.

Druhým problémem disertační práce z oblasti rozvrhování lidských zdrojů je problém přerozvržení přiřazených směn zdravotních sester (Nurse Rerostering Problem, NRRP). Tento problém nastává např. při onemocnění některé ze sester, kdy její směny musí být přiřazeny sestře jiné. V práci byl navržen paralelní algoritmus za účelem co nejvíce zkrátit potřebnou dobu k řešení NRRP. Paralelní algoritmus byl navíc navržen pro grafickou kartu (GPU), která umožňuje masivní paralelizaci. Dle našeho nejlepšího vědomí je to první použití GPU zaměřené na řešení NRRP. Výkonnost paralelního algoritmu byla testována na NRRP instancích z reálného života, výsledky byly vyhodnoceny ze dvou hledisek. Prvním hlediskem byla kvalita, kde byly výsledky našeho paralelního algoritmu porovnány s nejlepšími známými výsledky z literatury. Druhé porovnání bylo zaměřeno na zkrácení doby výpočtu. Paralelní algoritmus vyžaduje výrazně kratší dobu výpočtu pro získání stejné kvality NRRP řešení jako algoritmus sekvenční, a to v průměru 15 krát kratší.