Dissertationsvorhaben

Heuristische Lösungsverfahren für das ressourcenbeschränkte Projektdauerminimierungsproblem mit partiell-erneuerbaren Ressourcen und allgemeinen Zeitbeziehungen

Die Anzahl und Komplexität durchgeführter Projekte hat in der Wirtschaft in den letzten Jahren stark zugenommen, entsprechend gewinnen auch das Projektmanagement und insbesondere die Projektplanung immer stärker an Bedeutung. Eine aus der Literatur bekannte und bereits vielfach untersuchte Problemstellung aus der Projektplanung ist das sogenannte ressourcenbeschränkte Projektdauerminimierungsproblem mit allgemeinen Zeitbeziehungen (RCPSP\max). Ziel bei der Lösung dieses Problems ist die zeitliche Planung eines Projektes bzw. dessen Teilvorgänge, sodass die Projektdauer minimiert und gleichzeitig alle Ressourcen- und Zeitrestriktionen eingehalten werden. Bei Letzteren kann es sich beim RCPSP/max sowohl um zeitliche Mindest- als auch Höchstabstände, d.h. allgemeine Zeitbeziehungen zwischen den Vorgängen des Projektes handeln.

Üblicherweise werden im Rahmen des ressourcenbeschränkten Projektdauerminimierungsproblems erneuerbare Ressourcen betrachtet. Dieser Ressourcentyp stößt aber bei der Modellierung flexiblerer Ressourcenbeschränkungen an seine Grenzen. In diesem Falle kommen sogenannte partiell-erneuerbare Ressourcen zum Einsatz, die in der Literatur bislang wenig Beachtung gefunden haben. Sie stellen eine Verallgemeinerung erneuerbarer und nicht-erneuerbarer Ressourcen dar. Analog zu nicht-erneuerbaren Ressourcen besitzen sie eine Gesamtkapazität, die sich jedoch nicht auf den gesamten Planungshorizont, sondern lediglich auf eine beliebige Teilmenge der Perioden bezieht. Werden Vorgänge des betrachteten Projekts in diesen kapazitierten Perioden ausgeführt, so verbrauchen sie in dieser Zeit die Ressource entsprechend ihres gegebenen Ressourcenbedarfes. Mithilfe solcher partiell-erneuerbarer Ressourcen lassen sich beispielsweise flexible Arbeitszeitmodelle oder zeitlich flexible Wartungsarbeiten an Maschinen berücksichtigen.

Ziel des Dissertationsvorhabens ist die Entwicklung heuristischer Lösungsverfahren für die beschriebene Problemstellung des ressourcenbeschränkten Projektdauerminimierungsproblems mit partiell-erneuerbaren Ressourcen und allgemeinen Zeitbeziehungen (RCPSP\max-π ). Im Rahmen dessen soll zunächst eine Konstruktionsheuristik zur Generierung möglichst guter Startlösungen entworfen werden. Hierzu wird einerseits ein konstruktionsbasierter Ansatz, bei dem die Vorgänge des Projekts sukzessive, aber nicht zwingend so früh wie möglich zeit- und ressourcenzulässig eingeplant werden, und andererseits ein relaxationsbasierter Ansatz betrachtet und verglichen. Anschließend sollen lokale Suchverfahren bzw. populationsbasierte Verfahren entwickelt werden, um die konstruierten Startlösungen weiter zu verbessern. Darüber hinaus sollen die Problemstellung um erneuerbare Ressourcen zum RCPSP\max-π -ρ  erweitert und die entwickelten Verfahren entsprechend angepasst werden.

Erweiterungen und Lösungsverfahren für das Resource-Renting-Problem

Die Anzahl und Komplexität durchgeführter Projekte in Unternehmen hat in den letzten Jahren stark zugenommen, entsprechend gewinnt auch das Projektmanagement und insbesondere die Projektplanung immer stärker an Bedeutung. Im Rahmen des Projektmanagement wird ein Projekt als eine Menge von Vorgängen, sowie Zeitbeziehungen zwischen diesen, verstanden. Die Ausführung eines Vorgangs innerhalb eines Projekts erfordert Ressourcen während der gesamten Ausführungsdauer, wobei die kostenminimale Bereitstellung der notwendigen Ressourcen, eine Zielgröße der Projektplanung ist. Eine häufig betrachtete Art von Ressourcen sind erneuerbare Ressourcen die bei Benutzung nicht „verbraucht“ werden, sondern in der nachfolgenden Planungsperiode wieder zur Verfügung stehen, typische Beispiele für diesen Ressourcentyp stellen Maschinen oder Mitarbeiter dar.

Beim Resource-Renting-Problem (RRP) wird von der Annahme ausgegangen, dass die für ein Projekt erforderlichen Ressourcen nicht angeschafft werden oder bereits vorhanden sind, sondern zeitweise angemietet werden müssen. Insbesondere bei der Planung von Bauprojekten spielen gemietete Ressourcen eine wichtige Rolle. Schweres Gerät wie zum Beispiel Bagger, Kräne oder Bulldozer werden häufig explizit für die zeitweise Nutzung auf einer Baustelle gemietet.

Bei der Anmietung von Ressourcen fallen zwei Arten von Kosten an, mengenabhängige Bereitstellungskosten und zeitabhängige Mietkosten pro Mengen- und Zeiteinheit. Letzte entsprechen den Mietkosten einer Maschine pro Tag, die erste Art von Kosten fällt durch die Anmietung einer Ressourceneinheit an. Dies können z.B. Transportkosten sein, da ein Bagger nicht selbstständig zu seinem Einsatzort fahren kann sondern ein teurer Transport auf einem geeigneten Lkw notwendig ist.

