Two-dimensional stock cutting and rectangle packing: binary tree model representation for local search optimization methods

This paper presents a binary tree hierarchical representation for bounding boxes (rectangles) comprised of shapes (other rectangles in our case) that are to be cut from a two-dimensional sheet of material. Although tree-representations of this problem have been presented in the open literature extensively, the binary tree representation is shown in this work to be capable of capturing any configuration of such rectangular shapes in two-dimensional space, such as rotations through right angles and translations, and to be advantageous and more general over other approaches when local search optimization procedures are to be utilized. The construction is such that these boxes must be bound together in pairs having a common edge, and can be extended to contain constraints regarding vertical or horizontal space between the actual objects as well as special types of cuts, e.g. guillotine cuts used in the glass cutting industry. Finally, a simple continuous sheet application is shown as a demonstration of the capabilities of the algorithm in connection with a local search method, specifically threshold accepting.