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

Simple item page
dc.contributor.authorTian, Xiang
dc.contributor.authorLiu, Xiyu
dc.contributor.authorZhang, Hongyan
dc.contributor.authorSun, Minghe
dc.contributor.authorZhao, Yuzhen
dc.creator.orcidhttps://orcid.org/0000-0001-8503-9761en_US
dc.date.accessioned2023-04-03T17:00:40Z
dc.date.available2023-04-03T17:00:40Z
dc.date.issued2020-12-02
dc.description.abstractA 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(n2) 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.en_US
dc.description.departmentManagement Science and Statisticsen_US
dc.identifier.citationTian, X., Liu, X., Zhang, H., Sun, M., & Zhao, Y. (2020). A DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton model. PLOS ONE, 15(12), e0242083. doi:10.1371/journal.pone.0242083en_US
dc.identifier.issn1932-6203
dc.identifier.otherhttps://doi.org/10.1371/journal.pone.0242083
dc.identifier.urihttps://hdl.handle.net/20.500.12588/1810
dc.language.isoen_USen_US
dc.publisherPublic Library of Science (PLOS)en_US
dc.relation.ispartofseriesPLOS ONE, 15(12);
dc.rightsAttribution 3.0 United States*
dc.rights.urihttp://creativecommons.org/licenses/by/3.0/us/*
dc.titleA DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton modelen_US
dc.typeArticleen_US

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
Tian 2020 - A DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton model.pdf
Size:
2.31 MB
Format:
Adobe Portable Document Format
Description:
Download

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.86 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Carlos Alvarez College of Business Faculty Research