Systém pro optimalizaci a řízení lidských zdrojů

ArisoTelos

A r i sto Te l o s Systém pro optimalizaci a řízení lidských zdrojů

AristoTelos

The Workforce Management System

Wo r k fo rce m a n a gem ent ( W F M ) Optimalizace a řízení lidských zdrojů

AristoTelos = [řecky] optimální řešení

•komerční software pro plánování pracovních sil •založen na diplomové práci na MFF ve spolupráci s MSPS s.r.o. MSPS = Matematické + Statistické Projekty + Software Štefan Pacinda

AristoTelos


Popis problému, který AristoTelos řeší Tvorba plánu směn pro zaměstnance (kontaktního centra) splňujícího sadu 'tvrdých' omezení, který je zároveň co možná nejlepším vzhledem k sadě optimalizačních kritérií.

AristoTelos


Plán směn Omezení & Optimalizační kritéria Omezení: • požadavky na zdroje • přestávky mezi směnami, týdenní volno, dodržení odsouhlasených požadavků • dodržení fondu pracovní doby • omezení počtu směn na nějaké aktivitě či směně • zákaz noční směny po pohotovosti či pohotovosti po šesti směnách Optimalizační kriteria: • automatické požadavky • fair policy • preference zaměstnanců, popularita směn • shlukování dnů volna Uvolnění tvrdých omezení: Někdy vstupní data nedovolují vytvořit rozvrh, musíme tedy rozvolnit některé požadavky. Příklad: ve čtvrtek 24.11. má být na přednášce 8 studentů a jsou tu jen 4. Pan docent ale stejně bude vyučovat a potřebuje vygenerovat zasedací pořádek.

AristoTelos


AristoTelos Under the Hood

• Každá část aplikace může běžet na jiném stroji, komunikace přes WCF na HTTP.

• Nás zde bude zajímat generátor modelu a calculation service.

AristoTelos


AristoTelos Možné přístupy k řešení

• CSP – programování s omezujícími podmínkami [Constraint Satisfaction Problem]

• Genetické algoritmy • Vlastní heuristika

• MIP – (smíšený) celočíselný program [Mixed Integer Program]

• a další.. • měli jsme problém a neměli řešení; review literatury přineslo slibných 30-50 článků o rosteringu (tvorba plánů směn) • většina autorů použila MIP či MIP s column generation • zvolili jsme MIP a nenarazili jsme na žádnou neřešitelnou překážku a vítěznou taktiku MIP jsme neměnili

AristoTelos


Celočíselný program Drobný náhled na modelování • 10 typů proměnných, 17 typů constraintů • základním stavebním prvkem je proměnná reprezentující jednu položku plánu směn • tato proměnná modeluje položku na plánu směn; • binární doména; hodnota určuje, zda se daná proměnná objeví v plánu směn či ne • vygenerujeme veškeré smysluplné a platné proměnné – pro všechny zaměstnance, aktivity, dny a směny, pro které je daná položka platná • dané proměnné svážeme v různých typech constraintů tak, aby optimální ohodnocení splňovalo všechny požadavky • pro každou proměnnou musíme ukládat meta-data definující význam dané proměnné, abychom mohli efektivně model tvořit a poté interpretovat řešení (postavit plán směn) • dvě úrovně reprezentace • třídy držící meta data a explicitně informace o vztazích mezi entitami • technická nízko-úrovňová reprezentace modelu • vzájemné mapování

AristoTelos


Celočíselný program Praktická ukázka • požadavky na zdroje • testování validnosti proměnné: požadavky, znalosti agenta, vstupní plán, minulý plán • uvolnění „tvrdého“ omezení • přestávky mezi směnami • rozbor komplexnější situace

• limity na počet směn s aproximací nelineární penalizace • mocninu aproximujeme lomenicí

• vynucení fondu pracovní doby se započítáním žádostí o volno • problém, jak počítat s hodnotou, kterou neznáme; uvolnění omezení

• v různých situacích musíme vystačit pouze s lineárními výrazy, nicméně pomocí pomocných proměnných a pomocných constraintů jsme schopni emulovat různé logické spojky, a další netriviální vztahy • v praxi se často ukazuje, že máme teoretickou možnost leccos modelovat, ale za cenu značného zvětšení modelu

