The Two-Dimensional, Rectangular,Guillotineable-Layout Cutting Problemwith a Single Defect

In this paper, a two-dimensional cutting problem is consideredin which a single plate (large object) has to be cut down into a set of smallitems of maximal value. As opposed to standard cutting problems, thelarge object contains a defect, which must not be covered by a small item.The problem is represented by means of an AND/OR-graph, and a Branch& Bound procedure (including heuristic modifications for speeding up thesearch process) is introduced for its exact solution. The proposed methodis evaluated in a series of numerical experiments that are run on probleminstances taken from the literature, as well as on randomly generatedinstances...

MoreLess

Year of publication:	2008-12-01
Authors:	Neidlein, Vera ; Wäscher, Gerhard ; Vianna, Andréa C. G. ; Arenales, Marcos N.
Institutions:	Universität <Magdeburg> / Fakultät für Wirtschaftswissenschaft
Subject:	AND/OR-Gatter \| Zuschneideproblem

1 Introduction
2 Fundamentals
2.1 Problem Definition and Characterization
2.2 Formal Representation
2.3 Literature Review
3 The AND/OR-Graph Approach to the 2D_UG_SLOPP
3.1 Guillotine Cuts and Intermediate Plates
3.2 AND/OR-Graphs
3.3 Upper and Lower Bounds
3.4 A Branch & Bound Algorithm
3.5 Heuristic Modifications
4 Dealing with a Single Defect
4.1 Dimensions and Location of a Defect on an Intermediate Plate
4.2 Upper and Lower Bounds for a Defective Plate
5 Numerical Experiments
5.1 Data Sets
5.2 Implementation of the Algorithm
6 Computational Results
6.1 Instances of Carnieri, Mendoza, and Luppold
6.2 Randomly Generated Instances
7 Conclusions and Outlook

Persistent link: https://ebvufind01.dmz1.zbw.eu/10005867177