Models for the two‐dimensional rectangular single large placement problem with guillotine cuts and constrained pattern

• Author: Mateus Martin,Ernesto G. Birgin,Reinaldo Morabito,Pedro Munari,Rafael D. Lobato
• DOI: http://doi.org/10.1111/itor.12703
• Date: 01 March 2020
• Published date: 01 March 2020

Intl. Trans. in Op. Res. 27 (2020) 767–793

DOI: 10.1111/itor.12703

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Models for the two-dimensional rectangular single large

placement problem with guillotine cuts and constrained pattern

Mateus Martina, Ernesto G. Birginb, Rafael D. Lobatob,

Reinaldo Morabitoaand Pedro Munaria

aDepartment of Production Engineering, FederalUniversity of S ˜

ao Carlos, Via WashingtonLuiz km. 235, 13565-905,

S˜

ao Carlos, SP, Brazil

bDepartment of Computer Science, University of S˜

ao Paulo, S˜

ao Paulo, Brazil

E-mail: mateus.pmartin@gmail.com [Martin]; egbirgin@ime.usp.br [Birgin]; lobato@ime.usp.br [Lobato];

morabito@ufscar.br[Morabito]; munari@dep.ufscar.br [Munari]

Received 19 October 2018; receivedin revised form 28 April 2019; accepted 22 June 2019

Abstract

In this paper,we address the constrained two-dimensional rectangular guillotine single large placement prob-

lem (2D_R_CG_SLOPP). This problem involves cutting a rectangular object to produce smaller rectangular

items from orthogonal guillotine cuts.In addition, there is an upper limit on the number of copies that can be

produced of each item type. To model this problem, we propose a new pseudopolynomial integer nonlinear

programming (INLP) formulation and obtain an equivalent integer linear programming (ILP) formulation

from it. Additionally, we developed a procedure to reduce the numbers of variables and constraints of the

integer linear programming (ILP) formulation, without loss of optimality. From the ILP formulation, we

derive two new pseudopolynomial models for particular cases of the 2D_R_CG_SLOPP, which consider

only two-staged or one-group patterns. Finally, as a specific solution method for the 2D_R_CG_SLOPP,

we apply Benders decomposition to the proposed ILP formulation and develop a branch-and-Benders-cut

algorithm. All proposed approaches are evaluated through computational experiments using benchmark

instances and compared with other formulations availablein the literature. The results show that the new for-

mulationsare appropriate in scenarios characterized by few item types that are largewith respect to the object’s

dimensions.

Keywords: cutting and packing problems; constrained two-dimensional guillotine cuts; integer programming models;

branch-and-Benders-cut algorithm

1. Introduction

Cutting operations in manufacturing industries can be seen as a policy foreconomies of scale in the

purchase and storage of raw material (objects), or even to avoid risks of object unavailabilities in

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.

768 M. Martin et al. / Intl. Trans.in Op. Res. 27 (2020) 767–793

future purchases. In fact, cutting a large stocked object to produce the required items of demands

known a posteriori is often a safer economical policy than storing several required items of demand

unknown apriori. These decisions are known as cutting and packing (C&P) problems in the field of

Operations Research—see W¨

ascher et al. (2007) for a survey and typology. They may represent the

cutting of steel bars, paper reels, wooden boards, flat glass, stones, among other types of objects and

items from different productive systems. C&P problems can also be analyzed in a wider framework,

for instance,in logistical scenarios (C ˆ

ot´

e et al., 2017; De Queiroz et al., 2017) or in combination with

other manufacturing decisions, such as layout, setups, and lot-sizing issues (Linhares and Yanasse,

2002; Henn and W¨

ascher, 2013; Melega et al., 2018).

This paper addresses the constrained two-dimensional rectangular guillotine single large place-

ment problem (2D_R_CG_SLOPP). Its applicability in a different productive environment mo-

tivates the proposition of several solution methods since the seminal papers of Christofides and

Whitlock (1977) and Wang (1983) for this problem. However, the first mathematical models to

completely formulate this problem only appeared in the literature more than 30 years after the

mentioned seminal papers (Ben Messaoud et al., 2008; Furini et al., 2016). This problem considers

cutting a rectangular stocked object of dimensions L×Wto produce an assortment of rectangular

small item types, while maximizing the total (usable) area or the sum of the values of the cut items.

Each item type k∈{1,...,m}is characterized by its dimensions lk×wk,valuevk, and maximum

number of copies to be cut rk. The cutting must satisfy the following requirements:

1. Cuts are orthogonal to the object’s edges and of guillotine type, that is, any small item of the

cutting pattern is obtained by a sequence of edge-to-edge cuts.

2. The number of guillotine stages is unlimited.

3. No rotations of items is allowed (fixed orientation).

4. The items must not overlap each other and must comply with the object dimensions.

5. For each item type kup to rkcopies can be produced.

According to W¨

ascher et al. (2007), the 2D_R_CG_SLOPP is a variant of the standard two-

dimensional rectangular single large placement problem (2D_R_SLOPP) in which the cuts are of

the guillotine type and there is a limit on the number of copies that can be produced of each item

type. Additionally, we address two special types of guillotine patterns, namely two-staged and one-

group patterns, which arise in productive systems in which shorter cycle times are sought even if

detrimental to exploitation rates. In such contexts, cutting patterns with a few guillotine stages are

likely to be more relevant than highly staged patterns—the number of stages refers to the quantity

of 90◦rotations of the cutting saw. In two-staged patterns, items are obtained by first cutting

horizontal (resp., vertical) shelves that are then followed by vertical (resp., horizontal) cuts—a shelf

is any edge-to-edge cut on the large object. In one-group patterns, there are horizontal and vertical

shelves, and shelves that are cut in the first stage are stacked and cut together in the second stage.

Figure 1 illustrates differenttypes of patterns—blank rectangles represent the items and the hatched

areas are waste. The term nonexact refers to the possibility of an additional cut for splitting an item

and waste for guillotine patterns, whereas in the exact case this step is not allowed. The approaches

proposed in this paper can also be used to address the nonfixed orientation case, if we add a new

item type kwith length wk,widthlk, and value vk, for each k∈K.

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies