na FI Rozvrhovanie magisterských štátnych skúšok

F A K U L T A I N F O R M A T I K Y

^ÄS

Rozvrhovanie magisterských štátnych skúšok na FI

D I P L O M O V Á P R Á C A

Radoslav Štefánik

B r n o , jaro 2014

Prehlásenie

Prehlasujem, že táto diplomová práca je mojím pôvodným autor­

ským dielom, ktoré som vypracoval samostatne. Všetky zdroje, pra­

mene a literatúru, ktoré som pri vypracovaní používal alebo z nich čerpal, v práci riadne citujem s uvedením úplného odkazu na prí­

slušný zdroj.

Radoslav Štefánik

Vedúci práce: doc. Mgr. Hana Rudová, Ph.D.

Poďakovanie

Predovšetkým by som chcel poďakovať doc. Mgr. Hane Rudovej, Ph.D. za cenné rady a veľkú trpezlivosť pri vedení tejto práce. Ďa­

lej by som chcel poďakovať Tomášovi Miillerovi, ktorý je autorom nástroja, ktorý umožnil vznik tejto práce.

Zhrnutie

Táto práca sa zaoberá rozvrhováním magisterských štátnych skúšok na Fakulte informatiky Masarykovej univerzity V úvode je priblí­

žená oblasť rozvrhovacích problémov a používaných metód na ich riešenie. Ďalej je popísaný nástroj CPSolver využitý pri implementá­

cie tejto práce. V ďalšej časti je detailne popísaný riešený problém a popísaný postup pri riešení problému. Súčasťou práce je aj porovna­

nie kvality použitých algoritmov s ručne vytvorenými rozvrhmi.

Kľúčové slová

Programovanie s obmedzujúcimi podmienkami, CPSolver, rozvrho- vanie, magisterské štátne skúšky, iterativně dopredné prehľadávanie

Obsah

1 Úvod 1 2 Rozvrhovacie problémy vo výuke 3

3 Programovanie s obmedzujúcimi podmienkami a CPSolver 7

3.1 Prehľadávacie techniky 8 3.1.1 Systematické prehľadávanie 8

3.1.2 Stochastické a heuristické algoritmy 10

3.2 CPSolver 12 3.3 Doménové premenné a hodnoty 12

3.4 Pevné obmedzenia 12 3.5 Optimalizačné kritéria 13 3.6 Model problému 13 3.7 Prehľadávanie v CPSolveri 14

4 Opis problému 17 4.1 Pevné obmedzenia 19

4.1.1 Základné obmedzenia 19 4.1.2 Oborové obmedzenia 19 4.1.3 Obmedzenia zdrojov 20 4.2 Optimalizačné kritériá 21

4.2.1 Oborové preferencie komisie 21

4.2.2 Využitie času 22 5 Model problému v CPSolveri 25

5.1 Pevné obmedzenia 26 5.2 Optimalizačné kritériá 31 5.3 Konštrukčná fáza 32 5.4 Vylepšovanie riešenia 37

5.4.1 Definícia okolia 37 5.4.2 Zrušenie priradení 38 5.4.3 Prehľadávanie 39

6 Experimenty 41 6.1 Evaluator 41 6.2 Nastavenia prehľadávacích algoritmov 42

6.2.1 Nastavenie konštrukčnej fázy 44

6.2.2 IFS 46 6.2.3 Simulované žíhanie 47

6.3 Nastavenie váh optimalizačných kritérií 49

7 Diskusia k ďalším rozšíreniam 57

8 Záver 59 A Obsah CD 65

1 Úvod

Rozvrhovanie je široká oblasť zahŕňajúca mnohé rozdielne problémy.

Cieľom rozvrhovania je obvykle zaradenie konkrétnych osôb alebo úloh na konkrétne miesto a čas v rozvrhu a je potrebné pritom do­

držať obmedzenia vyplývajúce z problému. Podľa typov problémov vieme rozvrhovanie rozdeliť do širších kategórii s určitými spoloč­

nými znakm,i ako je napríklad rozvrhovanie dopravy, športov, stro­

jov, zamestnancov alebo rozvrhovanie výuky [17]. V rámci tejto práce sa budeme zaoberať problémom rozvrhovania magisterských štát­

nych skúšok na Fakulte informatiky, ktorý spadá do oblasti rozvrho­

vania výuky. Každý semester sa na Fakulte informatiky konajú záve­

rečné štátne skúšky. Týchto skúšok sa musí zúčastniť veľké množ­

stvo študentov, ktorých je potrebné vhodne rozvrhnúť. Toto obdobie záverečných štátnych skúšok trvá obvykle dva týždne, pričom v pr­

vom týždni sa konajú bakalárske štátne skúšky [7] a v nasledujú­

com týždni magisterské skúšky. Skúška každého študenta je zložená z dvoch častí obhajoby záverečnej práce a z ústnej skúšky. Pri obha­

jobe sa naviac k u skúške dostaví vedúci a oponent záverečnej práce a preto môžme rozvrhnúť študenta len vtedy, ak sú obaja členovia ob­

hajoby dostupní. U magisterských študentov musíme naviac dbať na vhodné zloženie komisie pre skúšanie jeho oboru.

Rozvrhovanie týchto skúšok má na starosti rozvrhár, ktorý na to využíva nástroj [15] umožňujúci manuálne rozvrhovať študentov a skúšajúcich. Riešenie tohto problému ale nie je jednoduché a rozvr- hárovi môže zabrať značný čas. Preto je našou motiváciou pre túto prácu využiť dostupný výpočtový výkon, ktorý poskytujú počítače v dnešnej dobe pre uľahčenie práce rozvrhárovi a pomocou nich au­

tomaticky vygenerovať rozvrh spĺňajúci všetky obmedzenia.

V prvej kapitole tejto práce stručne popíše existujúce rozvrhova­

de problémy s ich charakteristikami a priblíži hlavné smery, ktoré sa venujú ich riešeniu.

Ďalšia kapitola priblíži oblasť programovania s obmedzujúcimi podmienkami. Uvedieme základne pojmy používané v rámci tejto problematiky. Popíšeme používané prehľadávacie metódy. V ďal­

šej časti kapitoly predstavíme nástroj CPSolver [13] použitý v tejto práci. Uvedieme jeho jednotlivé časti a ako sa využívajú pri modelo-

vaní problému. Následne popíšeme prehľadávacie metody, ktoré sú využívané CPSolverom.

Nasledujúca kapitola priblíži problém, ktorého riešením sa za­

oberá táto práca. Popíšeme základné entity problému a uvedieme všetky obmedzenia, ktoré musí spĺňať výsledné riešenie. Potom si uvedieme optimalizačné kritéria, na ktorých závisí kvalita rozvrhu.

Implementácia problému v CPSolveri je obsahom ďalšej kapitoly.

V nej uvedieme, ako vyzerajú základné triedy problému a popíšeme použité obmedzenia. Následne je navrhnutý postup konštrukcie ini- ciálneho riešenia, v ktorom sa postupne konštruujú jednotlivé komi­

sie. Pre zvolenú komisiu sa vyberie obor, potom sa do nej priradia skúšajúci a následne sa do nej rozvrhnú študenti. Takto zostrojené riešenie sa ďalej vylepšuje pomocou algoritmov lokálneho prehľa­

dávania, ktoré sú popísané v ďalšej časti kapitoly spolu s navrhnu­

tými definíciami okolí, ktoré sú využívané v prehľadávacích algorit- moch.

V nasledujúcej kapitole sú popísané vykonané experimenty, ktoré sa venovali popisu vplyvu nastavení parametrov pre prehľadáva­

cie algoritmy na priebeh algoritmu. Ďalej je vyhodnotený vplyv na­

stavenia váh rôznych optimalizačných kritérií na jednotlivé veličiny určujúce kvalitu riešenia. N a záver kapitoly je uvedené porovna­

nie použitých algoritmov a porovnanie riešenia vytvoreného prog­

ramom oproti ručne vytvorenému riešeniu. N a záver práce je uve­

dený možný smer pre budúce rozšírenia nutné pre prípadné použitie v praxi.

2 Rozvrhovacie problémy vo výuke

V tejto práci sa budeme zaoberať problémom z oblasti rozvrhovania výuky. Túto oblasť sa zvykne deliť na tri základné oblasti: stredoš­

kolské rozvrhovanie, rozvrhovanie predmetov a rozvrhovanie skú­

šok. Problémy z oblastí rozvrhovania predetov a rozvrhovania skú­

šok boli predmetom súťaže International Timetabling Competition 2007 (ITC) [11]. Stredoškolské rozvrhovanie bolo predmetom súťaže ITC 2011 [18].

V typických problémoch stredoškolského rozvrhovania (High school timetabling^x) [22] rozvrhujeme učiteľov a triedy na určitý čas a miest­

nosť v rozvrhu. Trieda je n-tica študentov, ktorí majú presne rovnaký rozvrh. Každý vyučujúci i má s triedou j určitý počet predmetov vy­

