Fekete and Schepers' graph-based algorithm for the two-dimensional orthogonal packing problem revisited

• Type: Chapter or Part of a Book
• Date: 2008

Authors

Eduarda Pinto Ferreira (Author) Other; José Fernando Oliveira (Author) FEUP

Book

Title: Intelligent Decision Support: Current Challenges and Approaches

1º Edition

Pages: 15-31

ISBN: 978-3-8349-0930-5

Publisher: Gabler Edition Wissenschaft

Scientific classification

FOS: Engineering and technology > Other engineering and technologies

CORDIS: Physical sciences > Mathematics > Applied mathematics > Operations research ; Technological sciences > Engineering > Industrial engineering

Other information

DOI: 10.1007/978-3-8349-9777-7_2

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific