Please use this identifier to cite or link to this item:
https://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 |
| Scientific areas: | Ciências da engenharia e tecnologias::Outras ciências da engenharia e tecnologias Engineering and technology::Other engineering and technologies |
| DOI: | 10.1007/978-3-8349-9777-7_2 |
| URI: | https://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 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.