==== Front PLoS One PLoS One plos plosone PLoS ONE 1932-6203 Public Library of Science San Francisco, CA USA 10.1371/journal.pone.0242083 PONE-D-20-17896 Research Article Computer and Information Sciences Computing Systems Molecular Computing Physical Sciences Mathematics Applied Mathematics Algorithms Research and Analysis Methods Simulation and Modeling Algorithms Physical Sciences Mathematics Optimization Engineering and Technology Management Engineering Management Planning and Control Gantt Charts Computer and Information Sciences Computers Physical Sciences Mathematics Discrete Mathematics Combinatorics Biology and life sciences Molecular biology Molecular biology techniques DNA construction DNA manipulations DNA separation Research and analysis methods Molecular biology techniques DNA construction DNA manipulations DNA separation Social Sciences Economics Labor Economics Employment Jobs A DNA algorithm for the job shop scheduling problem based on the Adleman-Lipton model A DNA algorithm for the job shop scheduling problemhttps://orcid.org/0000-0001-5507-8284Tian Xiang ConceptualizationInvestigationMethodologySoftwareVisualizationWriting – original draftWriting – review & editing1 Liu Xiyu ConceptualizationFunding acquisitionMethodologySupervision1* Zhang Hongyan Formal analysisMethodologyValidation1 Sun Minghe SupervisionValidationWriting – review & editing2 Zhao Yuzhen ValidationWriting – review & editing1 1 Business School, Shandong Normal University, Jinan, China 2 College of Business, The University of Texas at San Antonio, San Antonio, TX, United States of America Lin Shih-Wei Editor Chang Gung University, TAIWAN Competing Interests: The authors have declared that no competing interests exist. * E-mail: xyliu@sdnu.edu.cn 2 12 2020 2020 15 12 e024208316 6 2020 27 10 2020 © 2020 Tian et al2020Tian et alThis is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.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. http://dx.doi.org/10.13039/501100001809National Natural Science Foundation of China61876101Liu Xiyu http://dx.doi.org/10.13039/501100001809National Natural Science Foundation of China61802234http://dx.doi.org/10.13039/501100001809National Natural Science Foundation of China61806114Zhao Yuzhen Social Science Fund Project of Shandong11CGLJ22Social Science Fund Project of Shandong16BGLJ06http://dx.doi.org/10.13039/501100007129Natural Science Foundation of Shandong ProvinceZR2019QF007Youth Fund for Humanities and Social Sciences, Ministry of Education19YJCZH244Zhang Hongyan China Postdoctoral Special Funding Project2019T120607Zhao Yuzhen http://dx.doi.org/10.13039/501100002858China Postdoctoral Science Foundation2017M612339http://dx.doi.org/10.13039/501100002858China Postdoctoral Science Foundation2018M642695Zhao Yuzhen This work was partly supported by the National Natural Science Foundation of China (Nos. 61876101, 61802234, 61806114), the Social Science Fund Project of Shandong (Nos. 11CGLJ22, 16BGLJ06), the Natural Science Foundation of the Shandong Province (No. ZR2019QF007), the Youth Fund for Humanities and Social Sciences, Ministry of Education (No. 19YJCZH244), the China Postdoctoral Special Funding Project (No. 2019T120607), and the China Postdoctoral Science Foundation Funded Project (Nos. 2017M612339, 2018M642695). Data AvailabilityAll relevant data are within the manuscript and its Supporting Information files.Data Availability All relevant data are within the manuscript and its Supporting Information files. ==== Body 1. Introduction It is well known that the traditional silicon-based computers use serial algorithms, so that their computing speed cannot qualitatively leap. It is also well known that optimal solutions of most of the celebrated computationally intractable problems can only be found by an exhaustive search through all possible solutions. However, the insurmountable difficulty lies in the fact that such an exhaustive search is too vast to carry out using currently available computing technology, so that numerous intractable problems cannot be solved effectively. Some visionary remarks were made about new ways of solving such problems through possible miniaturizations. Feynman’s view [1] was widely accepted, stating the possibility of establishing “sub-microscopic” computers. Since then, although significant progresses have been made in relation to computer miniaturization, the goal of sub-microscopic computers has not yet been achieved. As a new interdisciplinary area, DNA computing has received increasing attentions. Massive parallelism and huge storage capacity are two significant advantages of DNA computing. Parallelism means DNA computing can perform billions of operations simultaneously. Furthermore, DNA computers can solve more intractable problems, such as non-deterministic polynomial-time) (NP)-hard problems, in linear time, as compared with conventional electronic computers in exponential time. In addition, the high density of data stored in DNA strands and the ease in duplicating them can make such exhaustive searches possible. Adleman’s experiment [2] solved the Hamiltonian Path Problem for a given directed graph, and demonstrated the strong parallel computing power of DNA computing. Lipton’s DNA-based solution of the satisfiability problem [3] used some of Adleman’s basic operations. Indeed, it used an exhaustive search that was made computationally feasible by the massive parallelism of the DNA strands. Ouyang et al. [4] turned the maximal clique problem, another NP-complete problem, into the maximum independent set problem, and solved the problem with six vertices in the laboratory by using the parallel overlap assembly technology. Roweis et al. [5] introduced a new DNA computing model, i.e., the sticker model, and used this model to solve the minimal set cover problem and the data encryption problem. Furthermore, the self-assembly model [6], the hairpin model [7] and the surface-based model [8, 9] had already been proposed and built. Among the many DNA computing models mentioned above, the Adleman-Lipton model and the sticker model are most widely used in solving classical combinatorial optimization problems. There are numerous publications in the literature addressing the combinatorial optimization problems using the Adleman-Lipton model. For example, Xiao et al. [10] solved maximum cut problems using the Adleman-Lipton model with O(n2) steps. Hsieh et al. [11] solved the graph isomorphism problem with the Adleman-Lipton model with stickers using a polynomial number of basic biological operations. Yang et al. [12] proposed a theoretical DNA algorithm to solve the quadratic assignment problem using the Adleman-Lipton-sticker model, which was executed with an O(kn4) complexity and could handle the medium-sized cases. Nehi and Hamidi [13] corrected and further improved the DNA model proposed by Yang et al. [12]. Wang et al. [14] solved a traveling salesman problem by a DNA algorithm using the Adleman-Lipton model with an O(n) complexity. Based on the Adleman- Lipton model, Wang et al. [15] proposed a new DNA computing algorithm to tackle the capacitated vehicle routing problem with an O(n2) complexity. In accordance with the processing order, the shop scheduling problem can typically be divided into three categories: the flow shop scheduling problem (FSSP), the job shop scheduling problem (JSSP) and the flexible job shop scheduling problem (FJSP). These three categories of problems are all about scheduling n jobs with varying processing times on m machines with varying speeds and capacities. In a JSSP, each job to be processed contains multiple operations, each of which is processed on a specified machine, and each job has a different machining path. In a FSSP, all jobs have the same machining path, i.e., the same operation sequence, without distinction between the operation and the machine. In a FJSP, the machining paths of the jobs are not necessarily the same and a job is allowed to be processed by any machine in a given set of machines. Many heuristic approaches have been developed to solve shop scheduling problems, such as particle swarm optimization (PSO), genetic algorithms (GA), simulated annealing (SA), tabu search (TS), artificial immune (AI), differential evolution algorithm (DEA), and ant colony optimization (ACO), among others, as well as their hybrids [16]. Mohamed Kurdi [17] proposed an effective genetic algorithm with a critical-path-guided Giffler and Thompson crossover operator (GA-CPG-GT) for JSSP. Zhou et al. [18] presented a hybrid social-spider optimization algorithm with a differential mutation (SSO-DM) operator to solve JSSP. Cruz-Chávez et al. [19] proposed a parallel algorithm that generated a set of parallel working threads, where each thread performed a simulated annealing process to solve JSSP. For JSSP, Pongchairerks [20] proposed a new two-level meta-heuristic algorithm composed of an upper-level algorithm and a lower-level algorithm. However, due to the premature and local convergence of GA, its performance in dealing with complex JSSP is limited [21]. The particle swarm optimization (PSO) algorithm cannot effectively search the entire solution space, and may converge to a local optimal solution prematurely, and thus cannot achieve a good exploration- exploitation balance [22]. The quality of the optimal solution obtained by TS lies on the initial solution [23]. Due to the lack of memory function in SA, it may lead to repeated searches and easily fall into local optima, greatly affecting the effectiveness of SA and causing excessive search time [23]. Due to the dependence on random natural selection and recombination, the optimization results obtained by classical evolutionary algorithm are still limited [24]. Also due to the stubborn nature of JSSP, a single meta-heuristic method can no longer solve this problem well [18]. In addition, these heuristic approaches do not traverse all possible solutions, and can only find relatively good solutions through operations such as crossover, mutation and iteration. Even if a heuristic finds the optimal solution, the heuristic itself cannot prove that the solution it found is the actual optimal solution. By contrast, DNA computing may be used to solve the JSSP. As long as appropriate encoding and manipulation are used, all possible solutions to the problem can be produced in one step. Deaton et al. [25] summarized three basic steps in using DNA computing to solve a problem: encoding, interaction and extraction. The first step is the basis of the other two steps, so that the key and the difficult part of DNA computing is to transform the problem into an equivalent DNA computing model by mapping. Until now, there is not much reported research on solving JSSPs using DNA computing. Yin et al. [26] solved a FSSP using DNA computing by transforming the FSSP problem into a directed graph. Wang et al. [27] proposed a new parallel DNA algorithm to solve the task scheduling problem based on the Adleman-Lipton model, with an enlightening idea. In this work, an appropriate encoding strategy is developed first to generate all possible solutions in parallel using DNA computing. The advantage of this encoding is that, once a scheduling sequence is determined, the makespan corresponding to each schedule is also determined. Theoretically efficient and parallel DNA algorithms based on Adleman-Lipton model are then proposed for solving the JSSP which can be solved with an O(n2) complexity. In the experiments, the DNA computing algorithms proposed in this work is simulated through two tool libraries of Python. Simulation experiments with 58 benchmark instances show that the proposed DNA algorithm outperforms other comparative heuristics. The remainder of this paper is organized as follows. Section 2 describes the Adleman-Lipton model and describes the JSSP. Section 3 proposes a DNA algorithm for the JSSP and provides a performance analysis of the proposed DNA algorithm. Section 4 reports the experimental results of the proposed DNA algorithm and the comparison with several heuristic algorithms on 58 benchmark instances. Section 5 concludes this work with a summary and future research directions. 2. Preliminaries This section is composed of two parts. The first part explains the Adleman-Lipton model, and the second part gives a formal description of the JSSP. 2.1 The Adleman-Lipton model DNA is a polymer which is strung together from monomers called deoxyribonucleotides [28]. A single strand DNA molecule consists of a sequence of nucleotides with four different bases, i.e., adenine, guanine, cytosine and thymine, abbreviated as A, G, C and T, respectively. Every strand, according to its chemical structure, has a 5'-3' direction or a 3'-5' direction, with the 5'-end matching the 3'-end. In the double strand molecule, the two single strands have opposite directions. Using the Watson-Crick complementarity, i.e., the A-T pairing and the G-C pairing, without other possible pairings, a double strand DNA molecule can be formed under appropriate conditions. For instance, the single strand 5'-ACGTTA-3' and its complement 3'-TGCAAT-5' can form a double strand, also referred to as a duplex. Assume the upper strand runs from left to right in the 5'-3' direction, and consequently the lower strand runs from left to right in the 3'-5' direction. The complement 3'-TGCAAT-5' of the strand 5'-ACGTTA-3' is denoted by ACGTTA¯. The length of a single strand DNA molecule is the number of nucleotides in the molecule. Thus a single strand consisting of 12 nucleotides is said to be a 12 mer, i.e., a polymer consisting of 12 monomers. The Adleman-Lipton model A test tube is a set of molecules of DNA, i.e., a multi-set of finite strings over the alphabets {A, G, C, T}. The following operations can be performed: Merge (N1,N2,…,Nk): given k test tubes N1,N2,…,Nk, this operation pours the DNA solution in each of the test tubes N2,…,Nk into test tube N1. The uniform mixed solution is referred to as N1. Amplify(N1,N2,…,Nk): given a test tube N1, this operation creates copies of N1 and amplifies them into test tubes N2,…,Nk. Separation (N1, X, N2): given a test tube N1 and a string X, this operation transfers all the single strands containing string X in test tube N1 to test tube N2. The single DNA strands removed from test tube N1 are no longer contained in test tube N1. If N1 does not contain X, this operation does nothing. Selection (N1, L, N2): given a test tube N1 and an integer L, this operation filters all DNA strands of length L in N1 and put them into test tube N2. Consequently, N1 no longer contains these filtered DNA strands. Append-head(N,S): given a test tube N and a single strand S, this operation attaches (pastes) S to the front of every strand in N. Append-tail (N,R): given a test tube N and a single strand R, this operation attaches (pastes) R to the end of every strand in N. Annealing (N): given a test tube N with some single strands, this operation derives all possible double strands according to the Watson-Crick complementarity pairing principle, leaves them in N, and removes the other single strands from N. Denaturation (N): given a test tube N, this operation separates every double-stranded DNA molecule into two single strands by heating without breaking the phosphodiester bond of each single strand. Briefly, the double-stranded DNA in N is separated as follows [EFEF¯]⇒[EF],[EF¯]. Cutting (N, ω1ω2): given a test tube N and strings with ω1ω2, this operation divides every strand containing [ω1ω2] in N to different strands as follows [⋯αω1ω2βω1ω2γ⋯]⇒[⋯αω1],[ω2βω1],[ω2γ⋯], where ω1ω2 corresponds to the recognition site of the cutting operation. Discard (N): given a test tube N, this operation clears all strands in N, that is, emptying N. Read (N): given a test tube N, this operation obtains the precise DNA sequences of all strands in N. Sort (N1,N2,N3): given a test tube N1 and two empty test tubes N2 and N3, this operation chooses the shortest strands in N1 and puts them in N2, chooses the longest strands in N1 and puts them in N3, and keeps the rest of the strands in N1. Ligation (N): given a test tube N, this operation links all the DNA molecules (double strands) in N together by enzymes called ligases. Detect (N): given a test tube N, this operation returns “true” if N contains at least one DNA strand, and returns “false” otherwise. T: = B(N,ω): given a test tube N and a string ω, this operation produces the test tube T consisting of all strands in N which begin with the string ω. L: = Length(N,ω,Ω): given a test tube N, this operation returns the length L of the specific single strand beginning with the string ω and ending with the string Ω in N. In actual biological experiments, the above operations are feasible and achievable. Take the Sort(N1, N2, N3) operation as an example. In gel electrophoresis, the migration speed of DNA strands is related to its own length. The longer the strand, the slower the migration speed. Therefore, through gel electrophoresis experiments, the longest and shortest DNA strands in the test tube can be obtained. Since all operations mentioned above can be performed in lab within constant biological steps, it is reasonable to assume that the complexity of each operation is O(1). In previous works ([10–12, 14, 15, 27]), many researchers have used this same approach to analyze the complexity of DNA computing algorithms. Therefore, the same approach is used in this study. 2.2 The job shop scheduling problem The JSSP is already known as a typical NP-hard problem [29]. An n × m JSSP can be formally described as follows [30]. There are n jobs and m machines denoted as J = (J1, J2, ⋯,Jn) and M = (M1, M2, ⋯,Mm), respectively. Each job must be processed (or handled) through all m machines to fulfil its processing tasks. The processing of a job is also called an operation. Each job requires m operations. Only one machine is required for each operation, and only one operation can be handled on one of the m machines. Once started on a specified machine, an operation is not allowed to be interrupted until the processing of the job is completed, meaning that each operation begins only when all its previous operations are finished, i.e., preemption is not allowed. The processing time and the sequence of operations, i.e., the machining paths are given in advance. The goal of a JSSP is to find the optimal schedule in order to minimize the maximum makespan. A JSSP with n jobs and m machines has (n!)m possible solutions. The notations used for the mathematical description of the JSSP are given below. n and m denote the numbers of jobs and machines, respectively. Oi,j represents the operation i of job j, where i ∈ [1, m] and j ∈ [1, n]. ti,j represents the processing time of Oi,j. TJi,j represents the completion time of Oi,j, i.e., the cumulative completion time of job j up to operation i. TMi,j represents the earliest start time of Oi,j, i.e., the cumulative time (not including ti,j) of machine i before job j starts. The mathematical programming model of the JSSP is given in the following. Min(Max1≤j≤n(TJm,j))(1) Subject to TJi−1,j+ti,j≤TJi,j,fori∈[1,m]andj∈[1,n](2) TMi,j+ti,j≤TJi.j,fori∈[1,m]andj∈[1,n](3) TJij≥0,TMij≥0,fori∈[1,m]andj∈[1,n].(4) The objective function minimizes the makespan, i.e., the maximum completion time. Constraint (2) represents precedence relationship between the operations. Constraint (3) means that preemption is not allowed. Constraint (4) gives the domains of the variables. Example 1 Table 1 shows a n × m = 4 × 2 FSSP example with 4 jobs J1, J2, J3 and J4 and 2 machines M1 M1 and M2. The jobs have the same operation sequence, i.e., the same machining path, where they first pass through machine 1 (M1) and then pass through machine 2 (M2). The time needed by each job on each machine is shown in the table. 10.1371/journal.pone.0242083.t001Table 1 A n × m = 4 × 2 FSSP. Machine Job J1 J2 J3 J4 M1 15 8 6 12 M2 4 10 5 7 Example 2 Table 2 shows a n × m = 3 × 3 JSSP example with 3 jobs J1, J2 and J3, each with a different machining path, processed on 3 machines, M1, M2 and M3. The machines required are shown in the column Mi and the time needed by each job on each machine is shown in the column ti,j. For instance, the 1st operation of job 1 (J1), i.e., O1,1, is processed on machine 3 (M3) and the processing time corresponding to O1,1 is t1,1 = 7 units. The 2nd operation of job 1 (J1), i.e., O2,1, is processed on machine 1 (M1) and the processing time corresponding to this operation is t2,1 = 4 units, and so on. 10.1371/journal.pone.0242083.t002Table 2 A n × m = 3 × 3 JSSP. i J1 J2 J3 Mi ti,1 Mi ti,2 Mi ti,3 1 3 7 2 5 2 4 2 1 4 3 6 1 2 3 2 2 1 3 3 3 From the two examples above, it is intuitive that the JSSP is an extension of the FSSP. The biggest difference between a JSSP and a FSSP lies in the machining paths of the jobs, as shown in Tables 1 and 2. As compared with the FSSP as shown in Table 1, the machining paths of the jobs are different from each other in a JSSP as shown in Table 2. If all the jobs have the same machining path, i.e., each job needs the same operations, without distinction between the operations and the machines, the JSSP becomes a FSSP. As compared with FSSP, JSSP is much more complicated and closer to the practical problems in production. In a FSSP, only one time matrix is needed. However, in a JSSP, two matrices are required, one represents the processing time and the other represents the machines needed by the jobs. Therefore, this work focuses on the more practical and representative JSSP for an in-depth study. 3. A DNA algorithm for the job shop scheduling problem Encoding is the key and difficult part of solving the combinatorial optimization problem with DNA computing. Therefore, this section starts with the coding scheme and then gives an overview of the proposed algorithm. The detailed algorithm is finally presented. 3.1 Encoding A schedule, or scheduling sequence, of an n × m JSSP can be denoted by OP1−OP2−⋯OPn×m, where OPi∈[1, n] indicates a job number. In this schedule, the ith appearance of job j indicates operation i of job j, i.e., Oi,j. Each number OPi appears exactly m times. Take a scheduling sequence 1-3-2-2-1-3-3-1-2 of a 3 × 3 JSSP as an example. The first number ‘1’ indicates operation 1 of job 1; the second number ‘3’ indicated operation 1 of job 3. The fourth number ‘2’ (the 2nd appearance of job 2) indicates operation 2 of job 2. Similarly, the seventh number ‘3’ (the 3rd appearance of job 3) indicates operation 3 of job 3. Obviously, once a scheduling sequence is determined, the makespan corresponding to this schedule is uniquely determined. For example, referring to the data in Table 2 in Example 2, the completion times or makespans of the 3 jobs can be easily calculated. The completion times of jobs 1, 2 and 3 are 13, 18 and 18, respectively. Consequently, the makespan (completion time) for this schedule is 18. Fig 1 in the following shows this schedule as a Gantt chart. 10.1371/journal.pone.0242083.g001Fig 1 A Gantt chart for the schedule 1-3-2-2-1-3-3-1-2 of Example 2. Effective encoding needs to be used to reasonably map real problems to DNA molecular computing models, and to generate all possible solutions in parallel in one step. In the following, p, Ei, q, Fj are used to represent different DNA single strands with the same length, e.g., u mer, with u as a positive integer. The notations p and q are used for DNA ligation, as defined in Section 2.2, and Ei and Fj represent the single strands for operation i and job j, respectively. The single strand pEiqFj can be used to indicate operation i of job j, i.e., Oi,j. In this way, all (n!)m possible solutions can be easily generated. Example 3 Table 3 shows a n × m = 5 × 6 JSSP example with 5 jobs, each with a different machining path, processed on 6 machines. Data for each job are shown in two columns in the table. The first column shows the corresponding machine number and the second column shows the time needed by the job on each machine. 10.1371/journal.pone.0242083.t003Table 3 A n × m = 5 × 6 JSSP. i J1 J2 J3 J4 J5 Mi ti,1 Mi ti,2 Mi ti,3 Mi ti,4 Mi ti,5 1 3 3 2 6 3 1 4 7 5 6 2 1 10 3 8 4 5 1 4 2 10 3 2 9 5 1 6 5 3 4 3 7 4 4 5 6 5 1 5 2 3 6 8 5 6 3 1 3 2 9 5 1 1 5 6 5 10 4 3 5 1 6 3 4 4 Fig 2 in the following is an optimal scheduling sequence of this 5×6 JSSP. It means that the jobs are processed in the order of 5-4-2-1-3 for the 1st operation, in the order of 5-2-1-4-3 for the 2nd operation, and so on, where the number ‘0’ in the middle represents a separator. The same job processed by different machines are identified with the same color. A DNA encoding method based on scheduling sequences is proposed below. 10.1371/journal.pone.0242083.g002Fig 2 An optimal schedule of the 5×6 JSSP in Example 3. In accordance with Algorithm 1, the DNA strands {pE1qF5pE1qF4pE1q- F2pE1qF1pE1qF3} will be generated to denote that the jobs are processed in the order of 5-4-2-1-3 in the 1st operation. In this way, DNA strands can be obtained to denote all n jobs in every operation. By encoding the jobs in this manner, all (n!)m possible schedules will be obtained. Fig 3 in the following is the optimal schedule presented as a Gantt chart corresponding to the optimal scheduling sequence given above in Fig 2, where the maximum completion time, i.e., the makespan, of this schedule is 45. The result 45 is calculated using the data in Table 3. 10.1371/journal.pone.0242083.g003Fig 3 Gantt chart of an optimal schedule of the 5×6 JSSP in Example 3. In JSSP, different jobs may require the same machine in some operations, so that some jobs may have to wait for others to finish before being processed and machines may become idle while having to wait for jobs to come. Different schedules have different job and machine waiting times and might have different makespans. The advantage of this encoding is that, once a scheduling sequence, i.e., a schedule, is determined, the makespan corresponding to this schedule is also uniquely determined. However, it should be noted that the makespan is, but the corresponding scheduling sequences may not be, unique. 3.2 An outline of the algorithm The basic idea of this DNA algorithm for solving the JSSP is to find an optimal solution by checking all possible solution candidates. This brute force approach is realized through DNA computing. Specifically, this proposed algorithm consists of four steps. Generate the initial solution space in test tube N0 for the JSSP; Screen the DNA strands representing the feasible schedules and discard the ones representing infeasible schedules; Append time information strands at the end of the strands representing feasible schedules and calculate the completion time of each feasible schedule; Select the strands corresponding to the optimal schedule that minimizes the maximum completion time, i.e., the makespan. The flowchart of the algorithm is shown in Fig 4 as follows. 10.1371/journal.pone.0242083.g004Fig 4 Algorithm flow chart. 3.3 Detailed algorithm 3.3.1 Initialization of the sequence of the n jobs for each operation Initial test tube: Ni={pEiq}for1≤i≤m Q={F1,F2,⋯,Fn,qF1¯,qF2¯,⋯,qFn¯,qF1p¯,qF2p¯,⋯,qFnp¯} Algorithm 1. Initialization of the sequence of the n jobs for each operation Begin 1: for i = 1 to m do 2:   Merge(Ni, Q); 3:  Annealing(Ni); 4:  Ligation(Ni); 5:  Denaturation(Ni); 6:  Selection(Ni, 4nu, Vi); 7:  Discard(Ni); 8:  Vi: = B(Ti, pEiq); 9:  for j = 1 to j = n do 10:   Separation(Vi, qFjp, Ui); 11:   Discard(Vi); 12:   Amplify(Ui, Vi); 13:   Discard(Ui); 14:  end for 15:  Amplify(Vi, Ni); 16:  Discard(Vi); 17:  Append-tail(Ni, ai2S); 18:  Append-head(Ni, ai1); 19: end for End Algorithm 1 produces DNA strands representing all n jobs for every possible operation, for instance, {a11pE1qF2pE1qF4pE1qF5pE1qF1pE1qF3a12S}and{a21pE2qF2pE2qF1pE2qF5pE2qF4pE2qF3a22S}, and so on. The lengths of the single strands ai,j and S are also u mer. The strands ai,j and S are used for connection in the following algorithm. 3.3.2 Generation of all possible strands for the JSSP Initial test tube N0: N0={a12Sa21¯,a22Sa31¯,a32Sa41¯,⋯,am−1,2Sam1¯} Algorithm 2. Generation of all possible strands for the JSSP Begin 1: Merge (N0, N1, N2,…, Nm); 2: Annealing (N0); 3: Denaturation (N0); 4: N0: = B (N0, a11pE1q); 5: Selection (N, (4n+3)mu, N0); 6: for i = 1 to i = m do 7:  Separation (N0, ai2S, N1); 8:  Discard (N0); 9:  Amplify (N1, N0); 10:  Discard (N1); 11: end for End After executing Algorithm 2, all possible DNA strands representing all possible solutions of the JSSP can be obtained as shown below {a11pE1qFj1⋯pE1qFjk⋯pE1qFjna12Sa21pE2qFj1⋯pE2qFjk⋯pE2qFjna22S⋯}, where the subscript jk of Fjk is uniquely determined by the value of k for 1 ≤ k ≤ n, and Fjk∈{F1,F2,⋯,Fn}, i.e., the sequence j1, …,jk, …,jn is an arbitrary out-of-order combination of the sequence 1,…,n. 3.3.3 Computation of the final completion time of each job for every strand In Algorithm 3, as explained in Section 2.2, TJi,jk denotes the completion time of job jk in operation i, TMi,jk is the cumulative time (not including ti,jk) of the required machine corresponding to job jk in operation i, and ti,jk is the corresponding processing time of job jk in operation i. The value of jk is also uniquely determined by the value of k for 1 ≤ k ≤ n, where jk ∈{1,2,⋯,n}. The final completion time of the n jobs are stored separately in n test tubes. The single strand Ψ, also with a length of u mer, in Algorithm 3 denotes one unit of time. Algorithm 3. Computation of the final completion time of each job for every strand Begin 1: Amplify (N0,N1,N2, …,Nn); 2: Discard (N0); 3: for i = 1 to m do 4:  for k = 1 to n do 5:   if i>1 then 6:    Separation (Njk,Sω, Ujk); 7:    Discard (Njk); 8:    Cutting (Ujk,Sω); 9:    Njk: = B (Ujk,a11pE1q); 10:    Discard (Ujk); 11:   else 12:    Continue 13:   if TJi−1,jk>TMi,jk(when i = 1, both initial values are 0) then 14:    Append-tail (Njk, ω⏟TJi−1,jk+ti,jkΨΨ⋯ΨΨΩ); 15:   else 16:    Append-tail (Njk, ω⏟TMi,jk+ti,jkΨΨ⋯ΨΨΩ); 17:   TJi,jk: = Length(Njk, ω, Ω); 18:   TMi,jk: = Length(Njk, ω, Ω); 19:  end for 20: end for End 3.3.4 DNA optimization This algorithm finds the optimal schedule that minimizes the maximum completion time, i.e., the makespan, Min(Max1≤j≤n(TJm,j)), where TJm,j is the final completion time of job j in the last operation. Algorithm 4. DNA optimization Begin 1: for i = 1 to n do 2:  Sort (Ni, V1, V2); 3: end for 4: Sort (V2, V0, V3); 5: Cutting (V0, Sω); 6: T0: = B (V0, a11pE1q); 7: Read (V0) End Theorem in the following is obtained by inspecting Algorithms 1–4 line by line. Theorem Without loss of generality, n ≥ m is assumed. The solutions of a n×m JSSP has an O(n2) complexity using DNA computing. Proof The total complexity of the four algorithms is as follows O(Algorithm1)=O(m(7+4n+4))≈O(4n2+11n)=O(n2); O(Algorithm2)=O(5+4m)≈O(4n+5)=O(n); O(Algorithm3)=O(10mn+2)≈O(10n2+2)=O(10n2)=O(n2); O(Algorithm4)=O(n+4)=O(n); O=O(Algorithm1)+O(Algorithm2)+O(Algorithm3)+O(Algorithm4)=O(n2)+O(n)+O(n2)+O(n)=O(n2) In conclusion, the optimal schedule of a JSSP can be found with an O(n2) complexity. Summary The solution of the JSSP can be represented by a strand with a polynomial length. Explanation Suppose the length of the different strands is ||Ei||=||Fj||=||aij||=||S||=||Ψ||=||Ω||=||ω||=||p||=||q||=umer,fori∈[1,m]andj∈[1,n]. Let l = ΣΣtij, and also assume m ≤ n. The length of DNA strand L corresponding to the optimal schedule in Algorithm 4 is as follows. ||L||=n∑i=1m||Ei||+m∑j=1n||Fj||+mn(||p||+||q||)+||Ω||+||ω||+⏟Min(Max1≤j≤n(TJm,j))<