Das RRP setzt sich aus zwei Teilproblemen zusammen, einem Scheduling-Problem, bei dem es gilt, einen zeitzulässigen Schedule für ein Projekt zu generieren und dem Mietpolitikproblem, dass dazu dient, die für einen Schedule benötigten Ressourcen möglichst günstig anzumieten. Dabei gilt es zu entscheiden, wann Ressourcen bereitgestellt werden und wann sie wieder abgegeben werden sollen. Eine Schwierigkeit dabei besteht darin, dass es in bestimmten Situationen günstig sein kann Ressourcen zu behalten, obwohl für diese zeitweise kein Bedarf besteht, da die erneute Bereitstellung teurer wäre als das Bezahlen der Mietkosten für den ungenutzten Zeitraum.

Im Rahmen des Dissertationsvorhabens sollen verschiedene MILP Formulierungen für das Resource-Renting-Problem entwickelt und untersucht werden. Grundlage dafür bieten aus der Literatur zum Projektmanagement bekannte Formulierungen für das ressourcenbeschränkte Projektdauerminimierungsproblem und das Ressourcennivellierungsproblem. Weiter liegt der Fokus auf der Entwicklung eines heuristischen Lösungsverfahrens, bei dem das RRP schrittweise in kleinere Subproblem zerlegt und gelöst wird (Fix&Optimize). Darüber hinaus soll die Problemstellung um substituierbare Ressourcen zum RRP\sub erweitert und die entwickelten Verfahren entsprechend angepasst werden.

Transportoptimierung in Leergut-Behälternetzwerken der Volkswagen AG

Die Volkswagen Konzernlogistik GmbH & Co. OHG verantwortet die Planung, Steuerung und Überwachung der Transportnetzwerke im Konzernnetzwerk der Volkswagen AG. Hierzu gehört der Transport fremdgefertigter Bauteile von den Lieferanten zu den konzernweiten Produktionswerken, der aufgrund der Tatsache, dass der Transport einzelner, loser Bauteile weder aus wirtschaftlicher noch aus logistischer Sicht sinnvoll ist, nahezu ausschließlich in Mehrweg-Ladungsträgern erfolgt. Die befüllten Ladungsträger werden nach Ankunft im Werk bedarfsgerecht an der Produktionslinie angestellt oder just-in-time an das Produktionsband transportiert, bevor die Teile für den Verbau im Fahrzeug entnommen werden. Damit der Ladungsträgerkreislauf geschlossen wird und auch zukünftige Bauteillieferungen in den Mehrweg-Ladungsträgern erfolgen können, ist ein Rücktransport des Leergutes von den Werken zu den Lieferanten zwingend erforderlich. Diese nicht direkt wertschöpfenden Transporte sind kostenintensiv und verursachen hohe CO2-Emissionen. Nicht zuletzt, da sich Volkswagen im Rahmen der Konzernstrategie „TOGETHER 2025⁺“ sowie der daraus abgeleiteten goTOzero-Strategie verpflichtet hat, bis 2025 im Vergleich zum Jahr 2018 30% der CO2-Emissionen einzusparen und im Jahr 2050 bilanziell CO2-neutral zu sein, besteht ein hohes Interesse an neuen Optimierungsansätzen.

Ziel dieses Dissertationsvorhabens ist es, die Leerguttransporte von Werken zu Lieferanten im Hinblick auf heutige und zukünftige Anforderungen möglichst effizient zu planen. In enger Zusammenarbeit mit der Volkswagen Konzernlogistik sollen neue Konzepte für die Ladungsträgerallokation im Transportnetzwerk entwickelt und anhand einer experimentellen Performanceanalyse auf Basis realitätsnaher Testinstanzen miteinander verglichen werden. Die zentrale Herausforderung besteht dabei zum einen in der schieren Größe des Optimierungsproblems und zum anderen in der Komplexität der Prozessstrukturen. So gilt es bei dem zu lösenden Transportproblem neben rund 50 Werken, mehr als 1.000 Lieferanten sowie circa 50 Universalladungsträgertypen auch Sendungslaufzeiten, degressive Transportkosten und verschiedene Verkehrsträger zu berücksichtigen. Aufgrund der Zugehörigkeit des zugrundeliegenden Dynamic Multicommodity Fixed Charge Transport Problems zur Klasse der NP-schweren Probleme in Kombination mit der Größe der zu lösenden Instanzen stoßen Standardsolver an ihre Grenzen. Daher soll das Hauptaugenmerk im Rahmen des Forschungsvorhabens auf der Entwicklung heuristischer Lösungsansätze liegen. In einem ersten Schritt soll ein realitätsnahes Instanzset für die Problemstellung des Leerguttransportproblems generiert werden. Im nächsten Schritt sollen für die vorliegende Problemstruktur bestehende Netzwerkansätze aufgegriffen und neue Ansätze konzeptioniert werden, bevor Lösungsverfahren für die Erzeugung möglichst guter, zulässiger Lösungen entwickelt werden. Im Fokus steht hierbei die Entwicklung von für die Problemstellung spezifischen Konstruktionsheuristiken. Anschließend sollen die so erzeugten Lösungen durch den Einsatz geeigneter Verbesserungsverfahren weiter verbessert werden.