Begrepp
Hur automatisk generering faktiskt fungerar
Utan marknadsföringsprat. Vad motorn faktiskt gör, varför problemet är svårt och varför kvaliteten på era villkor betyder mer än algoritmens skärpa.
Problemet, rakt på sak
Ni har en mängd undervisningspass. Varje pass behöver en tid, en sal och en lärare. Vissa resurser är delade, vissa pass får inte överlappa, och en lång lista regler begränsar vilka kombinationer som är tillåtna. Hitta en tilldelning som inte bryter mot något hårt villkor och som bryter mot så få önskemål som möjligt.
Detta är ett villkorsuppfyllelseproblem, och högskoleschemaläggning är ett välstuderat svårt specialfall av det. Antalet möjliga tilldelningar växer explosionsartat med antalet pass: uttömmande sökning är inte bara långsam, den är astronomiskt omöjlig även för en måttligt stor fakultet.
Därför söker inget praktiskt system uttömmande. De använder heuristiker — kvalificerade strategier för att avgöra vad som ska placeras härnäst och vad som ska göras när man kört fast — för att snabbt hitta en bra lösning i stället för en bevisbart optimal lösning någon gång.
Vad motorn faktiskt gör
- Ordning. Att avgöra vilka pass som placeras först. Starkt bundna pass — en stor kull som behöver ett visst laboratorium med en enda kvalificerad tekniker — placeras oftast tidigt, eftersom en placering sist innebär att allt annat måste rivas upp.
- Placering. Att tilldela ett pass en tillåten kombination av tid, sal och lärare som inte bryter mot något hårt villkor.
- Ångra och backa. Att ångra tidigare beslut när det visar sig att ett pass inte har någon tillåten placering kvar. Det är här det mesta av körtiden går åt.
- Poängsättning. Att bedöma hur väl den aktuella partiella lösningen uppfyller de mjuka önskemålen, så att sökningen kan föredra bättre delar av sökrymden.
- Förbättring. När en komplett tillåten lösning finns: att göra lokala ändringar som förbättrar poängen utan att något går sönder.
Varför era villkor betyder mer än algoritmen
Det här är det leverantörer helst undviker att säga. Med en väl specificerad uppsättning villkor ger de flesta kompetenta motorer jämförbara resultat. Med en dåligt specificerad ger ingen motor något användbart.
Det vanligaste felet är inte algoritmiskt. Det är en uppsättning villkor där önskemål har förklarats oantastliga, så att ingen tillåten lösning finns och motorn korrekt rapporterar ett stort antal pass som inte kan placeras. Det näst vanligaste är föråldrade eller felaktiga indata — salskapaciteter som ingen kontrollerat sedan en ombyggnad, tillgänglighet som samlades in för sex veckor sedan.
Därför är den användbara frågan till en leverantör inte "vilken algoritm använder ni" utan "hur hjälper ni mig att få villkoren och tillgängligheten rätt".
Hur bra ser ut i praktiken
Ett användbart system genererar så snabbt att omgenerering är rutin i stället för ett nattligt jobb — Wise Timetable omgenererar även stora scheman på under en minut, vilket innebär att ni experimenterar i stället för att binda er vid en enda körning.
Det rapporterar vad det inte kunde placera, och varför, i stället för att i det tysta bryta en regel för att åstadkomma något som ser färdigt ut. Det respekterar pass som ni har låst, så att automatiskt och manuellt arbete kan blandas. Och det tar fram flera varianter så att ni kan jämföra i stället för att acceptera.
Vill ni se hur det fungerar?
Boka en onlinepresentation på 45 minuter, så går vi igenom den mot ert eget lärosätes schemaläggningsproblem.