Co je Tvůrce rozvrhů
Školní rozvrhy snadno a rychle
Screenshoty z programu
Sreenshot #1Sreenshot #2Sreenshot #3Sreenshot #4Sreenshot #5

Tvorba školních rozvrhů

Program Tvůrce rozvrhů umožňuje plně automatickou tvorbu školních rozvrhů s využitím techniky genetických algoritmů. Výstupem programu jsou jednak rozvrhy hodin pro jednotlivé třídy, jednak rozvrhy učitelů. Vygenerované rozvrhy lze exportovat do HTML.

Program sestavuje školní rozvrhy podle zadaných omezujících podmínek, kterými jsou:

1) Silné podmínky (povinné)

  • žádný učitel nesmí v daném čase (vyučovací hodině) učit více než jeden předmět.

Za přípustné řešení rozvrhovací úlohy je považováno takové, ve kterém není žádný těžký konflikt, neboli, jinými slovy, splňuje silná omezení.

2) Slabé podmínky (volitelné)

  • maximální přípustný počet výskytů stejného předmětu v daném dnu,
  • maximální přípustná mezera v rozvrhu,
  • maximální přípustná mezera na začátku dne,
  • maximální přípustný počet hodin denně,
  • minimální přípustný počet hodin denně.

Naplnění všech slabých podmínek není pro přípustné řešení nezbytně nutné, přesto při tvorbě rozvrhů hrají důležitou roli. Právě slabé podmínky určují do jaké míry budou vygenerované rozvrhy použitelné v praxi. Čím lépe jsou omezující podmínky splněny, tím je řešení kvalitnější.

Rozvrhy a genetické algoritmy

Program Tvůrce rozvrhů používá pro nalezení optimálního řešení techniku genetických algoritmů (GA), která je založena na přirozeném výběru, reprodukčním procesu a mutaci genetické informace. GA pracuje s populací jedinců, která se vyvíjí v čase. Každý jedinec v populaci odpovídá jednomu z možných řešení rozvrhovací úlohy (= kompletním rozvrhům). V průběhu generací (času) dochází k nárůstu kvality populace jedinců. Toho je dosaženo aplikováním selekce, křížení a mutace. Selekce provádí výběr jedinců, kteří se podílí na reprodukci. Čím je jedinec kvalitnější, tím větší má šanci, že bude vybrán. Křížení zajišťuje výměnu genetického materiálu mezi dvěma jedinci - rodiči. Potomek získá od každého rodiče pouze část genetické informace. A konečně mutace udržuje variabilitu v populaci, aby proces hledání řešení neuvízl v lokálním optimu. Program Tvůrce rozvrhů navíc používá tzv. opravnou mutaci, která významně napomáhá při odstraňování konfliktů v rozvrhu. Více informací o genetických algoritmech můžete najít např. na této stránce.

(c) Pavel Jaroš