A combined approach to the solution to the general one-dimensional cutting stock problem

In this article a combined method for the solution to the general one-dimensional cutting stock problem (G1D-CSP) is proposed. The main characteristic of G1D-CSP lies in that all stock lengths can be different. The new approach combines two existing methods: sequential heuristic procedure (SHP) and...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2005-07, Vol.32 (7), p.1793-1807
Main Authors: Gradisar, Miro, Trkman, Peter
Format: Article
Language:English
Subjects:
Applied sciences
Branch & bound algorithms
Branch-and-bound
Cutting
Exact sciences and technology
Heuristic
Heuristics
Operational research and scientific management
Operational research. Management science
Optimization
Optimization. Search problems
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this article a combined method for the solution to the general one-dimensional cutting stock problem (G1D-CSP) is proposed. The main characteristic of G1D-CSP lies in that all stock lengths can be different. The new approach combines two existing methods: sequential heuristic procedure (SHP) and branch-and-bound. The algorithm based on the proposed method leads to almost optimal solutions, which are substantially better than the solutions of known methods at the expense of slightly increased time complexity, which is still low. So, the new method is suitable for all sizes of the problem. A comparison with the SHP is presented.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2003.11.028