Cutting stock with no three parts per pattern: Work-in-process and pattern minimization

The Pattern Minimization Problem (PMP) consists in finding, among the optimal solutions of a cutting stock problem, one that minimizes the number of distinct cutting patterns activated. The Work-in-process Minimization Problem (WMP) calls for scheduling the patterns so as to maintain as few open stacks as possible. This paper addresses a particular class of problems, where no more than two parts can be cut from any stock item, hence the feasible cutting patterns form the arc set of an undirected graph G. The paper extends the case G=K"n introduced in 1999 by McDiarmid. We show that some properties holding for G=K"n are no longer valid for the general case; however, for special cases of practical relevance, properly including G=K"n, quasi-exact solutions for the PMP and the WMP can be found: the latter in polynomial time, the former via a set-packing formulation providing very good lower bounds.

• Publication year

  2011

• Venue

  Discrete Optimization

• Publication date

  2011-05-01

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1016/j.disopt.2010.10.002
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Graph Theory

  2016influential reference
• On LP relaxations for the pattern minimization problem

  2011cited by this paper
• TRCS Series Cutting Stock with Bounded Open Stacks : a New Integer Linear Programming Model

  2010cited by this paper
• Controlling open stacks and flow time in a cutting process

  2009cited by this paper
• A Lower Bound for the Cutting Stock Problem with a Limited Number of Open Stacks.

  2009cited by this paper
• A branch-and-price-and-cut algorithm for the pattern minimization problem

  2008cited by this paper
• An integrated cutting stock and sequencing problem

  2007cited by this paper
• Setup and Open-Stacks Minimization in One-Dimensional Stock Cutting

  2007cited by this paper
• Minimum Flow Time Graph Ordering

  2003cited by this paper
• Combinatorial optimization. Polyhedra and efficiency.

  2003cited by this paper
• The Lazy Cook Problem, or Scheduling Two Parallel Machines to Optimize Vehicle Utilization

  2003cited by this paper
• A linear algorithm for the Hamiltonian completion number of the line graph of a tree

  2001cited by this paper
• Exact Algorithm for Minimising the Number of Setups in the One-Dimensional Cutting Stock Problem

  2000influential reference
• Pattern Minimisation in Cutting Stock Problems

  1999influential reference
• CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem

  1995cited by this paper
• Bin-packing and Matchings in Threshold Graphs

  1995cited by this paper
• Scheduling: Theory, Algorithms, and Systems

  1994influential reference
• On the Equal-Subset-Sum Problem

  1992cited by this paper
• A Linear Programming Approach to the Cutting-Stock Problem

  1961cited by this paper

• On formulations for the one-dimensional cutting stock with a limited number of open stacks problem

  2025cites this paper
• Mathematical models for the one-dimensional cutting stock problem with setups and open stacks

  2025cites this paper
• Formulations and exact solution approaches for a coupled bin-packing and lot-sizing problem with sequence-dependent setups

  2022cites this paper
• Formulations and theoretical analysis of the one-dimensional multi-period cutting stock problem with setup cost

  2022cites this paper
• Modeling and solving a real-world cutting stock problem in the marble industry via mathematical programming and stochastic diffusion search approaches

  2021cites this paper
• Algorithmic Aspects of the Maximum 2-edge-colorable Subgraph Problem

  2021cites this paper
• Coverage Subject to a Budget on Multi-Interface Networks with Bounded Carving-Width

  2020cites this paper
• Constrained Connectivity in Bounded X-Width Multi-Interface Networks

  2020cites this paper
• Budgeted Constrained Coverage on Series-Parallel Multi-interface Networks

  2020cites this paper
• A cutting stock problem in the wood products industry: a two-stage solution approach

  2020cites this paper
• Budgeted constrained coverage on bounded carving-width and series-parallel multi-interface networks

  2020cites this paper
• Distributing Energy Consumption in Multi-interface Series-Parallel Networks

  2019cites this paper
• Energy consumption balancing in multi-interface networks

  2019cites this paper
• On the fixed-parameter tractability of the maximum 2-edge-colorable subgraph problem

  2019cites this paper
• Balancing Energy Consumption for the Establishment of Multi-interface Networks

  2015cites this paper
• On cutting stock with due dates

  2014cites this paper
• Batch scheduling in a cutting process with finite buffers

  2012cites this paper
• New lower bounds based on column generation and constraint programming for the pattern minimization problem

  2009cites this paper