Diese Arbeit befasst sich mit der mathematischen Modellierung und heuristischen Lösung komplexer Scheduling Probleme im Kontext automatisierter IT Umgebungen. In solchen Umgebungen werden oft hunderttausende automatisierte Jobs in einem verteilten Netzwerk von heterogenen Maschinen ausgeführt. Da Verzögerungen in der Ausführung beziehungsweise der Beendigung dieser Jobs, aufgrund von Service Level Agreements, oft mit hohen Kosten verbunden sind, ist eine Optimierung der Abläufe eine Aufgabe mit von grundlegender Bedeutung.<br />Um das Problem mit optimierungstheoretischen Mitteln behandeln zu können muss eine geeignete Formalisierung gefunden werden. In einem ersten Schritt werden einige Modelle auf ihre Adäquatheit hin evaluiert. Aufgrund ihrer mangelnden Flexibilität wird anstelle von klassischen Maschinen-Scheduling Modellen den extensiveren Projekt-Scheduling Modellen der Vorzug gegeben.<br />Die endgültige Formulierung schließlich erfolgt als multimodales ressourcenbeschränktes Projekt-Scheduling Problem mit verallgemeinerten Vorgängerbeziehungen (MRCPSP/max oder MRCPSP-GPR). Dieses trägt nicht nur der Tatsache Rechnung, dass im Gegensatz zu Maschinenumgebungen in IT-Umgebungen das Konzept der Ressource ein erheblich flexiblerer ist, sondern erlaubt auch eine Erweiterung der Abhängigkeiten zwischen Arbeitsschritten. Während diese in Maschinenumgebungen meist von kausalen Abhängigkeiten dominiert werden treten in IT-Umgebungen flexiblere Zeitbedingungen auf.<br />All diese Flexibilität in der Modellierung führt typischerweise zu einer höheren Komplexität der Modelle. Es wird gezeigt, dass sich das MRCPSP/max schon bei relativ geringer Instanzgröße nicht mehr praktikabel mit exakten Methoden lösen lässt. Daher wurde im Zuge dieser Arbeit eine Software-Bibliothek erstellt, die hochqualitative Lösungen in annehmbaren Zeitrahmen mit heuristischen Optimierungsverfahren liefern kann. Der Literatur zu dem Thema folgend dient hierbei ein genetischer Algorithmus als Metaheuristik. Die Arbeit gibt einen Überblick zu den Details bereits vorhandenen Implementierungen und kombiniert die Ansätze zu einer flexiblen Software-Lösung. Daneben stellen wir auch neue evolutionäre Operatoren vor, die sich bei umfassenden Tests mit Benchmark-Instanzen bewährt haben.<br />
de
This work is concerned with the task of mathematical modeling and the heuristical resolution of complex scheduling problems in the context of automated IT environments.<br />Today's corporate IT systems often contain several hundred thousand automated jobs that have to be executed in the heterogeneous network on a daily basis. Because delays of the execution or finalization of these jobs is often coupled with high costs by using legal service level agreements (SLAs), an optimization of the processes in the system is of crucial importance.<br />In order to tackle a practical scheduling problem with the means of scientific optimization theory it is necessary to find a formalization in mathematical terms. This subproblem is considered in the first part of this work, where a number of models is examined for their adequacy. Because of their lack of flexibility, the classical machine scheduling models are discarded in favor of the broader project scheduling models. As final formalization the very general multi-mode resourceconstrained project scheduling problem with generalized precedence relations (MRCPSP/max or MRCPSP-GPR) is chosen. This choice is justified by the fact that this model allows the modeling of resources in a more adequate way to capture the broader concept of a resource in IT environments. Furthermore it enables the formalization of complex timing constraints in a natural way.<br />This increased flexibility comes with a tradeoff in the form of increased complexity. It is shown that the resolution of MRCPSP/max instances with mixed integer programming methods is not practical, even for small instances. Therefore in the course of this work a software library has been implemented with the goal to provide solutions with high quality in a practical time frame by using heuristic optimization methods. Following the proposals in the scientific literature genetic algorithms serve as the underlying metaheuristic. This work provides an overview on the details of available implementations from the literature and presents a combination of several approaches in the form of a flexible software library. Furthermore we present new evolutionary operators which are proven to perform well in extensive benchmark tests.
