Optimierung von Klausurplänen an Universitäten

Inhaltsverzeichnis

Abbildungsverzeichnis

Abkürzungsverzeichnis

Symbolverzeichnis

1 Einleitung und Aufbau der Arbeit

2 Grundlagen
2.1 Schriftliche Prüfungen
2.2 Vorlesungsverzeichnis

3 Verfahren des Operations Research
3.1 Historische Entwicklung
3.2 Einblick in die Modelle der universitären Prüfungsplanung
3.3 Optimierungsmodell ohne Kapazitätsbeschränkungen
3.3.1 Problemstellung
3.3.2 Modellformulierung
3.4 Optimierungsmodell mit Kapazitätsbeschränkungen
3.4.1 Anwendungsfall in dem Modell
3.4.2 Problemspezifische Anforderungen an den Prüfungsplan
3.4.3 Mathematische Formulierung des Problems
3.5 Vergleich der Problemformulierungen

4 Lösungsverfahren
4.1 Überblick
4.2 Simulated Annealing
4.3 Tabu Search
4.4 Gegenüberstellung

5 Fazit und Ausblick

Literaturverzeichnis

Abbildungsverzeichnis

Abbildung 1: Zuordnung der zentralen Planungsprobleme an Universitäten

Abbildung 2: Prüfungszeitraum der ,,Märchen-Universität"

Abbildung 3: Beispiel für eine Prüfungsbewegung

Abbildung 4: Beispiel für eine einfache Veränderung an einer Stelle

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Symbolverzeichnis

Symbole aus Kapitel 3.3.2:

Abbildung in dieser Leseprobe nicht enthalten

Symbole aus Kapitel 3.4.3:

Abbildung in dieser Leseprobe nicht enthalten

Symbole aus Kapitel 4.2:

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung und Aufbau der Arbeit

Die schönste Zeit im Leben ist das Studium. Diese oder ähnliche Aussagen werden häufig getroffen, ohne dabei zu berücksichtigen, mit wie vielen Belastungen Studierende konfrontiert werden. Eine der größten Schwierigkeiten für Studenten ist es, die Prüfungsphase erfolgreich zu bewältigen. Neben persönlichen Faktoren wie der eigenen Lerninitiative und der geistigen Befähigung, spielt u.a. der Aufbau des Prüfungsplanes eine wesentliche Rolle bei der erfolgreichen Bewältigung der Klausuren.

Die Erstellung eines Prüfungsplanes ist eine äußerst herausfordernde Aufgabe für Universitäten. In den meisten Fällen handelt es sich um die Modifizierung des Prüfungsplanes aus dem Vorjahr, welcher für das aktuelle Jahr angepasst wird. Prinzipiell wird der Plan per Hand oder mit Hilfe eines simplen Verwaltungssystems aufgestellt. Die Problemstellung ergibt sich aus der zeitlichen Kompatibilität der Prüfungsplanungen verschiedener Veranstaltungen^[1]. Daher wird versucht die Klausuren bestmöglich über die gesamte Prüfungsperiode zu verteilen, um Überschneidungen von Prüfungsterminen zu vermeiden.^[2]

Gegenstand dieser Arbeit ist die Optimierung von Prüfungsplänen an Universitäten. Dabei ergibt sich als Hauptziel die maximale Verringerung der Unzufriedenheit der Studenten über den Klausurplan. Der Schwerpunkt wird auf der Prüfungsplanung der schriftlichen Prüfungen liegen.

Dementsprechend wird in Kapitel 2 damit begonnen einen Überblick über die Problematik der Planerstellung zu vermitteln. Im Zuge dessen wird das Problem in seine zwei wesentlichen realen Situationen unterteilt und näher behandelt.

Im Anschluss beschäftigt sich Kapitel 3 mit den unterschiedlichen Ansätzen der Forschung. Hier wird eine Literaturübersicht vorgestellt, um aufzuzeigen, wie das Problem in den letzten Jahren thematisiert wurde. Der Fokus richtet sich im weiteren Verlauf auf zwei ausgewählte Modelle und geht auf die einzelnen Nebenbedingungen intensiv ein. Die Modelle stellen den Einfluss der Kapazitätsberücksichtigung auf das Problem der universitären Prüfungsplanung dar.

In Kapitel 4 werden zwei Lösungsverfahren zur Optimierung der resultierenden Prüfungspläne präsentiert. Es werden sowohl ihre Vorgehensweisen als auch ein Einblick in die Umsetzung sowie eine Gegenüberstellung beschrieben.

Den Abschluss der Arbeit rundet das Fazit, welches eine kurze Zusammenfassung der Ergebnisse wiedergibt, ab und ein weiterer Forschungsausblick wird gegeben.

2 Grundlagen

Das allgemeine Interesse an der universitären Prüfungsplanung ist über die letzten Jahrzehnte angestiegen. Einer der Gründe dafür ist deren Relevanz im Bildungserfolg. Es wurde sowohl eine Tendenz in Richtung einer Flexibilität von Lehrplänen als auch die Tatsache einer enorm ansteigenden Anzahl von immatrikulierten Studierenden beobachtet. Diese und weitere Umstände erhöhen signifikant die Komplexität dieses an sich schon schwierigen Problems.^[3]

Eine weitere Schwierigkeit ist die Tatsache, dass eine Veranstaltung oftmals für unterschiedliche Studiengänge angeboten wird. Das ist bspw. der Fall bei der Masterveranstaltung „Entscheidungsunterstützungssysteme“ an der Universität Duisburg-Essen, Campus Duisburg. Diese Vorlesung wird von Studenten aus verschiedenen Studiengängen besucht. Vor allem von verschiedenen Master-Studiengängen aus dem Bereich des Ingenieurwesens.^[4] Somit muss das Prüfungsdatum für die unterschiedlichen Studiengänge so gelegt werden, dass es für alle Studierenden zeitlich möglich ist. Weiterhin muss bedacht werden, dass die meisten Studenten auf eine vergleichsweise weit auseinander liegende Streuung der Prüfungstermine Wert legen, da die verfügbare Lernzeit zwischen den Klausuren erhöht wird. Dadurch wird jedoch die gesamte Klausurphase verlängert. Aus Sicht der Prüfenden bzw. Lehrenden wird generell eine kürzere Prüfungsperiode präferiert. Sie sehen den subjektiven Vorteil darin, mehr Zeit für die Vorbereitung des nächsten Semesters zur Verfügung zu haben.^[5] Somit haben die Verantwortlichen der Prüfungsplanung es mit gegenläufigen Präferenzen der Studenten und Lehrenden zu tun. Nachdem die Präferenzen berücksichtigt wurden, geht es nun um die mechanischen Bereiche der Planung. Sie wird in zwei elementare Bereiche unterteilt. Zum einen gibt es den universitären Prüfungsplan und zum anderen den Vorlesungsplan. Zwar scheinen diese Probleme zunächst ähnlich, jedoch beinhalten sie diverse Unterschiede.^[6]

