Koncepti
Kako samodejno generiranje dejansko deluje
Brez trženja. Kaj počne algoritem, zakaj je problem težak in zakaj je kakovost Vaših omejitev pomembnejša od iznajdljivosti algoritma.
Problem, preprosto povedano
Imate množico terminov pouka. Vsak potrebuje časovno okno, učilnico in predavatelja. Nekateri viri so skupni, nekateri termini se ne smejo prekrivati, dolg seznam pravil pa omejuje, katere kombinacije so dopustne. Poiščite razporeditev, ki ne krši nobenega trdega pravila in krši čim manj želja.
To je problem izpolnjevanja omejitev, univerzitetno urnikovanje pa je njegov dobro raziskan težak primer. Število možnih razporeditev eksplozivno narašča s številom terminov: izčrpno iskanje ni le počasno, temveč je že za skromno fakulteto astronomsko neizvedljivo.
Zato noben praktičen sistem ne išče izčrpno. Uporabljajo hevristike — informirane strategije za odločanje, kaj umestiti naslednje in kaj storiti, ko se zatakne — da hitro najdejo dobro rešitev, namesto da bi sčasoma našli dokazljivo optimalno.
Kaj algoritem v resnici počne
- Razvrščanje. Odločanje, katere termine umestiti najprej. Zelo omejene termine — velika skupina, ki potrebuje določen laboratorij z enim usposobljenim tehnikom — običajno umestimo zgodaj, ker bi njihova umestitev na koncu pomenila razgradnjo vsega drugega.
- Umeščanje. Dodelitev termina dopustni kombinaciji časa, učilnice in predavatelja, ki ne krši nobene trde omejitve.
- Vračanje. Razveljavitev prejšnjih odločitev, kadar se izkaže, da za termin ni več dopustne umestitve. Tu se porabi največ časa izvajanja.
- Ocenjevanje. Vrednotenje, kako dobro trenutna delna rešitev izpolnjuje mehke želje, da lahko iskanje daje prednost boljšim območjem prostora rešitev.
- Izboljševanje. Ko obstaja popolna dopustna rešitev, lokalne spremembe, ki izboljšajo oceno, ne da bi karkoli porušile.
Zakaj so Vaše omejitve pomembnejše od algoritma
O tem ponudniki najmanj radi govorijo. Pri dobro opredeljenem naboru omejitev večina sposobnih algoritmov da primerljive rezultate. Pri slabo opredeljenem noben algoritem ne da nič uporabnega.
Najpogostejša napaka ni algoritemska. Gre za nabor omejitev, v katerem so želje razglašene za nedotakljive, zato dopustna rešitev ne obstaja, algoritem pa upravičeno sporoči veliko neumeščenih terminov. Druga najpogostejša so zastareli ali napačni vhodni podatki — zmogljivosti učilnic, ki jih nihče ni preveril od prenove, ali dostopnost, zbrana pred šestimi tedni.
Zato koristno vprašanje ponudniku ni "kateri algoritem uporabljate", temveč "kako mi pomagate pravilno določiti omejitve in dostopnost".
Kako izgleda dober sistem v praksi
Uporaben sistem generira dovolj hitro, da je ponovno generiranje rutina in ne nočno opravilo — Wise Timetable tudi velike urnike znova generira v manj kot minuti, zato lahko eksperimentirate in se ne vežete na en sam zagon.
Sporoči, česa ni mogel umestiti in zakaj, namesto da bi tiho kršil pravilo in ustvaril nekaj, kar je videti dokončano. Upošteva termine, ki ste jih zaklenili, zato lahko mešate samodejno in ročno delo. In ustvari več različic, da lahko primerjate, namesto da sprejmete prvo.
Želite videti, kako deluje?
Rezervirajte 45-minutno spletno predstavitev, na kateri bomo postopek prikazali na primeru urnikovnega problema Vaše ustanove.