DNA Algorithm In Solving Job-shop Scheduling Problem

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