[Back]

M. Sturm:
"Solving multimodal resource constrained project scheduling problems";
Supervisor: G. Raidl; Institut für Computergraphik und Algorithmen, 2012; final examination: 2012-09.

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. 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.
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.
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.

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.
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.
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.
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.

http://publik.tuwien.ac.at/files/PubDat_211655.pdf