In the cutting stock pattern minimisation problem, we wish to satisfy demand for various customer reels by cutting as few as possible jumbo reels, and further to minimise the number of distinct cutting patterns used. We focus on the special case in which any two customer reels ÿt into a jumbo, but no three do: this case is of interest partly because it is the simplest case that is not trivial, and partly because it may arise in practice when one attempts to improve a solution iteratively. We ÿnd that the pattern minimisation problem is strongly NP-hard even in this special case, when the basic problem of ÿnding a minimum waste solution is trivial. Our analysis focusses on 'balanced' subsets, and suggests an approach for heuristic methods involving searching for balanced subsets. ?
It is known that pattern minimisation is NP-hard REF .
Pattern minimisation in cutting stock problems
Computer Science Mathematics