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: | Alvarez-Valds Ramn, Parajn Antonio, Tamarit Jos Manuel |
Keywords: | heuristics |
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