Roostergeneratie / Algoritme voor het automatisch genereren van roosters

De roostergeneratie van Omniscol berekent automatisch de plaatsing van de lessen van een weekrooster, een cyclisch rooster of een kalenderrooster. Ze plaatst de lessen die zijn aangemaakt maar nog niet geplaatst, kan al geplaatste lessen verplaatsen als dat het rooster verbetert, en laat vergrendelde lessen op hun plaats staan.

Hoe het werkt

Wanneer u een roostergeneratie start, zet Omniscol een eigen, geparallelliseerde rekenomgeving op. De school hoeft geen wachtrij te beheren; de initialisatie duurt vaak een tiental seconden voordat de eerste berekeningen zichtbaar worden. Het resultaat hangt af van de kwaliteit van de ingevoerde gegevens: vestigingen, lokalen, docenten, groepen, urenvolumes, beschikbaarheid en incompatibiliteiten. Hoe talrijker of tegenstrijdiger de beperkingen, hoe langer de roostergeneratie kan duren of hoe groter de kans op een gedeeltelijk resultaat.

De motor is een optimalisatie-AI van het type neurosymbolische Monte-Carlo-metaheuristiek: ze combineert stochastisch zoeken, symbolische bedrijfsregels en het scoren van de beperkingen. Het belangrijkste punt is operationeel: het algoritme voor roostergeneratie is gemaakt voor gevallen met zeer veel beperkingen en meldt onmogelijke situaties in plaats van conflicten te verbergen.

Harde beperkingen

De roostergeneratie houdt zich strikt aan de beperkingen die het rooster ongeldig zouden maken:

• een docent kan niet op twee plaatsen tegelijk zijn;
• een klas kan niet twee lessen tegelijk volgen, behalve in de gevallen die zijn voorzien voor groepen in een klasverdeling;
• beschikbaarheid en beperkingen op het niveau niet beschikbaar blokkeren de plaatsing;
• een gewoon lokaal kan niet aan twee lessen tegelijk plaats bieden;
• een groot lokaal kan alleen aan meerdere lessen tegelijk plaats bieden binnen de ingestelde grenzen voor capaciteit en aantal klassen;
• gespecialiseerde lokalen, capaciteiten, materiële resources en verplaatsingen tussen vestigingen moeten verenigbaar blijven;
• een vergrendelde les behoudt haar positie.

Optimalisatiebeperkingen

De zachte beperkingen dienen om de gevonden oplossingen te beoordelen en te verbeteren. Ze worden niet genegeerd: ze worden strafpunten die de roostergeneratie probeert terug te dringen.

Veelvoorkomende voorbeelden:

• ongewenste beschikbaarheid of beperkingen voor een docent, een lokaal, een cursus, een groep of een klas;
• pedagogische incompatibiliteiten tussen vakken, bijvoorbeeld vermijden dat een practicum vóór de bijbehorende theorieles valt, vermijden dat sport meteen na een zeer zware les komt, of de volgorde van een leerlijn opleggen;
• vermijden dat een klas twee keer hetzelfde vak op dezelfde dag heeft;
• een minimum of maximum aantal lesuren per dag of per week;
• evenwicht tussen de dagen;
• minder tussenuren in de roosters van de klassen en de docenten;
• het aantal aanwezigheidsdagen van de docenten, volgens de gewoonten van de instelling of van het land.

Het zoeken naar een geldige oplossing is de eerste stap. Het optimaliseren van de strafpunten kan daarna het langste deel van de berekening worden.

Beschikbaarheid

• Weekroosters — beschikbaar.
• Cyclische roosters — beschikbaar.
• Kalenderroosters — beschikbaar, met lessen op datum en een datumbereik.

Wat te doen als de roostergeneratie mislukt

Wordt er geen volledige oplossing gevonden, dan bewaart Omniscol het beste berekende rooster en laat het de lessen die niet te plaatsen zijn in de lijst met niet-geplaatste post-its staan. U kunt dan het gedeeltelijke rooster inspecteren, de diagnose lezen en de beperkingen corrigeren.

Veelvoorkomende oorzaken:

• te beperkende beschikbaarheid (een docent heeft geen enkel verenigbaar vrij tijdslot),
• te weinig lokalen, of geen gespecialiseerd lokaal beschikbaar,
• een inconsistente groepsuitlijning (verschillende urenvolumes tussen de uitgelijnde groepen),
• te veel of te strikte incompatibiliteiten,
• theoretisch aantal leerlingen van de klas > capaciteit van alle in aanmerking komende lokalen.

Zie Een mislukte roostergeneratie diagnosticeren.

De plaatsing van een les afdwingen

U kunt de positie van een les vergrendelen voordat u de roostergeneratie opnieuw start: het algoritme verplaatst die les dan niet meer, maar past de andere eromheen aan. Handig om “onwrikbare” lessen te verankeren (externe sprekers die contractueel vastliggen, examens met een vaste datum, enzovoort).