论文部分内容阅读
Job-shop调度问题（Job-shop Scheduling Problem，JSSP）是一类具有时间约束、次序约束和资源约束的组合优化问题。在理论上已经证明，JSSP是一个NP难题。DNA分子生物技术，这是一个最新发展起来的以模拟分子生物DNA的双螺旋结构和碱基互补配对规律进行信息编码的方法和技术。从遗传进化、人工神经网络和DNA分子生物技术对智能的模拟过程看，它们分别对应生物群体、生物神经元和生物分子三个截然不同的层次，由此可以看到，基于对分子生物DNA的模拟和研究将有可能更深刻地揭示智能形成的本质。DNA分子生物算法具有高度的并行性，运算速度快；DNA作为信息的载体其贮存的容量非常之大，1立方米的DNA溶液可存储1万亿亿的二进制数据；DNA分子生物计算所消耗的能量只有一台电子计算机完成同样计算所消耗的能量的十亿分之一；DAN计算的上述特性，即运算的高度并行性、大容量、低消耗是目前计算机和并行计算机所无法比拟和替代的。正因为如此，DNA计算机成为人们所追求的目标。首先，本文对Job-shop调度问题的研究现状、DNA算法的思想及其研究现状、DNA算法在NP难题方面的研究现状及存在的问题等方面进行全面综述，并提出课题的来源。其次，给出解决Job-shop调度问题的DNA编码方法和相应的解码、重组、框架转移变异方法，对死锁现象也进行了详细阐述。DNA链可看作由四个不同符号、、和组成的串，它在数学上就像计算机中的编码“0” 和“1”一样，可表示成四个字母的集合来译码信息。最后，给出基于该编码方法的DNA算法。DNA串可作为译码信息；酶可看作模拟在DNA序列上简单的计算。论文中只给出简单流程图和少数几个子程序。论文最后给出实验结果。