jadrený číslom fij. Cieľom je potom rozvrhnúť predmety tak, aby žiadny učiteľ a žiadna trieda nemala v rovnakom čase dva alebo viac predmetov [5]. Rozvrh triedy v jednom dni musí byť súvislý, nemôže tak obsahovať časovú medzeru medzi predmetmi, v ktorej nemá žiadnu výuku. V rozvrhu musia byť pritom dodržané kapa­

city jednotlivých miestností. Ďalšie obvyklé požiadavky na stredoš­

kolské rozvrhy je napríklad rozvrhovanie predmetov, ktoré sú vy­

učované viac krát do týždňa maximálne raz za deň [16].

Ďalšie dve uvedené kategórie zahrňujú rozvrhovacie problémy v univerzitnom prostredí. Každý semester sa na univerzitách musí vykonávať rozvrhovanie predmetov (Course timetabling) [10]. N a roz­

diel od stredoškolského rozvrhovania tu nie sú študenti rozdelení do pevne stanovených tried, ale každý študent si môže vybrať sku­

pinu predmetov, ktoré bude navštevovať. Dáta týkajúce sa všetkých študentov často nemusia byť v čase rozvrhovania kompletné, pre­

tože rozvrhovanie predmetov sa často koná pred samotným zápisom predmetov.

Rozvrhovanie skúšok (Exam timetabling) [10] sa koná k u koncu se­

mestra a rieši problém, kde v určitom časovom období musia štu­

denti absolvovať skúšky zo všetkých svojich zapísaných predmetov.

Jednotlivé skúšky je potrebné rozvrhnúť do tohto obdobia tak, aby termíny, ktoré sa prekrývajú, nemali spoločných študentov. N a roz­

diel od rozvrhovania predmetov sa kladie dôraz na čo najväčší rozp- 1. Základné pojmy majú v zátvorkách uvedený aj svoj anglický názov.

tyl skúšok pre študentov Ďalší rozdiel oproti rozvrhovaniu predme­

tov je, že v niektorých prípadoch môže byť povolené konanie via­

cerých predmetov v jednej miestnosti. Ďalej v čase rozvrhovania sú vždy známe konečné počty študentov, ktorí sa budú účastniť skú­

šok .

Problém, ktorým sa zaoberá táto práca by podľa názvu patril do kategórie problémov rozvrhovania skúšok, avšak v mnohých ob­

lastiach sa od tejto kategórie líši. N a rozdiel od klasických problé­

mov rozvrhovania skúšok sa študent dostaví k u skúškam iba raz a pri skúške musí mať prítomného vedúceho a oponenta svojej záve­

rečnej práce. Tento rozvrhovací problém si podrobnejšie priblížime v jednej z nasledujúcich kapitol.

Takmer všetky reálne problémy, ktoré spadajú medzi uvedené problémy rozvrhovania výuky sú NP-úplné problémy [9]. To zna­

mená, že pre tieto problémy nevieme zostrojiť algoritmus, ktorý by vedel nájsť optimálne riešenie v polynomiálnom čase. Z tohto dô­

vodu sa pre riešenie týchto problémov používajú rôzne heuristické algoritmy, ktoré sa snažia nájsť akceptovateľné riešenie z pohľadu užívateľa. Riešeniu rozvrhovacích problémov sa venujú rôzne rie­

šiace metódy a havné z nich si uvedieme.

V minulosti populárna technika spočívala v redukcii problému na problém ofarbenia grafu [5]. Rozvrhovací problém sa vyjadrí ako graf, kde vyučujúci, študenti a predmety sú vyjadrené ako uzly a hrany grafu. Predmety sa vyjadria ako vrcholy grafu a predmety, ktoré majú spoločných študentov alebo vyučujúcich sa spoja hra­

nami. Graf sa potom ofarbí k farbami, kde k určuje počet dostupných časových úsekov v rozvrhu .

Ďalší často využívaný prístup je založený na princípoch mate­

matického programovania [23]. Problém sa vyjadrí ako lineárny celočí­

selný optimalizačný problém pomocou lineárnych rovníc a optima­

lizačnej funkcie. Takto vyjadrené problémy mávajú často krát veľké množstvo premenných. Z tohto dôvodu sa problém zvykne rozdeliť na podproblémy, ktoré sa riešia sekvenčne.

Veľmi populárne algoritmy sú z oblasti metaheuristík [9]. Tieto al­

goritmy využívajú heuristické metódy na vyššej úrovni v kombinácii s lokálnym prehľadávaním priestoru riešení. Typickými zástupcami algoritmov z tejto oblasti sú simulované žíhanie (simulated annea-

2. ROZVRHOVACIE PROBLÉMY VO VÝUKE ling), Tabu search, genetické algoritmy a mnoho iných. Bližší popis spomenutých metód je možné nájsť napríklad v [6].

Relatívne nový smer predstavujú hyperheuristiky [3]. Sú to algo­

ritmy, ktoré používajú viaceré základné heuristiky k zmene stavu riešenia. V každom kroku sa potom snažia zvoliť najvhodnejšiu he­

uristiku pre konkrétny stav riešenia. Výhodou tohto prístupu je, že na rozdiel od niektorých iných prístupov nie sú hyperheuristiky opti­

malizované na jednu konkrétnu inštanciu problému, ale dajú sa po­

užiť aj na širšiu oblasť problémov [4].

3 Programovanie s obmedzujúcimi podmien­

kami a CPSolver

Nástroj CPSolver, použitý v tejto práci, je založený na princípoch programovania s obmedzujúcimi podmienkami [19]. Problém sa de­

finuje pomocou pevných obmedzení. To sú také podmienky, ktoré musia byť v riešení splnené. Pri programovaní s obmedzujúcimi pod­

mienkami sa neurčuje ako sa má problém riešiť, ale definuje sa po­

mocou deklaratívnych obmedzení.

Problém s obmedzujúcimi podmienkami (CSP) P je vyjadrený ako tro­

jica P = (X, D, C), kde

• X — (xi,..., xⁿ) je množina premenných problému

• D = (Di,..., Dⁿ) je množina príslušných domén takých, že

• C = ( C i , . . . , C^m) sú obmedzenia. Každé obmedzenie C j G C tvorí dvojica (tj,Rj), kde t j C X je podmnožinou k premen­

ných a Rj je /c-árna relácia na príslušnej podmnožině domén dj.

Konzistentné riešenie problému je také priradenie konkrétnych hodnôt do podmnožiny premenných z ich príslušných domén, ktoré nepo­

rušujú žiadne obmedzenie. A k je v riešení jedna alebo viac premen­

ných s nepriradenou hodnotou, tak toto riešenie voláme čiastočné rie­

šenie problému. Riešenie je konzistentné, ak žiadne priradenie hodnoty do príslušnej premennej neporušuje žiadne obmedzenie z C. Úplné riešenie je také, v ktorom je každej premennej priradená jedna hod­

nota z príslušnej domény a toto priradenie neporušuje žiadne ob­

medzenie. Typicky riešenými úlohami môže byť nájdenie jedného úplného riešenia, nájdenie všetkých riešení problému alebo nájdenie riešenia s optimálnou hodnotou definovanou pomocou objektívnej funkcie na niektorých alebo všetkých premenných.

Deklaratívny prístup k vyjadreniu problému blízky k princípom logického programovania viedol k u vzniku smeru Constraint Logic Programming (CLP) [21], ktorý kombinuje deklaratívny prístup logic­

kého programovania s programovaním s obmedzujúcimi podmien­

kami. Problémy riešené pomocou C L P sa vyjadria pomocou logic­

kých obmedzujúcich podmienok. Pre takto vyjadrené problém sa pri

prehľadávaní potom využijú techniky propagácie obmedzení, ktoré zmenšujú prehľadávaný stavový priestor.

Pre mnoho reálnych problémov sa neuspokojíme s nájdením ne­

jakého riešenia, ale vyžadujeme od neho, aby malo dobrú kvalitu.

Pre vyjadrenie kvality riešenia sa preto obvykle definujú optimali­

začné funkcie [1], ktoré každému riešeniu spočítajú číselnú hodnotu.

Cieľom výpočtu je potom nájsť riešenie, ktoré spĺňa všetky obme­

dzenia a pritom minimalizuje hodnotu optimalizačnej funkcie.

3.1 Prehľadávacie techniky

N a riešenie CSP sú využívané dva hlavné prístupy: systematické prehľadávanie priestoru riešení a stochastické techniky lokálneho prehľadávania.

3.1.1 Systematické prehľadávanie

Systematické prehľadávanie je založené na myšlienke postupného generovania všetkých možných riešení problému a kontrole splnení obmedzení v týchto riešeniach. Často využívané metódy prehľadá­

vania sú založené na metóde backtrackingu [19], ktoré postupne sys­

tematicky prehľadávajú celý priestor riešení. Základný backtracking buduje riešenie postupným priraďovaním hodnôt do premenných, až kým sa nedostane do situácie, keď už nemôže ďalej pokračovať.

