Backtracking Greedy Algorithm for Cutting Stock Problems

This paper presents a greedy search placement algorithm which incorporates backtracking for the leather stock cutting problem. In the leather manufacturing industry the efficient cutting of component parts (stencils) form a hide is of prime importance to maintain profitability. Consequently, the development of new approaches for generating cut-plans that minimise material waste and which can handle problem constraints have practical value. The unique feature of the greedy placement algorithm method presented in this paper is that it incorporates backtracking which allows previous placement steps to be retraced in situations where no placement solution can be found. The underlying encoding method is based on the use of the no-fit polygon (NFP) which describes the boundary around a stencil shape such that a second stencil shape can be placed while just touching the first but without overlapping. A material coverage of 64% can be achieved when taking placement constraints into account.