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

Xiang Tian; Xiyu Liu; Hongyan Zhang; Minghe Sun; Yuzhen Zhao

doi:10.1371/journal.pone.0242083

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

PLoS One. 2020 Dec 2;15(12):e0242083. doi: 10.1371/journal.pone.0242083. eCollection 2020.

Authors

Xiang Tian¹, Xiyu Liu¹, Hongyan Zhang¹, Minghe Sun², Yuzhen Zhao¹

Affiliations

¹ Business School, Shandong Normal University, Jinan, China.
² College of Business, The University of Texas at San Antonio, San Antonio, TX, United States of America.

Abstract

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(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.

Publication types

Research Support, Non-U.S. Gov't

MeSH terms

Algorithms
Computer Simulation*
Computers
Computers, Molecular / trends*
DNA / genetics*
Heuristics
Humans

Substances

DNA

Grants and funding

This work was partly supported by the National Natural Science Foundation of China (Nos. 61876101, 61802234, 61806114), the Social Science Fund Project of Shandong (Nos. 11CGLJ22, 16BGLJ06), the Natural Science Foundation of the Shandong Province (No. ZR2019QF007), the Youth Fund for Humanities and Social Sciences, Ministry of Education (No. 19YJCZH244), the China Postdoctoral Special Funding Project (No. 2019T120607), and the China Postdoctoral Science Foundation Funded Project (Nos. 2017M612339, 2018M642695).