Skip to content. | Skip to navigation

Personal tools

Sections
You are here: Home / Publikationen / Informatik / Theorie und Praxis der automatischen Stundenplanerstellung / Diplomarbeit / html / Wahl der Heuristik: Die Tabuliste als notwendiges Element

Wahl der Heuristik: Die Tabuliste als notwendiges Element

next up previous contents
Next: Tabusuche als allgemeines Optimierungsverfahren Up: Verfahren 1: Tabusuche Previous: Allgemeine Betrachtungen zum Lösungsraum

Wahl der Heuristik: Die Tabuliste als notwendiges Element

Wie obige Überlegungen und auch die in Abschnitt 4.6 zeigen, stellt die hohe Symmetrie der harten Nebenbedingung, die aber wegen der weichen Nebenbedingungen nicht durch Wahl einer anderen Kodierung beseitigt werden darf, ein wesentliches Problem dar. Die einzige gängige und auch im Timetabling-Bereich eingesetzte Metaheuristik, die in der Lage ist, dieses Problem zu bewältigen, ist die Tabusuche, da die Tabuliste so gestaltet werden kann, daß sie permutierte Wiederholungen genauso ausschließt wie vollständige. ST¨UBER[StŸ97] bezeichnet Tabusuche ebenfalls als das einzig geeignete Verfahren für größere Probleme, zieht aber direkte Heuristiken noch vor.
Die meisten Implementierungen der Tabusuche (vgl. [Dow97]) ignorieren diesen Symmetriezusammenhang dennoch und verwenden überwiegend direkte Kriterien, z.B. daß eine bestimmte Schulstunde zu einem bestimmten Zeitpunkt stattfindet.

In dieser Arbeit wurde bei der Konstruktion der Tabuliste dementsprechend ein anderes System verwandt: Sobald eine Schulstunde aus einer konkreten Zeitstunde entfernt wird, wird ein Paar, bestehend aus einem Verweis auf sie und eine zufällig gewählte andere Schulstunde, die in derselben Zeitstunde liegt, in die Tabuliste eingetragen. Die Tabubedingung ist nun, daß keine Stunden der beiden zugehörigen Kurse mehr zusammengelegt werden dürfen. Diese Orientierung nach Kursen und nicht nach Stunden fördert ein gleichartiges Verhalten zu einem Kurs gehöriger Stunden, was prinzipiell Blockungen (time-coherence
citecooper1993), d.h. das Parallellegen mehrerer Stunden zweier Kurse fördert, ohne es allerdings hart zu erzwingen.

Des weiteren wird in [KMSV94] gezeigt, daß mittels direkter Abstiegsverfahren für k-Sat Probleme eine Approximationsgüte von tex2html_wrap_inline6648 erreicht werden kann. Da bei geeigneter Wahl der Aspirationsfunktion (s. unten) die Tabusuche zu Beginn mit dieser einfachen Form der lokalen Suche identisch ist, könnte diese Schranke somit erzwungen werden, wenn man die Zielfunktion analog zu [KMSV94] modifiziert. Wenn man aber annimmt, daß die Differenzierungsgröße in tex2html_wrap_inline6650 wächst, erreicht man damit also bereits kein besseres Ergebnis als der triviale Algorithmus.


next up previous contents
Next: Tabusuche als allgemeines Optimierungsverfahren Up: Verfahren 1: Tabusuche Previous: Allgemeine Betrachtungen zum Lösungsraum

(c) Martin Loehnertz 1999