In der nachfolgenden Abbildung wird ein Überblick über die Zuordnung der Problembereiche geschaffen. Die unten stehende Grafik benennt als Oberpunkt die Probleme der Ablaufplanung (Übersetzung des englischen scheduling problems ^[7] ). Diesen sind die timetabling problems untergeordnet. Eine der Untergliederungen der Ablaufplanung sind die allgemeinen Probleme des Zeitplans. Dessen Schwierigkeiten sind im Alltag verankert und beziehen sich auf verschiedene Institutionen wie bspw. den Personaleinsatzbereich, die Industrie und die Bildungseinrichtungen.^[8] Das in dieser Arbeit betrachtete und in der Grafik dargestellte Problem der Zeitplanerstellung wird im Bildungsbereich vorgefunden und unterscheidet sich in den Schul- und Universitätsbereich.^[9]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Zuordnung der zentralen Planungsprobleme an Universitäten

(Quelle: Babaei et al. (2014): 2)

Oft können Modelle der Ablaufplanung wegen der umfassenden Rechenzeiten nicht gelöst werden. Genauer gesagt sind die bisher bekannten Algorithmen zur Optimierung der Modelle nicht im Stande, in einer gegebenen Zeit eine optimale Lösung zu erarbeiten. Diese Modelle werden innerhalb der Komplexitätstheorie als NP-schwer beschrieben. Wenn eine Problemstellung schon einen als NP-schwer gekennzeichneten Gegenstand beinhaltet, so wird davon ausgegangen, dass das vorangegangene Problem ebenso NP-schwer sein muss. Dieser Umstand ist darauf zurückzuführen, dass der neu beobachtete Gegenstand, wie das erfasste Problem gleichermaßen, in die übereinstimmende Entscheidungsversion polynomial modifiziert wird. Aufgrund dessen kann es als NP-Vollständig charakterisiert werden.^[10] Zudem ist bekannt, dass die timetabling problems in fast allen Varianten den NP-vollständigen Problemen zuzuordnen sind.^[11] Es existieren drei Ansätze, um eine NP-schwere Problemstellung zur Generierung angebrachter Ablaufpläne zu lösen. Diese Methoden sind bekannt als Heuristiken, Metaheuristiken und Optimierungsverfahren.^[12]

Damit ein einwandfreier Prüfungsplan erstellt werden kann, muss ein Zeitraum gefunden werden, aus dem keine Konflikte hervorgehen. Konflikte bezeichnen in diesem Kontext, dass Prüflinge nicht mehr als eine Prüfung zur gleichen Zeit schreiben. Zudem existieren weitere Faktoren, die die Planung erschweren, wie z.B. die Verfügbarkeit von Prüfungs- und Aufsichtspersonen, freie Räumlichkeiten etc.^[13]

Der Hauptunterschied^[14] dieser beiden Pläne ist es, dass es bei der Erstellung des Klausurplanes dazu kommen kann, dass Prüfungen in demselben Raum zur gleichen Zeit auf dem Plan stehen können. Bei dem Veranstaltungsplan soll dies vermieden werden.^[15] Forscher betonen im Rahmen ihrer Studie, dass sowohl Prüfungen in unterschiedlichen Fächern als auch Vorlesungen in getrennten Räumlichkeiten stattfinden sollten.^[16] Falls zwei oder mehrere Prüfungen in einem Raum stattfinden, kann dies auch Vorteile bringen. So müsste bspw. eine geringere Anzahl von Aufsichtspersonen eingesetzt werden und nur ein Raum statt mehrerer Räume wird besetzt. Nichtsdestoweniger müssen auch die Nachteile bedacht werden, wie z.B. sehr nah beieinander sitzende Prüflinge. Diese Konstellation kann möglicherweise Abschreiben und Unterschleif erleichtern. Um dieses zu verhindern, müsste eine adäquate Planung der Sitzordnung erfolgen.^[17] Diese Sitzordnung würde wiederum Unübersichtlichkeit erzeugen und die Anzahl des Aufsichtspersonals müsste durch die hohe Anzahl von Prüfungen trotzdem gesteigert werden, um einen reibungslosen und fairen Ablauf der Prüfung zu gewährleisten. Die organisatorischen Vorteile von zusammengelegten Prüfungen werden somit außer Kraft gesetzt. Weder wird der Planungsaufwand geringer, da man nun die Sitzordnung festlegen muss, noch wird eine Verringerung des nötigen Personals erzielt. Deswegen sollte jeder Prüfung nur ein Raum zu einer bestimmten Zeit zugeteilt werden.

In den folgenden Abschnitten wird das Problem der Prüfungsplanung in die zwei wesentlichen Bestandteile aufgeteilt und beschrieben, um eine anschauliche Darstellung des zu behandelnden Problems präsentieren zu können.

2.1 Schriftliche Prüfungen

Der Begriff Examination Timetabling bezeichnet die Erstellung eines Planes für schriftliche Prüfungen. Eine Prüfung ist normalerweise so gestaltet, dass mehrere Prüflinge aus einem Fach in diesem geprüft werden. Das organisatorische Ziel bei schriftlichen Prüfungen ist es, die komplette Anzahl der schriftlichen Prüfungen aller Teilnehmer auf Zeiträume so zu verteilen, dass keiner der Studenten mehrere Prüfungen gleichzeitig ablegen muss. Parallel hierzu erfolgt die Zuordnung der Räume für den Klausurort.^[18]

Zunächst muss die Optimierung problemspezifisch anhand von Qualitätsanforderungen, an denen der Plan gemessen wird, festgelegt werden. Diese manifestieren sich in Kriterien an einen Klausurplan, die Aufschluss darüber geben, ob das Resultat der Planung positiv oder negativ zu bewerten ist.^[19]

Nach McCollum et al. (2012) ist ein Prüfungsplan erst dann brauchbar, wenn alle Prüfungen in einer Periode und dem jeweiligen Raum zugeordnet werden und präsentiert folgende Bedingungen, die zusätzlich erfüllt sein müssen:

I. Hinsichtlich der Zuordnung der Prüfungen darf kein Prüfling in mehr als einer Prüfung sitzen. Hier müssen die oben genannten Prüflings-Konflikte in Betracht gezogen werden, die minimiert werden sollen.
II. Zu keinem Zeitpunkt der Prüfungsphase darf die Kapazität der einzelnen Räume^[20] überschritten werden. Ein Prüfungsraum muss mindestens die Kapazität der Prüflinge umfassen, die die betreffende Klausur antreten.
III. Die Zeitperiode, in der die Prüfungen eingeordnet werden, darf nicht überschritten werden. Das setzt voraus, dass die gesamte Dauer des Prüfungszeitraumes vor der Erstellung bestimmt werden muss.
IV. Harte Bedingungen^[21] in Bezug auf die Prüfungsperiode müssen erfüllt sein. Diese Bedingungen haben den Zweck, die Rangfolgen zwischen den Klausuren zu kontrollieren. Somit folgt eine Klausur des Aufbaumoduls logischerweise der Prüfung aus dem Grundlagenkurs.
V. Was die Räumlichkeiten angeht, müssen die harten Bedingungen erfüllt sein, d.h. in dem fertigen Prüfungsplan, muss jede Klausur so verteilt worden sein, dass keine zwei Prüfungen innerhalb eines Raumes stattfinden.^[22]

Wird die Anzahl der zu erfüllenden Anforderungen gesteigert, so wird der Komplexitätsgrad der Problemstellung sukzessiv erhöht. Damit bei diesem schwierigen Problem trotzdem eine Lösung gefunden werden kann, wird in der realen Planungssituation von wenigen Bedingungen ausgegangen.^[23]

2.2 Vorlesungsverzeichnis

Unter dem Begriff Course Scheduling wird die Zuordnung einer gewissen Anzahl an universitären Veranstaltungen auf eine beschränkte Anzahl von Perioden verstanden. Dieses Scheduling muss so erstellt werden, dass kein Professor und kein Student für mehr als eine Vorlesung gleichzeitig zugeteilt wird. Zudem ist die Verfügbarkeit der Räumlichkeiten, in denen die Vorlesungen, Seminare etc. stattfinden, unbedingt zu beachten.^[24]

Das Ziel der klassischen Veranstaltungsplanung ist nach Hertz (1991) , die Anzahl der Konflikte zu minimieren, die dann entstehen, wenn Lehrveranstaltungen sich überschneiden. In Universitäten stellt sich das Problem als besonders komplex dar, da exemplarisch folgende Restriktionen zusätzlich in Betracht gezogen werden müssen:^[25]

I. Die Länge der Veranstaltungen an Universitäten ist unterschiedlich, wohingegen in Schulen die Dauer einer Unterrichtseinheit festgesetzt ist. An Hochschulen ist die Zeit meist vom Veranstaltungsrhythmus abhängig. An der MSM (Mercator School of Management), Fakultät für Betriebswirtschaftslehre in Duisburg, finden geblockte und semesterübergreifende Lehreinheiten^[26] statt.^[27] Die Veranstaltung „Operations Research“ an der MSM ist beispielsweise ein semesterübergreifender Lehrgang des Bachelor-Studiengangs Betriebswirtschaftslehre und sie findet wöchentlich sowohl im ersten als auch im zweiten Block statt, d.h. diese Veranstaltung dauert somit ca. 120 Minuten.^[28] Dieses Prüfungsfach muss so zugeteilt werden, dass es sich zeitlich mit den geblockten Veranstaltungen, die ebenfalls für das Semester vorgesehen sind, nicht überschneidet. Die Schwierigkeit bei der Festlegung von Semesterterminen an Instituten, wie der Mercator School of Management besteht darin, dass eine Veranstaltung so zugeordnet wird, dass sie über das ganze Semester zur selben Zeit im selben Raum stattfindet.
II. In Fall der Hochschullehrenden müssen sowohl deren Verfügbarkeiten und Zeitpräferenzen berücksichtigt werden. An Universitäten ist es üblich, dass ein Lehrstuhl sich auf ein Fachgebiet spezialisiert. Hierdurch wird die Zuteilung der Veranstaltungen erschwert, da die betreffende Lehreinheit von einem Lehrstuhl angeboten wird, obwohl Studierende unterschiedlicher Studiengänge diese Veranstaltung besuchen müssen. Meist haben diese Studenten auch Veranstaltungen von komplett gegensätzlichen Lehrstühlen, die sich im Zweifelsfall nicht untereinander abstimmen.
III. Den Studenten muss ausreichend Zeit zwischen den Vorlesungen oder Seminaren gegeben werden, damit sie sich von einem Gebäude bis zu einem anderen bewegen können.^[29]

Außerdem können einige Prüfungsfächer für die jeweiligen Studiengänge aus Wahlfächern bestehen. Die Schwierigkeit hierbei stellt sich so dar, dass den Studierenden so viel Freiheit gewährt werden muss, dass sie die Wahlfächer nach ihren Präferenzen wählen können. Dies ist nicht gegeben, wenn sich die präferierten Veranstaltungen mit den Pflichtveranstaltungen überschneiden.^[30]

