Skip to content. | Skip to navigation

Personal tools

Sections

Das Kurswahlproblem

next up previous contents
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. tex2html_wrap_inline5220 sei eine 0,1-Matrix, die aussagt, ob Schüler i an Kurs f teilnimmt und tex2html_wrap_inline5228 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.

eqnarray598

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