Pattern minimisation in cutting stock problems

DOI10.1016/S0166-218X(99)00112-2zbMath0987.90085OpenAlexW2093285251MaRDI QIDQ1961237

Colin J. H. McDiarmid

Publication date: 17 January 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00112-2

zbMATH Keywords

partitiondynamic programmingNP-hardcutting stockcutting patterns

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Solving real-world cutting stock-problems in the paper industry: mathematical approaches, experience and challenges, Combined cutting stock and lot-sizing problem with pattern setup, Solution approaches for the cutting stock problem with setup cost, In situ column generation for a cutting-stock problem, Pattern-based ILP models for the one-dimensional cutting stock problem with setup cost, Formulations and theoretical analysis of the one-dimensional multi-period cutting stock problem with setup cost, Two-dimensional skiving and cutting stock problem with setup cost based on column-and-row generation, A heuristic approach to minimize the number of saw cycles in small-scale furniture factories, Hybrid heuristic for the production replanning problem under varying demands in manufacturing industries, Cutting stock with no three parts per pattern: work-in-process and pattern minimization, An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem, Computer-assisted proof of performance ratios for the differencing method, Optimal job splitting on a multi-slot machine with applications in the printing industry, Two heuristics for the capacitated multi-period cutting stock problem with pattern setup cost, A hybrid heuristic to reduce the number of different patterns in cutting stock problems, Modified greedy heuristic for the one-dimensional cutting stock problem, New lower bounds based on column generation and constraint programming for the pattern minimization problem, Strips minimization in two-dimensional cutting stock of circular items, One-dimensional cutting stock problem to minimize the number of different patterns

Cites Work

• Unnamed Item
• Unnamed Item
• Optimal solutions for the cutting stock problem
• The modified differencing method for the set partitioning problem with cardinality constraints
• A Linear Programming Approach to the Cutting-Stock Problem
• Simple Constructions of Almost k-wise Independent Random Variables
• Cutting and Packing Problems: A Categorized, Application-Orientated Research Bibliography
• The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp
• A Linear Programming Approach to the Cutting Stock Problem—Part II
• The NP-completeness column: An ongoing guide