Identification of Promising Infant Clusters to Obtain Improved Block Layout Designs

Authors: Mustahsan Mir, Ahmed Hassanin, Mohammed A. Al-Saleh

Abstract:

The layout optimization of building blocks of unequal areas has applications in many disciplines including VLSI floorplanning, macrocell placement, unequal-area facilities layout optimization, and plant or machine layout design. A number of heuristics and some analytical and hybrid techniques have been published to solve this problem. This paper presents an efficient high-quality building-block layout design technique especially suited for solving large-size problems. The higher efficiency and improved quality of optimized solutions are made possible by introducing the concept of Promising Infant Clusters in a constructive placement procedure. The results presented in the paper demonstrate the improved performance of the presented technique for benchmark problems in comparison with published heuristic, analytic, and hybrid techniques.

Keywords: Block layout problem, building-block layout design, CAD, optimization, search techniques.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1111873

References:

[1] J. Funke, S. Hougardy, J. Schneider, “An exact algorithm for wirelength optimal placements in VLSI design”, Integration, the VLSI Journal, July 2015.
[2] D. Y. Zaporozhets, D. V. Zaruba, and V. V. Kureichik. "Hierarchical Approach for VLSI Components Placement", Artificial Intelligence Perspectives and Applications, pp. 79-87, 2015.
[3] Y. Matsuoka and H. Zhao, "Multi-Objective Optimization Techniques for VLSI Placements", International Conference on IT Convergence and Security (ICITCS), 2014.
[4] C. Hoo, et. al., “Hierarchical congregated ant system for bottom-up VLSI placements”, Engineering Applications of Artificial Intelligence, Vol. 26, No. 1, pp. 584–602, Jan 2013.
[5] M. F. Anjos and F. Liers, "Global approaches for facility layout and VLSI floorplanning", Handbook on Semidefinite, Conic and Polynomial Optimization, Springer US, pp. 849-877, 2012.
[6] D. Hill, et al., “Algorithms and techniques for VLSI layout synthesis”, Springer Science & Business Media, Vol. 65, 2012.
[7] I. L. Markov, J. Hu, and M. C. Kim. "Progress and challenges in VLSI placement research”, IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 2012.
[8] B. S. Babu, R. R. Swetha, and K. A. S. Devi. "Comparison of hierarchical mixed-size placement algorithms for VLSI physical synthesis", International Conference on Communication Systems and Network Technologies (CSNT), 2011.
[9] S. Chen, S. Dong, X. Hong, Y. Ma and C.K. Cheng, “VLSI block placement with alignment constraints”, IEEE Trans. on Circuits and Systems, Vol. 53, No. 8, pp. 622-626, Aug. 2006.
[10] S.Y. Ho, S.J. Ho, Y.K. Lin, and W. C. Chu, “An orthogonal simulated annealing algorithm for large floorplanning problems”, IEEE Trans. on VLSI Systems Vol. 12, No. 8, pp. 874-877, Aug. 2004.
[11] J. Hou, Q. Zhou and X. Hong, “A Thermal-Driven Force-Directed Macro Cell Placement Algorithm,” International Conference on Communications, Circuits and Systems, pp. 2420-2423, June 2006.
[12] M. Mir, "Analytical technique for macrocell placement optimization with multiple constraints", 10th IEEE Int’l Conference on Electronics, Circuits and Systems, pp. 503-506, Dec. 14-17, 2003.
[13] M. Sarrafzadeh, M. Wang, and X. Yang. "Macro-Cell Placement," Modern Placement Techniques. Springer US, 2003. 159-174.
[14] M. Mir and M. Al-Saleh, “A constructive procedure for optimizing the placement of macrocells", Proceedings of 2001 IEEE Int’l. Symposium on Circuits and Systems, Vol. 5, pp. 57-60, 2001.
[15] J. F. Gonçalves, and M. C. Resende, “A biased random-key genetic algorithm for the unequal area facility layout problem”, European Journal of Operational Research, Vol. 246, No. 1, pp. 86-107, October 2015.
[16] I.A. Tasadduq, M.H. Imam, and A. Ahmad, “A hybrid algorithm for optimising facility layout”, South African Journal of Industrial Engineering, Vol 26, No. 1, pp 120-134, 2015.
[17] R. Matai, “Solving multi objective facility layout problem by modified simulated annealing,” Applied Mathematics and Computation, vol. 261, pp. 302–311, Jun. 2015.
[18] B. Ulutas and A. A. Islier, “Dynamic facility layout problem in footwear industry”, Journal of Manufacturing Systems, Vol. 36, pp. 55–61, July 2015.
[19] A. Tasadduq, M.H. Imam and A. Ahmad, “A novel adaptive boundary search algorithm for solving facility layout problems,” The 43rd Atlantic Schools of Business Conference, Canada, September 27-29, 2013.
[20] M. Mir and M. H. Imam, "A Hybrid Optimization Approach for Layout Design of Unequal-Area Facilities", Journal of Computers and Industrial Engineering, Vol. 39, pp. 49-63, 2001.
[21] W-C Chian, G. Mudunuri, G. Cai, W. Zhu and X. Xu, “Two-Stage Tabu-Particle Swarm Algorithms for Facility Layout Problem with Size Constraints,” IEEE Congress on Evolutionary Computation, pp. 1679-1686, June 2011.
[22] M. Al-Saleh, M. Mir, and A. Hassanin, “Comparison of Enhanced Constructive Layout Optimization Technique with Tabu-Search and Particle Swarm Optimization Methodologies”, Proceedings of 5th International IEOM Conference, pp. 475-481, UAE, March 3-5, 2015.
[23] P. Arikaran, V. Jayabalan and R. Senthilkumar, “Analysis of Unequal Areas Facility Layout Problems,” Intl. Journal of Engineering (IJE), Vol. 4, pp. 44-51, Jan. 2010.
[24] A. Drira, H. Pierreval and S. H. Gabouj, “Facility Layout Problems: A Survey,” Annual Reviews in Control, Vol. 31, pp. 255-267, 2007.
[25] S. P. Singh and R. R. K Sharma, “A Review of Different Approaches to the Facility Layout Problems,” Intl. J. Manufacturing Technology, Vol. 30, pp. 425-433, 2006.
[26] A. R. McKendall, J. Shang, and Kuppusamy, “Simulated Annealing Heuristics for the Dynamic Facility Layout Problem” Computers and Operations Research, Vol.33, pp. 2431-2444, 2006.
[27] P. S. Welgama and P. R. Gibson, “A construction algorithm for the machine layout problem with fixed pick-up and drop-off points”, International Journal of Production Research, Vol. 31, pp. 2575-2590, 1993.
[28] J. Balakrishnan, et al. "A hybrid genetic algorithm for the dynamic plant layout problem." International Journal of Production Economics 86.2 (2003): 107-120.
[29] P. Corry, and E. Kozan. "Ant colony optimisation for machine layout problems." Computational optimization and applications 28.3 (2004): 287-310.
[30] G. Moslemipour and T. S. Lee. "Intelligent design of a dynamic machine layout in uncertain environment of flexible manufacturing systems." Journal of Intelligent Manufacturing 23.5 (2012): 1849-1860.
[31] M. H. Imam and M. Mir, "Cluster Boundary Search Algorithm for Building-Block Layout Optimization", Journal of Advances in Engineering Software, Vol. 29, No. 2, pp. 165-173, 1998.
[32] D. G. Leunberger, Introduction to Linear and Non-linear Programming, Addison-Wesley, Massachusetts,1973.
[33] Engineering Optimization Software, VIP-PLANOPT: www.planopt.com
[34] A. R. Ahmad, O. Basir, K. Hassanein and M. H. Imam, “An effective module placement strategy for genetic algorithms based layout design”, International Journal of Production Research, 44, pp. 1545-1567, 2006.
[35] A. R. Ahmad, An intelligent expert system for decision analysis & support in multi-attribute layout optimization. PhD Thesis, University of Waterloo, Canada, 2005. Available online: https://uwspace.uwaterloo.ca/handle/10012/785.
[36] S. Kulturel-Konak and A. Konak, “Linear programming based genetic algorithm for the unequal area facility layout problem”, International Journal of Production Research, 51, pp. 4302-4324, 2013.
[37] S. K. Das, “A facility layout method for flexible manufacturing systems”, Int. J. Prod. Res., 31, pp. 279-297, 1993.
[38] M. H. Imam and M. Mir, “Nonlinear programming approach to automated topology optimization”, Computer Aided Design, 21, pp. 107-115, 1989.