Posudek oponenta na diplomovou práci
Rozvrhování magisterských státních zkoušek pro FI
Radoslava Štefánika, studenta Fakulty informatiky MU
Předložená diplomová práce se zabývá problematikou rozvrhování magisterských státních zkoušek, které jsou každý semestr realizovány na FI. Součástí zadání práce je požadavek na modelování problému pomocí programování s omezujícími podmínkami a použití open source řešiče Constraint Solver Library (CPSolver) ze systému pro rozvrhování předmětů a zkoušek UniTime. Výsledkem práce je algoritmické vytvoření rozvrhu zkoušek pro předchozí tři semestry a jeho porovnání s ručně vytvořenými oficiálními rozvrhy.
Po úvodní části popisující současnou praxi na FI druhá kapitola velmi stručně popisuje problematiku rozvrhování ve vzdělávání a existující přístupy k řešení těchto problémů. Bohužel tu chybí větší důraz na rozvrhování zkoušek, zejména pak jasnější vymezení oproti existujícímu výzkumu v této oblasti. Také mi tu chybí zmínka o problémech rozvrhování personálu, ke kterým má v mnoha ohledech řešený problém rozvrhování magisterských státních zkoušek na FI blíže než k tradičním problémům rozvrhování ve vzdělávání.
Třetí kapitola popisuje problém rozvrhování s omezujícími podmínkami a základní přístupy k řešení tohoto problému. Následuje stručný popis knihovny CPSolver. Větší důraz by měl být kladen na použitou literaturu (některá tvrzení jsou bez reference, např. u zmiňovaného důkazu o konzistenci po cestě). Mezi stochastickými a heuristickými algoritmy chybí zmínka o simulovaném žíhání, které je v práci použito.
Čtvrtá kapitola popisuje samotný problém, který diplomant řešil. Problém je velmi dobře popsán slovně, chybí zde však důraz na formální popis problému.
Model problému pomocí řešiče CPSolver je popsán v páté kapitole. Diplomant zde popisuje, jak je jaká třída naprogramována, bohužel se tu ale trochu ztrácí modelování řešeného problému jako problému s omezujícími podmínkami: co je proměnná, jaké může mít hodnoty a proč je řešený problém modelován právě takto. Například z popisu není úplně jasné, jak se vytvoří různé proměnné (s různými doménami) pro jednotlivé členy komise a studenty (například to, že sloty pro studenty mají koncem dne různé domény). Druhá část páté kapitoly pak popisuje algoritmus řešení problému.
Šestá kapitola popisuje experimenty. Důraz je kladen na nastavení jednotlivých parametrů řešiče a jejich vlivu na výsledné řešení. V některých případech nemusí být technika zkoumání nastavení vždy jen jednoho parametru ideální. Porovnání s manuálním řešením je zajímavé. Řešení jsou bohužel porovnávána na (částečně) odlišných parametrech než implementovaná optimalizační kritéria. Také není z popisu úplně jasné, zdali manuální řešení splňují všechny pevné podmínky tak, jak jsou v práci definovány a implementovány ve výsledném řešiči.
Sedmá kapitola jen velmi krátce a v několika bodech shrnuje další vlastnosti rozvrhovacího problému, které implementované řešení nesplňuje a které by byly potřeba přidat pro úspěšné nasazení implementovaného řešení do praxe. Kapitola postrádá jakoukoliv diskuzi o těchto parametrech, například proč nejsou součástí implementovaného řešení nebo jak by je bylo možné implementovat.
Součástí práce jsou zdrojové kódy implementovaného řešení. Zdrojové kódy jsou přehledně napsány a strukturovány, chybí jim ale podrobnější (inline / Javadoc) dokumentace. Také by nebylo na škodu odstranit kód, který není ve výsledném řešení použit a ostatní pozůstatky předchozího testování. Použitá data jsou dostupná pouze na vyžádání (obsahují citlivé informace) a ani vstupní / výstupní formát není popsán.
Poznámky k implementaci: Podmínka MinCommissionAppearenceConstraint může vracet různé konflikty v závislosti na pořadí přiřazovaných proměnných. Všechna čtyři kritéria mají problémy s inkrementalitou, to jest, v průběhu řešení v paměti držená aktuální hodnota kritéria nemusí odpovídat součtu hodnot všech přiřazených proměnných. To může mít neblahý vliv na efektivitu řešiče. V případě simulovaného žíhání je obvyké, že sousední řešení je vybráno náhodně. Pokud vždy vybíráte nejlepší přiřazení (pro učitele či studenta), použití pravděpodobnosti přijetí zhoršujícího se řešení přestává mít smysl.
Celkově hodnotím tuto práci pozitivně. Jako velkou výhodu vidím řešení reálného problému s v praxi použitelným výsledkem. Bohužel tato výhoda je i velkou nevýhodou, protože výsledný model i řešič je příliš specifický pro daný problém. Vzhledem k celkové kvalitě doporučuji tuto práci uznat jako diplomovou a navrhuji ji ohodnotit známkou B (velmi dobře).
Otázky na obhajobu:
● Může komise během prohledávání změnit obor, nebo toto nastavení zůstává po ukončení konstrukční fáze nezměněno?
● Co vás vedlo k odpřiřazování komise během řešení? Zkoušel jste jiné přístupy k opušťení lokálního optima?
● Splňují ručně vytvořené oficiální rozvrhy všechna pevná omezení tak, jak jsou v práci definována a implementována ve výsledném řešiči?
Ve Zlíně 15. června 2014 RNDr. Ing. Tomáš Müller, Ph.D.
Space Management & Academic Scheduling Purdue University