Zusammengefasst bestehen die Planungsprobleme an Hochschulen aus der Terminierung des Lehrprogramms. In diesem Kontext ergeben sich zwei verschiedene Probleme, die eng miteinander verwandt sind. Zum einen geht es um die Organisation der Veranstaltungen (Vorlesungen, Seminare, Kurse etc.) und zum anderen darum, Prüfungstermine auf effiziente Art und Weise zu planen. Die timetabling problems sind für Forscher von anhaltendem Interesse. Dies ist darauf zurückzuführen, dass diese Probleme Spielraum dafür geben kombinatorische Lösungsmethoden in mathematische Formulierungen anzuwenden, die wiederum schwierige praktische Probleme darstellen.^[31]

3 Verfahren des Operations Research

Die Problematik der universitären Prüfungsplanung ist ein von der Literatur weitreichend erforschtest Themengebiet, innerhalb dessen sich im Grunde ähnliche, aber problemspezifische Modelle entwickelt haben. Zunächst wird in diesem Abschnitt der Ursprung des Operations Research dargelegt und parallel der Bezug in den Bildungsbereich geknüpft. Anschließend wird ein Überblick der bisher bekannten Ansätze von Forschern gegeben. Die unterschiedlichen Aspekte der Ansätze werden hierbei hervorgehoben und die mathematischen Bestandteile des OR werden teilweise erklärt. Das Hauptaugenmerk wird sich jedoch auf die theoretische Erklärung richten. An späterer Stelle werden zwei ausgewählte Modelle, die sich auf die Kapazitätsbedingungen in der Planungssituation stützen, ausgiebig beschrieben. Am Ende des Kapitels werden die beiden Modelle miteinander verglichen und ausschlaggebende Unterschiede aufgezeigt. Dadurch soll dargelegt werden, welche Betrachtungsweise sich am ehesten für die Problemstellung eignet.

3.1 Historische Entwicklung

Die historische Entstehung des Operations Research ist auf das Jahr 1937 zurückzudatieren. Im Umfeld der britischen Wehrmacht ist sie zum ersten Mal konzipiert worden und entsprechend wurde in diesem Jahr eine Gruppe von Wissenschaftlern in der englischen Armee so bezeichnet. Diese Forschergruppe befasste sich mit den Funktionen und Anwendungsmöglichkeiten eines Radars. Nach 1945 etablierte sich das Operations Research, im Zuge ihrer Erfolge während der Kriegsjahre, auch im zivilen Bereich.^[32]

Die Technik des Operations Research (OR) wurde im Laufe der Zeit vom militärischen Sektor zum Bildungssektor transferiert. Seitdem wird das OR im Bildungskontext zahlreich angewandt. Dabei wird unter anderem auf die Probleme der Wege- und Ablaufplanung hingewiesen. Beispiele hierfür sind Routenprobleme von Schulbussen oder die Zuordnung von Schülern zu Klassen. Gerade in Bezug auf den strukturellen Wandel von Hochschulen (Zuwachs der Studenten, größeres Leistungsangebot an Studiengängen und Veranstaltungen etc.) ist eine effiziente Generierung von Prüfungs- und Kursplänen von enormer Bedeutung und in der Folge auch die Anwendung des OR auf diese Problematiken. Vor allem die Hinzuziehung eines Entscheidungsunterstützungssystems kann hier, im Hinblick auf zeitökonomische Aspekte, wesentliche Vorteile bringen.^[33]

Die Suche nach einer optimalen Entscheidung unter Berücksichtigung von zahlreichen Nebenbedingungen charakterisiert das OR. Die Gemeinsamkeit aller typischen OR Anwendungen besteht darin, eine Zielfunktion entweder zu maximieren oder zu minimieren. Dies ist abhängig davon wie man ein Problem lösen möchte bzw. muss. Damit ein Problem mathematisch formuliert werden kann, ist es zunächst nötig, dass ein problemspezifischer Zustand besteht.^[34]

3.2 Einblick in die Modelle der universitären Prüfungsplanung

In diesem Kapitel werden einige Ansätze zur Formulierung und Lösung des Problems der Prüfungsplanung vorgestellt und ein allgemeiner Literaturüberblick gegeben. Es wird versucht auf fundamentalen Ansätzen aufzubauen, um deutlich zu machen, wie sich die Forschung in diesem Themenkomplex weiterentwickelt hat.

Broder (1964) beschreibt als einer der ersten das Problem der universitären Prüfungsplanung, wobei er sich jedoch nur auf die Planerstellung von Abschlussprüfungen bezieht.^[35] Aus diesem Grund wird auf seine Publikation nicht näher eingegangen.^[36]

Carter (1986) fasst im Rahmen seiner Studie viele der bisher entwickelten Lösungsansätze zusammen und setzt sie in Verbindung mit dem damaligen Stand der Technik. Seine Motivation hierfür entstand dadurch, dass die vorangegangen Verfahren zur Problemlösung immer für spezifische Probleme entwickelt worden sind und damit nicht als Grundlage für die Anwendung anderer Probleme innerhalb der Prüfungsplanung zu gebrauchen sind. Die Problemstellung wird mithilfe eines Graphenfärbungsproblems beschrieben. Jede Prüfung wird durch einen Knoten dargestellt und zwei Knoten werden durch eine Kante miteinander verbunden. Das Ziel ist es, jedem Knoten eine Farbe (die Farbe stellt eine verfügbare Prüfungsperiode dar) zu vergeben, so dass keine zwei verbundenen Knoten der gleichen Farbe zugeordnet werden. Eine andere Zuordnung ist nicht möglich, da diese Knoten mindestens einen gemeinsamen Prüfling enthalten und somit einige Studenten zwei Prüfungen zur selben Zeit ablegen müssten.^[37]

In einer weiteren Publikation von Carter et al. (1994) wird angestrebt ein Verfahren zu entwickeln, das sich an die Bedürfnisse vieler Bildungseinrichtungen anpasst. Es wird ebenfalls darauf hingewiesen, dass es sich um einen erweiterten Ansatz von anderen Forschern handelt.^[38] In der vorangegangen Perspektive wurde eine Prüfung als Knoten dargestellt und diesem eine Farbe zugewiesen. In dem jetzigen Ansatz soll eine Verbesserung bzgl. des Zuordnungssystems aufgezeigt werden. Dementsprechend werden zuerst die Prüfungen, die mit den größten Schwierigkeiten^[39] verbunden sind, zugewiesen. Im zweiten Schritt kommt eine Zielfunktion zum Einsatz, welche Strafkosten^[40] verteilt. Diese Kosten werden auferlegt, wenn die Grenze der maximalen Klausuren innerhalb einer Prüfungsphase überschritten wird.^[41] Dieser zweite Ansatz stellt besonders wegen der erweiterten Zielfunktion eine Verbesserung, im Vergleich zu Carter (1986) , dar. Die Ergebnisse können an der Verbesserung bzw. Verschlechterung des Zielfunktionswertes erfasst werden. Damit kann eine Lösung auf eine aussagefähigere Art und Weise begründet werden.

In dem Ansatz von Burke und Newall (1999) wird das Zuordnungsproblem mit einem Verbesserungsverfahren aus der Gruppe der genetischen Algorithmen^[42] gelöst. Sie präsentieren die Implementierung eines evolutionären Algorithmus. Die Problematik besteht darin, einen Prüfungsplan so zu generieren, dass eine bestimmte Menge von Klausuren (E) auf eine begrenzte Anzahl von Prüfungszeiten^[43] (P) ideal zugeordnet werden, mit der Bedingung, dass es eine festgesetzte Anzahl von Sitzmöglichkeiten zur jeweiligen Zeit (S) existieren.^[44]

Bei der Problemformulierung wird eine zusätzliche Periode (P+1) hinzugezogen. In dieser zusätzlichen Periode werden alle nicht zugeordneten Klausuren^[45] gesammelt, damit jede Prüfung durch die zusätzliche Periode zugeordnet werden kann. Diese Periode hat einen großen Einfluss auf den Zielfunktionswert. Tritt die Situation auf, dass die Extraperiode in Anspruch genommen werden muss, dann wird dieser Umstand mit einem Wert von 5.000 Punkten bestraft. Damit soll verhindert werden, dass Prüfungen nicht zugeordnet bleiben. Die Zielfunktion wird wie folgt formuliert:^[46]

Abbildung in dieser Leseprobe nicht enthalten

Die Zielfunktion summiert über alle Prüfungen die jeweiligen Fälle der Perioden, in denen Prüflinge in derselben Zeit mehrere Klausuren ablegen müssen. Das soll durch die Vergabe in Höhe von Strafkosten minimiert werden.^[47]

Die Anzahl der Prüflinge, die sowohl für die Klausur i als auch für j angemeldet sind ([Abbildung in dieser Leseprobe nicht enthalten])^[48] werden multipliziert mit t=1, wenn die Prüfungen unterschiedlichen Zeiten zugewiesen wurden. Wurden die Klausuren tatsächlich verschiedenen Zeiten zugeordnet, ist der Term [Abbildung in dieser Leseprobe nicht enthalten]. Das Produkt aus diesen vier Komponenten würde dem Ausmaß von [Abbildung in dieser Leseprobe nicht enthalten] entsprechen. Falls die Zeiten der beiden Klausuren auf denselben Tag treffen, ist der Term [Abbildung in dieser Leseprobe nicht enthalten]. Dadurch wäre [Abbildung in dieser Leseprobe nicht enthalten] verdreifacht und somit widersprüchlich zum eigentlichen Effekt der Formel.^[49] Wenn die zugeteilten Prüfungszeiten konfliktfrei verstreut sind, dann weist die Zielfunktion einen niedrigen Wert auf. Strafpunkte werden vergeben, wenn ein Umstand nicht erwünscht ist. Dementsprechend, sollten dennoch Prüfungen nicht eingeplant sein, wird die Sonderperiode hinzugezogen und belastet in diesem Szenario den Zielfunktionswert mit Strafkosten i.H.v. 5.000 Punkten. Bei diesen Formulierungen wird durch das [Abbildung in dieser Leseprobe nicht enthalten] immer davon ausgegangen, dass es Studenten gibt, die sich für mehrere Klausuren angemeldet haben. Je mehr Prüflinge sich für eine Prüfung einschreiben, desto höher fällt [Abbildung in dieser Leseprobe nicht enthalten] aus und umso größer wird der Zielfunktionswert, da diese Parameter miteinander multipliziert werden.

Zusammenfassend kann festgehalten werden, dass es in dieser Problemformulierung darum geht, die Prüfungen den Prüfungszeiten bestmöglich zuzuweisen. Hierbei wird besonders darauf Acht gegeben, dass jede Klausur einer Zeit zugewiesen wird bzw. nicht ohne Zuteilung bleibt. In dem angewandten Lösungsverfahren teilt sich das gesamte Problem in Teilprobleme auf und es wird der Reihe nach versucht, die Qualität des resultierenden Prüfungsplanes zu optimieren.^[50]

Einige Jahre später erweitern Burke und Newall (2004) ihr Modell, um die Anwendung auf mehrere Zeitplanprobleme zu übertragen. Sie entwickeln die folgende zweite Zielfunktion, um die Lösungen auf zwei alternativen Wegen zu bestimmen und aussagekräftiger zu begründen:^[51]

Abbildung in dieser Leseprobe nicht enthalten

Mit dieser Minimierungsfunktion wird die Zerstreuung von Prüflingen, die mehrere Prüfungen ablegen werden, gemessen. Sie verwenden sowohl die Zielfunktion aus dem Modell von Burke und Newall (1999) als auch die jetzt genannte Zielfunktion. Diese zwei Alternativen unterstützen durch den gegenseitigen Vergleich die Entscheidungsfindung einer Lösung.^[52] Es heißt, je besser die Studenten verteilt sind, desto besser sind die zugehörigen Prüfungen (von demselben Prüfling) voneinander entfernt. Deutlich zu erkennen ist, dass die Strafkosten für die Extraperiode verzehnfacht wurden. Der Strafwert wird jeder Prüfung i vergeben, dessen timeslot sich in der zusätzlichen Periode (P+1) befindet.

