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: | Janiak Adam, Lichtenstein Maciej, Kozik Andrzej |
Keywords: | packing |
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.