Optimal compactification of a floorplan and its relation to other optimization problems – a dynamic programming approach.

*(English)*Zbl 0768.90081Summary: 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 |

Full Text:
DOI

**OpenURL**

##### 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 |

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.