A DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton model

A DNA (DeoxyriboNucleic Acid) algorithm is proposed to solve the job shop scheduling problem. An encoding scheme for the problem is developed and DNA computing operations are proposed for the algorithm. After an initial solution is constructed, all possible solutions are generated. DNA computing ope...

Descripción completa

Detalles Bibliográficos
Autores principales: Tian, Xiang, Liu, Xiyu, Zhang, Hongyan, Sun, Minghe, Zhao, Yuzhen
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Public Library of Science 2020
Materias:
Research Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7710087/
https://www.ncbi.nlm.nih.gov/pubmed/33264317
http://dx.doi.org/10.1371/journal.pone.0242083
Descripción
Sumario:A DNA (DeoxyriboNucleic Acid) algorithm is proposed to solve the job shop scheduling problem. An encoding scheme for the problem is developed and DNA computing operations are proposed for the algorithm. After an initial solution is constructed, all possible solutions are generated. DNA computing operations are then used to find an optimal schedule. The DNA algorithm is proved to have an O(n(2)) complexity and the length of the final strand of the optimal schedule is within appropriate range. Experiment with 58 benchmark instances show that the proposed DNA algorithm outperforms other comparative heuristics.

Ejemplares similares