Pattern minimisation in cutting stock problems
type: Item
instance of: scholarly article
title: Pattern minimisation in cutting stock problems
zbMATH Open document ID: 0987.90085
DOI: 10.1016/S0166-218X(99)00112-2
published in: Discrete Applied Mathematics
publication date: 2000-01-17T00:00:00Z
review text: 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 focusses on `balanced' subsets, and suggests an approach for heuristic methods involving searching for balanced subsets.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 1389502
zbMATH Keywords: cutting stock
zbMATH Keywords: cutting patterns
zbMATH Keywords: partition
zbMATH Keywords: NP-hard
zbMATH Keywords: dynamic programming
author: Colin McDiarmid
MaRDI profile type: Publication
cites work: Simple Constructions of Almost k-wise Independent Random Variables
cites work: Q4002885
cites work: A Linear Programming Approach to the Cutting-Stock Problem
cites work: A Linear Programming Approach to the Cutting Stock Problem—Part II
cites work: Optimal solutions for the cutting stock problem
cites work: The NP-completeness column: An ongoing guide
cites work: Q4726042
cites work: Cutting and Packing Problems: A Categorized, Application-Orientated Research Bibliography
cites work: The modified differencing method for the set partitioning problem with cardinality constraints
cites work: The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp
full work available at URL: s0166-218x(99)00112-2
OpenAlex ID: W2093285251
description: scientific article; zbMATH DE number 1389502