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

Full description

Saved in:
Bibliographic Details
Published in:PloS one 2020-12, Vol.15 (12), p.e0242083-e0242083
Main Authors: Tian, Xiang, Liu, Xiyu, Zhang, Hongyan, Sun, Minghe, Zhao, Yuzhen
Format: Article
Language:English
Subjects:
Algorithms
Biology and life sciences
Business schools
Computation
Computer and Information Sciences
Computer Simulation
Computers
Computers, Molecular - trends
Data encryption
Deoxyribonucleic acid
DNA
DNA - genetics
Encoding (Memory)
Engineering and Technology
Genetic algorithms
Genetic research
Heuristic
Heuristics
Humans
Job shop scheduling
Job shops
Methods
Molecular computing
Mutation
Optimization
Physical Sciences
Problem solving
Research and Analysis Methods
Schedules
Scheduling
Social Sciences
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1932-6203
1932-6203
DOI:10.1371/journal.pone.0242083