Heinrici, Albrecht

Leistungsvergleich von Nachbarschaftssuchverfahren

Reihe: Akademische Abhandlung zu den Wirtschaftswissenschaften
ISBN: 3-930324-76-8
1996
Preis: 46,90 €
210 Seiten

Abstract

Im Bereich des Operations Research werden seit vielen Jahren unterschiedliche kombinatorische Optimierungsprobleme behandelt.
Zu Ihrer Lösung wurden allgemeine und spezialisierte, exakte und heuristische Lösungsverfahren vorgeschlagen und überprüft. In den letzten 15 Jahren zog dabei eine neue Klasse von heuristischen Verfahren, die Nachbarschaftssuchverfahren (NBSV), zunehmend Aufmerksamkeit auf sich. Zu dieser Verfahrensklasse gehören Tabu Search, Simulated Annealing, das Sintflut-Verfahren und Record-to-Record-Travel. Diese Lösungsverfahren wurden bisher hauptsächlich einzeln untersucht, so daß kaum deutlich wurde, welche der Verfahren besonders effizient sind.
>Die vorliegende Titel bietet einen fundierten Vergleich der NBSV an einem bekannten betrieblichen Problem. In den Vergleich wurden auch mehrere bekannte erfolgreiche Heuristiken einbezogen, so daß nicht nur die NBSV miteinander verglichen werden konnten, sondern auch ihre Qualität mit der der anderen Heuristiken verglichen werden konnte.
Die Darstellung der NBSV erfolgt zunächst allgemein in Struktogrammform. Die einzelnen Verfahren werden dann abgeleitet und ebenfalls in Struktogrammform vorgestellt. Bei allen einzelnen Verfahren werden die vom Anwender zu treffenden Entwurfsentscheidungen hervorgehoben.
Das Bandabgleichproblem wird nach einer Einordnung in die Produktionsplanung ausführlich vorgestellt. Die einfachste Form des Modells sowie eine große Zahl von Erweiterungen werden besprochen, wobei auch auf existierende Lösungsverfahren eingegangen wird. In der vorliegenden Arbeit werden insgesamt fünf neue Verfahren vorgestellt und implementiert. Das erste ist ein exaktes Verfahren, welches auf dem A*-Verfahren basiert. Die weiteren Verfahren sind die erwähnten NBSV, die mit umfangreichen Testläufen kalibriert werden. Es werden unterschiedliche Startlösungen und Nachbarschaften untersucht. Die Parameterentscheidungen werden anhand von Berechnungen getroffen, die für ein Beispielset von Probleminstanzen ausgeführt werden. Jeder einzelne Parameter wird auf den Wert gesetzt, der das beste Gesamt- ergebnis im Set brachte. Die Datenstrukturen und die Modularisierung des entwickelten Programmsystems werden so gestaltet, daß die übergreifende Verwendbarkeit von Prozeduren und Datentypen eine gute Vergleichbarkeit der Rechenzeiten ermöglicht. Zusätzlich wurden zwei aus der Literatur bekannte spezialisierte Heuristiken implementiert.
Der endgültige Vergleich der Lösungsverfahren wird anhand zweier Problemsets vorgenommen. Das erste Set ist aus der Literatur bekannt und wurde bereits mehrfach zur Evaluierung von Lösungsverfahren zum Bandabgleichproblem verwandt. Es enthält Probleminstanzen des SALBP ohne zusätzliche Restriktionen mit einer Größe von bis zu 111 Arbeitsvorgängen. Das zweite Set wurde vom Autor zusammengestellt und enthält realistischere Instanzen. Sie sind mit zusätzlichen Restriktionen ausgestattet und bis zu 200 Arbeitsvorgängen groß.
Alle Instanzen beider Problemsets wurden mit den Heuristiken unter Vorgabe einer Rechenzeitschranke von zehn Sekunden gelöst. Als Ergebnis dieser Berechnungen ließ sich Tabu Search als leistungsfähigstes Verfahren feststellen. Es übertrifft in der Qualität der gefundenen Ergebnisse sowohl die anderen NBSV als auch die Standard- heuristiken. Record-to-Record-Travel erzielt ähnlich gute Ergebnisse und besitzt für einen Anwender den Vorzug, daß es wesentlich einfacher zu kalibrieren ist. Durch den Vergleich mit der Hoffmann-Heuristik erwies sich das vorgestellte Tabu-Search-Verfahren als beste Heuristik für das Bandabgleichproblem.

Name      
Adresse   
          
          
Stadt     
Land      
Telefon   
Email     
Bemerkung