Mehr lesen
Der Verfasser setzt sich mit dem Standardproblem eindimensionalen Zuschneidens auseinander, und hier im besonderen mit Fragen der Vorteilhaftigkeit und der Beurteilung von Lösungsverfahren sowohl für den relaxierten als auch für den ganzzahligen Fall. Ausgehend von alternativen Möglichkeiten der Modellierung und der Ausnutzung der Äquivalenz zum bekannteren Bin Packing Problem werden mehrere Dekompositionsheuristiken vorgeschlagen, durch deren kombinierten Einsatz es dem Verfasser gelungen ist, für 11.959 der betrachteten 12.000 Probleminstanzen eine optimale, ganzzahlige Lösung zu bestimmen. Des Weiteren wird das spaltenerzeugende Verfahren von Gilmore und Gomory, das wesentlicher Bestandteil dieser Dekompositionsheuristiken ist, erstmalig in derartiger Ausführlichkeit analysiert und diskutiert.
Inhaltsverzeichnis
Inhaltsübersicht: Einführung.- Das Standardproblem: Problemformulierung und Typologisierung.- Eindimensionale Schnittmuster.- Modellierung als lineares Problem.- Verwandte Probleme.- Problemkomplexität.- Relaxierung der Ganzzahligkeitsbedingungen.- Integer Round Up (IRU) Eigenschaft.- Methodik der Analyse und Beurteilung von Lösungsverfahren: Definitorische Abgrenzung heuristischer und exakter Lösungsverfahren.- Grundsätzliche Überlegungen zum methodischen Vorgehen.- Beurteilungskriterien.- Auswahl und Generieren von Testproblemen.- Ansätze zur Lösung des relaxierten Standardproblems: Explizit vollständige Lösungsansätze.- Das spaltenerzeugende Verfahren als ein implizit vollständiger Lösungsansatz.- Vergleich des spaltenerzeugenden Verfahrens mit explizit vollständigen Lösungsansätzen.- Ansätze zur Lösung des ganzzahligen Standardproblems: Exakte Lösungsverfahren zur Bestimmung ganzzahliger Lösungen des Standardproblems.- FFD-Heuristik.- Motivation der Auswahl und Implementation weiterer heuristischer Verfahren.- Dekompositionsheuristiken.- Zusammenfasssung und Ausblick.