V tom prípade sa vráti naspäť k najbližšej premennej, z ktorej môže ďalej pokračovať. Takto systematicky prehľadáva celý priestor až kým nenájde úplné riešenie. Časová náročnosť takéhoto prehľadá­

vania je pre väčšinu problémov exponenciálna. Veľká neefektívnosť algoritmu je spôsobená častým opakovaným zlyhaním spôsobeného rovnakým problémom. Ďalšou príčinou býva neskoré zistenie spô­

sobeného konfliktu.

Ďalší spôsob hľadanie riešenia je založený na myšlienke propa­

gácie obmedzení. Priradenie hodnoty do premennej môže často za­

brániť špecifickým priradeniam v iných doménových premenných.

Týmto premenným potom môžeme obmedziť ich doménu o tieto hodnoty. Často využívané sú konzistenčné techniky [1]. Základné konzistenčné techniky sú popísané pomocou grafových algoritmov.

3. P R O G R A M O V A N I E S O B M E D Z U J Ú C I M I P O D M I E N K A M I A C P S O L V E R

CSP bude reprezentovaný pomocou grafu nasledovne: Doménové premenné problému sa vyjadria ako vrcholy a každé binárne obme­

dzenie na premenných i a j sa spojí príslušnou hranou medzi odpo­

vedajúcimi vrcholmi.

Najjednoduchšou technikou je vrcholová konzistencia. Tá z domény premennej vyradí všetky hodnoty, ktoré porušujú unárne obmedze­

nia na danej premennej.

Ďalšou technikou je hranová konzistencia. Tá zaistí konzistenciu bi­

nárnych obmedzení problému. To znamená, že hrana (Vi, Vj) je kon­

zistentná práve vtedy, ak pre každú hodnotu x z domény V existuje nejaká hodnota y v doméne Vj taká, že priradenie Vi — x a Vj — y neporušuje binárne obmedzenia medzi Vi a Vj. Existujú viaceré al­

goritmy hranovej konzistencie od AC-1 po AC-7. Ich popis je možné nájsť napríklad v [19].

Silnejšou technikou na redukciu domén premenných je konzisten­

cia po ceste [1]. Táto konzistencia kontroluje, či pre každý pár premen­

ných X a Y existuje priradenie hodnôt do každej premennej, ktorá sa nachádza na ceste medzi X aY. Bolo dokázané, že CSP je konzis­

tentný po ceste práve vtedy, ak sú konzistentné všetky cesty dĺžky 2.

Prehľadávanie často kombinuje metódy systematického prehľa­

dávania s obmedzovaním domén. N a zefektívnenie prehľadávania pomocou backtrackingu boli navrhnuté viaceré metódy. Základné techniky pre zefektívnenie backtrackingu spočívajú vo vyhnutí sa opakujúcim priradeniam spôsobujúcim nekonzistentnosť riešenia.

Metóda backjumpingu sa snaží vyhnúť takémuto opakovaniu. Pre­

hľadávanie postupuje ako backtracking, ale ak narazí na nekonzis­

tentné priradenie, tak sa pozrie na premenné, ktoré spôsobili kon­

flikt. A k algoritmus už navštívil všetky hodnoty v daných domé­

nach, tak sa vráti do najbližšej premennej, ktorá spôsobila konflikt.

Základný backtracking môže byť ďalej rozšírený o ďalšie heuris­

tické metódy, ktoré vyberajú ďalšiu premennú podľa určitých krité­

rií. Môže sa jednať napríklad o premennú s najmenšou doménou.

Takýto výber má za úlohu odstrániť možné problémy čo najskôr a zabrániť tak opakovanému výberu tejto premennej v neskoršej fáze.

3.1.2 Stochastické a heuristické algoritmy

Alternatívou systematického prehľadávania sú algoritmy založené na lokálnom prehľadávaní. Takéto algoritmy na rozdiel od syste­

matického prehľadávania negarantujú nájdenie úplného riešenia, ale vďaka svojej efektivite sú často jedinou možnosťou pre riešenie reál­

nych problémov. Základnou myšlienkou takýchto algoritmov je za­

čať s nejakým náhodným alebo heuristicky skonštruovaným rieše­

ním, ktoré je nekonzistentné alebo neúplné, a toto zlepšenie postupne vylepšovať drobnými zmenami.

Najjednoduchšou používanou metódou lokálneho prehľadáva­

nia je metóda Min-Conflicts [19]. V každom kroku algoritmu sa vybe­

rie náhodná premenná s nepriradenou hodnotou, alebo hodnotou, ktorá porušuje obmedzenia, a tejto premennej sa snaží vybrať nová hodnota, ktorá minimalizuje celkový počet spôsobených konfliktov alebo nepriradených premenných. A k sa nenájde hodnota, ktorá zni­

žuje celkový počet porušených premenných, tak sa vyberie hodnota ktorá tento počet nezhoršuje.

Ďalším populárnym algoritmom je Hill-climbing [í]. Tento algo­

ritmus v každom kroku vyberá novú hodnotu niektorej premennej, ktorá zlepší celkový počet porušených obmedzení problému alebo zníži počet premenných bez priradenej hodnoty. Po tom ako algorit­

mus narazí na lokálne minimum, to znamená, že nevie nájsť ďalšiu hodnotu, ktorá by zlepšila riešenie, sa algoritmus spustí znova z ná­

hodne vygenerovaného stavu.

V tejto práci použitý nástroj je založený na algoritme iteratívneho dopredného prehľadávania (Iterative Forward Search, ďalej ako IFS) [13]. Riešenia, s ktorými výpočet pracuje musia byť vždy konzis­

tentné, čiže také, v ktorých nie sú porušené žiadne pevné obme­

dzenia. Tieto riešenia ale nemusia byť nutne úplné, čo znamená, že niektoré premenné môžu ostať bez priradenej hodnoty. Prehľadá­

vanie pomocou IFS pracuje v iteráciách (algoritmus 3.1). Začína sa s prázdnym riešením a algoritmus si pamätá najlepšie nájdené rieše­

nie (riadky 2-3). Algoritmus pokračuje, až kým nie je splnená ukon­

čujúca podmienka, čo môže byť napríklad nájdenie kompletného riešenia alebo uplynutie určitej doby výpočtu (riadok 4). V každom kroku sa vyberie premenná, s ktorou sa bude pracovať (riadok 5).

Tejto premennej sa následne z jej domény vyberie nová hodnota (ria-

3. P R O G R A M O V A N I E S O B M E D Z U J Ú C I M I P O D M I E N K A M I A C P S O L V E R

Algoritmus 3.1 Popis algoritmu I F S function I F S

solution -(—prázdne riešenie best <— solution

while C A N C O N T I N U E do

var ^-SELECTVARlABLE(so/wíion) val SELECTVALUE(war)

conflicts -(—konflikty spôsobené priradením Ivar, val) for každé priradenie Ivar, val) z conflicts do

zruš priradenie Ivar, val) zo solution end for

pridaj priradenie Ivar, val) do solution if COMPARESOLUTlON(so/wíion, best) then

best <— solution end if

end while return best end function

dok 6). A k táto nová hodnota spôsobí konflikty v aktuálnom riešení (riadok 7), tak sa zruší priradenie všetkých hodnôt, ktoré sú v kon­

flikte s novým priradením (riadky 8-10). Kvalita riešenia sa porovná s najlepším nájdeným riešením, a ak je lepšie, tak sa uloží namiesto doterajšieho najlepšieho (riadky 12-14). Po dosiahnutí ukončujúcej podmienky sa obnoví najlepšie nájdené riešenie (riadok 16). Algo­

ritmus I F S ďalej závisí na niekoľkých metódach, pomocou ktorých sa dá upraviť priebeh prehľadávania. Tieto metódy sú: ukončujúca podmienka, výber premennej, výber hodnoty a porovnanie dvoch riešení. Ukončujúcou podmienkou môže byť dosiahnutie určitého času behu programu alebo určitý počet iterácií. Pre výber doméno- vej premennej a novej hodnoty priradenia tejto premennej sa môžu použiť rôzne heuristické algoritmy. Ako porovnanie riešení sa poze­

ráme na počet nepriradených premenných, a v prípade ak je tento počet rovnaký tak porovnávame váženú sumu optimalizačných kri­

térií riešenia.

3.2 CPSolver

N a riešenie problému rozvrhovania magisterských štátnych skúšok na Fakulte informatiky bol v tejto práci použitý nástroj CPSolver vy­

vinutý Tomášom Múllerom [13], ktorý je súčasťou systému UniTime.

Tento nástroj bol úspešne použitý aj pre rozvrhovanie predmetov na univerzite Purdue [20]. CPSolver (Constraint Solver Library) je založený na princípoch programovania s obmedzujúcimi podmien­

kami. Poskytuje nástroje umožňujúce modelovať problémy pomo­

cou základných objektov programovania s obmedzujúcimi podmien­

