Models and algorithms for packing rectangles into the smallest square |
| |
| Affiliation: | 1. Department of Computer Science, Institute of Mathematics and Statistics, University of São Paulo, Rua do Matão 1010, Cidade Universitária, São Paulo 05508-090, SP, Brazil;2. Department of Applied Mathematics, Institute of Mathematics, Statistics, and Scientific Computing, State University of Campinas, Rua Sérgio Buarque de Holanda 651, Campinas 13083-859, SP, Brazil;1. LERIA, Université d’Angers, 2 Bd Lavoisier, Angers 49045, France;2. Institut Universitaire de France, Paris, France |
| |
| Abstract: | We consider the problem of determining the smallest square into which a given set of rectangular items can be packed without overlapping. We present an ILP model, an exact approach based on the iterated execution of a two-dimensional packing algorithm, and a randomized metaheuristic. Such approaches are valid both for the case where the rectangles have fixed orientation and the case where they can be rotated by 90°. We computationally evaluate the performance and the limits of the proposed approaches on a large set of instances, including a number of classical benchmarks from the literature, for both cases above, and for the special case where the items are squares. |
| |
| Keywords: | Two dimensional packing Mathematical model Randomized algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