Ein weiterer Ansatz richtet sich nach Ahandani et al. (2012) . Die Autoren entwickeln ein eher simples Modell. Um eine zulässige Lösung zu generieren, strebten die Forscher an, nur eine harte Bedingung zu erfüllen. Diese eine Anforderung besagt, dass kein Prüfling durch den erstellten Prüfungsplan dazu gezwungen sein wird, zwei Klausuren in derselben Zeit ablegen zu müssen. Außerdem wird die Qualität nur anhand einer einzigen weichen Anforderung gemessen. Diese Bedingung sagt aus, dass die Prüfungszeiten bestmöglich verstreut sein sollen. Ihre Zielfunktion minimiert die Summe über alle Kosten, die für das Aufeinandertreffen (harte Restriktion) und für die Nähe (weiche Restriktion) von zwei timeslots ^[53] vergeben werden. Diese Summe wird durch die Anzahl der Prüflinge dividiert und vermindert dadurch die Höhe des Zielfunktionswertes.^[54] Diese Problemformulierung wurde sehr problemspezifisch entwickelt und würde sich eher weniger für die Umsetzung in reale Planungssituation eignen.

Das letzte Model nennt sich „MIP-Modell“ (Mixed Integer Programming) und wurde von Arbaoui et al. (2015) entwickelt. Diese Problemformulierung baut auf dem Original „IP-Modell“ (Integer Programming) von McCollum et al. (2012) auf.^[55]

McCollum et al. (2012) berichtet im Rahmen seiner Studie darüber, dass viele der präsentierten Modelle nicht die reale Planungssituation von den heutigen modernen Hochschulen erfassen. Aus diesem Grund war die Forschung bestrebt eine detaillierte Problemformulierung zu entwickeln, die die Forschung durch die Darstellung einer wirklichen Planungssituation ergänzt. Das grundlegende Ziel, einen optimierten Prüfungsplan zu erstellen, wird beibehalten. Die Erweiterung in der Forschung besteht in der Intensivierung der Parameter, Entscheidungsvariablen und den harten und weichen Beschränkungen^[56], die für die Entscheidungsfindung gegeben sein müssen. Die Zielfunktion minimiert die Summe über alle Strafkosten, mit denen die Randbedingungen bei Verstoß gewichtet werden. Das Problem wurde durch ein ganzzahliges Optimierungsmodell formuliert und soll als Basis für weitere Forschungen dienen.^[57]

Bei Arbaoui et al. (2015) wird das Problem durch ein gemischt ganzzahliges Modell beschrieben. Das Ursprungsmodell wird durch eine Verringerung der Beschränkungen verbessert bzw. präziser dargelegt.^[58] In der Vorgehensweise werden alle Prüfungen l zusammengefasst und mit dem Parameter Si bezeichnet (Sj kennzeichnet die Gruppe der j Klausuren).^[59] Das Ziel besteht darin, diese Gruppen gemeinsam auf die Prüfungszeiten mit entsprechend zugewiesenen Räumen zu verteilen. In der Zielfunktion wird die Summe der Anzahl von Prüfungen aus der Vereinigungsmenge [Abbildung in dieser Leseprobe nicht enthalten], die einem Raum zugewiesen werden können, maximiert. Ist der Zielfunktionswert (θij) kleiner als die Vereinigungsmenge im Betrag, so darf keine Prüfung l zur selben Periode mit einer Prüfung k zugewiesen werden.^[60]

In keinem der vorgestellten Ansätze wurde auf die Kapazitätsengpässe, die dieses Problem in Bezug auf etwa Räumlichkeiten hat, eingegangen. In einer Problemformulierung der universitären Prüfungsplanung, die die Kapazitätsprobleme hinzuzieht, wird das Planungsproblem realitätsnah formuliert. Neben der üblichen Zuweisung der Räume wird zusätzlich die Anzahl einer Prüflingsgruppe in Relation mit der Sitzkapazität eines Prüfungsortes betrachtet.^[61] Deswegen wird im weiteren Verlauf das Augenmerk auf solchen Modellen liegen, welche die Anforderungen diesbezüglich berücksichtigen und welche die Kapazitätsrestriktionen bewusst vernachlässigen. Das Ziel besteht darin, einen besseren Vergleich der Problemansätze aufzuzeigen und somit die Formulierungen besser einschätzen zu können.

3.3 Optimierungsmodell ohne Kapazitätsbeschränkungen

In dem folgenden Abschnitt wird ein Modell von Abdullah et al. (2007) vorgestellt. Sie zeigen in ihrer Studie zwei Problemformulierungen auf, welche dieselben Parameter benutzen. Das erste Modell gibt die Problemstellung der Prüfungsplanung wieder, ohne dabei jegliche Kapazitätsprobleme zu berücksichtigen. Im nächsten Modell werden hingegen zusätzlich Probleme bzgl. der Kapazitäten mit einbezogen. Die Autoren entwickelten in ihrer Forschung ein kurzes Optimierungsmodell. Innerhalb der mathematischen Formulierung wird nur ein Aspekt beachtet. Die Klausuren sollen über die Prüfungsperiode so zugeteilt werden, dass die Prüfungen von demselben Prüfling keine unmittelbare Nähe aufweisen.^[62] Im Rahmen dieser Arbeit wird deren „nicht kapazitätsbezogene“ Methode vorgestellt.

3.3.1 Problemstellung

Der Anwendungsfall richtet sich bei Abdullah et al. (2007) nach dem grundlegenden Problem bei der Planerstellung. Dieses bezieht sich auf die Zuordnung von Prüfungen auf Zeiten in einer vorher festgesetzten Klausurperiode, wobei je nach Bildungseinrichtung unterschiedliche Beschränkungen eingehalten werden müssen.^[63]

Sowohl in der Literatur als auch in dieser Arbeit soll aufgezeigt werden, dass Anforderungen an einen zulässigen Prüfungsplan heterogen sind. In dieser Problemstellung darf es keinen Zwang geben, dass Institutionen bestimmte Kriterien berücksichtigen müssen. Eventuell werden sie nicht benötigt oder aufgrund der Universitätsstruktur anders aufgefasst.^[64]

Nach Burke et al. (2004) existieren zwei fundamentale harte Beschränkungen, um eine akzeptable Lösung eines Prüfungsplanes zu erhalten:^[65]