kami ako sú premenné, hodnoty a obmedzenia. Nástroj CPSolver hľadá riešenie pomocou algoritmu IFS, ktorý je popísaný v pred­

chádzajúcej kapitole. Problém v CPSolveri je modelovaný pomocou definovaných tried, ktoré sú podrobnejšie popísané v nasledujúcich kapitolách.

3.3 Doménové premenné a hodnoty

Pri vytváraní modelu problému je potrebné určiť si doménové pre­

menné a ich hodnoty, ktoré i m môžu byť priradené. Doménové pre­

menné sú v CPSolveri reprezentované triedou Variable. Každá pre­

menná má vytvorenú vlastnú inštanciu. Premenná obsahuje svoju doménu hodnôt a uchováva si informáciu o aktuálne priradenej hod­

note. Doménová hodnota, ktorá sa priraďuje do premennej je repre­

zentovaná ako objekt typu Value. Objekt tejto triedy obsahuje dvoj­

icu hodnôt, doménovú premennú, k u ktorej patrí a hodnotu, ktorú reprezentuje. Každá premenná má určenú svoju jedinečnú doménu hodnôt, ktoré môžu byť tejto premennej priradené. Doménu je po­

trebné na začiatku inicializovať tak, že sa do atribútu values vložia všetky doménové hodnoty pre konkrétnu premennú.

3.4 Pevné obmedzenia

Počas celého priebehu prehľadávania je potrebné zachovávať kon­

zistenciu riešenia. Pred každým priradením hodnoty do premennej sa zrušia všetky priradenia, ktoré by spôsobili porušenie pevného obmedzenia. Preto je potrebné pred každým priradením hodnoty vy-

3 . P R O G R A M O V A N I E S O B M E D Z U J Ú C I M I P O D M I E N K A M I A C P S O L V E R

počítať všetky konfliktné hodnoty pre každé definované obmedze­

nie. Obmedzenia sú v CPSolveri reprezentované abstraktnou triedou Constraint. Každé obmedzenie typu Constraint musí implementovať metódu C O M P U T E C O N F L I C T S . Vstupom metódy je hodnota typu Va- lue, ku ktorej je potrebné skontrolovať porušené pevné obmedzenia, ktoré by spôsobilo priradenie tejto hodnoty. Všetky hodnoty, ktoré by spôsobili konflikt s danou hodnotou sa vkladajú do množiny con- flicts, ktorá je argumentom metódy.

3.5 Optimalizačné kritéria

Kvalita nájdených riešení sa určuje pomocou vážených optimalizač­

ných kritérií. Pri hľadaní riešenia sa snažíme minimalizovať celkovú váženú hodnotu sumy všetkých použitých kritérií. V CPSolveri sú tieto kritéria reprezentované abstraktnou triedou Criterion. Každá trieda typu Criterion poskytuje metódu G E T V A L U E na zistenie vplyvu priradenia hodnoty. Táto metóda podľa vstupnej hodnoty vráti de­

satinné číslo, ktoré určuje zmenu hodnoty daného optimalizačného kritéria, ktoré by spôsobilo priradenie danej hodnoty. Pretože je táto metóda v priebehu výpočtu volaná mnohokrát, je potrebné, aby sa celková hodnota kritéria počítala vždy inkrementálně. Zmena spô­

sobená priradením premennej sa pričíta k celkovej sume optimali­

začného kritéria, ktorá sa tak nemusí počítať cez všetky premenné.

Každé kritérium si uchováva celkovú sumu optimalizačných kritérií všetkých priradených hodnôt, ktorá je aktualizovaná vždy pri kaž­

dom priradení novej hodnoty alebo zrušení priradenia. Každé krité­

rium má definovanú svoju váhu, s ktorou je započítané do celkovej kvality riešenia.

3.6 Model problému

Definícia rozvrhovacieho problému je reprezentovaná triedou Mo­

del. Táto trieda obsahuje všetky doménové premenné, obmedzenia a optimalizačné kritéria a zároveň sa stará o reprezentovanie stavu riešenia, počítanie informácii o uchovávanom riešení a obsahuje rie­

šenie samotné. Všetky premenné, obmedzenia a kritéria je potrebné pri inicializácii do modelu pridať príslušnými metódami. Dôležitá

Model Variable Value

Constraint Criteria

C O M P U T E C O N F L I C T S O G E T V A L U E O

Obr. 3.1: Schéma modelu problému v CPSolveri¹

uložená informácie je počet premenných s priradenými a neprira- denými hodnotami. Okrem nich je možné v modeli uchovávať uží­

vateľsky definované premenné, ktoré sa budú priebežne aktualizo­

vať. Pred a po zmene priradenej hodnoty do doménovej premen­

nej sú v modeli vyvolané príslušné metódy B E F O R E A S S I G N E D , A F T E - R A S S I G N E D , B E F O R E U N A S S I G N E D , A F T E R U N A S S I G N E D , ktoré môžu upraviť stav modelu ako reakciu na zmenu priradených hodnôt v rie­

šení. Typicky sa tu priebežne ukladajú informácie, ktoré často využí­

vame počas výpočtu, ako napríklad rozvrhnutie skúšajúcich v kon­

krétnom čase. Schéma modelu problému v CPSolveri je znázornená v obrázku 3.1.

3.7 Prehľadávanie v CPSolveri

O prehľadávanie riešení v CPSolveri podľa algoritmu IFS sa stará trieda Solver. V každej iterácii sa vyberie nové okolie riešenia, ktoré je reprezentované triedou Neighbour a obsahuje informácie o pre­

mennej a novej hodnote. A k nová hodnota premennej poruší nejaké pevné obmedzenie, tak premenným, ktoré sú v konflikte s vybranou hodnotou, sa zruší priradenie ich hodnôt. Po skontrolovaní konflikt­

ných priradení sa vybraná hodnota priradí do premennej. Pre výber nového susedného riešenia sa môžu využiť rôzne heuristické me-

3. P R O G R A M O V A N I E S O B M E D Z U J Ú C I M I P O D M I E N K A M I A C P S O L V E R

tódy.

Metódy pre výber okolia sú reprezentované abstraktnou triedou NeighbourSelection, ktorá musí mať implementovánu metódu S E -

L E C T N E I G H B O U R . Výber okolia v sebe obsahuje výber premennej a výber hodnoty algoritmu IFS.

Výber okolia môže využívať techniky výberu premennej (variable selection), ktorej následne vyberie nové priradenie (value selection).

Pri výbere premennej sa zvolí jedna premenná, ktorej budeme pomo­

cou výberu priradenia vyberať novú hodnotu. Pre výber premennej a výber priradenia sú k tomu v CPSolveri určené rozhrania Variable- Selection a ValueSelection.

Pre jednoduchý výber premennej je v CPSolveri k dispozícii trieda GeneralVariableSelection. Táto trieda vyberie náhodnú premennú, ktorá nemá priradenú hodnotu, alebo ak majú všetky premenné pri­

radenú hodnotu, tak vyberie zo všetkých premenných jednu náhodne N a základný výber priradenia premennej je možné použiť triedu GeneralValueSelection. Tá vyberá novú hodnotu podľa viacerých kritérií, ktorých váha sa dá nastaviť. Medzi tieto kritéria patrí počet priradených hodnôt v riešení, ktoré by porušovali niektoré z pev­

ných obmedzení po jej priradení, ďalej počet konfliktov s danými hodnotami spôsobených v minulosti a vplyv hodnoty na optimali­

začné kritéria problému

CPSolver takisto poskytuje viaceré algoritmy výberu nového oko­

lia založené na lokálnom prehľadávaní, ktoré doplňujú IFS. Najjed­

noduchší výber okolia je reprezentovaný triedou StandardNeighbour- Selection, ktorá vyberá najlepšie priradenie len z podmnožiny oko­

litých riešení, v tomto prípade len priradenie pre jednu premennú.

Táto premenná sa vyberie pomocou zvolenej triedy VariableSelec- tion, ktorej potom vyberie najvhodnejšiu premennú pomocou vybra­

nej triedy ValueSelection.

CPSolver bol ďalej rozšírený o rôzne heuristické prehľadávacie algoritmy, ktoré boli doplnené v rámci súťaže ITC 2007 [14]. Medzi nimi sú napríklad Great deluge, Simulated annealing alebo Tabu se­

arch.

CPSolver umožňuje pri výbere okolia využiť rozširujúci nástroj konfliktnej štatistiky (Conflict-based Statistics) [13], ktorá počíta vý- 1. Pre schémy uvedené v texte tejto práce využívame UML class diagram [2]

skyt konfliktov spôsobených v minulosti spolu s priradeniami, ktoré ich spôsobili. Pri výbere sú tak hodnoty, ktoré spôsobili konflikt v mi­

nulosti penalizované a umožňujú tak zamedziť opakovaniu rovna­

kých zlých priradení a efektívne tak pôsobí ako dynamický výber okolia.

4 Opis problému

Študenti Fakulty informatiky musia ukončiť svoje štúdium absol­

