One‐dimensional cutting stock with a limited number of open stacks: bounds and solutions from a new integer linear programming model

• Author: Fabrizio Marinelli,Paolo Ventura,Claudio Arbib
• Date: 01 January 2016
• Published date: 01 January 2016
• DOI: http://doi.org/10.1111/itor.12134

Intl. Trans. in Op. Res. 23 (2016) 47–63

DOI: 10.1111/itor.12134

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

One-dimensional cutting stock with a limited number of open

stacks: bounds and solutions from a new integer linear

programming model

Claudio Arbiba, Fabrizio Marinelliband Paolo Venturac

aUniversit`

a degli Studi dell’Aquila via Vetoio, Coppito, I-67010 L’Aquila, Italy

bDipartimento di Ingegneria dell’Informazione, Universit`

a Politecnica delle Marchevia Brecce Bianche 12, I-60121

Ancona, Italy

cIstituto di Analisi dei Sistemi e Informatica, Consiglio Nazionale delle Ricerche, viale Manzoni 30, I-00185 Roma, Italy

E-mail: claudio.arbib@univaq.it [Arbib]; fabrizio.marinelli@univpm.it [Marinelli]; paolo.ventura@iasi.cnr.it [Ventura]

Received 12 July2013; received in revised form 19 September 2014; accepted 28 September 2014

Abstract

We address a one-dimensional cutting stock problem where, in addition to trim-loss minimization, cutting

patterns must be sequenced so that no more than sdifferent part types are in production at any time. We

propose a new integer linear programmingformulation whose constraints growquadratically with the number

of distinct part types and whose linear relaxation can be solved by a standard column generation procedure.

The formulation allowedus to solve problems with 20 part types for which an optimal solution was unknown.

Keywords:cutting stock; open stacks; pattern sequencing; integer linear programming

1. Introduction

1.1. The problem

The one-dimensional cutting stock problem (1-CSP, see Dyckhoff et al. (1996) for an old but vast

annotated bibliography) calls for cutting diparts wiunits wide (i∈B,|B|=m) from a minimum

number of identical stock items of width w.Acutting pattern specifies a way to cut parts from a

stock item: in the one-dimensional case, it corresponds to an integer solution p=(p1,...,pm)≥0

of inequality i∈Bwipi≤w(knapsack condition). A solution of the 1-CSP provides (a) a set Pof

distinct patterns, (b) the number of times each pattern of Pmust be repeated in order to cover the

parts requirement: this number is called the pattern run length. In practice, to reduce setups it is

customary to nonpreemptively run each pattern up to its run length. Together with P, the sequence

in which patterns are used—in fact, a permutation πof P—gives a cutting plan (P,π).

C

2014 The Authors.

International Transactionsin Operational Research C

2014 International Federation of OperationalResearch Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

48 C. Arbib et al. / Intl. Trans. in Op. Res. 23 (2016) 47–63

Along with the classical objective of trim-loss minimization, a major goal of industries deploying

a cutting process is to organize production in a way compliant with machine-tool resources and

capacity (see, e.g., Arbib and Marinelli, 2009; Arbib et al., 2002; Matsumoto et al., 2011). In this

respect, an important indicator is the number of open stacks: after cut, parts of the same size are

normally collected into a stack. A stack is open (closed) as soon as the first (the last) of its parts

has been cut. Because automated cutting machines usually have a downstream buffer with limited

capacity, only a limited number sof stacks can be maintained open throughout the cutting process,

and a problem of finding a feasible cutting plan arises.

In the literature,contributions can be found on the open stack minimization problem.This problem,

known with the acronym MOSP, calls for permuting a given set of patterns so as to minimize the

maximum number of open stacks. The MOSP was the subject of an international contest: in

Smith and Gent (2005), authors collected a quite large number of papers with algorithm details

and computation experiments. Recent research has focused on 0–1 matrices with the consecutive

ones property (C1P), providing an interesting integer linear programming formulation that uses

Oswald–Reinelt inequalities (de Giovanni et al., 2007); but a breakthrough (Chu and Stuckey,

2009) has recently been achieved by a smart combinatorial lower bound that, used in a branch-

and-bound scheme, reduced the best computation times in Smith and Gent (2005) by a factor

of 10–6.

Apparently, the MOSP is to be solved within a decomposition approach where one finds a

set of patterns minimizing trim loss first, and then sequences those patterns minimizing the

maximum number of open stacks. Unfortunately, this decomposition has a couple of important

drawbacks.

rFirst, the problem is not the same as minimizing open stacks under a prescribed trim loss: in fact,

cutting plans with similar trim losses may be obtained by many different pattern sets, and the

quality of a pattern sequence (as well as the time needed to compute it) can strongly depend on

the number and type of patterns chosen.

rMoreover, even an optimal solution to the latter problem may require more open stacks than

allowed by the cutting machine, and therefore be infeasible in practice.

The correct way to address the constraints on buffers is, in fact, to find a pattern set that both

covers demand and can be sequenced without exceeding buffer capacity: doing that with the goal

of minimizing trim loss is what we here call one-dimensional cutting stock with a limited number of

open stacks p roblem (1-CS-LOSP).

To the best of our knowledge, the 1-CS-LOSP has so far registered few contributions. Belov

and Scheithauer (2007) propose an effective sequential heuristic that makes use of pseudo-prices

in order to select the part types to be cut pattern after pattern. Arbib et al. (2012) design a

tabu-search heuristic that explores the space of sequences in which part types are produced and,

for each sequence considered, finds a pattern set by solving a constrained version of Gilmore–

Gomory’s model (Gilmore and Golmory, 1961, 1963). Yanasse and Pinto Lamosa (2007) formulate

the problem as integer linear programming: but the formulation, with exponentially many vari-

ables and constraints, just helps develop a lower bound (by lagrangian relaxation) and a primal

heuristic.

C

2014 The Authors.

International Transactionsin Operational Research C

2014 International Federation of OperationalResearch Societies