I. Kein Student darf in einer Prüfungsperiode zu derselben Zeit mehr als eine Prüfung antreten.
II. Während des gesamten Prüfungszeitraumes darf es zu keinem Raumengpass kommen.

In der nachstehenden Modellformulierung verzichtet Abdullah et al. (2007) auf das zweite Kriterium, da Kapazitätsprobleme vernachlässigt werden sollen.

3.3.2 Modellformulierung

Folgende Annahmen sind für die Formulierung des Modells festgesetzt:^[66]

N = Anzahl der Prüfungen

Ei = ist eine Prüfung, i [Abbildung in dieser Leseprobe nicht enthalten]

B = Set von allen N Prüfungen, B= [Abbildung in dieser Leseprobe nicht enthalten]

D = Anzahl der Tage

T = Anzahl der verfügbaren timeslots

M = Anzahl der Prüflinge

Br = bezeichnet das jeweilige Gebäude für den Prüfungsraum r

C = Konfliktmatrix, wobei jedes Element mit [Abbildung in dieser Leseprobe nicht enthalten] bezeichnet wird ([Abbildung in dieser Leseprobe nicht enthalten] und die Anzahl von Studenten darstellt, die sowohl die Prüfung i als auch die Prüfung j antreten werden.

[Abbildung in dieser Leseprobe nicht enthalten] bezeichnet den zugeteilten timeslots für die Prüfung [Abbildung in dieser Leseprobe nicht enthalten]

Mit dem nachstehenden Optimierungsmodell wird lediglich die Zerstreuung der Prüfungen in der gesamten Klausurphase präsentiert. In diesem Sinne wird die Zielfunktion wie folgt formuliert:^[67]

Abbildung in dieser Leseprobe nicht enthalten

Die Zielfunktion wird in Form eines Bruches angegeben. Im Zähler wird die Summe der Gleichung (2) für die Prüfung i dargestellt. Dieser Wert steht in Relation zu der Anzahl der gesamten Prüflinge. Die Funktion minimiert die Summe über alle Strafkosten, die für die Nähe einer Klausur i und j vergeben wurden. Die Schreibweise legt fest, dass die Anzahl der Prüfungen (N) von i bis N-1 summiert werden. Je nachdem welche Zahl das N annimmt ändert sie sich um eine Einheit. Es wird nicht angegeben wie sich der Zielfunktionswert auswirken würde, wenn N sich um zwei Einheiten vermindert.

Das [Abbildung in dieser Leseprobe nicht enthalten] wird wie folgt ermittelt wird:^[68]

Abbildung in dieser Leseprobe nicht enthalten

Das Produkt aus der Anzahl aller Prüflinge, die sowohl in Prüfung i als auch in Prüfung j geprüft werden ([Abbildung in dieser Leseprobe nicht enthalten]), multipliziert mit einem Näherungswert, wird über alle Prüfungen i (ab i+1) aufsummiert. Das F1(i) stellt die Summe der vergebenen Strafwerte, für die Nähe von zwei verschiedenen Klausuren, dar^[69] Die Näherungswerte stellen Strafkosten dar und ergeben sich aus:^[70]

proximity [Abbildung in dieser Leseprobe nicht enthalten]

[...]

---

^[1] In dieser Arbeit werden die Begriffe Veranstaltung, Vorlesung, Vortrag, Kurs synonym verwendet.

^[2] Vgl. Azimi (2005): 705 f.

^[3] Vgl. Pais und Amaral (2012): 342.

^[4] Vgl. LSF Universität Duisburg-Essen (o. J.a).

^[5] Vgl. Pais und Amaral (2012): 342.

^[6] Vgl. Burke und Petrovic (2002); 266 f; Lewis (2008): 169.

^[7] Vgl. Klemmt (2012): 1.

^[8] Vgl. Pais und Amaral (2012): 341.

^[9] Vgl. Babaei et al. (2014): 2.

^[10] Vgl. Hermann (2010): 70 f.

^[11] Vgl. Cooper und Kingston (1995): 283 ff; Schaerf (1999): 89 ff; Lewis (2008): 167; Pais und Amaral (2012): 346.

^[12] Vgl. Hermann (2010): 70 f.

^[13] Vgl. Pais und Amaral (2012): 342.

^[14] Dieser Hauptunterschied wird gleichzeitig in den Bedingungen an einen Optimalen Prüfungsplan nach McCollum et al. (2012) im Abschnitt 2.1, Punkt (V) aufgefasst.

^[15] Vgl. Lewis (2008): 169.

^[16] Obwohl Ausnahmen von dieser Restriktion möglich sind. Diese Anforderung wird relevant bei der mathematischen Formulierung des Problems. Hierbei geht es im Wesentlichen um die Kapazitätsprobleme; Vgl. hierzu Abschnitt 3.2 bzw. Kahar und Kendall (2010): 559 ff.

^[17] Gemeint ist hiermit, dass die Sitzreihen bspw. mit Prüfung A beginnen und dann im Turnus A und B regelmäßig wechseln.

^[18] Vgl. Juretzka (2001): 7.

^[19] Vgl. Elias (2015).

^[20] Mit Räumen sind innerhalb dieser Arbeit jegliche Prüfungsräumlichkeiten gemeint.

^[21] Eine harte Bedingung kennzeichnet eine Anforderung die gegeben sein muss, damit eine Lösung als zulässig bezeichnet werden kann. Analog hierzu werden weiche Bedingungen genutzt, um die Qualität des Resultats zu beurteilen; Vgl. Al-Betar et al. (2014): 24. Im Kapitel 3 werden die harten und weichen Restriktionen durch die mathematischen Problemformulierungen näher präsentiert.

^[22] Vgl. McCollum et al. (2012): 295.

^[23] Vgl. Burke et al. (2004): 510.

^[24] Vgl. Juretzka (2001): 29; Dimopoulou und Miliotis (2001): 203 f.

^[25] Vgl. Hertz (1991): 39.

^[26] Vgl. LSF Universität Duisburg-Essen (o. J.c).

^[27] An der Mercator School of Management besteht ein Semester besteht aus zwei Blöcken. Das Semester beginnt mit einem sechs wöchigen Vorlesungsblock. Im Anschluss gibt es eine Klausurvorbereitungswoche und darauffolgend die Prüfungsphase im ersten Block, welches ebenfalls eine Woche umfasst. Nach diesem Teil beginnt der zweite Vorlesungssatz und dauert auch sechs Wochen. Die nun folgende Klausurphase besteht aus ca. vier Wochen; Vgl. Mercator School of Management, Fakultät für Betriebswirtschaftslehre (o. J.).

^[28] LSF Universität Duisburg-Essen (o. J.b).

^[29] Vgl. Hertz (1991): 39.

^[30] Vgl. Hertz (1991): 39.

^[31] Vgl. Dimopoulou und Miliotis (2001): 202.

^[32] Vgl. Zimmermann (1987): 5 f.

^[33] Vgl. Johnes (2015): 687 f.

^[34] Vgl. Neumann und Morlock (2002): 5 ff.

^[35] Vgl. Broder (1964):494.

^[36] Des Weiteren fasst Carter (1986) in seiner Studie, die bis dato bekannten Ansätze zusammen. Darunter fällt u.a. auch der Ansatz von Broder (1964) ; Vgl. Carter (1986): 196.

^[37] Vgl. Carter (1986): 193 f.

^[38] Vgl. Carter et al. (1994): 109 f.

^[39] Wie oben erwähnt wurde, ergeben sich die Schwierigkeiten in Bezug auf die zeitliche Zuordnung im Graphen, da viele Klausuren (Knoten) die selbe Farbe präsentieren und genau dieser Umstand vermieden werden sollte. Eine Farbe stellt eine verfügbare Prüfungsperiode dar.

^[40] Da es sich um einen Algorithmus handelt, ist es üblich das die Durchführbarkeit wiederholt bewertet wird; Vgl. Carter et al. (1994): 111; ebenso wie Kapitel 4.

^[41] Vgl. Carter et al. (1994): 111.

^[42] Der Begriff „genetischer Algorithmus (GA)“ ist die Zusammenfassung einer Gesamtheit von stochastischen Heuristiken. Diese Gruppe untersucht einen Lösungsraum gleichzeitig an mehreren Stellen. Dabei wird der Grundsatz der biologischen Evolution zur Optimierung herangezogen. Hiermit ist gemeint, dass der Zustand jeder zulässigen Lösung der Problemstellung durch ihren Fitnesswert angegeben wird. Dieser Wert wird im Rahmen eines Optimierungsproblems vom Zielfunktionswert der jeweiligen Lösung dargestellt. In der Vorgehensweise und unter der Berücksichtigung vom Grundsatz der biologischen Evolution ist die Wahl einer zulässigen Lösung abhängig von ihrer Fitness; Vgl. Domschke und Drexl (1996): 37 ff.

^[43] Ein Tag besteht aus drei Tageszeiten zu denen eine Prüfung zugeteilt werden kann; Vgl. Burke und Newall (1999): 64.

^[44] Vgl. Burke und Newall (1999): 64.

^[45] Es wird nicht angegeben, wieso eine Prüfung nicht zugewiesen werden kann.

^[46] Vgl. Burke und Newall (1999): 64.

^[47] Vgl. Burke und Newall (1999): 64.

^[48] Im Allgemeinen wird dieser Parameter dafür genutzt, die zeitliche Zerstreuung von zwei Prüfungen darzulegen; Vgl. Juretzka (2001): 44.

^[49] Im Rahmen der Ansätze wird auf die Darstellung der einzelnen Annahmen verzichtet. Für eine ausführlichere Beschreibung vgl. Burke und Newall (1999): 64.

^[50] Vgl. Burke und Newall (1999): 65.

^[51] Vgl. Burke und Newall (2004): 112.

^[52] Vgl. Burke und Newall (2004): 112.

^[53] Der Begriff timeslot bezeichnet ein Zeitintervall, in dem jegliche Aktivitäten (Einteilung der Prüfer und Aufsichtspersonen, Vorlesung, Prüfungen, etc.) stattfinden. Somit kann bspw. ein timeslot einen Wochentag umfassen z.B. Dienstag oder einen Tag in Stunden bezeichnen z.B.: von 8 bis 9 Uhr; Vgl. Babaei et al. (2014): 2.

^[54] Vgl. Ahandani et al. (2012): 34.

^[55] Vgl. Arbaoui et al. (2015): 19 ff.

^[56] Die Bedingungen werden in drei Stufen unterschieden. Es gibt die „Strikt harten“ (diese müssen eingehalten werden, damit eine Lösung akzeptiert wird.), die „Entspannt harten “ (während der Planerstellung wird es toleriert, wenn einige Bedingungen zu diesem Zeitpunkt noch nicht umgesetzt worden sind. Diese Ergebnisse stellen für den Moment keine zulässige Lösung dar.) und die „Weichen“ Restriktionen. Die Nebenbedingungen des Modells unterliegen ebenfalls dieser Struktur; Vgl. McCollum et al. (2012): 296 ff.

^[57] Vgl. McCollum et al. (2012): 291 ff.

^[58] Vgl. Arbaoui et al. (2015): 19.

^[59] Für den weiteren Verlauf wird folgende Annahme getroffen: l ϵ Si und k ϵ Sj; Vgl. Arbaoui et al. (2015): 27.

^[60] Vgl. Arbaoui et al. (2015): 27.

^[61] Vgl. Pillay und Banzhaf (2009): 483.

^[62] Vgl. Abdullah et al. (2007): 355 ff.

^[63] Vgl. Burke et al. (2004): 509; Carter et al. (1996): 373.

^[64] Vgl. Juretzka (2001): 8.

^[65] Vgl. Burke et al. (2004): 509.

^[66] Vgl. Abdullah et al. (2007): 355.

^[67] Vgl. Abdullah et al. (2007): 356.

^[68] Vgl. Abdullah et al. (2007): 356.

^[69] Vgl. Abdullah et al. (2007): 356.

^[70] Gleichung (3) richtet sich nach Carter et al. (1996); Vgl. Abdullah et al. (2007): 356.