ISSN:
1436-6304
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Description / Table of Contents:
Zusammenfassung Zur Bestimmung der optimalen Lösung von 1- und 1 1/2-dimensionalen Verschnittproblemen werden zwei verschiedene LP-Modellformulierungen vorgeschlagen. Dies sind zum einen das vollständige Schnittmustermodell, das mit dem bekannten spaltenerzeugenden Verfahren von Gilmore und Gomory [9, 10] gelöst werden kann und zum anderen das Einzelschnittmodell von Rao [17] und Dyckhoff [2, 4], zu dessen Lösung Standardsoftware der Linearen Programmierung einsetzbar ist. Für die beiden Modelle und Lösungsverfahren werden bisher nicht beachtete Gemeinsamkeiten und Unterschiede herausgearbeitet, die Aufschluß über mögliche Anwendungsgebiete und die Vorzüge des jeweiligen Ansatzes erlauben. Es werden sowohl das Standardproblem der Verschnittoptimierung als auch praxisnahe Erweiterungen — wie verschiedene, beschränkt verfügbare Standardlängen und die Bewertung von Restlängen — untersucht. Zur Reduktion des Lösungsaufwandes werden drei auf beide Lösungsansätze anwendbare Reduktionsregeln angegeben. Testrechnungen mit drei aus der Literatur bekannten Verschnittproblemen zeigen die Vor- und Nachteile der beiden Ansätze.
Notes:
Summary There are two different LP-model formulations to obtain the optimal solution of 1- and 1 1/2-dimensional cutting stock problems. On the one hand there is the complete-cut LP-model which may be solved by the well-known column generation approach of Gilmore and Gomory [9, 10], while on the other hand Rao [17] and Dyckhoff [2, 4] propose an LP-model based on one-cuts to describe the cutting process, to be solved by standard LP software. For both models and solution approaches their commonalities and differences are elaborated, providing insights into possible application areas and the advantages of each approach. We will consider the standard cutting stock problem as well as real world extensions — like the limited availability of standard lengths and the evaluation of residual lengths. Furthermore, three reduction-rules are indicated which can reduce the solution effort. Test runs based on three cutting stock problems mentioned in the literature demonstrate the pros and cons of the two approaches.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01720208
Permalink
