Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

A constraint-based approach for the two-dimensional rectangular packing problem with orthogonal orientations

 
: Berger, M.; Schröder, M.; Küfer, K.-H.

:

Fleischmann, B. (Hrsg.) ; Deutsche Gesellschaft für Operations Research -DGOR-:
Operations research proceedings 2008 : Selected papers of the annual international conference of the German Operations Research Society (GOR) University of Augsburg, September 3 - 5, 2008
Berlin: Springer, 2009
ISBN: 978-3-642-00141-3
pp.427-432
German Operations Research Society (GOR Annual International Conference) <2008, Augsburg>
English
Conference Paper
Fraunhofer ITWM ()

Abstract
We propose a constraint-based approach for the two-dimensional rectangular packing problem with orthogonal orientations. This problem is to arrange a set of rectangles that can be rotated by 90 degrees into a rectangle of minimal size such that no two rectangles overlap. It arises in the placement of electronic devices during the layout of 2.5D System-in-Package integrated electronic systems. Moffitt et al. [2] solve the packing without orientations with a branch and bound approach and use constraint propagation. We generalize their propagation techniques to allow orientations. Our approach is compared to a mixed-integer program and we provide results that outperform it

: http://publica.fraunhofer.de/documents/N-148949.html