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

• Tipo: Capítulo ou Parte de Livro
• Data: 2008

Autores

Eduarda Pinto Ferreira (Autor) Outra; José Fernando Oliveira (Autor) FEUP

Livro

Título: Intelligent Decision Support: Current Challenges and Approaches

1º Edição

Páginas: 15-31

ISBN: 978-3-8349-0930-5

Editora: Gabler Edition Wissenschaft

Classificação Científica

FOS: Ciências da engenharia e tecnologias > Outras ciências da engenharia e tecnologias

CORDIS: Ciências Físicas > Matemática > Matemática aplicada > Investigação operacional ; Ciências Tecnológicas > Engenharia > Engenharia industrial

Outras Informações

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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica