用DNA算法求解车间调度问题的研究
|
摘要
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序列上简单的计算。论文中只给出简单流程图和少数几个子程序。论文最后给出实验结果。
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.
首先，本文对Job-shop调度问题的研究现状、DNA算法的思想及其研究现状、DNA算法在NP难题方面的研究现状及存在的问题等方面进行全面综述，并提出课题的来源。
其次，给出解决Job-shop调度问题的DNA编码方法和相应的解码、重组、框架转移变异方法，对死锁现象也进行了详细阐述。DNA链可看作由四个不同符号、、和组成的串，它在数学上就像计算机中的编码“0” 和“1”一样，可表示成四个字母的集合来译码信息。
最后，给出基于该编码方法的DNA算法。DNA串可作为译码信息；酶可看作模拟在DNA序列上简单的计算。论文中只给出简单流程图和少数几个子程序。论文最后给出实验结果。
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.
引文
1 陈荣秋.排序理论与方法.华中理工大学出版社，1987
2 S.M.Jlhnson.Optimal two and three-stage production schedules with setup times included.Naval Res.Logist.Q.,1(1954)m61-68
3 Yoshima T.and Hitomi K. .Optimal two and three stage production scheduling with set-up times separated.A.I.I.E.Tran.,1,P261-264,1979
4 越民义，韩继业.n个零件在m台机床上加工顺序问题.中国科学，5（1975），462-470
5 越民义，韩继业.同顺序m*n排序问题的一个新算法.科学通报，18（1979）
6 齐向彤，陈秋双，涂奉生.具有约束条件的单机JIT调度问题.自动化学报，1998，24（3）：421-423
7 姚伟力，杨德礼，胡祥培.Job-shop提前/拖期调度问题的研究.控制与决策，2000，15（3）：322-324
8 J.R.Jackson.An Extension of Johnson's Results on Joblot Scheduling .Naval Res.Log.Quart.,1956,3(3):201-203
9 Wagner H.M. .An Integer Programming Model for Machine Scheduling .Naval Res.Log.Quart.,1959,(6):131-140
10 Bowman E.H. .The Schedule-Sequencing Problem.Ops.Res.,1959,(7)；621-624
11 Manne A.S. .On the Job-shop Scheduling Problem.Opw.Res.1960.(6):219-223
12 Brooks G.H.White C.R..An Algorithm for Finding Optimal or Near Optimal Solutions to the Production Scheduling Problem.Journal of industrial Engineering,1965,(16)：34-40
13 Colorni A,Dorigo M,Maniezzo V.Ant System for Job Shop Scheduling .Belgian J.of Operations Research Statistics and Computer Science.1994,34(1):39-53
14 J.Westley Barnes,John B.Chambers.Solving the Job-shop Problem with Tabu Search .IIE Rransactions,1995,(27):257-263
15 张长水，阎平凡.解Job-shop调度问题的神经网络方法.自动化学报，1995，21（6）；706-712
16 沈刚，汪叔淳.用神经网络方法求解Job-shop类型调度问题.电子学报，1995，（8）：46-51
17 于海滨，薛劲松，王浩波，徐新和，郑艳.一种基于神经网络的生产调度方法.自动化学报，1999，25（4）：449-455
18 Peter B,Bemd J,Bemds.A Branch and Bound Algorithm for the Job-shop Scheduling Problem.Discrete Appl.Math.1994,(49):107-227
19 Peter B ,Bemd J, Audreas K. The Job-shop Problem and Immediate Selection. Ann. Oper.Res.,1994,(50):73-117
20 常会友，刘丕娥，张淑丽，王凤儒.一种基于效率函数求解Job-shop调度问题的算法.计算机集成制造系统-CIMS，1998，4（4）：51-56
21 Gittins, J.C. , Nash, P. .Scheduling queues and dynamic allocation indices. Proc. EMS. Prague. Pargue:Czechoslovak Academy of Science,1997,191-202
22 Shyh-Chang Lin, Erik D .Goodman , William F.Punch, III. A Genetic Algorithm Approach to Dynamic Job Shop Scheduling Problems. Proc.Seventh Int'l Conf.on Genetic Algorithms. 1997,481-488
23 Raman, N.,Rachamadugu,R.V.,Talbot,F.B.. Real-time Scheduling of an Automated Manufacturing Center. European Journal of Operational Research. 1989,40:222-242
24 Chung-Hsing Yeh. A Fast Finite Loading Algorithm for Job Oriented Scheduling .Computes Ops. Res.,1997,24(2):193-198
25 黄启春，陈齐，俞瑞钊.一种面向作业的快速调度算法.软件学报，1999，10（10）：1073-1077
26 Xu Weiwen, Wang Fengru,Chang Huiyou. Solving Nonstandard Job-shop Scheduling Problem by Using Queue.Advances in computer Science and Technology.The Fifth International Conference for Young Scientists.Nanjing,China.1999.8.Beijing：International Academic Publishers,1998,2:975-979
27 L Adleman. Molecular Computation of Solution to Combinatorial problems.Science,1994,66(11);1021-1024
28 任立红，等.DNA计算研究的现状与展望.信息与控制，1999，28（4）:241-247
29 Deaton R,et al.A DNA Based Implementation of an Evolutionary Search for Good Encodings for DNA Comprtation.Proceeding of 1997 IEEE International Conference on Evolutionary Computation ,Indianapolis,IN,USA.April 1997,13-16:267-271
Manganaro G,Gyvez J P D.DNA Compution Based on Chaos .Proceeding of
30 1997 IEEE International Conference on Evolutionary Computation ,Indianapolis,IN,RSA,April 1997,13-16:255-260
31 Russo M F et al.An Improved DNA Encoding Scheme for Neural Network Modeling, World Congress on Neural networks-San diego.1994 International Neural networks Society Annual meeting ,CA,USA.June 1994,5-9:354-359
32 Yoshikawa T et al.Emergence of Effective Fuzzy Rules for Controling Mobile Robots Using DNA Coding Method.Proceeding of 1996 IEEE International Conference on Evolutionary Computation , Nagoya,Japan,1996,5:581-586
33 Kari L.DNA Computing:Arrival of Biological Mathematics .The Mathematical Tntelligencer,1997,19(2):9-22
34 王丽薇，洪勇，洪家荣.遗传算法的收敛性研究.计算机学报，1996，No.10,P794-797
35 Eiben A.E.，Aarts E.H.，and Van Hee K.M.，Global Convergence of Genetic Algorithms ：An Infinite Markov Chain Analysis .Parallel Problem Solving from Nature，Schwefel，H.P，and Manner，R.，Eds.Heidelberg，Berlin;Springer-Verlad,1991,4-12
36 Qi，X.F.，Palmieri F.，Theoretical analysis of evolutionary algorithms with an infinite population size in continuous space part I：base properties of selection and mutation. IEEE trans Neural Networks，1994,5(1)：P102-119
37 Back T.，The Interaction lf Mutation Rate，Selection and Self-Adaptation within a genetic algorithm，in Parallel Problem Solving from Nature，2，Amsterdam：North Holland，1992，84-94
38 李小平，王凤儒，常会友.用定界-遗传算法解Job-shop调度问题.第五届中国计算机集成制造系统（CIMS）学术会议，1998，p5.63-5.67
39 Xiaoping Li，Fengru Wang ang Huiyou Chang，Sovling Job-shop Scheduling Problems by BEGA Based on Processing Route，Fifth International Conference Control，Automation，Robotics and Vision，1998
40 Deaton R，Murphy R C et al.A DNA based implementation of an evolutionary search for good encoding for DNA computation.In：Proc 1997 IEEE Conference on Evolutionary Computation，Indianaplis，IN，USA，1997.267-271
41 Yoshikawa T et al.Emergence of effective fuzzy rules for controlling mobile robots using DNAcoding method .In：Proc 1996 IEEE International Conference on Evolutionary Computation，Nogoya，Japan，1996.581-586
42 Mruphy R C et al.A new algorithm for DNA based computation.In：Proc 1997 IEEE Conference on Evolutionary Computation，Indianaplis，IN，USA，1997.207-212
43 Manganaro G ，Gyvez J P.DNA computing based on chaos.In：Proc 1997 IEEE Conference Evolutionary Comprtation，Indianaplis，IN，USA，1997.255-260
44 Bach E，Condon A et al.DNA model and algorithms for NP-complete problems.In：Proc Annual IEEE Conference on Comprtational Complexity，Los Almitos，CA，1996.290-300
45 邓少平，等.DNA计算的一些基本问题.科学（Scientifi American 中文版）1996，5：51-54
46 M H Garzon，et al.Biomolecular Computing and Programming.IEEE Trans.on Evolutionary Comprtation.1999,3(3)：236-250
47 张长水.用神经网络方法解工作调度问题的研究.清华大学博士学位论文，1992
48 李小平.用定界最优保存遗传算法解Job-shop调度问题的研究.哈尔滨理工大学硕士论文，1999.
49 王海英.有交货期的非标准Job-shop调度问题算法研究.哈尔滨理工大学硕士论文，2001.
2 S.M.Jlhnson.Optimal two and three-stage production schedules with setup times included.Naval Res.Logist.Q.,1(1954)m61-68
3 Yoshima T.and Hitomi K. .Optimal two and three stage production scheduling with set-up times separated.A.I.I.E.Tran.,1,P261-264,1979
4 越民义，韩继业.n个零件在m台机床上加工顺序问题.中国科学，5（1975），462-470
5 越民义，韩继业.同顺序m*n排序问题的一个新算法.科学通报，18（1979）
6 齐向彤，陈秋双，涂奉生.具有约束条件的单机JIT调度问题.自动化学报，1998，24（3）：421-423
7 姚伟力，杨德礼，胡祥培.Job-shop提前/拖期调度问题的研究.控制与决策，2000，15（3）：322-324
8 J.R.Jackson.An Extension of Johnson's Results on Joblot Scheduling .Naval Res.Log.Quart.,1956,3(3):201-203
9 Wagner H.M. .An Integer Programming Model for Machine Scheduling .Naval Res.Log.Quart.,1959,(6):131-140
10 Bowman E.H. .The Schedule-Sequencing Problem.Ops.Res.,1959,(7)；621-624
11 Manne A.S. .On the Job-shop Scheduling Problem.Opw.Res.1960.(6):219-223
12 Brooks G.H.White C.R..An Algorithm for Finding Optimal or Near Optimal Solutions to the Production Scheduling Problem.Journal of industrial Engineering,1965,(16)：34-40
13 Colorni A,Dorigo M,Maniezzo V.Ant System for Job Shop Scheduling .Belgian J.of Operations Research Statistics and Computer Science.1994,34(1):39-53
14 J.Westley Barnes,John B.Chambers.Solving the Job-shop Problem with Tabu Search .IIE Rransactions,1995,(27):257-263
15 张长水，阎平凡.解Job-shop调度问题的神经网络方法.自动化学报，1995，21（6）；706-712
16 沈刚，汪叔淳.用神经网络方法求解Job-shop类型调度问题.电子学报，1995，（8）：46-51
17 于海滨，薛劲松，王浩波，徐新和，郑艳.一种基于神经网络的生产调度方法.自动化学报，1999，25（4）：449-455
18 Peter B,Bemd J,Bemds.A Branch and Bound Algorithm for the Job-shop Scheduling Problem.Discrete Appl.Math.1994,(49):107-227
19 Peter B ,Bemd J, Audreas K. The Job-shop Problem and Immediate Selection. Ann. Oper.Res.,1994,(50):73-117
20 常会友，刘丕娥，张淑丽，王凤儒.一种基于效率函数求解Job-shop调度问题的算法.计算机集成制造系统-CIMS，1998，4（4）：51-56
21 Gittins, J.C. , Nash, P. .Scheduling queues and dynamic allocation indices. Proc. EMS. Prague. Pargue:Czechoslovak Academy of Science,1997,191-202
22 Shyh-Chang Lin, Erik D .Goodman , William F.Punch, III. A Genetic Algorithm Approach to Dynamic Job Shop Scheduling Problems. Proc.Seventh Int'l Conf.on Genetic Algorithms. 1997,481-488
23 Raman, N.,Rachamadugu,R.V.,Talbot,F.B.. Real-time Scheduling of an Automated Manufacturing Center. European Journal of Operational Research. 1989,40:222-242
24 Chung-Hsing Yeh. A Fast Finite Loading Algorithm for Job Oriented Scheduling .Computes Ops. Res.,1997,24(2):193-198
25 黄启春，陈齐，俞瑞钊.一种面向作业的快速调度算法.软件学报，1999，10（10）：1073-1077
26 Xu Weiwen, Wang Fengru,Chang Huiyou. Solving Nonstandard Job-shop Scheduling Problem by Using Queue.Advances in computer Science and Technology.The Fifth International Conference for Young Scientists.Nanjing,China.1999.8.Beijing：International Academic Publishers,1998,2:975-979
27 L Adleman. Molecular Computation of Solution to Combinatorial problems.Science,1994,66(11);1021-1024
28 任立红，等.DNA计算研究的现状与展望.信息与控制，1999，28（4）:241-247
29 Deaton R,et al.A DNA Based Implementation of an Evolutionary Search for Good Encodings for DNA Comprtation.Proceeding of 1997 IEEE International Conference on Evolutionary Computation ,Indianapolis,IN,USA.April 1997,13-16:267-271
Manganaro G,Gyvez J P D.DNA Compution Based on Chaos .Proceeding of
30 1997 IEEE International Conference on Evolutionary Computation ,Indianapolis,IN,RSA,April 1997,13-16:255-260
31 Russo M F et al.An Improved DNA Encoding Scheme for Neural Network Modeling, World Congress on Neural networks-San diego.1994 International Neural networks Society Annual meeting ,CA,USA.June 1994,5-9:354-359
32 Yoshikawa T et al.Emergence of Effective Fuzzy Rules for Controling Mobile Robots Using DNA Coding Method.Proceeding of 1996 IEEE International Conference on Evolutionary Computation , Nagoya,Japan,1996,5:581-586
33 Kari L.DNA Computing:Arrival of Biological Mathematics .The Mathematical Tntelligencer,1997,19(2):9-22
34 王丽薇，洪勇，洪家荣.遗传算法的收敛性研究.计算机学报，1996，No.10,P794-797
35 Eiben A.E.，Aarts E.H.，and Van Hee K.M.，Global Convergence of Genetic Algorithms ：An Infinite Markov Chain Analysis .Parallel Problem Solving from Nature，Schwefel，H.P，and Manner，R.，Eds.Heidelberg，Berlin;Springer-Verlad,1991,4-12
36 Qi，X.F.，Palmieri F.，Theoretical analysis of evolutionary algorithms with an infinite population size in continuous space part I：base properties of selection and mutation. IEEE trans Neural Networks，1994,5(1)：P102-119
37 Back T.，The Interaction lf Mutation Rate，Selection and Self-Adaptation within a genetic algorithm，in Parallel Problem Solving from Nature，2，Amsterdam：North Holland，1992，84-94
38 李小平，王凤儒，常会友.用定界-遗传算法解Job-shop调度问题.第五届中国计算机集成制造系统（CIMS）学术会议，1998，p5.63-5.67
39 Xiaoping Li，Fengru Wang ang Huiyou Chang，Sovling Job-shop Scheduling Problems by BEGA Based on Processing Route，Fifth International Conference Control，Automation，Robotics and Vision，1998
40 Deaton R，Murphy R C et al.A DNA based implementation of an evolutionary search for good encoding for DNA computation.In：Proc 1997 IEEE Conference on Evolutionary Computation，Indianaplis，IN，USA，1997.267-271
41 Yoshikawa T et al.Emergence of effective fuzzy rules for controlling mobile robots using DNAcoding method .In：Proc 1996 IEEE International Conference on Evolutionary Computation，Nogoya，Japan，1996.581-586
42 Mruphy R C et al.A new algorithm for DNA based computation.In：Proc 1997 IEEE Conference on Evolutionary Computation，Indianaplis，IN，USA，1997.207-212
43 Manganaro G ，Gyvez J P.DNA computing based on chaos.In：Proc 1997 IEEE Conference Evolutionary Comprtation，Indianaplis，IN，USA，1997.255-260
44 Bach E，Condon A et al.DNA model and algorithms for NP-complete problems.In：Proc Annual IEEE Conference on Comprtational Complexity，Los Almitos，CA，1996.290-300
45 邓少平，等.DNA计算的一些基本问题.科学（Scientifi American 中文版）1996，5：51-54
46 M H Garzon，et al.Biomolecular Computing and Programming.IEEE Trans.on Evolutionary Comprtation.1999,3(3)：236-250
47 张长水.用神经网络方法解工作调度问题的研究.清华大学博士学位论文，1992
48 李小平.用定界最优保存遗传算法解Job-shop调度问题的研究.哈尔滨理工大学硕士论文，1999.
49 王海英.有交货期的非标准Job-shop调度问题算法研究.哈尔滨理工大学硕士论文，2001.