Journal
NATURAL COMPUTING
Volume 20, Issue 1, Pages 145-159Publisher
SPRINGER
DOI: 10.1007/s11047-020-09786-3
Keywords
Two-dimensional cutting stock problem; Garment and leather industries; DNA computing; Sticker model
Categories
Funding
- High Performance Computing Research Center, Amirkabir University of Technology
Ask authors/readers for more resources
The paper presents a DNA computing algorithm based on the sticker model to solve the two-dimensional cutting stock problem (TDCSP), proving that the time complexity of this algorithm on DNA computers is polynomial, taking into account the number of small pieces and the dimensions of the main board.
Two-dimensional cutting stock problem (TDCSP) is a well-known combinatorial optimization problem in which a given set of two-dimensional small pieces with different shapes should be cut from a given main board so that the demand of each small piece is satisfied and the total waste is minimized. Since TDCSP is an NP-complete problem, it is unsolvable in polynomial time on electronic computers. However, using the structure of DNA molecules, DNA computing algorithms are capable to solve NP-complete problems in polynomial time. In this paper, a DNA computing algorithm based on the sticker model is presented to find the optimal solution to TDCSP. It is proved that the time complexity of this algorithm on DNA computers is polynomial considering the number of small pieces and the length and width of the main board.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available