Přejít na hlavní obsah

Dělání rozvrhů je věda. Systém jako na MUNI používají po celém světě

Nástroj, jehož výzkum iniciovala Hana Rudová z Fakulty informatiky MU, je dnes nasazený i na slavném MIT.

Hana Rudová přišla ve svojí dizertaci s prvním návrhem, který se časem přerodil v dnes celosvětově používaný systém UniTime.

Je to každosemestrální bitva: Kdo všechno se stihne zapsat do oblíbeného předmětu nebo vybojuje nejlepší seminární skupinu tělocviku? Tuhle bitvu svádějí studenti, jiné se ale odehrávají ještě pár týdnů předtím. Lidé, kteří vytvářejí rozvrhy, se snaží rozmístit na jednotlivých fakultách stovky až tisíce předmětů do omezeného počtu dní v týdnu a hlavně učeben. Pomáhá jim v tom nástroj, jehož výzkum iniciovala Hana Rudová z Masarykovy univerzity a dnes se používá i na MIT.

Když se nad tím člověk zamyslí, musí to být docela výzva. I na jedné jediné katedře se učí třeba i stovky předmětů. Někteří učitelé jsou na škole nastálo, ale někdo má jen částečný úvazek, takže může mít seminář nebo přednášku jen v některých časech. A všechno to komplikuje ještě to, že někde si studenti volí rozvrh každý podle svého, takže existuje mnoho kombinací předmětů, které by se neměly překrývat.

Dřív se tohle všechno dělalo ručně, například za pomoci excelových tabulek a hlavně díky velké zkušenosti jednotlivých rozvrhářů. „V době, kdy jsem nastoupila na doktorát, tedy ve druhé polovině 90. let, se ale ukázalo, že neexistují nástroje, které by uměly vytvořit rozvrh předmětů zohledňující individuální požadavky studentů. Proto jsem začala v rámci doktorátu tento rozvrhovací problém řešit,“ vzpomíná dnes už docentka Rudová, která přišla ve svojí dizertaci s prvním návrhem, který se časem přerodil v dnes celosvětově používaný systém UniTime.

Prvotní nápady prezentovala na konferenci, kde se setkala s lidmi z americké Purdue University, kde shodou okolností v té době řešili stejné věci. Mladá informatička tak dostala nabídku, aby se se svojí prací na půl roku přesunula do Indiany a v projektech zaměřených na rozvrhování předmětů pokračovala tam.

Po návratu z Purdue University pracovala na Masarykově univerzitě na několika projektech financovaných právě americkou univerzitou, v jejichž rámci vznikl základ dnešního systému UniTime. Do projektů se brzy zapojil Tomáš Müller původem z Univerzity Karlovy, který se stal hlavním výzkumníkem a vývojářem systému. Fakulta informatiky MU se ale na tomto výzkumu stále podílí.

Dnes už na 60 školách a institucích

Dnes už je systém etablovaný, a existuje také firma, která pomáhá s jeho implementací, i když spousty institucí tento volně dostupný systém využívají i bez její podpory. Kromě Purdue se používá na více než 60 školách a institucích, včetně věhlasného MIT. „Tam by si jistě dokázali vyvinout vlastní řešení. To naše se jim ale líbilo tolik, že to dělat nepotřebovali,“ komentuje Rudová.

Rudová pomáhala Unitime nasadit na filozofické fakultě, která řešila náročné rozvrhování v době velkých rekonstrukcí.

Na Masarykově univerzitě se systém prosazoval postupně, dnes ho využívá sedm z devíti fakult, ale ta informatická překvapivě nebyla první. „Jako první UniTime používala filozofická fakulta. Na konci října 2010 jsme měli velkou prezentaci pro všechny fakulty a kolegové z filozofické fakulty přišli s tím, že jim brzy začne rekonstrukce budov a všechny rozvrhy se musí předělat, protože se jim o hodně snížil počet místností. Říkala jsem si, že to nemůžeme stihnout, měli jsme na to asi jen šest týdnů, ale dokázali jsme to,“ vzpomíná Rudová.

V té době se UniTime používal už asi pět let na Purdue. Dnes tam zajišťuje tvorbu rozvrhu pro asi 39 tisíc studentů a jejich 190 tisíc registračních požadavků na devět tisíc kurzů.

Impulsem pro zavedení je často odchod rozvrháře

UniTime umožňuje snadné změny rozvrhu. Mezi jeho velké výhody patří i to, že dokáže vytvořit dobrý rozvrh při lepším využití učeben, a nejsou tak nutné jejich dodatečné pronájmy. Odstraňuje navíc problém se závislostí na osobě jednoho rozvrháře. „Impulsem pro nasazení systému bývá často nějaká změna na tomto postu. U nás rozvrhář odcházel, na fakultě sportovních studií šla rozvrhářka na mateřskou a v tom momentu všem došlo, že takový člověk v sobě kumuluje ohromné množství znalostí, které jdou jen obtížně předat,“ popisuje Rudová.

Na každé fakultě navíc fungují jiné zvyklosti a uplatňují se trochu jiná specifika. Na fakultě informatiky se rozvrh tvoří na základě registrace předmětů. Na pedagogické fakultě je náročné kombinovat dva obory a třeba na fakultě sportovních studií se musí myslet na přejíždění mezi jednotlivými sportovišti, na které zkrátka desetiminutová přestávka nestačí.

Nedá se vyhovět úplně každému

Algoritmus UniTimu tak trochu napodobuje činnost rozvrháře, který postupně bere jednotlivé předměty a umisťuje je do učeben, přičemž typicky začíná s těmi, které jsou obsazené největším množstvím studentů a potřebují velké učebny. Když narazí na problém, tak se o nějaký krok vrátí, něco odebere a udělá změnu. Aby se opravdu nevyskytly žádné časové nebo prostorové konflikty, musí se v systému napoprvé u každého předmětu pečlivě vyplnit řada informací. Výhodou ale je, že většina se jich už v dalších semestrech nemusí dodávat znovu, systém si je pamatuje i do dalších let.

Navíc jakmile se například u jednoho učitele vyplní, že každé úterý mezi 10. a 12. učit nemůže, protože má schůzi na děkanátu, automaticky se to propíše do všech jeho aktivit. A myslí se i na to, aby byla výuka vyvážená a někdo neučil ráno a pak až večer. „Bohužel ale není možné vytvořit ideální rozvrh pro všechny a vždy je třeba, aby se někdo přizpůsobil. Systém proto pomáhá rozvrháři se změnami, aby šlo i dodatečně zohlednit další požadavky,“ podotkla Rudová. Třeba v loňském podzimní semestru tak vznikl scénář výuky pro 6500 předmětů a 28 tisíc studentů s jejich 222 tisíci požadavky na předměty.

Rozvrhování je docela náročná disciplína, která vyžaduje schopnost pracovat s ohromným množstvím variant. Také proto se v něm dá i soutěžit. Aktuálně fakulta informatiky spoluorganizuje mezinárodní International Timetabling Competition 2019, do které se dá stále ještě zapojit. Účastníci v ní narazí třeba i na zadání z fakulty informatiky, pedagogické fakulty a fakulty sportovních studií.

Hlavní novinky