Ein zeitbasiertes Schedule-Generierungsschema für das Projektplanungsproblem mit Lagerressourcen und verallgemeinerten Vorrangbeziehungen
Bearbeiter | Mario Christian Sillus |
Forschungsschwerpunkt | Integrierte Routing- und Scheduling-Probleme |
Zusammenfassung
Lagerressourcen stellen Materialvorräte oder liquide Mittel dar, die beim Eintreten bestimmter Ereignisse während der Ausführung eines Projekts verbraucht und aufgefüllt werden. Sowohl erneuerbare als auch nicht-erneuerbare Ressourcen sind Spezialfälle von Lagerressourcen. Projektplanung unter Berücksichtigung von Lagerressourcen-Beschränkungen und verallgemeinerten Vorrangbeziehungen besteht darin, die Projektereignisse so zu ordnen, dass die Bestände der Lagerressourcen innerhalb vorgegebener Grenzen bleiben und vorgegebene minimale und maximale Zeitabstände zwischen den Ereignissen eingehalten werden. Ein solches Problem ergibt sich z. B. in der Produktionsplanung, wenn Materialverfügbarkeits- oder Lagerkapazitätsbeschränkungen für Zwischenprodukte eingehalten werden müssen, oder in Großprojekten, bei denen Zu- und Abflüsse liquider Mittel koordiniert werden müssen, um Liquiditätsengpässe zu vermeiden. Mit Lagerressourcen ist bereits das Lösbarkeitsproblem NP-schwer.
In der Literatur wurden verschiedene Enumerationsschemata für Projektplanungsprobleme mit Lagerressourcen und regulären Zielfunktionen wie der Projektdauerminimierung entwickelt. Wir entwickeln ein neues zeitbasiertes Schedule-Generierungsschema, das als Baustein für metaheuristische Verfahren zur Schedule-Verbesserung dienen soll. Das Verfahren dekodiert eine Ereignisliste in einen zulässigen Zeitplan, indem es Ressourcenkonflikte iterativ auflöst. So eine Bestandsunter- oder -überschreitung wird schrittweise durch Erhöhen oder Verringern von Untergrenzen für die Eintrittszeiten der entsprechenden Ereignisse abgebaut. Das Generierungsschema ist vollständig und garantiert, versehen mit etwas Zufall sowie unbegrenzter Rechenzeit, eine zulässige Lösung in einem einzigen Durchlauf.