Identification of Promising Infant Clusters to Obtain Improved Block Layout Designs
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.
[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.
[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.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:72287", author = "Mustahsan Mir and Ahmed Hassanin and Mohammed A. Al-Saleh", title = "Identification of Promising Infant Clusters to Obtain Improved Block Layout Designs ", 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. ", volume = "10", number = "3", pages = "488-6", }
