In der Diplomarbeit wurde ein heuristisches Planungsverfahren zur Ressourcenbelegung modelliert, implementiert und getestet. Es basiert auf einem Branch-and-Bound Algorithmus und wird durch einen Beam-Search Mechanismus heuristisch erweitert. Die Problembearbeitung findet parallel auf mehreren Rechnern eines Grids statt. Das Verfahren ist vielseitig einsetzbar und lässt sich sowohl auf akademische als auch auf praxisrelevante Probleme anwenden. Bei dem Entwurf wurde darauf geachtet, dass Erweiterungen und Anpassungen an zukünftige Bedürfnisse möglich sind. Die Simulationsergebnisse demonstrieren die Praxistauglichkeit des Systems.

Eine effiziente Einschränkung des Suchraums erhält man durch den Einsatz des Branch-and-Bound mit Erweiterung durch den Beam-Search Mechanismus. Modelliert man den Suchraum als Entscheidungsbaum, so repräsentieren Verzweigungen Einplanungen von Operationen auf Kapazitäten. Durch das Branch-and-Bound werden Äste des Baums abgeschnitten, wenn diese mit Sicherheit keine Pläne mehr enthalten, deren Bewertungen besser sind, als die eines bereits bekannten Plans. Der kombinatorischen Explosion der Einplanungsmöglichkeiten ist damit alleine nicht Einhalt geboten. Deshalb wird die Suche zusätzlich durch einen Beam-Search Mechanismus auf Bereiche beschränkt, in denen gute Lösungen vermutet werden. Durch eine prioritätsregelbasierte Vorschau werden globale Bewertungen für einzelne Verzweigungsentscheidungen gefunden. Teilpläne mit besten globalen Bewertungen werden untersucht. Durch die Vorschau werden zulässige Pläne in kurzer Zeit gefunden.

Die Problembearbeitung erfolgt parallel auf mehreren Rechnern eines Grids. Investitionen in neue Hardware werden durch die Erschließung ungenutzter Rechenkapazitäten von Arbeitsplatzrechnern vermieden. Die Rechner sind durch ein lokales Netzwerk verbunden, dessen Nachteile eine kleine Bandbreite und lange Verzögerungszeiten sind. Um den Effizienzverlust durch Kommunikationszeiten gegenüber einem Einzelplatzrechner gering zu halten, wird ein grob granulierter
Lastverteilungsansatz verwendet.

Das System kann als Planungskomponente für das Fertigungsleitsystem FLS-TEX verwendet werden. Planungsprobleme werden mit Hilfe eines Konverters in eine eigene kompakte Darstellung übertragen. Diese ist auf die speziellen Bedürfnisse des Systems zugeschnitten. Planungsergebnisse werden unmittelbar nach ihrem Eintreffen auf die FLS-TEX Datenstruktur übertragen. Neben den FLS-TEX Planaufträgen können andere Planungsprobleme bearbeitet werden. Es wurden zwei weitere Konverter implementiert, um textuelle Problemdarstellungen aus der Literatur einzulesen.

In der Simulation werden für akademische Testinstanzen gute Pläne innerhalb kurzer Rechenzeiten gefunden. Einige Testfälle werden exakt gelöst. Im Schnitt weichen die gefundenen Pläne nur 5% von der optimalen Lösung ab. Für die praktischen Probleme aus FLS-TEX wird innerhalb weniger Sekunden eine Lösung erzeugt, deren Güte im weiteren Programmlauf nur noch geringfügig verbessert wird. Für eine Testinstanz mit 1000 Planaufträgen (mit durchschnittlich je 4 Auftragsschritten) vergehen bis zum Eintreffen der Eröffnungslösung weniger als 30 Sekunden. Der gesamte Programmlauf ist in etwa drei Stunden beendet. Die hohe Güte der Eröffnungslösung wird durch eine prioritätsregelbasierte Vorschau erzielt, die für die Struktur der FLS-TEX Probleme kaum noch Verbesserungspotential lässt.