Solving the 3-Staged 2-Dimensional Cutting Stock Problem by Dynamic Programming and Variable Neighborhood Search

We present a variable neighborhood search (VNS) for the 3-staged 2-dimensional cutting stock problem employing “ruin-and-recreate”-based very large neighborhood search in which parts of the incumbent solution are destroyed and rebuilt using construction heuristics and dynamic programming. Experimental results show that for instances where the sizes of the elements are not too small compared to the sheet size the hybridization of VNS with dynamic programming significantly outperforms a VNS relying solely on construction heuristics.