Please use this identifier to cite or link to this item: http://hdl.handle.net/10216/91890
Author(s): Eduarda Pinto Ferreira
José Fernando Oliveira
Title: Fekete and Schepers' graph-based algorithm for the two-dimensional orthogonal packing problem revisited
Issue Date: 2008
Abstract: In this paper Fekete and Schepers' exact algorithm for the non-guillotinable two-dimensional orthogonal packing problem is discussed. A modification to this algorithm is also proposed. The Fekete and Schepers' algorithm relies on a graph representation of packing patterns to assess if there is a feasible packing for a problem. Yet, the algorithm's projection graphs construction mechanism sometimes degenerates and while it correctly assesses the existence of a feasible packing pattern, the resulting projection graphs are not equal to the graphs of the packing class to which the packing pattern belongs [1] [2]. The presented algorithm overcomes this problem by introducing an extra condition to avoid the aforementioned degeneration. This modification was tested over instances of previously published literature.
Subject: Investigação operacional, Engenharia industrial, Outras ciências da engenharia e tecnologias
Operations research, Industrial engineering, Other engineering and technologies
URI: http://hdl.handle.net/10216/91890
Source: Intelligent Decision Support: Current Challenges and Approaches
Document Type: Capítulo ou Parte de Livro
Rights: restrictedAccess
Appears in Collections:FEUP - Capítulo ou Parte de Livro

Files in This Item:
File Description SizeFormat 
57796.pdf489 kBAdobe PDF    Request a copy


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.