Solving two-dimensional cutting stock problem via a DNA computing algorithm. (English) Zbl 1530.68087
Summary: 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.
MSC:
| 68Q07 | Biologically inspired models of computation (DNA computing, membrane computing, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 90C27 | Combinatorial optimization |
Keywords:
two-dimensional cutting stock problem; garment and leather industries; DNA computing; sticker modelReferences:
| [1] | Adleman, L., Molecular computation of solutions to combinatorial problems, Science, 11, 266, 1021-1023 (1994) · doi:10.1126/science.7973651 |
| [2] | Ahrabian, H.; Mirzaei, A.; Nowzari-dalini, A., A DNA sticker algorithm for solving N-queen problem, Int J Comput Sci Appl, 5, 2, 12-22 (2008) |
| [3] | Alves, C.; Brás, P.; de Carvalho, JV; Pinto, T., New constructive algorithms for leather nesting in the automotive industry, Comput Oper Res, 39, 7, 1487-1505 (2012) · doi:10.1016/j.cor.2011.08.021 |
| [4] | Arnold, MG; Cardelli, L.; Shih, W., An improved DNA-sticker addition algorithm and its application to logarithmic arithmetic, DNA computing and molecular programming, 34-48 (2011), Berlin: Springer, Berlin · Zbl 1347.68375 · doi:10.1007/978-3-642-23638-9_6 |
| [5] | Babaei, M., A novel text and image encryption method based on chaos theory and DNA computing, Nat Comput, 12, 1, 101-107 (2013) · Zbl 1334.68056 · doi:10.1007/s11047-012-9334-9 |
| [6] | Baldacci, R.; Boschetti, MA; Ganovelli, M.; Maniezzo, V., Algorithm for nesting with defects, Discrete Appl Math, 163, 1, 17-33 (2014) · Zbl 1303.90084 · doi:10.1016/j.dam.2012.03.026 |
| [7] | Bennell, JA; Cabo, M.; Martínez-Sykoraa, A., A beam search approach to solve the convex irregular bin packing problem with guillotine cuts, Eur J Oper Res, 270, 1, 89-102 (2018) · Zbl 1403.90562 · doi:10.1016/j.ejor.2018.03.029 |
| [8] | Chang, WL; Guo, M.; Ho, M.; Guo, M.; Yang, LT, Solving the set-splitting problem in sticker-based model, Parallel and distributed processing and applications, 185-196 (2003), Berlin: Springer, Berlin · Zbl 1038.68046 · doi:10.1007/3-540-37619-4_20 |
| [9] | Cheng, CH; Feiring, BR; Cheng, TCE, The cutting stock problem—a survey, Int J Prod Econ, 36, 3, 291-305 (1994) · doi:10.1016/0925-5273(94)00045-X |
| [10] | Chu, C.; Antonio, J., Approximate algorithms to solve real-life multicriteria cutting stock problems, Oper Res, 47, 4, 495-508 (1999) · Zbl 1041.90536 · doi:10.1287/opre.47.4.495 |
| [11] | Cui, Y.; Lu, Y., Heuristic algorithm for a cutting stock problem in the steel bridge construction, Comput Oper Res, 36, 2, 612-622 (2009) · Zbl 1157.90504 · doi:10.1016/j.cor.2007.10.019 |
| [12] | Darehmiraki, M.; Mishmast Nehi, H., Molecular solution to the 0-1 knapsack problem based on DNA computing, Appl Math Comput, 187, 2, 1033-1037 (2007) · Zbl 1114.65328 |
| [13] | Farley, AA, The cutting stock problem in the canvas industry, Eur J Oper Res, 44, 2, 247-255 (1990) · Zbl 0684.90080 · doi:10.1016/0377-2217(90)90360-N |
| [14] | Glass, CA; van Oostrum, JM, Bun splitting: a practical cutting stock problem, Ann Oper Res, 179, 1, 15-33 (2008) · Zbl 1205.90245 · doi:10.1007/s10479-008-0458-3 |
| [15] | Kallrath, J.; Rebennack, S.; Kallrath, J.; Kusche, R., Solving real-world cutting stock-problems in the paper industry: Mathematical approaches, experience and challenges, Eur J Oper Res, 238, 1, 374-389 (2014) · Zbl 1338.90233 · doi:10.1016/j.ejor.2014.03.027 |
| [16] | Kang, Z.; Xiaojun, T.; Jin, X., Closed circle DNA algorithm of change positive-weighted Hamilton circuit problem, Syst Eng Electron, 20, 3, 636-642 (2009) |
| [17] | Kari, L., DNA computing, sticker systems, and universality, Acta Inform, 35, 5, 401-420 (1998) · Zbl 0904.68127 · doi:10.1007/s002360050125 |
| [18] | Khullar S, Chopra V, Kahlon MS (2007) DNA computing: migrating from silicon chips to test tubes. In: National conference on challenges and opportunities in information technology |
| [19] | Lee, JY; Shin, SY; Park, TH; Zhang, BT, Solving traveling salesman problems with DNA molecules encoding numerical values, BioSystems, 78, 1-3, 39-47 (2004) · doi:10.1016/j.biosystems.2004.06.005 |
| [20] | Liu, X.; Yang, X.; Li, S.; Ding, Y., Solving the minimum bisection problem using a biologically inspired computational model, Theoret Comput Sci, 411, 6, 888-896 (2010) · Zbl 1191.68321 · doi:10.1016/j.tcs.2009.07.031 |
| [21] | Lu, HC; Huang, YH; Tseng, KA, An integrated algorithm for cutting stock problems in the thin-film transistor liquid crystal display industry, Comput Ind Eng, 64, 4, 1084-1092 (2013) · doi:10.1016/j.cie.2013.02.009 |
| [22] | Madsen, OBG, Glass cutting in a small firm, Math Program, 17, 1, 85-90 (1979) · Zbl 0403.90055 · doi:10.1007/BF01588227 |
| [23] | MirHassani, SA; Jalaeian Bashirzadeh, A., A GRASP meta-heuristic for two-dimensional irregular cutting stock problem, Int J Adv Manuf Technol, 81, 1-4, 455-464 (2015) · doi:10.1007/s00170-015-7107-1 |
| [24] | Ouyang, Q.; Kaplan, PD; Liu, S.; Libchaber, A., DNA solution of the maximal clique problem, Science, 363, 6432, 446-449 (1997) · doi:10.1126/science.278.5337.446 |
| [25] | Paul, S.; Sahoo, G., A DNA computing model to solve 0-1 integer programming problem, Appl Math Sci, 2, 50, 2921-2929 (2008) · Zbl 1188.90180 |
| [26] | Pérez-Jiménez J, Sancho-Caparrini F (2001) Solving knapsack problems in a sticker based model. In: DNA computing. s.l.: international workshop on DNA-based computers. pp 161-171 · Zbl 1065.68555 |
| [27] | Pérez-Jiménez, MJ; Sancho-Caparrini, F.; Pérez-Jiménez, MJ; Romero-Jiménez, A.; Sancho-Caparrini, F., Generating pairwise disjoint families through DNA computations, Recent results in natural computing, 231-246 (2005), Sevilla: Fénix Editora, Sevilla |
| [28] | Razzazi, M.; Roayaei, M., Using sticker model of DNA computing to solve domatic partition, kernel and induced path problems, Inf Sci, 181, 17, 3581-3600 (2011) · doi:10.1016/j.ins.2011.04.026 |
| [29] | Rodrigues, MO; Toledo, FMB, A clique covering MIP model for the irregular strip packing problem, Comput Oper Res, 87, 221-234 (2017) · Zbl 1391.90391 · doi:10.1016/j.cor.2016.11.006 |
| [30] | Roweis, S., A sticker-based model for DNA computation, J Comput Biol, 5, 4, 615-629 (1998) · doi:10.1089/cmb.1998.5.615 |
| [31] | Sanches, CAA; Soma, NY, A polynomial-time DNA computing solution for the bin-packing problem, Appl Math Comput, 215, 6, 2055-2062 (2009) · Zbl 1191.68309 |
| [32] | Sanches, CAA; Soma, NY, A computational DNA solution approach for the quadratic Diophantine equation, Appl Math Comput, 238, 436-443 (2014) · Zbl 1334.11094 |
| [33] | Taghipour, H.; Rezaei, M.; Esmaili, HA, Solving the 0/1 knapsack problem by a biomolecular DNA computer, Adv Bioinform (2013) · doi:10.1155/2013/341419 |
| [34] | Toledo, FMB, The dotted-board model: a new MIP model for nesting irregular shapes, Int J Prod Econ, 145, 2, 478-487 (2013) · doi:10.1016/j.ijpe.2013.04.009 |
| [35] | Tyagi, SK; Ghorpade, A.; Karunakaran, KP; Tiwari, MK, Optimal part orientation in layered manufacturing using evolutionary stickers-based DNA algorithm, Virtual Phys Prototyp, 2, 1, 3-19 (2007) · doi:10.1080/17452750701330968 |
| [36] | Wang, Z.; Pu, J.; Cao, L.; Tan, J., A parallel biological optimization algorithm to solve the unbalanced assignment problem based on DNA molecular computing, Int J Mol Sci, 16, 10, 25338-25352 (2015) · doi:10.3390/ijms161025338 |
| [37] | Winfree, E., DNA computing by self-Assembly, The Bridge, 33, 31-38 (2003) |
| [38] | Wood, DH, DNA computing capabilities for game theory, Nat Comput, 2, 1, 85-108 (2003) · doi:10.1023/A:1023332711880 |
| [39] | Xingpeng, J.; Yin, L.; Ya, M.; Dazhi, M., A new DNA alogorithm to solve graph coloring problem, Prog Nat Sci, 17, 6, 733-738 (2007) · Zbl 1276.92059 · doi:10.1080/10002007088537467 |
| [40] | Xu, J.; Dong, Y.; Wei, X., Sticker DNA computer model-part 1: theory, Chin Sci Bull, 49, 8, 772-780 (2004) · Zbl 1104.68510 |
| [41] | Xu, J.; Qiang, X.; Gang, F.; Zhou, K., A DNA computer model for solving vertex coloring problem, Chin Sci Bull, 51, 2541-2549 (2006) · doi:10.1007/s11434-006-2145-6 |
| [42] | Zhang H, Liu X (2016) A DNA sticker model for the hierarchical clustering problems. In: China, IEEE advanced information management, communicates, electronic and automation control conference (IMCEC) |
| [43] | Zimmermann, KH, Efficient DNA sticker algorithms for NP-complete graph problems, Comput Phys Commun, 144, 3, 297-309 (2002) · Zbl 1001.68092 · doi:10.1016/S0010-4655(02)00270-9 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
