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

Kolonko, Michael

Z. Oper. Res. 37, No. 1, 75-95 (1993).

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.

MSC:

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

Keywords:

VLSI-layout; floorplans; automated design of electronic circuits; multistage decision

References:

[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