期刊
NATURAL COMPUTING
卷 20, 期 1, 页码 145-159出版社
SPRINGER
DOI: 10.1007/s11047-020-09786-3
关键词
Two-dimensional cutting stock problem; Garment and leather industries; DNA computing; Sticker model
类别
资金
- High Performance Computing Research Center, Amirkabir University of Technology
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据