vovaním záverečných štátnych skúšok. Tie sa konajú na konci kaž­

dého semestra v posledných týždňoch skúškového obdobia. Magis­

terským skúškam predchádzajú bakalárske skúšky, ktoré sa konajú predchádzajúci týždeň. Bakalárske skúšky majú podobný formát ako magisterské a ich popis je možné nájsť v [7, 8]. Magisterská záve­

rečná skúška pozostáva z dvoch častí, pričom každá má dĺžku 30 mi­

nút. Prvá časť štátnej skúšky je obhajoba diplomovej práce, po kto­

rej nasleduje ústna skúška. Počas obhajoby prezentuje študent svoju diplomovú prácu, k u ktorej má pridelených vedúceho práce a opo­

nenta, ktorí by mali byť prítomní počas obhajoby práce. Pri ústnej časti skúšky je študent skúšaný členmi komisie z otázok súvisiacimi s jeho oborom. Obe časti skúšky sú ohodnotené známkou, z ktorých sa na konci odvodí výsledná známka. Pre úspešné zloženie štátnej skúšky je potrebné dosiahnuť z oboch častí skúšky známku lepšiu ako F. V prípade, ak študent neuspeje pri jednej alebo oboch čas­

tiach skúšky, môže v nasledujúcom semestri opakovať neúspešnú časť skúšky. Úspešne spravenú časť už neopakuje a skúška je v tom prípade skrátená na 30 minút. Opakujúci študenti sú radení na záver dňa. Obvyklá dĺžka skúšania jednej komisie je 7-8 hodín.

Magisterské skúšky sa konajú počas doby jedného týždňa a na­

sledujú po skončení bakalárskych skúšok v predchádzajúcom týždni.

Počas tohto obdobia musia byť vyskúšaní všetci študenti, ktorí sa účastnia záverečných skúšok. Každý študent je priradený do jednej komisie, v ktorej sa bude konať skúška. Komisia je zložená z troch ľudí, ktorí skúšajú študentov počas celého dňa. Títo vyučujúci sú prítomní v miestnosti pre danú komisiu počas celého dňa okrem pre­

stávky na obed a ich zloženie ani miestnosť sa počas dňa väčšinou nemení. Jeden z členov komisie plní funkciu predsedu komisie a os­

tatní dvaja sú členmi komisie. Ukážka rozvrhu komisie s prirade­

nými študentmi je zobrazená v obrázku 4.1.

N a Fakulte informatiky je možný výber zamerania štúdia spo­

medzi viacerých oborov. Študenti všetkých oborov majú záverečné skúšky v spoločnom termíne a nie sú striktne členení podľa oborov.

Pri ústnej skúške sú otázky pre študenta vyberané z okruhov tém

Obhajoby diplomových prací

Komise prof. RNDr. Luboš Brim, CSc. (předseda) Ing. Matej Lexa, Ph.D.

RNDr. David Šafránek, Ph.D.

středa 26.6.2013, učebna C511

Vedoucí práce Oponent

08:00 - 09:00 Krejčí Adam Lexa Bystrý BIO

09:00 - 10:00 Motola Pavol Barnat Brim INS

10:00 - 11:00 Beneš Zdeněk Šafránek Klement BIO 11:00 - 12:00 Nižnan Juraj Pelánek Brázdil PDS 13:00 - 14:00 Sirný Richard Sehnal Svobodová Vařeková AP 14:00 - 15:00 Lukáš Radek Sehnal Svobodová Vařeková INS 15:00 - 16:00 Čechová Andrea Svobodová Vařeková Prokop BIO 16:00 - 17:00 Michalovová Monika Kejnovský Bartoš BIO

Obr. 4.1: Príklad zostavenej komisie. V hornej časti sú uvedení čle­

novia komisie a v spodnej časti sú uvedení študenti s časom skúšky, vedúcim a oponentom práce a svojím oborom štúdia.

jeho štúdia. Jednotliví skúšajúci avšak môžu byť podľa svojej špecia­

lizácie viac alebo menej vhodní pre skúšanie študentov rôznych obo­

rov. Je nutné, aby študenta skúšala komisia zložená z ľudí, ktorí sa vyznajú v danom obore študenta. U niektorých oborov sa vyžaduje, aby bol v tejto komisii človek špeciálne zameraný na tento obor. A b y sme vyjadrili vhodnosť jednotlivých vyučujúcich pre skúšanie štu­

dentov z daných oborov, každý skúšajúci má pre každý obor určenú jeho preferenciu vyjadrenú ako celé číslo medzi 0 a 6. Týmto hod­

notám sme priradili význam nasledovne: 0 - vynikajúci, 1 - veľmi dobrý, 2 - dobrý, 3 - neutrálny, 4 - nepreferovaný, 5 - nevhodný, 6 - zakázaný.

V rámci tejto práce budeme pod pojmom vyučujúci myslieť všet­

kých vyučujúcich, ktorí sa účastnia štátnych záverečných skúšok buď ako člen komisie, alebo ako člen obhajoby. Pod pojmom skúšajúci bu­

deme myslieť všetkých vyučujúcich takých, že ich môžeme rozvr­

hnúť do komisie na skúšanie študentov. Pod členom komisie budeme myslieť skúšajúceho rozvrhnutého na konkrétne miesto v komisii.

4. O P I S P R O B L É M U

4.1 Pevné obmedzenia

Pre uvedenie problému si definujeme podmienky, ktoré musí rieše­

nie vždy spĺňať. Pre lepšiu prehľadnosť si tieto pevné obmedzenia rozdelíme do niekoľkých skupín. Obmedzenia pre problém rozvrho- vania magisterských štátnych skúšok sú podobné, ako v prípade roz- vrhovania bakalárskych štátnych skúšok [7, 8]. Hlavný rozdiel pre rozvrhovanie magisterských skúšok spočíva v tom, že pri rozvrho­

vaní je braný do úvahy aj obor študenta.

4.1.1 Základné obmedzenia

Základné podmienky, ktoré modelujú podstatnú časť problému, sú uvedené v prvej skupine. Tieto podmienky určujú ako môžu byť zo­

stavované komisie a ako sa budú rozvrhovať študenti.

H l V rovnakom čase nemôže byť pri jednej komisii skúšaný viac ako 1 študent

H2 Vyučujúci nemôže byť rozvrhnutý naraz na viacerých miestach H3 Študent sa zúčastní skúšok práve 1 raz

H4 Predsedom komisie môže byť len buď profesor, alebo docent H5 Profesor nie je zaraďovaný ako bežný člen komisie

H6 V niektorých prípadoch nie je docent zaraďovaný ako bežný člen komisie, ale len ako predseda.

H7 Študenti opakujúci niektorú časť záverečných skúšok sú rozvr­

hovaní až po študentoch, ktorí absolvujú obhajobu záverečnej práce spolu s ústnou skúškou.

4.1.2 Oborové obmedzenia

Každého študenta je vhodné zaradiť do komisie, v ktorej sú vhodní skúšajúci pre jeho obor. Vyučujúci tak môžu študentov skúšať z otá­

zok, ktoré sú blízke ich zameraniu. N a to, aby bol študent priradený do oborovo vhodnej komisie, sú zavedené nasledujúce obmedzenia,

ktoré zohľadňujú obor študenta a preferenciu jednotlivých skúšajú­

cich.

H8 Študent nemôže byť rozvrhnutý do komisie, ak niektorý z jej čle­

nov má hodnotu preferencie oboru študenta vyššiu ako x

H9 Študent musí mať v komisii aspoň dvoch členov s preferenciou jeho oboru y a menej

H10 A k existuje skúšajúci s preferenciou oboru študenta rovnou 0, tak aspoň jeden z nich musí byť členom komisie, v ktorej je tento študent

U obmedzení H8 a H9 sme pre riešenie nášho problému para­

metre x a y zvolili ako hodnotu 4 pre x a 2 pre y.

4.1.3 Obmedzenia zdrojov

Medzi skúšajúcimi sa snažíme zachovať spravodlivý počet rozvr­

hnutí do komisii tak, aby sa nestalo, že niektorý skúšajúci bude za­

sadať v komisii viac krát a niekto iný ani raz. Z tohto dôvodu sa za­

viedli pre každého skúšajúceho spodné a horné hranice určujúce mi­

nimálny a maximálny počet účastí. Horná a spodná hodnota týchto hraníc sa pritom líši maximálne o 1, aby bola zachovaná férovosť rozvrhovania medzi skúšajúcimi a zároveň nám to necháva určitú voľnosť pri rozvrhovaní. Tieto hranice sme nastavili podľa prísluš­

nosti jednotlivých skúšajúcich k fakulte. Príklad nastavenia týchto parametrov môže vyzerať nasledovne. Profesori sú rozvrhovaní 2- krát, docenti 2-krát, odborní asistenti 3-krát a externí pracovníci sú rozvrhovaní 1 až 2-krát. Každý skúšajúci môže mať naviac tieto hra­

