Towards Quick Solutions for Generalized Placement Problem

摘要

The problem of placement is well known in Computer Aided Design (CAD) of VLSI Chips, DNA Micro arrays and Microfluidic biochips. Because of the similarity of the placement problem across diverse domains a generalization of the same is reported in the literature. The generalized placement problem is an instance of the classical Quadratic Assignment Problem (QAP). In this paper, we present a new randomization based heuristic algorithm for QAP. The key to success of the proposed technique is a novel probability distribution that is employed by the heuristics to generate the necessary randomization. We show through simulation results that the proposed algorithm finds competitive solutions comparable with one of the best heuristics reported in literature, while consuming significantly smaller amount of CPU time.