Board Cutting from Logs: Optimal and Heuristic Approaches for the Problem of Packing Rectangles in a Circle

The cutting of logs when the sawing pattern must be defined to produce boards that satisfy a pre-established demand presents a particularly interesting problem. This problem can be reduced to one of optimal bi-dimensional packing of rectangles in a circular container, which we call the problem of packing rectangles in a circle. To tackle this problem, we present a mathematical formulation based on nonlinear mixed integer programming in order to rapidly solve small-scale problems. For larger problems, two heuristic methods are proposed: a constructive method that fits the rectangles by decreasing order of height inside the circular container and a second method based on simulated annealing that considers an array defining the order in which the rectangles must be considered by a construction function. A set of test problems is selected by which the constructive heuristic delivers an average yield of 91.3%, whereas the simulated annealing approach generates packing patterns with an average yield of 93.6% of the usable area, but at the expense of computing times that are longer than 1 h in the most extreme cases. It is concluded that both methods can be used to support decision making by choosing the most adequate approach depending on the scale of the problem to be solved. © 2013 Elsevier B.V. All rights reserved.