Pattern minimisation in cutting stock problems

Pattern minimisation in cutting stock problems

0.00 Avg rating0 Votes
Article ID: iaor20003519
Country: Netherlands
Volume: 98
Issue: 1/2
Start Page Number: 121
End Page Number: 130
Publication Date: Nov 1999
Journal: Discrete Applied Mathematics
Authors:
Keywords: programming: dynamic
Abstract:

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 fit 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 find that the pattern minimisation problem is strongly NP-hard even in this special case, when the basic problem of finding a minimum waste solution is trivial. Our analysis focuses on ‘balanced’ subsets, and suggests an approach for heuristic methods involving searching for balanced subsets.

Reviews

Required fields are marked *. Your email address will not be published.