Optimal compactification of a floorplan and its relation to other optimization problems – a dynamic programming approach. (English) Zbl 0768.90081

Summary: We examine an algorithm for the compactification of an arrangement of rectangles in the plane as it is used for floorplans in the automated design of electronic circuits (also called sizing of floorplans). We reformulate this problem as a multistage decision problem and show that the algorithm is in fact the optimal solution obtained by the backward induction procedure of dynamic programming. The model allows generalizations to non-geometrical applications in scheduling and reliability.


90C39 Dynamic programming
90B25 Reliability, availability, maintenance, inspection in operations research
90B30 Production models
90B35 Deterministic scheduling theory in operations research
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C90 Applications of mathematical programming
Full Text: DOI


[1] Dai WM, Kuh ES (1986) Hierarchical Floor Planning for Building Block Layout. Proceedings IEEE Int. Conf. CAD (ICCAD), Santa Clara, 454-457
[2] Kolonko M (1990) Parallel Dynamic Programming with Applications to Layout Problems. Hildesheimer Informatikberichte 3/90, Universität Hildesheim
[3] Lengauer T (1990) Combinatorial Algorithms for Integrated Circuit Layout. Teubner, Stuttgart, J Wiley, Chichester · Zbl 0709.68039
[4] Stockmeyer L (1983) Optimal Orientation of Cells in Slicing Floorplan Designs.Information and Control 57:91-101 · Zbl 0545.68030
[5] Otten RHJM (1983) Efficient Floorplan Design. Proceedings IEEE Int. Conf. Computer Design (ICCD) 499-502
[6] Zimmermann G (1988) A New Area and Shape Function Estimation Technique for VLSI Layouts. Proceedings ACM/IEEE Design Automation Conference 60-65
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.