Pro optimalizaci studijního rozvrhu tak, aby se minimalizovaly časové kolize (tedy situace, kdy jeden a tentýž student má v témže čase více předmětů), se obvykle používají metody kombinující modelování konfliktů a heuristické či exaktní řešiče. Níže je jeden postup „na míru“ univerzitnímu či střednímu rozvrhu:
1) Sběr vstupních dat
a) Matice zápisů: pro každý předmět P a každého studenta S informaci „P zapsal S / nezapsal S.“
b) Počet dostupných časových bloků a místností (kapacity, technické požadavky, speciální vybavení).
c) Případné požadavky vyučujících (nepřítomnost v určité dny/časy, blokové výuky aj.).
2) Vytvoření matice konfliktů
Pro každý pár předmětů (P₁,P₂) spočítejte, kolik studentů je zapsáno do obou. To vytvoří „váhový“ konfliktový graf G, kde uzly = předměty a hrany mají váhu = počet společných studentů.
3) Formulace problému jako grafového obarvování nebo celočíselného programování
a) Grafové obarvování:
– Barva = časový blok (např. pondělí 8–10, pondělí 10–12, …).
– Cíl: přiřadit barvu každému uzlu tak, aby hrany s vysokou váhou nebyly obě zbarveny stejně.
– Optimalizační cíl: minimalizovat součet vážených konfliktů (tj. váha hrany × indikátor, že oba uzly mají stejnou barvu).
b) Celočíselné programování (ILP/CP-SAT):
– Binární proměnné x[P,t] = 1, je-li předmět P v čase t.
– Pro každý P: ∑ₜ x[P,t] = 1 (každý předmět se vyučuje v jednom čase).
– Pro každý pár (P₁,P₂) a každý čas t: x[P₁,t] + x[P₂,t] ≤ 2 – δ[P₁,P₂], kde δ je hodnota 1, pokud mezi P₁ a P₂ nechceme souběh (dle počtu společných studentů může být δ = 1 pro hraniční konflictové páry a 0 pro netěžké případy).
– Minimalizovat ∑_{P₁,P₂,t} w[P₁,P₂] · (x[P₁,t]·x[P₂,t]).
4) Výběr řešiče a implementace
– Pro menší školy: open-source nástroje jako Google OR-Tools (CP-SAT), COIN-OR CBC, OptaPlanner.
– Pro větší nasazení: komerční CP/ILP řešiče (Gurobi, CPLEX), případně specializované systémy univerzitního rozvrhování.
5) Heuristiky a ladění
a) Nejprve proveďte „barevné“ rozvrhování podle nejhustších částí konfliktového grafu (largest‐degree ordering).
b) Poté zlepšujte lokálně („swap“ dvou předmětů do jiných časů, „Kempe chain“ výměny) tak, abyste srazili zbývající konflikty na nulu nebo minimální možnou úroveň.
c) Pokud je problém stále nevyřešitelný (přesycení bloků), zaveďte prioritizaci: některé předměty (povinné ročníkové) mají vyšší váhu a musí zůstat bezkolizní, ostatní lze částečně kompromitovat.
6) Validace a nasazení
– Ověřte na reálných datech několika minulých semestrů, porovnejte počet kolizí s aktuálním stavem.
– Zapojte zpětnou vazbu vyučujících a studentů, dolaďte časové bloky nebo kapacity.
– Po schválení přeneste rozvrh do SIS/rozvrhovacího systému a umožněte studentům reálnou kontrolu zápisu.
Shrnutí:
1) Vygenerujte konfliktový graf z dat o zápisech.
2) Formulujte úlohu jako obarvování grafu nebo ILP.
3) Použijte komerční či open-source řešič (např. Google OR-Tools).
4) Doplňte heuristické vylepšení (swap, Kempe chain).
5) Ověřte, dolaďte a nasaďte do provozu.
Tímto přístupem docílíte, že se předměty s největším počtem společných studentů nebudou krýt a významně tak omezíte potřebu dodatečných úprav rozvrhu.