AristoTelos


Celočíselný program Reálná instance problému • velikost modelu závisí na počtu agentu, počtu aktivit, délce plánovacího období, počtu směn a struktuře požadavků na zdroje • běžně řešíme instance problému

• 30-40 agentů • 10 typů směn

• 10 typů aktivit • měsíční plánovací období

• takovému zadání obvykle odpovídá model s 15 000 – 20 000 proměnnými (cca 80% binárních) a podobným počtem constraintů • doba řešení problému • open source solver LP Solve: vůbec nemá šanci v reálném čase jednotek dní se přiblížit ani k suboptimálnímu řešení • nejlepší open source solver SCIP na jednom jádru: desítky hodin do optima • nejlepší komerční solver Gurobi na 8 jádrech: desítky minut do optima

AristoTelos


Celočíselné programování Největší praktický nepřítel

• jedna z největších komplikací v praktickém využití MIP v našem projektu je neřešitelnost modelu • ve fázi vývoje modelu jsou občasné neřešitelnosti nepříjemností, v případě modelu v produkci je neřešitelnost opravdu velkým problémem • předcházení neřešitelnosti • vstupní data pocházejí od uživatele; naším úkolem je zjistit a priori, zda na základě vstupu lze vytvořit rozvrh, anebo zda obsahují nějaký spor • v ideálním případě odchytíme všechny kombinace vstupů, které vedou k neřešitelnému problému a uživateli vrátíme vstup k přepracování bez spouštění výpočtu

• bohužel je (alespoň v této fázi projektu) téměř nemožné odhalit 100% vedoucích k neřešitelné instanci problému

případů

• pokud dostaneme neřešitelný model, pomocí specializovaných nástrojů lze spočítat nejmenší nerozložitelnou spornou množinu pravidel (irreducible infeasible set) a na základě té ohlásit uživateli zhruba, kde se chyba vyskytla • často je ale sporná množina složena i z desítek constraintů a je potřeba ruční zásah někoho, kdo se v modelu vyzná; obvykle na základě takového pozorování odvodíme nový a priorní test

AristoTelos


Testování a feedback Interakce s lidmi • úspěch všech projektů založených na matematickém modelování závisí na zpětné vazbě • v našem projektu je zásadní cyklus • přímý sběr požadavků • začlenění nových požadavků do modelu • konfrontace plánů směn založených na novém modelu se zákazníkem

• testování celého procesu tvorby modelu je velmi těžké • testujeme dílčí feature na malých instancích problému

• testování vyžaduje poměrně velký podíl ruční práce - v komplexnějších případech není úplně jednoduché identifikovat trade-offy, které musí solver vážit • unit testy je možné nasadit na pomocné rutiny a dílčí metody

AristoTelos


Technologie Není třeba být zbytečně efektivní • v našem projektu je efektivita naprosto zásadní – jde nám o to najít v co nejkratším čase co nejlepší řešení • doba výpočtu solveru je řádově delší než doba, kterou tvoří vytvořit model a interpretovat výsledky; proto je možné použít vyšší programovací jazyky – C#, Java a off-the-shelf řešení pro reprezentaci MIP

• dokonalý model je k ničemu, pokud nespolupracuje se spolehlivou a efektivní prezentační vrstvou, která • sbírá data • prezentuje výsledky

• umožňuje manuální úpravy automaticky získaných výsledků

AristoTelos


Motivace Lineární programování umí být užitečné a vydělat peníze • přestože celočíselné a lineární programování jsou teoretické koncepty, mají skutečnou praktickou použitelnost i v prostředí České republiky • je možné zkombinovat psaní diplomové/bakalářské práce, ročníkového či softwarového projektu s prací pro firmu u které dostanete za svou práci zaplaceno a ještě Vaše práce nezůstane pouze na polici v knihovně, ale bude pomáhat v nějaké firmě či instituci efektivně řídit provoz či alokovat zdroje • pro praktické použití lineárního/celočíselného programování je potřeba aktivní znalost nějakého programovacího jazyka (C#, C++, Java apod.), nejenom porozumění teorii či praxi na papíře; není ovšem potřeba být kodér na nejvyšší úrovni

AristoTelos


Systém pro optimalizaci a řízení lidských zdrojů

Recommend Documents