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
_version_ 1783617876471578624
author Tian, Xiang
Liu, Xiyu
Zhang, Hongyan
Sun, Minghe
Zhao, Yuzhen
author_facet Tian, Xiang
Liu, Xiyu
Zhang, Hongyan
Sun, Minghe
Zhao, Yuzhen
author_sort Tian, Xiang
collection PubMed
description 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.
format Online
Article
Text
id pubmed-7710087
institution National Center for Biotechnology Information
language English
publishDate 2020
publisher Public Library of Science
record_format MEDLINE/PubMed
spelling pubmed-77100872020-12-03 A DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton model Tian, Xiang Liu, Xiyu Zhang, Hongyan Sun, Minghe Zhao, Yuzhen PLoS One Research Article 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. Public Library of Science 2020-12-02 /pmc/articles/PMC7710087/ /pubmed/33264317 http://dx.doi.org/10.1371/journal.pone.0242083 Text en © 2020 Tian et al http://creativecommons.org/licenses/by/4.0/ This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) , which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
spellingShingle Research Article
Tian, Xiang
Liu, Xiyu
Zhang, Hongyan
Sun, Minghe
Zhao, Yuzhen
A DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton model
title A DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton model
title_full A DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton model
title_fullStr A DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton model
title_full_unstemmed A DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton model
title_short A DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton model
title_sort dna algorithm for the job shop scheduling problem based on the adleman-lipton model
topic Research Article
url 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
work_keys_str_mv AT tianxiang adnaalgorithmforthejobshopschedulingproblembasedontheadlemanliptonmodel
AT liuxiyu adnaalgorithmforthejobshopschedulingproblembasedontheadlemanliptonmodel
AT zhanghongyan adnaalgorithmforthejobshopschedulingproblembasedontheadlemanliptonmodel
AT sunminghe adnaalgorithmforthejobshopschedulingproblembasedontheadlemanliptonmodel
AT zhaoyuzhen adnaalgorithmforthejobshopschedulingproblembasedontheadlemanliptonmodel
AT tianxiang dnaalgorithmforthejobshopschedulingproblembasedontheadlemanliptonmodel
AT liuxiyu dnaalgorithmforthejobshopschedulingproblembasedontheadlemanliptonmodel
AT zhanghongyan dnaalgorithmforthejobshopschedulingproblembasedontheadlemanliptonmodel
AT sunminghe dnaalgorithmforthejobshopschedulingproblembasedontheadlemanliptonmodel
AT zhaoyuzhen dnaalgorithmforthejobshopschedulingproblembasedontheadlemanliptonmodel

Ejemplares similares