nice nastavené individuálne. Okrem spravodlivého rozloženia mu­

síme pri rozvrhovaní rešpektovať aj individuálne obmedzenia na možnú účasť skúšajúcich.

H l i Skúšajúci nemôže byť rozvrhnutý ako člen komisie v súčte s ba­

kalárskymi skúškami viac, ako je jeho maximálna hranica využi­

tia - limitMaxit)

H12 Skúšajúci nemôže byť rozvrhnutý ako člen komisie v súčte s ba­

kalárskymi skúškami menej, ako je jeho minimálna hranica vy­

užitia - UmitMin(t)

4. O P I S P R O B L É M U

H13 Vyučujúci sa môže zúčastniť skúšok len v časoch, ktoré má voľné pre záverečné skúšky

H14 V určitých špeciálnych prípadoch sa môže stať, že skúšajúcemu budeme chcieť rozvrhnúť všetkých jeho študentov do svojej ko­

misie. V tomto prípade nemôže byť študent, ktorému robí tento vyčujúci vedúceho alebo oponenta, rozvrhnutý do komisie, kde nie je jej členom

H15 V určitých prípadoch požadujeme, aby bol v komisii maximálne jeden člen komisie z určitej množiny skúšajúcich. Viacej osôb z tejto skupiny v jednej komisii by bolo nežiadúce. Prípadom ta­

kejto situácie je napríklad požiadavka, aby bol v komisii najviac jeden lektor.

4.2 Optimalizačné kritériá

Pre možnosť porovnania viacerých rôznych riešení sme zaviedli opti­

malizačné kritériá, ktoré určujú kvalitu jednotlivých riešení. Tieto kritériá sa počítajú cez celé riešenie a v optimálnom riešení sa sna­

žíme minimalizovať ich váženú hodnotu. Podobne ako pevné ob­

medzenia, aj optimalizačné kritériá pre rozvrhovanie magisterských štátnych skúšok sú podobné ako pre rozvrhovanie bakalárskych štát­

nych skúšok [7,8]. Hlavný rozdiel je opäť branie do úvahy obor štu­

denta.

4.2.1 Oborové preferencie komisie

Zaradenie študenta do konkrétnej komisie má veľký vplyv na kva­

litu riešenia. Niektorí študenti môžu byť pre konkrétnu komisiu vhod­

nejší ako iní. Medzi najdôležitejšie ciele optimalizácie riešenia pritom patrí zaradenie študenta do komisie, ktorá je vhodná pre jeho obor.

U niektorých oborov je vhodné, ak sú v komisii iba študenti týchto oborov. U iných je zas naopak až nežiadúce mať príliš mnoho štu­

dentov z jedného oboru ako je napríklad obor aplikovaná informa­

tika. Študentov tohto oboru je vhodné rozložiť do viacerých komi­

sií, pretože týchto študentov je schopná skúšať väčšina skúšajúcich a ich rozloženie umožní ľahšiu tvorbu rozvrhov štátnych záverečných

skúšok. Preto sme obory rozdelili do určitých skupín, podľa žiada­

nej homogenity študentov. Homogénne obory vyžadujú mať komisiu naplnenú študentmi toho istého oboru a nehomogénne zas preferujú komisiu so študentmi z rôznych oborov. Pre optimalizáciu týchto po- žiadavkov sú definované nasledujúce kritériá.

51 A k o hlavné optimalizačné kritérium sme určili vhodnosť oboru študenta. Funkcia počíta súčet štvorcov preferencii skúšajúceho pre obor študenta z dôvodu, aby sa penalizovali vysoké hodnoty tejto preferencie a je definovaná ako:

w(e, obor(s))²,

sGstudents eGcommission(s)

kde commission(s) je množina členov komisie v komisi študenta s a w(e, obor(s)) je hodnota určujúca preferenciu skúšajúceho e pre obor študenta s.

52 A k o ďalšie pomocné kritérium je počet študentov s rovnakým oborom v jednej komisii presahujúcim počet x, ak je pre daný obor nežiadúca homogenita študentov v komisii. Pre parameter x sme zvolili hodnotu 4.

4.2.2 Využitie času

Medzi ďalšie dôležité ciele optimalizácie riešenia je mať efektívne využitie ľudských zdrojov. Optimálny prípad by bol, ak by sa každý vyučujúci s viacerými študentmi dostavil ku skúškam iba raz. Táto požiadavka sa ale nedá vždy splniť a snažíme sa aspoň minimali­

zovať tieto prípady. Pre definíciu týchto požiadavok sme zaviedli nasledujúce kritériá:

S3 Pre vyučujúcich sa snažíme minimalizovať počet časových úse­

kov, v ktorých sa musia k u skúškam dostaviť všetci vyučujúci.

Táto hodnota je definovaná ako:

blocks(t),

tateachers

kde blocks(t) je počet súvislých časových blokov, počas ktorých sa musí vyučujúci dostaviť na štátne skúšky. Účasť v komisii sa

4. O P I S P R O B L É M U

počíta ako jeden súvislý blok za deň. Za jeden blok sa považuje aj situácia, ak sa vyučujúci účastní obhajob v bezprostredne nadvä­

zujúcom čase v inej miestnosti.

S4 Študentov sa snažíme rozvrhnúť do komisie, v ktorej zasadajú jeho vedúci a jeho oponent. Rozvrhnutia študentov, ktorí vo svo­

jej komisii nemajú svojich členov komisie sa snažíme minimali­

zovať. Hodnotu tohto kritéria definujeme ako:

\0\ + \V\,

kde O = {s G Students, opponent(s) G" commission^)} a V = {s G Students, supervisor (s) G⁷ commission^)},

kde supervisor (s) je vedúci práce študenta, opponent(s) je opo­

nentom záverečnej práce študenta a commission^) je množina skúšajúcich v komisi študenta s. Táto funkcia penalizuje aj prira­

denie do komisie takých študentov, ktorých vedúci alebo oponent nezasadá v žiadnej komisii, z dôvodu uprednostnenia rozvrhnu­

tia študenta do komisie so svojím vedúcim alebo oponentom pri heuristikách výberu.

Niektoré kritéria majú pre nás väčší význam ako ostatné, preto má každé kritérium určenú svoju váhu s akou sa započítava do cel­

kovej hodnoty. Tieto váhy sa dajú podľa potreby výsledného riešenia príslušne upraviť.

5 Model problému v CPSolveri

Pre implementáciu problému rozvrhovania štátnych skúšok v CP­

Solveri sme ako doménové premenné zvolili časové sloty, do ktorých priraďujeme osoby Časový slot reprezentuje časový úsek s počiatoč­

ným a koncovým časom, ktorý je umiestnený v komisii s určenou miestnosťou. V komisii sú potom rozdelené sloty pre členov komi­

sie a sloty pre študentov. V rámci jednej komisie sú vopred určené 3 sloty pre členov komisie, ktoré trvajú celý deň a sú určené len pre skúšajúcich. Okrem nich sú v komisii vytvorené ďalšie sloty pre štu­

dentov podľa potrebnej dĺžky trvania. V jednej komisii sa podľa po­

treby vytvorí 8-9 slotov pre študentov. Doménové hodnoty pre jed­

notlivé premenné sú tvorené osobami, ktoré môžeme do dané slotu umiestniť. To znamená, že pre slot členov komisie sú v doméne iba skúšajúci, ktorí môžu v danej komisii zasadať a v slotoch pre študen­

tov sú všetci študenti.

Časové úseky sú v modeli problému implementované ako trieda TimeSlot, ktorá je potomok triedy Variable. Priraďované hodnoty do premenných sú objekty triedy PersonPlacement rozširujúcu trie­

du Value. Každý TimeSlot má nastavený svoj začiatočný a koncový čas. Doména premennej TimeSlot obsahuje doménové hodnoty Per­

sonPlacement.

PersonPlacement obsahuje dvojicu hodnôt, premennú typu Ti­

meSlot a osobu Person, ktorú reprezentuje. Objekt tejto triedy repre­

zentuje priradenie konkrétnej osoby do určitého časového slotu.

Trieda Person reprezentuje osoby, ktoré sú rozvrhované v našom probléme. V našom modeli môže byť osoba buď vyučujúci alebo štu­

dent. Z dôvodu, že do časových slotov pre členov komisie rozvrhu­

jeme skúšajúcich a do ostatných slotov rozvrhujeme študentov, sme pre uľahčenie práce s CPSolverom zaviedli pre všetky doménové premenné rovnaký typ doménových hodnôt. Vyučujúci je reprezen­

tovaný triedou CommissionMember, ktorá rozširuje triedu Person.

Objekt tejto triedy obsahuje informácie o všetkých študentoch, kto­

rým sa účastní na obhajobe, ďalej obsahuje preferencie pre jednotlivé obory a informáciu o minimálnom a maximálnom počte rozvrhnutí do komisií. Ďalej si udržuje informácie o rozvrhnutí ako člen komisie alebo ako člen obhajoby v určitom čase. Tieto informácie sú dôležité

