Rozvrhování předmětů na univerzitě
8. května 2023
1 Popis problému
2 Iniciální tvorba rozvrhu
3 Interaktivní rozvrhování
Rozvrhování předmětů na univerzitě
Typy problémů
rozvrhování se studijními obory (curriculum-based timetabling)
curriculum (studijní obor): množina předmětů
každý studen je zapsán do (jednoho nebo více) curricula
cíl: rozvrhování všech předmětů curricula bez překrývání
typické také pro rozvrhování na střední škole
rozvrhování se zápisy studentů (enrollment-based timetabling)
každý student je individuálně zapsán/zaregistrován do nějaké množiny
předmětů
studentský konflikt: student není schopen absolvovat
(dva) zaregistrované předměty vzhledem k jejich překryvu
cíl: nalezení rozvrhu, který minimalizuje počet studenských konfliktů
př. rozvrhování na FI
dělení studentů na skupiny (student sectioning/student scheduling)
dělení studentů na skupiny pro velké předměty, kde je nutné několik
seminárních nebo přednáškových skupin
Iniciální tvorba rozvrhu (vytvoření rozvrhu ze začátku) vs.
Interaktivní rozvrhování: změny vytvořeného rozvrhu
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 2 8. května 2023
Rozvrhovací systém UniTime http://www.unitime.org
Vyvinutý na Purdue University (USA) ve spolupráci s FI MU a MFF UK
Komplexní systém pro univerzitní rozvrhování
rozvrhování předmětů se studijními obory i i se zápisy
dělení studentů na skupiny
iniciální tvorba rozvrhu, interaktivní rozvrhování
rozvrhování studentů, zkoušek, událostí
otevřený zdrojový kód
webové rozhraní, Java, SQL+hibernate, XML
Použití
používáno pro rozvrhování na Purdue University
70 různých problemů, celkem asi 40 000 studentů
Masarykova univerzita: používáno na téměř všech fakultách
např. MIT, USA, Lahore University of Management Sciences,
Pakistán, University of Zagreb, Chorvatsko, AGH University of Science
and Technology, Polsko, Antalya International University, Turecko,
Universidad de Ingeniería y Tecnología (UTEC), Peru, American
College of Middle East (ACM), Kuwait
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 3 8. května 2023
Literatura
Materiál k přednášce
přehledová práce – rozvrhování na Purdue University
H. Rudová, T. Müller, K. Murray, Complex university course timetabling.
Journal of Scheduling, 14(2): 187-207, Springer, 2011.
http://dx.doi.org/10.1007/s10479-010-0828-5
Další materiály
http://www.unitime.org/publications.php
rozvrhování na Filozofické fakultě MU
H. Rudová and T. Müller, Rapid Development of University Course
Timetables (extended abstract). Proceedings of the 5th Multidisciplinary
International Scheduling Conference (MISTA 2011), pages 649–652. 2011
http://www.fi.muni.cz/~hanka/publ/mista11.pdf
rozvrhování na Pedagogické fakultě MU a FSpS
T. Müller, H. Rudová, Real-life Curriculum-based Timetabling with Elective
Courses and Course Sections. Annals of Operations Research,
239(1):153-170, Springer, 2016.
http://dx.doi.org/10.1007/s10479-014-1643-1
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 4 8. května 2023
Struktura předmětu s jeho třídami (vyučovanými částmi)
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 5 8. května 2023
Typická omezení
Pevná Měkká
omezení omezení
Časy pro třídy∗ časové vzory (pro pravidelné časy) x
individuální časy x x
Místnosti pro třídy individuální budovy/místnosti x x
individuální vybavení místnosti x x
Omezení místnosti x
na zdroje vyučující x
Studenti konflikty mezi dvěma třídami x
časové závislosti mezi třídami x x
Distribuční časové precedence mezi třídami x x
omezení třídy rozvrhované v podobných časech x x
mezi třídami stejný nebo odlišný
den/čas/místnost výuky pro třídy x x
∗Třída je každá rozvrhovaná položka předmětu (přednáška, cvičení, ...)
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 6 8. května 2023
Omezení a účelové funkce
Pevné podmínky
musí být splněny
Měkké podmínky
nemusí být splněny, pokud je to nutné
Měkké podmínky v rozvrhování: přehled
studentské konflikty
měkká omezení na čas
měkká omezení na místností
měkké distribuční podmínky
Vážený problém splňování podmínek (weighted CSP, WCSP) P
zahrnuje pevné a měkké podmínky
cíl: minimalizace F jako součtu vah nesplněných měkkých podmínek
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 7 8. května 2023
Iterativní dopředné prohledávání
(Iterative Forward Search, IFS) pro WCSP
P: WCSP, F: účelová funkce, <: komparátor
1: function IFS(P, F, <)
2: i = 0
3: ω = ∅ (současné přiřazení/rozvrh)
4: σ = ∅ (nejlepší přiřazení/rozvrh)
5: while canContinue(ω, i) do
6: i = i + 1
7: v = selectVariable(P, ω) (v reprezentuje třídu)
8: d = selectValue(P, ω, F, <, v) (d reprezentuje umístění v rozvrhu)
9: γ = hardConflicts(P, ω, v/d) (předměty, které musím odpřiřadit)
10: ω = ω\γ ∪ {v/d}
11: if F(ω) < F(σ) then σ = ω
12: end while
13: return σ
14: end function
Poznámka: není používána žádná propagace omezení
proměnná má buď přiřazenu iniciální hodnotu nebo má plnou iniciální doménu
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 8 8. května 2023
Funkce v IFS
Nalezení konfliktních proměnných γ = hardConflicts (P, ω, v/d)
vypočítá množinu proměnných γ takovou, že ω\γ ∪ {v/d} neporuší
žádnou pevnou podmínku
lze aplikovat jednoduchý algoritmus – vyšší počet iterací je lepší než
sofistikovány algoritmus
Výběr proměnné selectVariable(P, ω)
nevýznamný – chyby mohou být odstraněny budoucími iteracemi
aplikováno náhodné uspořádání
Výběr hodnoty selectValue(P, ω, F, <, v)
velmi důležitý
pro minimalizaci porušení měkkých podmínek:
výběr hodnoty d proměnné v s minimálním zhoršením ∆F(ω, v/d)
hodnoty účelové funkce s ohledem na měkká omezení
∆F(ω, v/d) = F(ω ∪ {v/d}) − F(ω) (výpočet inkrementální)
pro minimalizaci porušení pevných podmínek: konfliktní statistika
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 9 8. května 2023
Konfliktní statistika pro třídu CS 101 Lab 2
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 10 8. května 2023
Konfliktní statistika
Předpoklad: při výběru hodnoty a proměnné A je nutné
zrušit přiřazení hodnoty b proměnné B, tj. [A = a → ¬ B = b]
V průběhu výpočtu si tedy lze pamatovat:
A = a ⇒ 3׬ B = b, 4׬ B = c, 1׬ C = a, 120׬ D = a
Při výběru hodnoty
výběr hodnoty s nejnižším počtem konfliktů váženým jejich frekvencí
konflikt započítáme pouze, pokud to vede k odstranění přiřazení
př. A = a ⇒ 3 × ¬ B = b, 90 × ¬ B = c,
1 × ¬ C = a, 120 × ¬ D = a
A = b ⇒ 1 × ¬ B = a, 3 × ¬ B = b, 2 × ¬ C = a
za předpokladu, že máme přiřazení B = c, C = a, D = b
nechť A/a vede ke konfliktu s B/c: vyhodnoceno jako 90
není konflikt s C/a, tak se nezapočítává
nechť A/b vede ke konfliktu s C/a: vyhodnoceno jako 2
tj. vybereme hodnotu b pro proměnnou A
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 11 8. května 2023
Konfliktní statistika II.
CBS[x = dx → ¬ y = dy ] = cxy : při přiřazení x = dx bylo nutné
zrušit přiřazení y = dy v minulosti cxy-krát
Jestliže je hodnota d vybrána pro proměnnou v v IFS,
potom hardConflicts(P, ω, v/d) vypočítá přiřazení
γ = {v1/d1, v2/d2, . . . vn/dn}, které musí být zrušeno, aby byla
vynucena konzistence nového částečného přiřazení
Jako důsledek jsou navýšeny čítače
CBS[v = d → ¬ v1 = d1], CBS[v = d → ¬ v2 = d2], ...,
CBS[v = d → ¬ vn = dn] .
Konfliktní statistika je používána jako heuristika pro výběr hodnoty
Evaluace hodnoty d proměnné v:
vi /di ∈ω ∧ vi /di ∈hardConflicts(P,ω,v/d)
CBS[v = d → ¬vi = di ]
tj. konflikt započítáme pouze tehdy, pokud to vede k odstranění přiřazení
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 12 8. května 2023
Interaktivní rozvrhování: návrhy
Uvažovány změny s třídou PSY 120 Lec 5
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 13 8. května 2023
Opravná verze metody větví a mezí (Repair-based BB)
Algoritmus
n nejlepších návrhů ω je vráceno uživateli
prohledávání s časovým limitem
hodnoty s nejlepší ∆F(ω, v/d) prozkoumávány nejdříve
konfliktní statistika není brána v úvahu vzhledem k výpočetní náročnosti
Meze
omezená hloubka prohledávání
abychom umožnili pouze malý počet změn proměnných
pro zahrnutí změny na jedné třídě
nemá smysl měnit příliš mnoho dalších tříd
M: maximální hloubka
hodnota účelové funkce F musí být lepší než n-tý nejlepší návrh
Ω[n]: n-tý nejlepší návrh
Opakování RepairBB: provádění nového RepairBB
se zvětšenou hloubkou prohledávání a/nebo
zvětšeným časovým limitem
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 14 8. května 2023
Opravná verze metody větví a mezí
P: WCSP
ω: současné přiřazení
vbb: proměnná (třída), která bude přiřazována
1: function RepairBB(P, ω, vbb)
2: if {vbb/d} ⊆ ω then ω = ω\{vbb/d}
3: else d = nil
4: γ = {vbb/d}
5: return backtrack(P, ω, ∅, γ, ∅, 0)
6: end function
backtrack(P, ω, µ, γ, Ω, m)
µ: nově vybrané přiřazení aktuálním prohledáváním do hloubky
γ: proměnné (s případným původním přiřazením),
pro které hledáme přiřazení
Ω: návrhy (několik dosud nejlepších nalezených přiřazení)
m: aktuální hloubka prohledávání
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 15 8. května 2023
Funkce backtrack
1: function backtrack(P, ω, µ, γ, Ω, m)
2: if γ + m > M then return ∅ (M je maximální hloubka)
3: if γ = ∅ then return ω (konflikty vyřešeny)
4: if timeout then return ∅
5: if LowerBound(F(ω ∪ γ)) ≥ F(Ω[n]) then return ∅
(odhad kvality nového přiřazení (po zahrnutí γ) je horší než n-tý návrh)
6: v = selectVariableBB(γ) (je vybrána některá nepřiřazená proměnná)
7: let v/do ∈ γ (d0 je původní hodnota proměnné v)
8: for d ∈ Dv ordered by ∆F(ω, v/d) do
9: if d = do then continue (je vybrána původní hodnota)
10: α = hardConflicts(P, ω, v/d)
11: if α ∩ µ = ∅ then continue (konflikt s už vybraným přiřazením)
12: Ω = Ω ∪ backtrack(P, ω ∪ {v/d}, µ ∪ {v/d},
γ\{v/do} ∪ α, Ω, m + 1)
13: end for
14: return Ω
15: end function
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 16 8. května 2023
UniTime.org: GUI s vygenerovaným rozvrhem
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 17 8. května 2023
Fakulta informatiky MU
Jaro 2014 Podzim 2014
Místnosti 14+5 14+6
Vyučující 197 231
Předměty 190 199
Třídy 500 604
Registrace 12 701+ 14 055+
Registrace + obory 17 599 20 670
Konflikty dop.průchody 4x
Konflikty 958 1 440
Preference na čas 75,89 % 78,2 %
+
odstraněny registrace cca 25 studentů s více než 20 předměty
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 18 8. května 2023
International Timetabling Competition 2019
Mezinárodní soutěž, kterou organizovala i FI MU
https://www.itc2019.org
rozvrhování univerzitních předmětů
Vychází z reálných problémů shromážděných v systému UniTime
řešení problémů z celého světa včetně rozvrhování FI MU
anonymizovaná data
málo významné charakteristiky problémů odstraněny
snaha soustředit se na důležité rysy problému
Průběh soutěže
3 × 10 datových sad publikováno během soutěžního období
dostupný validátor řešení – založený na řešiči UniTime
submitování validních řešení přes web soutěže
Výsledky
zahrnuty tři problémy z FI MU
vítězný řešič časově náročný (výsledky po 24 hodinách i déle)
matheuristika: matematické programování kombinované s heuristikami
řešič založený na UniTime druhý nejlepší
schopný produkovat výsledky v krátkém čase (hodina až dvě)
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 19 8. května 2023
Rozvrhování předmětů na univerzitě: shrnutí
Typy řešených problémů
studijní obory, zápisy, dělení na skupiny
iniciální vs. interaktivní rozvrhování
UniTime
Model problému
struktura předmětu
omezení a účelové funkce
Prohledávání
iterativní dopředné prohledávání
konfliktní statistika
opravná verze metody větví a mezí
Hana Rudová, FI MU: Rozvrhování předmětů na univerzitě 20 8. května 2023