ISSN:
1436-6304
Keywords:
Cutting stock
;
integer solutions
;
heuristics
;
linear programming
;
column generation
;
numerical experiments
;
Zuschneideprobleme
;
Ganzzahligkeit
;
Heuristiken
;
Lineare Optimierung
;
Spaltengenerierung
;
Numerische Experimente
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Description / Table of Contents:
Zusammenfassung In der vorliegenden Arbeit betrachten wir das Problem der Bestimmung ganzzahliger Lösungen für das Standardproblem der eindimensionalen Zuschnittplanung. Insbesondere werden eine spezielle Klasse heuristischer Lösungsverfahren, die in der Literatur beschrieben sind, sowie einige naheliegende Varianten dieser Verfahren vorgestellt. Auf der Grundlage eines numerischen Experiments, bei dem 4.000 Probleme zufällig erzeugt und gelöst wurden, werden die Verfahren miteinander verglichen und im Hinblick auf die Kriterien „Lösungsqualität“ und „Rechenzeitbedarf“ beurteilt. Dabei zeigt sich nicht nur, daß zwei Verfahren deutlich besser als die übrigen einzustufen sind, sondern auch, daß mit ihrer Hilfe nahezu jede Problemausprägung des klassischen eindimensionalen Zuschneideproblems optimal gelöst werden kann.
Notes:
Abstract In this paper the problem of generating integer solutions to the standard one-dimensional cutting stock problem is treated. In particular, we study a specific class of heuristic approaches that have been proposed in the literature, and some straightforward variants. These methods are compared with respect to solution quality and computing time. Our evaluation is based on having solved 4,000 randomly generated test problems. Not only will it be shown that two methods are clearly superior to the others but also that they solve almost any instance of the standard one-dimensional cutting stock problem to an optimum.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01539705
