Exact algorithms in bar nesting: How to cut general items from linear stocks so that wastage is minimised

This paper proposes exact, polynomial-time algorithms that solve the problem of cutting items with angled sides from a single linear stock so that wastage is minimised. In industry, this problem is called “bar nesting”. Here we give an algorithmic framework that solves several important variants of the problem, including cutting items from stocks with asymmetric cross-sections, cutting items whose sides occur on different planes, and the minimum score separation problem. • Exact, polynomial-time algorithms are given for single-stock bar nesting problems. • Several industry-related problem variants are considered. • Correctness proofs and source code are provided.