New perspectives in VLSI design automation: deterministic packing by Sequence Pair

New perspectives in VLSI design automation: deterministic packing by Sequence Pair

0.00 Avg rating0 Votes
Article ID: iaor20106146
Volume: 179
Issue: 1
Start Page Number: 35
End Page Number: 56
Publication Date: Sep 2010
Journal: Annals of Operations Research
Authors: , ,
Keywords: packing
Abstract:

In the paper we consider a problem of packing rectangular blocks on a plane, which is known as Block Packing Problem (BPP). This problem is a central issue of the modern VLSI chips design methods. Basing on a new interpretation of the Sequence-Pair representation of the packing solution-space, which is based on Complementary Mirror Constraint Graphs (CMCG), we develop the efficient method of neighborhood exploration. This method might be able to improve the efficiency of other neighborhood-based search methods, such as simulated annealing or tabu search, as well as, to construct efficient heuristics. We illustrate application of the developed method by constructing a heuristic algorithm for solving BPP and comparing its efficiency and effectiveness to the algorithms commonly used so far.

Reviews

Required fields are marked *. Your email address will not be published.