- II -

Inhaltsverzeichnis

Inhaltsverzeichnis   II

Abbildungsverzeichnis   III

1  Einleitung.  1

2  Theorie  1

3  Universitäre und schulische Anwendung.  3

3.1  Universitäre Stundenplanerstellung  3

3.2  Schulische Stundenplanung  5

3.3  Lösungen.  6

3.3.1  Constraintlogische Programmierung (CLP)  6

3.3.2  Andere Techniken und Ansätze zur Lösung  9

4  Betriebswirtschaftliche Anwendung.  9

5  Fazit.  10

Literaturverzeichnis   11

Verzeichnis  von Web-Adressen  12

- III -

Abbildungsverzeichnis   

Abbildung  1 Funktionsweise des diffn-Constraint  

Abbildung  2 Lösungsansätze für das Stundenplanproblem  

^{- 1 -} 1 Einleitung

Das Problem der Stundenplanerstellung besitzt ein breites Spektrum an Anwendungsmöglichkeiten. Ein nahe liegender Anwendungsbereich ist die Stundenplanung an Schulen und Universitäten, sowie die Prüfungsplanerstellung. Das Stundenplanproblem besteht aus einer Zuordnung von Objekten zu Raum- und Zeitressourcen, so dass eine möglichst große Zahl an vorgegebenen Nebenbedingungen erfüllt wird. Die manuelle Lösung eines Stundenpla nproblems benötigt meist mehrere Tage Arbeit und kann außerdem im Hinblick auf geforderte Bedingungen mögliche rweise eine nur unbefriedigende Lösung bereitstellen.

Weitere Anwendungsbereiche ergeben sich in der Betriebswirtschaft. Zu nennen sind hier z.B. die Maschinenbelegungsplanung in der Produktionsplanung und -steuerung (kurz: PPS) sowie die Werkstatt- oder Dienstplanung.

Auch bei der Planung von Sportveranstaltungen oder auch dem Prozessor-Scheduling wird die Stundenplanerstellung eingesetzt.

Das Ziel dieser Arbeit ist deshalb die Beschreibung verschiedener Anwendungen der Stundenplanerstellung, insbesondere im Bereich der Universitäten und Schulen. Weiterhin sollen für das nicht effizient lösbare Problem der Stundenplanerstellung Lösungsmöglichkeiten vorgestellt werden um eine Automatisierung der Lösungsberechnung mit Hilfe der Informatik zu erreichen.

In Kapitel 2 wird dazu kurz die Theorie der Komplexitätstheorie beleuchtet und die Einteilung des Stundenplanproblems in eine Komplexitätsklasse vorgenommen. Kapitel 3 befasst sich im Folgenden mit dem Problem der Stundenplanerstellung im schulischen und universitären Bereich. Mit Hilfe der constraintlogischen Programmierung wird in Kapitel 3.3.1 eine interaktive, automatische Lösung für dieses Problem vorgestellt. Die constraintlogische Programmierung konnte in vielen Anwendungen zur Lösung komplexer diskreter Probleme eingesetzt werden. Im Weiteren wird noch ein Ausblick auf weitere Lösungsverfahren gegeben. In Kapitel 4 sollen kurz betriebswirtschaftliche Anwendungen der Stundenplanerstellung betrachtet werden, im Speziellen hier die Maschinenbelegungsplanung. Zuletzt wird in Kapitel 5 ein abschließendes Fazit gezogen.

2 Theorie

Das Problem der Stundenplanerstellung (scheduling problem) wird nach [Weg03] auch als Lastverteilungsproblem bezeichnet. Unter Berücksichtigung von Nebenbedingungen geht es darum, Aufgaben auf Maschinen oder Personen zu verteilen. Die Komplexitätstheorie untersucht den Ressourcenverbrauch eines Algorithmus zumeist in Bezug auf die Rechenzeit. Zusammen mit der Berechenbarkeitstheorie und der Automatentheorie bilden diese drei die Hauptbereiche der theoretischen Informatik.

^{- 2 -} Einesder wesentlichen Forschungsgebiete der Komplexitätstheorie ist die Klassifizie-rung von Problemen im Hinblick auf den zu ihrer Lösung notwendigen Aufwand. Zur Analyse definiert die Komplexitätstheorie geeignete Kostenfunktionen, die eine Zuord-nung der Arbeitsschritte des Algorithmus zu den verbrauchten Ressourcen ermöglichen. Dafür ist es nötig festzulegen welche Art Arbeitsschritt einem Algorithmus erlaubt ist. Diese Festlegung erfolgt in der Komplexitätstheorie mit Hilfe von abstrakten Maschi-nenmodellen. Die Kostenfunktion wird dann durch eine Zuordnung von Kostenwerten zu den jeweils erlaubten Befehlen definiert.

Es wird in der Komplexitätstheorie in deterministische und nichtdeterministische Maschinenmodelle unterschieden. Meist existiert sowohl ein deterministisches Modell als auch eine nichtdeterministische Version. Nichtdeterministische M aschinen verfügen über die unrealistische Fähigkeit des Erratens eines richtigen Pfades im Berechnungsbaum. Der Begriff nichtdeterministisch bedeutet hier, dass nicht reproduzierbare und undefinierte Zustände auftreten. Automaten, die einen Algorithmus ausführen, können bei gleicher Eingabe mehrere Möglichkeiten für den Übergang in den nachgelagerten Zustand haben Dazu gibt es zwei verschiedene Arbeitsweisen. Die eine ist das Ausprobieren aller Rechenwege, die andere Möglichkeit gibt dem Algorithmus die Fähigkeit zu Raten. Der Begriff deterministisch bedeutet, dass zu jedem Zeitpunkt der nächste Rechenschritt eindeutig festgelegt ist. Es treten nur definierte und reproduzierbare Zustände auf.

Besonders häufig eingesetzte Maschinenmodelle sind der endliche Automat, der Kellerautomat, die Registermaschine und die Turingmaschine, weitere Informationen findet der Leser hierzu bspw. in [5]. Ein wesentliches Resultat der Komplexitätstheorie ist die Bildung von Komplexitätsklassen und Aussagen über deren wechselseitige Beziehungen.

Das Stundenplanproblem gehört zu der Problemklasse NP-vollständig, das heißt es gibt nach [3] einen nichtdeterministischen Algorithmus der das Problem in polynomieller Zeit löst. Daneben gibt es auch die Problemklasse P. In dieser Klasse liegen solche Probleme, für die es einen deterministischen Algorithmus gibt, der das Problem in polynomieller Zeit löst. Da jedes Problem, das von einem deterministischen Algorithmus gelöst werden kann, erst recht von einem nichtdeterministischen Algorithmus gelöst wird, ist P ⊆ NP. Unklar ist aber, ob P = NP. Als NP-vollständig bezeichnet man solche Probleme aus NP, von denen vermutet wird, dass sie nicht in P liegen. Das heißt, sollte ein deterministischer Algorithmus für das Problem gefunden werden, kann man nach [3] damit nachweisen, dass die Problemklassen P und NP gleich sind. Die Eigenschaft der NP-Vollständigkeit eines beliebigen Problems kann nach [3] durch eine Zurückführung des Problems auf das Graph-Coloring Problem bewiesen werden, da dieses bekanntermaßen NP-vollständig ist und damit auch jedes Problem, welches sich auf