Das Kurswahlproblem
Next: Prüfungsverteilung (Examination-Timetabling) Up: Übersicht über das Spektrum Previous: Universitäre Veranstaltungsplanung (University-Timetabling/UTP)
Das Kurswahlproblem
Informelle Beschreibung:
Im Bereich des Kursunterrichts (z.B. gymnasiale Oberstufe) ist es zumeist so, daß die Schüler sich zunächst ihr individuelles
Programm auswählen können, danach versucht wird, einen Stundenplan zu erzeugen, der diesem möglichst entspricht und
dann Schüler, in deren Stundenplan Konflikte auftreten, umwählen müssen. Ziel ist hier dann auch nicht, möglichst viele
Stunden zu verteilen, sondern möglichst wenige Konflikte auszulösen (Allerdings besteht hier häufig ein linearer
Zusammenhang; vgl. Abschnitt 4.10.6.). Zumeist werden hier a priori ganze Kurse parallel gelegt, wobei
allerdings fraglich ist, ob dies optimal sein muß.
Darstellung als ILP:
Es tritt wiederum eine Variante des UTP auf, diesmal allerdings nicht als reines Suchproblem, sondern als Optimierungsaufgabe.
Hier ist allerdings zu beachten, daß ein ausfallender Kurs ebenfalls als Kollision gewertet werden muß. Hierbei seien
I die Schüler und F die Fächer. sei eine 0,1-Matrix, die aussagt, ob Schüler i an Kurs f teilnimmt und
sei die Zahl der Stunden von Kurs f. Die x geben die Stunden der Schüler und der Vektor der y die Zeitpunkte der Kurse an.
Nebenbedingungen:
Dieses Problem erscheint für theoretische Ansätze besonders interessant, da gar keine Nebenbedingungen auftreten.
Die Minimierung der Umwahlzahlen hat Vorrang vor allen anderen Überlegungen und eine Optimierung der Verteilung
wird zumeist gemäß der Problemstellung in Abschnitt 3.6.3 vorgenommen.
(c) Martin Loehnertz 1999