基于 Adleman-Lipton 模型的作业车间调度问题的 DNA 算法。
A DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton model.
机构信息
Business School, Shandong Normal University, Jinan, China.
College of Business, The University of Texas at San Antonio, San Antonio, TX, United States of America.
出版信息
PLoS One. 2020 Dec 2;15(12):e0242083. doi: 10.1371/journal.pone.0242083. eCollection 2020.
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.
提出了一种 DNA（脱氧核糖核酸）算法来解决作业车间调度问题。为该问题开发了一种编码方案，并为算法提出了 DNA 计算操作。在构建初始解决方案后，生成所有可能的解决方案。然后使用 DNA 计算操作来找到最佳计划。证明 DNA 算法的复杂度为 O(n2)，并且最佳计划的最终链长度在适当范围内。对 58 个基准实例的实验表明，所提出的 DNA 算法优于其他比较启发式算法。
Zotero 插件