Algorithmen im Visier
LiSA - eine Programmbibliothek für Schedulingprobleme
Als Exponat auf der weltgrößten Computermesse CeBIT 99 präsentierten Peer Willenius und Martin Harborth aus dem Institut für Algebra und Geometrie der Fakultät für Mathematik das Softwareprodukt LiSA, eine Programmbibliothek für Schedulingprobleme. Diese umfangreiche Programmbibliothek wurde unter der wissenschaftlichen Leitung von Prof. Dr. Heidemarie Bräsel in der Arbeitsgruppe Schedulingtheorie erarbeitet. Das Land Sachsen-Anhalt fördert dazu ein Projekt mit dem Titel Lateinische Rechtecke in der Schedulingtheorie im Rahmen des Forschungsschwerpunktes Beitrag zur rechnergestützten Steuerung logistischer Produktionsprobleme.
Nicht nur Theorie
In einem Schedulingproblem sollen verschiedene Aufträge auf einer Menge von Maschinen unter gegebenen Nebenbedingungen bearbeitet werden, wobei eine Zielfunktion zu minimieren ist. Eine Lösung eines solchen Problems kann durch eine zulässige Kombination von technologischen (Reihenfolge der Maschinen für jeden Auftrag) und organisatorischen Reihenfolgen (Reihenfolge der Aufträge auf jeder Maschine) beschrieben werden.
Schedulingtheorie
In der Schedulingtheorie geht es darum, eine bestimmte Menge von Aufträgen über eine Menge (Anzahl) von Maschinen so zu steuern, daß technologische Bedingungen für die Auftragsbearbeitung erfüllt bleiben und zum Beispiel die Gesamtbearbeitungszeit für alle Aufträge als Zielgröße optimiert wird. Dazu werden geeignete mathematische Modelle aufgestellt, die auf Rechnern realisiert werden.
Aufgrund des Praxisbezugs der Problemstellung beinhaltet die Forschung neben theoretischen Untersuchungen auch die rechentechnische Umsetzung exakter und näherungsweiser Lösungsverfahren. Um die Implementation forschungsspezifischer Testprogramme zu diesem Thema zu vereinfachen und zu beschleunigen, entwickelte unsere Arbeitsgruppe LiSA (Library of Scheduling Algorithms). Diese Software enthält sowohl eine Bibliothek schedulingspezifischer allgemeiner Klassen, wie Pläne für verschiedene Schedulingprobleme, Metaheuristiken und angepaßte Speicherstrukturen, als auch eine nutzerfreundliche graphische Oberfläche, unter der die entwickelten Algorithmen ausgetestet werden können. Neue Algorithmen lassen sich über eine definierte Schnittstelle sowohl in das Hauptprogramm als auch in Form von eigenständigen Programmen einbinden.
Einsatz in der Lehre
Neben dem Einsatz zu Forschungszwecken soll LiSA auch in der Lehre Anwendung finden. Die Studenten können damit sowohl verschiedene vorhandene Lösungsverfahren für eine Problematik vergleichen und auf Anwendbarkeit sowie Güte testen als auch mit Hilfe der bereits implementierten Programmbausteine neue Verfahren zusammensetzen.
Das Programm selbst ist in der objektorientierten Sprache C++ geschrieben, während die Oberfläche die Skriptsprache TCL/TK benutzt, so daß eine einfache Erweiterbarkeit gegeben ist. Es ist bisher auf Workstations unter HP-UX sowie auf PC's unter LINUX verfügbar. Für den weiteren Einsatz ist auch eine WindowsNT-Version geplant.