The multiperiod two‐dimensional non‐guillotine cutting stock problem with usable leftovers

• Author: D. P. Ronconi,E. G. Birgin,O. C. Romão
• Published date: 01 May 2020
• DOI: http://doi.org/10.1111/itor.12648
• Date: 01 May 2020

Intl. Trans. in Op. Res. 27 (2020) 1392–1418

DOI: 10.1111/itor.12648

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

The multiperiod two-dimensional non-guillotine cutting stock

problem with usable leftovers

E. G. Birgina,O.C.Rom

˜

aoaand D. P. Ronconib

aDepartment of Computer Science, Institute of Mathematics and Statistics, University of S˜

ao Paulo, Rua do Mat˜

ao, 1010,

Cidade Universit´

aria, 05508-090, S˜

ao Paulo, Brazil

bDepartment of Production Engineering, EP-USP, University of S˜

ao Paulo, Av. Prof.Almeida Prado, 128, Cidade

Universit´

aria, 05508-900, S˜

ao Paulo, Brazil

E-mail: egbirgin@ime.usp.br[Birgin]; oberlan@ime.usp.br [Rom˜

ao]; dronconi@usp.br [Ronconi]

Received 24 September 2018; receivedin revised form 4 January 2019; accepted 16 February 2019

Abstract

A mixed integer linear programing model forthe two-dimensional non-guillotine cutting problem with usable

leftovers was recently introduced by Andrade et al. The problem consists in cutting a set of ordered items

using a set of objects of minimum cost and, within the set of solutions of minimum cost, maximizing

the value of the usable leftovers. Since the concept of usable leftovers assumes they can potentially be

used to attend new arriving orders, the problem is extended to the multiperiod framework in this work. In

this way, the decision at each instant does not minimize in a myopic way the cost of the objects required

to attend the orders of the current instant; but it aims to minimize the overall cost of the objects up to

the considered time horizon. Some variants of the proposed model are analyzed and numerical results

are presented.

Keywords:non-guillotine cutting and packing; usable leftovers; MIP models; multiperiod scenario

1. Introduction

Cutting stock problems appear in a wide range of industrial processes where a variety of large

pieces of material, such as paper, glass, steel, wood, or fabric, need to be cut in order to produce

smaller pieces of ordered sizes and quantities. Aiming to reduce operating costs, several aspects of

the cutting process may be taken into account, and returning leftovers to stock so they can be used

in future orders is one of them (see, for example, Koch et al. (2009) and Chen et al. (2019), where

the usage of leftovers in the wood-processing and plastic-film industries are considered).

In this work, we are concerned with the two-dimensional non-guillotine cutting problem of

cutting an heterogeneous set of small rectangular pieces (items) from a set of large rectangular

pieces (objects). The problem is said to be two-dimensional because it involves the widths and

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies

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

USA.

E. G. Birgin et al. / Intl. Trans. in Op. Res. 27 (2020) 1392–1418 1393

heights of items and objects, while it is said to be non-guillotine because cuts are not restricted to

be guillotine cuts. A multiperiod scenario is considered in which, at each instant p(0 ≤p≤P−1),

there are ordered items and available purchasable objects, and items ordered at instant pmust

be produced within the period [p,p+1]. An item ordered at instant pmay be produced from a

purchased object available at that instant or from a leftover of a previously used object. Thus, we

consider that, at each instant, an heterogeneous set of objects is available.

In Andrade et al. (2014), the single-period scenario of the problem described in the paragraph

above was tackled. In the single-period scenario, the goal is to minimize the cost of the objects

required to produce all ordered items, and, within the set of solutions with minimum cost, to

maximize the value of objects’ usable leftovers. (The formal definition of usable leftover adopted

in this work will be given in the next section.) The consideration of usable leftovers assumes

their utilization to produce forthcoming orders of items; thus, extending the problem considered

in Andrade et al. (2014) to the multiperiod scenario appears as a natural option. In the multiperiod

scenario, given a time horizon represented by Pinstants 0,...,P−1, the goal is to minimize the

overall cost of the objects required to produce all items ordered at instants 0,...,P−1, and,

within the set of solutions with minimum cost, to maximize the value of usable leftovers available

at instant P(i.e., at the end of the considered time horizon). It is very clear that this formulation of

the problem is expected to produce better quality solutions than the myopic alternative of solving a

single-period problem ateach instant. Note that, following Andrade et al. (2014), in the present work

there is a clear hierarchy betweenthe two considered objectives—cost must be minimized in the first

place and, among solutions of minimum cost, a solution with maximum value of usable leftovers is

seeked. This goals’ hierarchyfits the tackled problem in the bilevel optimization framework(Dempe,

2002), in opposition to the multiobjective approach (Miettinen, 1998).

Several works were written regarding one-dimensional cutting problems with leftovers (see the

pionners’ works of Roodman (1986) and Scheithauer (1991), the recent survey by Cherri et al.

(2014) and the references therein, and the works of Poldi and Arenales (2010), Cherri et al. (2013),

and Tomat and Gradis̆ar (2017)). In Poldi and Arenales (2010), the authors introduce a mixed

integer linear programing model, a column generation approach to solve its linear relaxation, and

a heuristic rolling horizon approach for rounding off fractional solutions. In Tomat and Gradis̆ar

(2017), a multiperiod problem that combines the minimization of the trim-loss and the amount of

usable leftovers in stock is considered, and a heuristic method is proposed and tested. In Cherri

et al. (2013), to avoid leftovers remaining in stock for a long period of time, it is considered that the

leftovers have a priority-in-use compared to standard objects in stock. A heuristic approach is also

proposed and tested.

On the other hand, only a few works address two- and three-dimensional cutting problems with

leftovers.In Andrade et al. (2014), a mixed integer linear programing model for the two-dimensional

non-guillotine cutting stock problem with usable leftovers was introduced. In the considered single-

period problem, the goal is to minimize the cost of the objects required to produce a given set

of ordered items and, within the set of minimum cost, maximize the value of the usable leftovers.

In Andrade et al. (2016), the non-exact two-stage guillotine cutting stock version of the same

problem was analyzed. In Viegas et al. (2016), a heuristic cutting decision process for daily tailored

orders of a real-life steel retailer is proposed. The considered problem is a three-dimensional cutting

and packing problem in which usable leftovers of preceding periods may be used to produce items

of the current period. A three-staged two-dimensional cutting stock problem with usable leftover

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation of OperationalResearch Societies