A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems

A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems

0.00 Avg rating0 Votes
Article ID: iaor20023283
Country: United Kingdom
Volume: 29
Issue: 7
Start Page Number: 925
End Page Number: 947
Publication Date: Jun 2002
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics
Abstract:

In this paper we develop several heuristic algorithms for the two-dimensional cutting problem (TDC) in which a single stock sheet has to be cut into a set of small pieces, while maximising the value of the pieces cut. They can be considered to be general purpose algorithms because they solve the four versions of the TDC: weighted and unweighted, constrained and unconstrained. We begin by proposing two constructive procedures based on simple bounds obtained by solving one-dimensional knapsack problems. We then use these constructive algorithms as building blocks for more complex procedures. We have developed a greedy randomised adaptive search procedure (GRASP) which is very fast and obtains good results for both constrained and unconstrained problems. We have also developed a more complex tabu search algorithm that obtains high quality results in moderate computing times. Finally, we have implemented a path relinking procedure to improve the final results of the above algorithms. For the computational results we have used the set of large-scale test problems collected and generated by Fayard et al.

Reviews

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