Heuristische Lösungsverfahren für das Ressourcentransferprobleme

Bearbeiter Mario Christian Sillus
Forschungsschwerpunkt Integrierte Routing- und Scheduling-Probleme
Illustration: 123rf/sentavio

Zusammenfassung

In der Literatur existiert eine Vielzahl von Arbeiten, die sich mit dem Capacitated Vehicle Routing Problem (CVRP) oder dem Resource-Constrained Project Scheduling Problem (RCPSP) und deren Varianten und Verallgemeinerungen beschäftigen. Vergleichsweise wenige Veröffentlichungen behandeln Modelle, die in der Lage sind, beide Typen von Ablaufplanungsproblemen zu integrieren. Mit dem Resource Transfer Problem (RTP) lassen sich solche allgemeinen Scheduling- und Routing-Probleme modellieren und lösen. Gegenstand der Planung in einem RTP sind Ereignisse, erneuerbare Ressourcen, deren Einheiten den Ereignissen alloziert und zwischen den Ereignissen transferiert werden, und Lagerressourcen, deren Einheiten beim Eintreten der Ereignisse verbraucht bzw. erzeugt werden. Jedes Ereignis kann in einem von mehreren alternativen Modi eintreten. Das RTP besteht darin, den Ereignissen ihre Eintrittszeitpunkte, Eintrittsmodi und Einheiten erneuerbarer Ressourcen so zuzuweisen, dass vorgeschriebene Zeitabstände zwischen den Ereignissen und die Dauern für den Transfer von Ressourceneinheiten beachtet werden, die Bestände der kumulativen Ressourcen innerhalb vorgegebener Intervalle verlaufen und eine gegebene Zielfunktion in Eintrittszeitpunkten und -modi optimiert wird. Darüber hinaus können für Paare von Ereignissen Inklusions- und Inkompatibilitätsbedingungen für die Mengen zugewiesener Ressourceneinheiten formuliert werden. Über Paare aus Start- und Endereignissen lassen sich auf diese Weise sowohl Transformationsprozesse mit ressourcen- und reihenfolgeabhängigen Umrüstzeiten als auch zeitliche und räumliche Transferprozesse von Ressourcen repräsentieren.

Ein bestehender Branch-and-Bound-Algorithmus von Weiss (2018) eignet sich zur exakten Lösung kleiner Probleminstanzen des RTP. Ziel des Promotionsvorhabens ist die Entwicklung heuristischer Verfahren, die auch für praxisrelevante Problemgrößen in vertretbarer Rechenzeit gute Pläne berechnen können. Hierfür soll ein allgemeines Schedule-Generierungsschema entwickelt werden, das den Ereignissen iterativ ihre Eintrittszeitpunkte, Eintrittsmodi und Ressourceneinheiten zuweist. Dabei lassen sich bei Vorhandensein zeitlicher Höchstabstände oder kumulativer Ressourcen typischerweise Deadlock-Situationen nicht vermeiden, in denen in einen Teilplan keine weiteren Ereignisse mehr zulässig eingeplant werden können. Zur Auflösung dieser Konflikte sollen verschiedene Techniken angepasst, entwickelt und miteinander kombiniert werden. Zu diesen gehört das Unscheduling, bei dem bereits eingeplante Ereignisse wieder ausgeplant und zeitlich verzögert werden, die Zulassung temporärer Unzulässigkeiten, die in den nachfolgenden Iterationen zielgerichtet abgebaut werden, und ein Zwei-Phasen-Ansatz, bei dem in der ersten Phase die Einhaltung der unteren Bestandsgrenzen und in der zweiten Phase die Einhaltung der oberen Bestandsgrenzen garantiert wird. Das entwickelte Schedule-Generierungsschema bildet die Grundlage für metaheuristische Verfahren, deren Nachbarschaftsstrukturen z. B. auf der Menge der Einplanungsreihenfolgen der Ereignisse definiert werden können.

 

 

Kontakt  Sitemap  Data Privacy  Imprint
© TU Clausthal 2019