An efficient, effective, and robust decoding heuristic for metaheuristics-based layout optimization

Abstract

This paper proposes a new effective and robust algorithm for solving the classic NP-complete rectangle packing problem that is often encountered in various layout design work domains. The complexity and subjectivity in most layout design applications indicate the need for providing advanced design and analysis support to layout designers in order to facilitate the procurement of a superior solution in a timely manner. An automated system for providing efficient and easy ways of generating and analysing superior layout alternatives seems to be a logical choice in this direction. In this regard, various metaheuristics are known to be effective solution techniques. However, the efficiency of such techniques is largely determined by the efficiency and efficacy of the decoding placement algorithms employed. Here we propose an efficient and robust placement algorithm and compare it with some popular existing algorithms. Various quantitative fitness metrics and subjective evaluation of the aesthetic value of layout solutions by design experts are employed in our comparison regime. Comparative studies demonstrate the superiority of the proposed algorithm in terms of speed and robustness. Notably, the proposed algorithm consistently furnishes layout alternatives carrying relatively high aesthetic values. Such efficient and robust placement algorithms are expected to facilitate an efficient and effective utilization of resources in layout design applications and to stimulate future research in associated areas.

Keywords:

• Packing problems
• Placement heuristics
• BL algorithm
• Facilities/VLSI layout design
• Metaheuristics

Acknowledgements

The authors are grateful to the anonymous referees whose insightful comments on an earlier version of this paper helped improve both content and presentation. Special thanks to an anonymous technical support specialist at VIP-PlanOpt™ (http://www.planopt.com) for resourceful electronic discourse culminating in an improved understanding of the structure of the problem. This research is partially supported by a strategic grant from National Sciences and Engineering Research Council of Canada.