【作者】 朱红；

【导师】 王凤儒；

【作者基本信息】 哈尔滨理工大学 ， 计算机应用技术， 2003， 硕士

【摘要】 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序列上简单的计算。论文中只给出简单流程图和少数几个子程序。论文最后给出实验结果。更多还原

【Abstract】 Job-shop scheduling problem (which JSSP is short for) is a combinatorial optimum problem that is constrained with time, sequence and resource. It has been proven in theory that the JSSP is a classical NP-hard. DNA molecular biology technique is a method occurring recently to encode information by simulating the double helix structure of DNA and the Watson-Crick complementary condition. Evolutionary Computation, Neural Computation and DNA molecular biology technique are respectively corresponding to three different levels which are organism, nerve cell and molecular in the process of simulating brainpower. So we can see that the last method that base on simulating and studying on DNA of biology is more probably to show up the essence of formation of brainpower. DNA molecular biology algorithm has the advantages of huge parallelism and high computing speed; As a storage media of information, DNA has a huge capability. Storing information in molecules of DNA could allow for an information density of approximately 1 bit per cubic nanometer. The energy consumed by DNA molecular biology computing is billionth of that consumed by one conventional computer. The characteristics of DNA molecular biology computing mentioned above which are high parallelism, huge capability and low consumption are incomparable and irreplaceable to the existing computers and parallel ones. Thus, DNA computers become the aim people go after.First, this paper generally summarizes the study status of Job-shop scheduling problem, the idea and the study status of the DNA algorithm, the study status and existent problems of DNA algorithm in solving NP-hard and so on. Also, we present where our thesis comes from.Second, we present the DNA encoding method in solving Job-shop scheduling problem and the corresponding decoding method, recombination and frameshift mutation operators, and deadlock is also described in detail. DNA sequence can be seen as a character string including A, G, C and T which are like binary code ’0’ and ’1’ in computer science. Hence, strands of DNA are just sequences over the alphabet<WP=8>{A, G, C, T} in decoding information.Third, we present the DNA algorithm based on the encoding method mentioned above. DNA sequences can be used to encode information while enzymes can be employed to simulate simple computations. We only give the flow chart and few sub-procedures in the paper. We give the results of the experiment at the end of the paper.更多还原