OpenScheduling

OpenScheduling

Ablaufplanung spielt in vielen Unternehmen eine wichtige Rolle, so z.B. bei der Planung der optimalen Auslastung von Maschinen, bei der Routenplanung von Warentransporten oder bei der Erstellung von Schichtplänen. Ziel ist immer, bestimmte Optimierungsziele unter Einhaltung zu beachtender Nebenbedingungen möglichst gut zu erreichen. Alle Ablaufplanungsprobleme basieren auf einem gemeinsamen theoretischen Ansatz: Es gibt Prozessoren (z.B. Maschinen) und Jobs (z.B. Bearbeitung von Werkstücken), die auf den Prozessoren ausgeführt werden. Bei einer optimalen Ablaufplanung (Scheduling) sollen dann beispielsweise alle Jobs so auf die Prozessoren verteilt werden, dass diese gleichmäßig ausgelastet sind und alle Jobs in einer möglichst kurzen Zeit abgearbeitet werden. Im aktuellen Forschungsprojekt OpenScheduling entwickeln Florian Blasius und Konstantin Klein (beides Studenten der Medieninformatik) unter Betreuung von Prof. Dr. Oliver Braun eine Software, die es ermöglicht, die verschiedenen theoretischen Modelle zur Ablaufplanung visuell darzustellen und zu untersuchen.

„Scheduling ist spannend und macht Spaß“, so Florian Blasius, der seine Bachelorthesis und seine Master-Projektarbeiten im Rahmen des Forschungsprojekts absolviert hat. „Das Projekt ist interdisziplinär und verknüpft die Medieninformatik mit betriebswirtschaftlichen Anwendungen. Die Optimierung von Abläufen in Unternehmen durch die richtige Scheduling-Strategie spart Zeit und Geld und ist nachhaltig. Am meisten begeistert mich die Entwicklungsarbeit, da sie sehr viel Spaß macht. Die Visualisierung ist aus Anwendersicht sehr anschaulich, denn die komplexen theoretischen Modelle lassen sich dadurch viel leichter verstehen.“

Bei der Entwicklung der Software wird großer Wert auf Flexibilität gelegt und die implementierten Ablaufplanungsmodelle sollen möglichst einfach erweiterbar sein. So bietet OpenScheduling beispielsweise die Möglichkeit, die Modelle individuell zu konfigurieren und hierzu die Anzahl der Prozessoren und Jobs auszuwählen, die Dauer der Jobs zu variieren sowie die Job-Unterbrechungen einzustellen. In der Lehre soll die Software zur Visualisierung der Funktionsweise von Schedulingalgorithmen eingesetzt werden. In der Forschung wird die Software bereits zu Analysezwecken neuer Schedulingalgorithmen verwendet. Prof. Braun hat kürzlich gemeinsam mit den renommierten Wissenschaftlern Ron Graham und Fan Chung von der University of California in San Diego die Schedulingtheorie um die praktisch relevante Nebenbedingung erweitert, dass ein Prozessor zur Bearbeitung von Aufträgen jeweils eine Ressource benötigt, welche nach Fertigstellung des Auftrages erneuert werden muss. Der Prozessor könnte eine Maschine sein und die Ressource ein Behälter: Nach Beendigung eines Arbeitsschrittes muss der Behälter erst gesäubert werden, bevor der nächste Auftrag gestartet werden kann (und dies benötigt Zeit). Auf ähnliche Art und Weise lassen sich der Turnaround von Verkehrsflugzeugen, die Durchführung von Krankentransporten, das Energiemanagement in einem Unternehmen und unzählige weitere praktisch relevante Fragestellungen modellieren.

Braun, Chung und Graham zeigen, dass dieses Problem NP-schwer ist und damit zu den schwierigsten kombinatorischen Optimierungsproblemen gehört. Die Autoren führen eine Worst-case-Analyse durch und zeigen, dass bei B=2 Ressourcen ein beliebiger Ablaufplan niemals um mehr als 4/3 länger als ein optimaler Ablaufplan sein kann und dass bei B>2 Ressourcen der entsprechende Faktor 2-1/(B-1) beträgt (plus jeweils eine kleine Konstante). Die erzielten Forschungsergebnisse wurden im August 2013 im Journal of Scheduling veröffentlicht (Single processor scheduling with time restrictions, Journal of Scheduling, 2013, DOI 10.1007/s10951-013-0342-0). Das Journal of Scheduling zählt zu den herausragenden internationalen wissenschaftlichen Zeitschriften und ist im Ranking des Verbands der Hochschullehrer für Betriebswirtschaft (VHB) mit A gerankt. Graham und Chung gehören zu den renommiertesten und mit zahlreichen Preisen geehrten mathematischen Persönlichkeiten der heutigen Zeit. Nebeneffekt der Veröffentlichung: Weil Graham und Chung Co-Autoren von Paul Erdös, einem der bedeutendsten Mathematiker des 20. Jahrhunderts, sind und somit die Erdös-Nummer 1 tragen, erhält Braun als Co-Autor der beiden nun die Erdös-Nummer 2.

Prof. Braun: „Während meiner Forschungsaufenthalte an der UC San Diego haben wir intensiv an der Lösung des Problems gearbeitet. Ron Graham war Chef-Wissenschaftler bei den Bell Labs von AT&T, hat Projekte für die NASA durchgeführt, war Gastwissenschaftler in Princeton, Stanford, an der UC Davis und UC Los Angeles und ist an der UC San Diego Inhaber des Irwin and Joan Jacobs Chair of Computer Science and Engineering Department und Chief Scientist am California Institute of Telecommunication and Information Technology. Er hat mehr als 300 Paper und 5 Bücher veröffentlicht, ist Träger des Steele-Preises für sein Lebenswerk und hat zahlreiche mathematische Gebiete entweder begründet oder entscheidend vorangetrieben."

Prof. Braun weiter: „Ich bin sehr froh und dankbar, mit solch herausragenden Wissenschaftlern und Persönlichkeiten zusammenarbeiten zu dürfen wie Ron und Fan Chung Graham. Von Ron Graham konnte ich während der ganzen Zeit sehr viel lernen – fachlich wie menschlich. Trotz seiner hohen Reputation ist er immer bereit zuzuhören, andere Ideen zu verstehen und seine eigenen Argumente zu hinterfragen. Er ist stets auf der Suche nach neuen Herausforderungen und ruht nicht eher, bis ein Problem gelöst ist. Ich habe eine weitere Einladung für die nächsten drei Jahre vorliegen und bin froh darüber, dass ich mein Büro an der UCSD während der Forschungsaufenthalte weiter nutzen kann. Wir arbeiten bereits an einem neuen Problem und da wird uns die Software OpenScheduling hoffentlich gute Dienste leisten. Mein Wunsch ist es, weitere Studierende für das Thema Scheduling zu interessieren. Unsere Studierenden am Umwelt-Campus sind also herzlich eingeladen, im Projekt mitzuarbeiten."

In diesem Zusammenhang werden Projekt- und Abschlussarbeiten sowohl für Studierende der Umwelt- und Betriebswirtschaft als auch für Studierende der Informatik und verwandter Studiengänge vergeben. Interessenten können sich direkt an Prof. Braun wenden. Weitere Informationen: www.umwelt-campus.de/ucb/index.php