Article Preview
TopIntroduction
The BPP can be simply described as follows: put a certain number of items into some boxes with the same volume, make the volume sum of the items in each box not exceed the volume of the box, and finally ensure that the number of the boxes used in the process is the least. It is a typical combinatorial optimization problem, and involved in many fields, especially in the field of computer science and industry, it has extensive application background, such as multi-processor scheduling, memory management, resource allocation, transportation plan and so on (Johnson, 1974), so the research of bin packing problem has wide application value.
Up to now, researchers have proposed many solutions and approximation algorithms to solve the BPP, such as the grouping genetic algorithm (Falkenauer, 1996), hybrid genetic algorithm (Reeves, 1996), Ant colony optimization(Levine & Ducatelle, 2004), the next adaptation, the first adaptation, the descending next fit, the best adaptation and so on (Coffman, Garey, & Johnson, 1996), whereas the results have a great relationship with the volume of the items when using these approximate algorithm to solve the problem with complex constraints.
However, the DNA self-assembly can solve the above problem in theory. DNA self-assembly is one of the most important applications of DNA computation, and the process is cost effective, versatile, facile, and the process occurs towards the system’s thermodynamic minima, resulting in stable and robust structures (Lehn, 1993). The relation of DNA computation with self-assembling structures was developed in the mid-1990s, largely through the theoretical and experimental work of Adleman (1994), Winfree, Eng, and Rozenberg (2001)Winfree (1998), Seeman (1998), Reif (2002), and Rozenberg and Spaink (2003). Because of its massive parallel computing function and large amounts of information storage ability, it has gradually become a mainstream method to solve the basic arithmetic problems and NP-Complete problems. For example, Arithmetic computation in the tile assembly model: Addition and multiplication (Brun, 2007), Arithmetic computation using self-assembly of DNA tiles: subtraction and division (Brun, 2008), Solving satisðability in the tile assembly model with a constant-size tileset (Zhang, Wang, Chen, Xu, & Cui, 2009), DNA self-assembly for the minimum vertex cover problem (Wang, Hu, Zhang, & Cui, 2011), DNA 3D self-assembly algorithmic model to solve the maximum clique problem (Ma, Li, & Dong, 2011), 3D DNA self-assembly model for graph vertex coloring (Lin, Xu, & Zhang, 2010), Application of DNA computing by self-assembly on 0-1 knapsack problem (Cui, Li, Zhang, Wang, Qi, Li, & Li, 2009), Application of DNA self-assembly on maximum clique problem (Cui, Li, Li, Zhang, & Li, 2009), DNA tile assembly model for 0-1 knapsack problem (Wang, Lu, Zhang, & Cui, 2010) and so on.
In this paper, we propose a DNA self-assembly model with a subtraction system for solving the Bin Packing problem. The rest of the paper is organized as follows: First we describe the basic knowledge and the mechanism of DNA self-assembly; we give the definition of the Bin Packing problem; we then show the DNA self-assembly model for solving the Bin Packing problem; finally, we give a conclusion.