Optimal cutting directions and rectangle orientation algorithm



The first stage in hierarchical approaches to Floorplan Design defines topological relations between components that intend to optimize a given objective in a circuit board. These relations determine a placement that is subsequently optimized in order to minimize a cost measurement (that will probably be one between chip area or perimiter). The board optimization gives rise to multiple subproblems that need to be answered in order to obtain a good solution. Among the most relevant ones we find the problem of defining the optimal orientation of cells and the definition of the optimal cutting sequence that minimize the placement board area. We will present a generalization of an algorithm due to Stockmeyer so that it obtains a solution that not only defines tha optimal cell orientation but also the slicing cuts sequence that will lead to this optimal orientation and overall area minimization.


Optimization; Compaction; Cutting direction; Rectangle orientation; Nondominated solution;


Floorplan optimization


European Journal of Operational Research, Vol. 109, pp. 600-671, Elsevier, January 1998


Cited by

Year 2015 : 1 citations

 C Shih, M Huang, Z Liang. An Color Interference Checking Chip Dicing Plan for Multiple Project Wafer. Intelligent Systems and Applications, Proc. of the International Computer Symposium (ICS), Taichung, Taiwan, December 2014, pp. 321-331 (2015).

Year 2003 : 2 citations

 Complexity and approximability results for slicing floorplan designs,
VG Deneko, GJ Woeginger, European Journal of Operational Research, 2003

 Ernesto de Queirós Vieira Martins (1945-2000): An appreciation by Mário S. Rosa
Mário S. Rosa, Networks, Volume 41, Issue 4 , Pages 181 - 183, 2003

Year 2000 : 1 citations

 Stephen Lau Wong :"Cutting board machine computer aided nesting software system implementation","Computer Application" 2000-S1, China.