nach oben

Natural Computing

Erschienen in:

07.03.2020

Solving two-dimensional cutting stock problem via a DNA computing algorithm

verfasst von: M. Dodge, S. A. MirHassani, F. Hooshmand

Erschienen in: Natural Computing | Ausgabe 1/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Evolving graphs with semantic neutral drift

Nächster Artikel DNAQL: a query language for DNA sticker complexes

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Adleman L (1994) Molecular computation of solutions to combinatorial problems. Science 11(266):1021–1023CrossRef

Ahrabian H, Mirzaei A, Nowzari-dalini A (2008) A DNA sticker algorithm for solving N-queen problem. Int J Comput Sci Appl 5(2):12–22

Alves C, Brás P, de Carvalho JV, Pinto T (2012) New constructive algorithms for leather nesting in the automotive industry. Comput Oper Res 39(7):1487–1505CrossRef

Arnold MG (2011) An improved DNA-sticker addition algorithm and its application to logarithmic arithmetic. In: Cardelli L, Shih W (eds) DNA computing and molecular programming. Springer, Berlin, pp 34–48CrossRef

Babaei M (2013) A novel text and image encryption method based on chaos theory and DNA computing. Nat Comput 12(1):101–107MathSciNetCrossRef

Baldacci R, Boschetti MA, Ganovelli M, Maniezzo V (2014) Algorithm for nesting with defects. Discrete Appl Math 163(1):17–33MathSciNetCrossRef

Bennell JA, Cabo M, Martínez-Sykoraa A (2018) A beam search approach to solve the convex irregular bin packing problem with guillotine cuts. Eur J Oper Res 270(1):89–102CrossRef

Chang WL, Guo M, Ho M (2003) Solving the set-splitting problem in sticker-based model. In: Guo M, Yang LT (eds) Parallel and distributed processing and applications. Springer, Berlin, pp 185–196CrossRef

Cheng CH, Feiring BR, Cheng TCE (1994) The cutting stock problem—a survey. Int J Prod Econ 36(3):291–305CrossRef

Chu C, Antonio J (1999) Approximate algorithms to solve real-life multicriteria cutting stock problems. Oper Res 47(4):495–508CrossRef

Cui Y, Lu Y (2009) Heuristic algorithm for a cutting stock problem in the steel bridge construction. Comput Oper Res 36(2):612–622CrossRef

Darehmiraki M, Mishmast Nehi H (2007) Molecular solution to the 0–1 knapsack problem based on DNA computing. Appl Math Comput 187(2):1033–1037MathSciNetMATH

Farley AA (1990) The cutting stock problem in the canvas industry. Eur J Oper Res 44(2):247–255CrossRef

Glass CA, van Oostrum JM (2008) Bun splitting: a practical cutting stock problem. Ann Oper Res 179(1):15–33CrossRef

Kallrath J, Rebennack S, Kallrath J, Kusche R (2014) Solving real-world cutting stock-problems in the paper industry: Mathematical approaches, experience and challenges. Eur J Oper Res 238(1):374–389CrossRef

Kang Z, Xiaojun T, Jin X (2009) Closed circle DNA algorithm of change positive-weighted Hamilton circuit problem. Syst Eng Electron 20(3):636–642

Kari L et al (1998) DNA computing, sticker systems, and universality. Acta Inform 35(5):401–420MathSciNetCrossRef

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

Lee JY, Shin SY, Park TH, Zhang BT (2004) Solving traveling salesman problems with DNA molecules encoding numerical values. BioSystems 78(1–3):39–47CrossRef

Liu X, Yang X, Li S, Ding Y (2010) Solving the minimum bisection problem using a biologically inspired computational model. Theoret Comput Sci 411(6):888–896MathSciNetCrossRef

Lu HC, Huang YH, Tseng KA (2013) An integrated algorithm for cutting stock problems in the thin-film transistor liquid crystal display industry. Comput Ind Eng 64(4):1084–1092CrossRef

Madsen OBG (1979) Glass cutting in a small firm. Math Program 17(1):85–90MathSciNetCrossRef

MirHassani SA, Jalaeian Bashirzadeh A (2015) A GRASP meta-heuristic for two-dimensional irregular cutting stock problem. Int J Adv Manuf Technol 81(1–4):455–464CrossRef

Ouyang Q, Kaplan PD, Liu S, Libchaber A (1997) DNA solution of the maximal clique problem. Science 363(6432):446–449CrossRef

Paul S, Sahoo G (2008) A DNA computing model to solve 0-1 integer programming problem. Appl Math Sci 2(50):2921–2929MATH

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

Pérez-Jiménez MJ, Sancho-Caparrini F (2005) Generating pairwise disjoint families through DNA computations. In: Pérez-Jiménez MJ, Romero-Jiménez A, Sancho-Caparrini F (eds) Recent results in natural computing. Fénix Editora, Sevilla, pp 231–246

Razzazi M, Roayaei M (2011) Using sticker model of DNA computing to solve domatic partition, kernel and induced path problems. Inf Sci 181(17):3581–3600MathSciNetCrossRef

Rodrigues MO, Toledo FMB (2017) A clique covering MIP model for the irregular strip packing problem. Comput Oper Res 87:221–234MathSciNetCrossRef

Roweis S et al (1998) A sticker-based model for DNA computation. J Comput Biol 5(4):615–629CrossRef

Sanches CAA, Soma NY (2009) A polynomial-time DNA computing solution for the bin-packing problem. Appl Math Comput 215(6):2055–2062MathSciNetMATH

Sanches CAA, Soma NY (2014) A computational DNA solution approach for the quadratic Diophantine equation. Appl Math Comput 238:436–443MathSciNetMATH

Taghipour H, Rezaei M, Esmaili HA (2013) Solving the 0/1 knapsack problem by a biomolecular DNA computer. Adv Bioinform. https://doi.org/10.1155/2013/341419CrossRef

Toledo FMB et al (2013) The dotted-board model: a new MIP model for nesting irregular shapes. Int J Prod Econ 145(2):478–487CrossRef

Tyagi SK, Ghorpade A, Karunakaran KP, Tiwari MK (2007) Optimal part orientation in layered manufacturing using evolutionary stickers-based DNA algorithm. Virtual Phys Prototyp 2(1):3–19CrossRef

Wang Z, Pu J, Cao L, Tan J (2015) A parallel biological optimization algorithm to solve the unbalanced assignment problem based on DNA molecular computing. Int J Mol Sci 16(10):25338–25352CrossRef

Winfree E (2003) DNA computing by self-Assembly. The Bridge 33:31–38

Wood DH (2003) DNA computing capabilities for game theory. Nat Comput 2(1):85–108CrossRef

Xingpeng J, Yin L, Ya M, Dazhi M (2007) A new DNA alogorithm to solve graph coloring problem. Prog Nat Sci 17(6):733–738CrossRef

Xu J, Dong Y, Wei X (2004) Sticker DNA computer model-part 1: theory. Chin Sci Bull 49(8):772–780MATH

Xu J, Qiang X, Gang F, Zhou K (2006) A DNA computer model for solving vertex coloring problem. Chin Sci Bull 51:2541–2549MathSciNetCrossRef

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)

Zimmermann KH (2002) Efficient DNA sticker algorithms for NP-complete graph problems. Comput Phys Commun 144(3):297–309MathSciNetCrossRef

Titel: Solving two-dimensional cutting stock problem via a DNA computing algorithm
verfasst von: M. Dodge
S. A. MirHassani
F. Hooshmand
Publikationsdatum: 07.03.2020
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 1/2021
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-020-09786-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2021

DNAQL: a query language for DNA sticker complexes

A novel hybrid BPSO–SCA approach for feature selection

An enhanced monarch butterfly optimization with self-adaptive crossover operator for unconstrained and constrained optimization problems

Evolving graphs with semantic neutral drift

Ensemble learning based on fitness Euclidean-distance ratio differential evolution for classification

Integrated probability multi-search and solution acceptance rule-based artificial bee colony optimization scheme for web service composition