Sloving Floorplanning And Three-dimensional Bin Packing Problems Based On Moving Modal Sequence And Memetic Algorithms

In recent years,the research on Bin Packing Problems has attracted increasing attentions,including one-dimensional, two-dimensional and three dimensional bin packing problems. We all knows,floorplanning is a two-dimensional bin packing problem,which is the key physical design to the Very Large Scale Integration and has an important impact on the size and overall structure of the chip interconnects.With the development of the technology,the chip design is increasingly complex and the internal interconnect performance requirements are also increasing,making floorplanning particularly important.For this problem,the algorithms had been researched rarely used evolutionary methods,here is a new coding method—MMS, which is short for Moving Modal Sequence,we use global search—Genetic Algorithm(GA) and local search-Tabu Search(TS) in order to optimize the problem.In the paper,we optimize the position of the components in accordance with floorplanning.We all know that floorplanning problems can be seen as the two-dimensional packing problems,thusing expanding the idea to the three-dimensional space in order to optimize the three-dimensional bin packing problem.The new coding method named 3D-MMS which is short for Three-dimensional Moving Modal Sequence.The outline of the paper is as follows.1.We apply the coding method that exists in floorplanning and view every component as a two-dimensional object,moving the module according to its movement mode. GA a kind of the evolutionary algorithm.Compared with traditional algorithms,GA has advantages of its universal、simple、 robust and parallel computing,but practical experiments show that GA is not enough to solve this kind problems.We should make the best use of every individual’s features,so we use memetic algorithm,applying TS into the framework of GA,for obtaining the best result.Experienments show the methods can find the best results quickly.2.Extending the MMS in the two-dimensional space to the three-dimension,we propose the 3D-MMS,which is a new method to solve the three-dimensional bin packing problems. In this part,we introduce the new method and its placement strategies.3.3D-BPP is an important problem in industrial production,such as pallet loading,ship loading,warehouse management and plane cargo management.In the process of transportation of goods,the efficient of the resources and space is the core competitive between companies.Based on this point,we use memetic algorithm which includes GA and Hill Climbing algorithm to solve 3D-BPP. Experienments show that the method has obvious advantages over others.