Variable Value

~7y

Commission

1 1..* TimeSlot

1 0..*

1 1..* 1 0..* 1 0..*

0..* r-, 0..* r-,

PersonPlacement person: Person

Person

Student

supervisor: CommissionMember opponent: CommissionMember

CommissionMember students[]: Student

Obr. 5.1: Implementácia premenných v CPSolveri

pre efektívne zistenie dostupnosti vyučujúcich v konkrétnom čase.

Druhý typ triedy Person je jej potomok Student. Táto trieda re­

prezentuje jednotlivých študentov, ktorí sa účastnia štátnych záve­

rečných skúšok. Študent si uchováva informácie o svojom vedúcom a oponentovi, ktorí sa účastnia na jeho obhajobe. Okrem toho obsa­

huje hodnotu, ktorá určuje jeho umiestnené v rámci rozvrhu štátnych skúšok. Diagram hierarchie jednotlivých tried je zobrazený na ob­

rázku 5.1.

5.1 Pevné obmedzenia

Obmedzenia implementované v tejto práci vychádzajú z obmedzení definovaných v kapitole 4.1. Implementované postupy majú pri sebe

5. M O D E L P R O B L É M U V C P S O L V E R I

uvedené, ktorých obmedzení sa týkajú.

Návrh modelu, s premennými zvolenými ako časové sloty, auto­

maticky zaručuje splnenie obmedzenia H l , pretože jeden časový slot môže mať v danom čase maximálne 1 priradenie.

O niektorých doménových hodnotách vieme určiť už dopredu, že vždy budú porušovať niektoré z pevných obmedzení. Napríklad, ak je vyučujúci nedostupný v určité dni, tak do slotov v týchto dňoch nikdy nebudeme môcť priradiť daného vyučujúceho alebo niekto­

rého z jeho študentov. Takéto prípady sa v CPSolveri dajú riešiť už pri inicializácii programu pomocou obmedzenia domén pre jednot­

livé premenné. S hodnotami, ktoré sa vyradia z domén premenných sa tak už ďalej zbytočne nepočíta a urýchľuje sa tak beh algorit­

mov. Obmedzenia, ktoré vieme už dopredu preniesť do domén pre­

menných sa týkajú jednotlivých miest v komisiách (obmedzenia H4, H5 a H6) a dostupných časov vyučujúcich (obmedzenie H13). Os­

tatné obmedzenia sú implementované ako jednotlivé triedy rozši­

rujúce triedu Constraint uvedené, s príslušnou metódou C O M P U T E - C O N F L I C T S a tie si postupne popíšeme.

V triede DirectConflictConstraint sa kontrolujú obmedzenia (Al­

goritmus 5.1), ktoré by spôsobili rozvrhnutie osoby na dve rôzne miesta v rovnakom čase (obmedzenie H2) a v prípade študentov kontroluje aj to, či je už rozvrhnutý do nejakej komisie (obmedze­

nie H3). Metóda si najskôr zistí komisiu a časový slot, do ktorých sa hľadá nové priradenie (riadky 2-3). Kontrola obmedzení rozlišuje, či sa jedná o rozvrhnutie študenta alebo skúšajúceho. A k sa jedná o štu­

denta, tak sa načíta študent reprezentovaný danou hodnotou (riadky 4-5). Pre daného študenta sa kontroluje, či je už rozvrhnutý na iné miesto, a ak je tak sa dané rozvrhnutie pridá do konfliktnej množiny (riadky 6-8). Potom sa pozrieme na jeho vedúceho a pozrieme, či už nie je rozvrhnutý v inej komisii ako člen komisie alebo člen obha­

joby (riadky 9-14). Rovnaká kontrola sa následne vykoná aj pre jeho oponenta (riadky 15-20).

A k doménová hodnota nového priradenia reprezentuje skúšajú­

ceho, tak sa načíta skúšajúci reprezentovaný danou hodnotou (riadky 21-22). Pre tohto skúšajúceho sa kontroluje, či v tomto dni nezasadá v inej komisii, alebo či nie je rozvrhnutý na obhajobu v inej miestnosti (riadky 23-27). N a skontrolovanie týchto podmienok sa využíva in­

formácia, ktorú si kontrolovaná osoba uchováva, či je už v danom

Algoritmus 5.1 Metóda C O M P U T E C O N F L I C T S triedy DirectConflict- Constraint

1: function C O M P U T E C O N F L I C T S ( w a / M e , conflicts)

2: commission <— value.commission 3: t <— časový interval slotu s value 4: if value.person je typu Student then 5: s <— value.person

6: if s je rozvrhnutý then

7: pridaj s. get Assignment do conflicts

8: end if

9: sup <— s.supervisor

10: for všetky priradenia as v čase t pre s-up do 11: if as nepatrí do commission then

12: pridaj as do conflicts

13: end if

14: end for

15: opp <— s.opponent

16: for všetky priradenia as v čase í pre opp do 17: if as nepatrí do commission then

18: pridaj as do conflicts

19: end if

20: end for

21: else if value.person je typu CommissionMember then 22: cm <— value.person

23: for všetky priradenia as v čase t pre cm do 24: if as nepatrí do commission then 25: pridaj as do conflicts

26: end if

27: end for

28: end if 29: end function

5. M O D E L P R O B L É M U V C P S O L V E R I

čase použitá.

Rozvrhnutie opakujúcich študentov definované obmedzením H7 rieši RepeatingStudentConstraint. Toto obmedzenie má na starosti kontrolu, že opakujúci študenti sú priradení ako poslední v komisii.

A k sa jedná o študenta, ktorý opakuje časť záverečných skúšok, tak všetci študenti s riadnym režimom skúšania rozvrhnutí až za týmto opakujúcim študentom sa priradia do konfliktnej množiny. A k sa na­

opak jedná o študenta v normálnom režime skúšok a pred ním sú rozvrhnutí nejakí opakujúci študenti, tak sa títo študenti pridajú do konfliktnej množiny.

SpecializationConstraint kontroluje splnenie obmedzení týkajú­

cich sa preferencii oborov (obmedzenia H8 a H9). Pre kontrolovanú hodnotu sa rozlišuje, či sa jedná o študenta alebo skúšajúceho. Pre štu­

denta sa kontroluje, či jeho obor nespôsobí presiahnutie najvyššej po­

volenej preferencie skúšajúceho, alebo či v komisii nie je viac ako jeden skúšajúci s preferenciou x a vyššou. A k je niektoré z týchto obmedzení porušené, tak sa do konfliktnej množiny pridajú všetci skúšajúci, ktorí sú v konflikte s priradením študenta. A k sa jedná o skúšajúceho, tak pre všetkých študentov v komisii sa skontroluje, či študent nemá obor s nevhodnou preferenciou, alebo či v kombi­

nácii s ostatnými členmi komisie nebudú dvaja skúšajúci s preferen­

ciou x. A k by priradenie skúšajúceho spôsobilo porušenie niektorého z týchto obmedzení, tak všetci študenti spôsobujúci porušenie obme­

dzení sa pridajú do množiny konfliktov.

Kontrolu obmedzenia H10 kontroluje trieda SpecialistlnCommis- sionConstraint. A k priraďovaný študent musí mať v komisii skúša­

júceho s preferenciou jeho oboru 0, tak sa kontroluje, či taký skúša­

júci v komisii je, alebo je pre neho voľné miesto v komisii. A k sa do komisie priradí tretí skúšajúci, tak sa kontroluje pre každého štu­

denta, ktorý vyžaduje špecializovaného skúšajúceho, či taký skúša­

júci je v komisii. V prípade ak tam nie je, tak sa všetci takíto študenti pridajú do konfliktnej množiny.

MaxCommissionAppearanceConstraint má na starosti kontrolu, aby sa jednotliví skúšajúci nemohli rozvrhnúť viac krát, ako je ich určená maximálna hranica počtu rozvrhnutí do komisií (obmedzenie H l i ) . A k by priradenie skúšajúceho spôsobilo presiahnutie hranice, tak sa náhodne vyberie jedno z jeho priradení v ostatných komisiách, a to sa pridá do množiny konfliktov.

Obmedzenie MinCommissionAppearanceConstraint sa stará o do­

držanie minimálnej hranice využitia jednotlivých skúšajúcich pre skú­

šanie v komisii (obmedzenie H12). V tomto obmedzení sa podľa ak­

tuálneho využitia skúšajúcich zistí počet nutných pozícii, ktoré mu­

sia byť obsadené skúšajúcimi, ktorí ešte nie sú rozvrhnutí v požado­

vanom rozsahu. A k je počet neobsadených slotov pre členov komisie rovný alebo nižší ako tento počet a skúšajúci, ktorého kontrolujeme už má splnený minimálny počet účastí, tak tohto skúšajúceho už ne­

môžeme v tomto prípade rozvrhnúť a do množiny konfliktných hod­

nôt pridáme jedno náhodne vybrané rozvrhnutie v iných komisiách.

