A computational study of LP-based heuristic algorithms for two-dimensional guillotine cutting stock problems

A computational study of LP-based heuristic algorithms for two-dimensional guillotine cutting stock problems

0.00 Avg rating0 Votes
Article ID: iaor2003988
Country: Germany
Volume: 24
Issue: 2
Start Page Number: 179
End Page Number: 192
Publication Date: Jan 2002
Journal: OR Spektrum
Authors: , ,
Keywords: programming: linear, heuristics
Abstract:

In this paper we develop and compare several heuristic methods for solving the general two-dimensional cutting stock problem. We follow the Gilmore–Gomory column generation scheme in which at each iteration a new cutting pattern is obtained as the solution of a subproblem on one stock sheet. For solving this sub-problem, in addition to classical dynamic programming, we have developed three heuristic procedures of increasing complexity, based on GRASP and Tabu Search techniques, producing solutions differing in quality and in time requirements. In order to obtain integer solutions from the fractional solutions of the Gilmore–Gomory process, we compare three rounding procedures, rounding up, truncated branch and bound and the solution of a residual problem. We have coded and tested all the combinations of algorithms and rounding procedures. The computational results obtained on a set of randomly generated test problems show their relative efficiency and allow the potential user to choose from among them, according to the available computing time.

Reviews

Required fields are marked *. Your email address will not be published.