Trieda DefencelnCommissionConstraint kontroluje splnenie ob­

medzenia H14. A k prirad'ovaný študent musí mať v komisii skú­

šajúceho, ktorý sa zároveň účastní obhajoby jeho práce, tak sa kon­

troluje, či taký skúšajúci v komisii je, alebo je pre neho voľné miesto v komisii. A k tento skúšajúci nie je v komisii a tá má obsadené všetky miesta, tak sa do konfliktnej množiny pridá náhodný člen komisie.

A k sa do komisie priradí tretí člen komisie, tak sa kontroluje pre kaž­

dého študenta, ktorý vyžaduje špecializovaného skúšajúceho, či taký skúšajúci už v komisii je. V prípade ak tam nie je, tak sa takýto štu­

dent pridá do konfliktnej množiny. A k sa jedná o študenta a v komisii je skúšajúci, ktorý vyžaduje mať svojich študentov vo svojej komisii, tak sa skontroluje, či je v tejto alebo v ostatných komisiách, v ktorých tento skúšajúci zasadá dostatok voľných miest pre jeho nerozvrhnu­

tých študentov. A k nie je dostatok voľných miest, tak sa náhodne vyberú študenti z tejto komisie, ktorí nemajú ako vedúceho alebo oponenta tohto skúšajúceho v počte rozdielu nepriradených študen­

tov tohto skúšajúceho a počtu voľných miest v komisii. V prípade člena komisie, ktorý vyžaduje mať svojich študentov vo svojej komi­

sii, zistíme či v tejto alebo ostatných komisiách, v ktorých zasadá, je dostatok neobsadených miest pre svojich nerozvrhnutých študentov.

V prípade, že nerozvrhnutí študenti presahujú počet voľných miest, tak sa z aktuálnej komisie vyberú študenti v počte tohto presahu, ktorí nemajú ako vedúceho alebo obhajobu tohto skúšajúceho.

Trieda Maxi Constraint rieši kontrolu splnenia obmedzenia H15.

A k prirad'ovaný člen komisie patrí do množiny skúšajúcich, ktorí môžu byť v komisii iba raz a v komisii je už nejaký iný skúšajúci patriaci do tejto množiny, tak sa tento skúšajúci pridá do konfliktnej množiny.

5. M O D E L P R O B L É M U V C P S O L V E R I Algoritmus ^5.2 Příklad funkcie G E T V A L U E triedy SpecializationCri- teria

1: function G E T V A L U E ^ a / w e ) ret <- 0

if value.•person je Student then

for všetkých CommissionMember c v komisii do x <— c.getPrefference(value.person.field) ret <— reí + x * x

end for

else if value.person je CommissionMember then for všetkých Student s v komisii do

x <— value.person.getPrefference(s.field) ret <— reí + x * x

end for end if return r e i end function

5.2 Optimalizačné kritériá

Optimalizačné kritériá sú implementované ako jednotlivé triedy roz­

širujúce triedu Criteria. Každé obmedzenie z kapitoly 4.2 je imple­

mentované ako jedna trieda typu Criteria. Počítaná hodnota je rov­

naká ako definícia optimalizačného kritéria. Počítanie hodnôt pre­

bieha vždy inkrementálně a výpočet rozlišuje, či sa počíta rozdiel hodnoty kritéria pre priradenie študenta alebo člena komisie. A k o príklad optimalizačného kritéria uvedieme triedu SpecializationCri- teria, je uvedený v Algoritme 5.2. Táto trieda reprezentuje optimali­

začné kritérium SI. Ohodnotenie priradenia sa na začiatku nastaví na 0 (riadok 2). Metóda rozlišuje, či sa jedná o študenta alebo skú­

šajúceho. Študentovi sa hodnota spočíta ako suma štvorcov prefe­

rencií jeho oboru všetkých skúšajúcich a táto suma sa priráta k ná­

vratovej hodnote (riadky 3-7). Skúšajúcemu sa hodnota priradenia spočíta ako suma štvorcov preferencií oboru každého študenta roz­

vrhnutého do komisie (riadky 8-12). Napočítaná hodnota hodnota priradenia sa vráti ako návratová hodnota metódy (riadok 14).

5.3 Konštrukčná fáza

Hľadanie riešenia pozostáva z dvoch fáz. Výpočet začína s prázd­

nym riešením, v ktorom je vytvorený potrebný počet komisii s prí­

slušnými časovými slotmi. A k o prvá fáza je konštrukčná fáza (Al­

goritmus 5.3). Jej cieľom je vytvoriť vhodné zloženie členov komisie a do komisii naplniť väčšinu študentov. Konštrukčná fáza postupuje po jednotlivých komisiách, kde najskôr vyberie vhodných členov ko­

misie a potom do nej naplní študentov. Algoritmus začína tým, že zo­

berie všetky prázdne komisie (riadok 2) a v každom kroku sa naplní jedna komisia, až kým neostane žiadna prázdna komisia (riadok 3).

Komisia, ktorá sa bude napĺňať, sa v každom kroku vyberá náhodne (riadok 4). Tejto komisii sa následne vyberie obor, pre ktorý bude táto komisia primárne určená (riadok 5).

Do komisie sa snažíme vybrať skúšajúcich s vyšším počtom svo­

jich študentov, ktorých môžme priradiť do danej komisie. Títo štu­

denti tak nebudú zaradení do inej komisie, v ktorej by porušovali obmedzenie týkajúce sa rozvrhnutia daného skúšajúceho v určitú dobu. Po vybraní oboru komisie sa preto skúšajúci vhodní pre daný obor a zároveň voľní v daný deň zoradia podľa počtu svojich štu­

dentov, ktorým sú členmi obhajoby, v pomere k počtu dní, počas kto­

rých sú dostupní k u skúšaniu (riadky 6-12). Do komisie sa potom vy­

berie skúšajúci s najvyšším pomerom a jeho študenti sa označia ako preferovaní do komisie (riadky 13-16). Po vybratí skúšajúceho potom vyberáme ostatných dvoch členov komisie (riadok 17). V prípade, ak je počet slotov pre študentov v komisii vyšší ako je množina prefero­

vaných študentov, tak sa komisiu snažíme doplniť do komisie skúša­

júceho so študentmi, ktorí obsadia zvyšné voľné miesta (riadok 18).

Pre komisiu sa zistí počet voľných miest pre študentov , ktoré zo­

stanú neobsadené po rozvrhnutí všetkých preferovaných študentov (riadok 19). Následne sa do komisie priradí prvý skúšajúci s počtom študentov rovným alebo menším, ako je počet voľných miest v ko­

misii (riadky 20-24). A k je počet preferovaných študentov väčší alebo rovný ako je počet miest v komisii, tak sa medzi členov komisie do­

plnia skúšajúci s najmenším počtom študentov (riadky 25-28).

Obor komisie sa vyberá vždy až v momente konštrukcie komisie (Algoritmus 5.4). Algoritmus si pamätá najvhodnejší nájdený obor s príslušnou hodnotou. N a začiatku začína bez vybratého oboru a

5. M O D E L P R O B L É M U V C P S O L V E R I

Algoritmus 5.3 Schéma konštrukčnej fázy l : function CONSTRUCTIONPHASE

2: empty Commissions <— všetky prázdne komisie 3: while emptyC'ommissions neprázdne do

4: comm <— vyber komisiu z emptyC ommissions 5: /žeZri ^-CHOOSEFlELD

6: teachers <— dostupní skúšajúci vhodní pre daný obor 7: for každý CommissionMember í z teachers do

8: students <— počet nerozvrhnutých študentov pre t 9: days <— počet dostupných dní pre t

10: t.sortValue <— students/days 11: end for

12: zorad' teachers podľa hodnoty z 13: priraď teachers[0] do comm

14: for všetkých Student s v teachers[0].students do 15: pridaj s do commission.preffered

16: end for

17: while commission má voľný slot pre skúšajúceho do 18: if comm.preffered < comm. student S lot s then

19: x <— commission, student S lot s — comm.preffered 20: í <— najbližší z teachers splňujúci students < x 21: priraď í do comm

22: for do

23: priraď s do comm.prefferedStudents 24: end for

25: else

26: í <— posledný skúšajúci z teachers 27: priraď í do comm

28: end if 29: end while

30: ASSIGNSTUDENTS(comm) 31: end while

32: end function

Algoritmus 5.4 Schéma výberu oboru

1: function C H O O S E F I E L D 2: max <— 0

3: maxField <— m/Z/

4: allExaminers <— všetci skúšajúci 5: for každý študijný obor o do

6: students <— počet nerozvrhnutých študentov oboru o 7: examiners <— 0

8: for každý skúšajúci e z allExaminers do 9: if e.getPrefference(o) < 3 then

10: examiners <— examiners+počet dostupných dní pre e

11: end if

12: end for

13: t>a/ <— students/examiners 14: if va/ > m a x then

15: m a x <— wa/

16: maxField <— o

17: end if

18: end for

19: return maxField 20: end function