并行遗传算法在车间作业调度问题上的应用
|
摘要
车间作业调度(JSSP)在企业生产经营活动中占有十分重要的地位。生产调度系统也是CIMS、ERP等系统中的重要组成部分。生产调度位于CIMS体系结构中的中间层,是控制与管理一体化的接合部。向上要给企业经营战略决策层提供决策依据,向下要安排生产加工任务,指导监督控制层的动作。因些,生产调度是实施CIMS的关键。由于车间作业调度问题是一个典型的NP-hard问题,因此受到学术界和工业界的广泛关注。对它的研究具有很高的理论意义和实际意义。
迄今为止,已有很多关于车间作业调度问题的研究方法,如分枝定界法、基于优先规则的启发式方法,但是常见的JSSP的困难性和复杂性使传统的搜索方法很难在合理的时间内找到最优解。近年来,已经引进了一些人工智领域的新技术来解决这些问题,如模拟退火(SA)、禁忌搜索(TA)、人工神经网络(ANN)、遗传算法(GA)等等。
遗传算法是一类借鉴生物界的进化规律演化而来的随机化搜索方法,其主要特点是直接对结构对象进行操作,不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法,能自动获取和指导优化的搜索空间,自适应地调整搜索方向,不需要确定的规则。遗传算法的这些性质,已被人门广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。
并行遗传算法(PGA)是过去十几年以来GA研究的热点之一,无论是理论还是应用上都取得一些成熟的成果。因此本文将PGA用于求解JSSP调度问题,本文主要有以下几项内容:
(1)介绍分析了车间作业调度的问题描述、模型表示、特点以及对它的研究方法和研究现状。本文将JSSP的研究方法分为两大类,最优化方法和近似/启发式方法;
(2)作为并行遗传算法的基础,介绍了标准遗传算法的来源,生物学方面的背景,编码方式,适应度函数,基本遗传操作(选择、交叉、变异),基本参数的设置原则;
(3)介绍了并行遗传算法的分类,以及他们各自发展的历史现状,粗粒度并行遗传算法的迁移策略,分为两种同步迁移和异步迁移;
(4)详细介绍了针对JSSP的特点设计的新的粗粒度并行遗传算法,主要包括算法流程,编码方式,遗传操作,迁移策略。最后,对两个经典的JSSP的实例即FT6×6、LA01,进行了仿真实验。通过对结果的分析,得出设计的新算法比普通的遗法效率高的结论。
Job-shop scheduling plays a great role in the production activity of an enterprise, job-shop scheduling system is also a great part of CIMS or ERP. Production scheduling is at the middle layer in the CIMS system structure, which is the joint of control and management. On one hand, it will supply decisions for the enterprise; on the other hand, it will arrange production tasks and supervise the control layer. So the production scheduling is the key of the CIMS. JSSP is a typical NP-hard problem, so it attracts great attention from both the academia and industry. Therefore, the study of job shop schedule is of great theoretical and practical importance.
So far there have been many research methods to deal with JSSP, such as branch-bound method and some heuristic procedures based on priority rules, but the difficulty and complexity of general JSSP makes it very hard for the conventional search-based methods to find an optimal solution in reasonable time. New techniques emerging from the field of artificial intelligence have been introduced to address these problems in recent years, such as simulated annealing, tabu search, artificial neural network and genetic algorithm , and so on .
The Genetic Algorithm (GA) is a random search method imitating the rules of the organic world. The main distinguishing feature are as following: operating on the composition target, requesting no guide and function continuance; having conceal concurrence and splendid capability with the better situation as a whole; adopting approximately the guiding of the most splendid means of leading, being able to gain voluntarily and the searching room the direction optimizes, self-adopting the regulation direction of search, not needing certain regulation. The features of GA have been widely used applied in territories such as optimization, machine learning, treatment of signal, self-adoption control, artificial existence and so on.
Parallel Genetic Algorithm (PGA) is one of the research focuses of GA from past 10 years, and has improved a lot both in theory and application. This paper use PGA to solve JSSP scheduling problem, and the main content is as following:
(1) Introduce and analyze some aspects about Job-shop scheduling problem, such as description of the problem, expression of the model, features and main research methods on JSSP. This paper divide all the methods into two classification, optimization method and heuristic procedures;
(2)Introduce the Simple Genetic Algorithm as the foundation of PGA, such as following aspects: SGA’s origin, background about biology, encoding methods, function, basic genetic operation(selection、crossover、mutation), and the regulation about the initialization of the basic parameters;
(3)Introduce and analyze Parallel Genetic Algorithm, classification and status quo on research, transferring methods of CPGA, synchronous and asynchronic;
(4)Introduce detailedly the new algorithm of CPGA aim at the features of the JSSP, include encoding methods, genetic operations, transferring methods. At last, implement the emulational experiment on the two typical examples of JSSP, FT6×6、LA01. The result prove that the new algorithm is better than the general GA.
迄今为止,已有很多关于车间作业调度问题的研究方法,如分枝定界法、基于优先规则的启发式方法,但是常见的JSSP的困难性和复杂性使传统的搜索方法很难在合理的时间内找到最优解。近年来,已经引进了一些人工智领域的新技术来解决这些问题,如模拟退火(SA)、禁忌搜索(TA)、人工神经网络(ANN)、遗传算法(GA)等等。
遗传算法是一类借鉴生物界的进化规律演化而来的随机化搜索方法,其主要特点是直接对结构对象进行操作,不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法,能自动获取和指导优化的搜索空间,自适应地调整搜索方向,不需要确定的规则。遗传算法的这些性质,已被人门广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。
并行遗传算法(PGA)是过去十几年以来GA研究的热点之一,无论是理论还是应用上都取得一些成熟的成果。因此本文将PGA用于求解JSSP调度问题,本文主要有以下几项内容:
(1)介绍分析了车间作业调度的问题描述、模型表示、特点以及对它的研究方法和研究现状。本文将JSSP的研究方法分为两大类,最优化方法和近似/启发式方法;
(2)作为并行遗传算法的基础,介绍了标准遗传算法的来源,生物学方面的背景,编码方式,适应度函数,基本遗传操作(选择、交叉、变异),基本参数的设置原则;
(3)介绍了并行遗传算法的分类,以及他们各自发展的历史现状,粗粒度并行遗传算法的迁移策略,分为两种同步迁移和异步迁移;
(4)详细介绍了针对JSSP的特点设计的新的粗粒度并行遗传算法,主要包括算法流程,编码方式,遗传操作,迁移策略。最后,对两个经典的JSSP的实例即FT6×6、LA01,进行了仿真实验。通过对结果的分析,得出设计的新算法比普通的遗法效率高的结论。
Job-shop scheduling plays a great role in the production activity of an enterprise, job-shop scheduling system is also a great part of CIMS or ERP. Production scheduling is at the middle layer in the CIMS system structure, which is the joint of control and management. On one hand, it will supply decisions for the enterprise; on the other hand, it will arrange production tasks and supervise the control layer. So the production scheduling is the key of the CIMS. JSSP is a typical NP-hard problem, so it attracts great attention from both the academia and industry. Therefore, the study of job shop schedule is of great theoretical and practical importance.
So far there have been many research methods to deal with JSSP, such as branch-bound method and some heuristic procedures based on priority rules, but the difficulty and complexity of general JSSP makes it very hard for the conventional search-based methods to find an optimal solution in reasonable time. New techniques emerging from the field of artificial intelligence have been introduced to address these problems in recent years, such as simulated annealing, tabu search, artificial neural network and genetic algorithm , and so on .
The Genetic Algorithm (GA) is a random search method imitating the rules of the organic world. The main distinguishing feature are as following: operating on the composition target, requesting no guide and function continuance; having conceal concurrence and splendid capability with the better situation as a whole; adopting approximately the guiding of the most splendid means of leading, being able to gain voluntarily and the searching room the direction optimizes, self-adopting the regulation direction of search, not needing certain regulation. The features of GA have been widely used applied in territories such as optimization, machine learning, treatment of signal, self-adoption control, artificial existence and so on.
Parallel Genetic Algorithm (PGA) is one of the research focuses of GA from past 10 years, and has improved a lot both in theory and application. This paper use PGA to solve JSSP scheduling problem, and the main content is as following:
(1) Introduce and analyze some aspects about Job-shop scheduling problem, such as description of the problem, expression of the model, features and main research methods on JSSP. This paper divide all the methods into two classification, optimization method and heuristic procedures;
(2)Introduce the Simple Genetic Algorithm as the foundation of PGA, such as following aspects: SGA’s origin, background about biology, encoding methods, function, basic genetic operation(selection、crossover、mutation), and the regulation about the initialization of the basic parameters;
(3)Introduce and analyze Parallel Genetic Algorithm, classification and status quo on research, transferring methods of CPGA, synchronous and asynchronic;
(4)Introduce detailedly the new algorithm of CPGA aim at the features of the JSSP, include encoding methods, genetic operations, transferring methods. At last, implement the emulational experiment on the two typical examples of JSSP, FT6×6、LA01. The result prove that the new algorithm is better than the general GA.
引文
[1] Holland J.H,Adaption in Natural and Artificial System,The University of Michigan Press,1975.
[2] Conway R.w.,Maxwell W.L. and Miller L.W., Theory of Scheduling. Addison Wesley,Reading,Mass,1967.
[3] Jonhson S.M., Optimal Two-And-Three-Stage Production Scheduling with Set-up times Included. Naval Research Logistics Quarterly, 1954,1:61-6.
[4] Florian M., Trepant P. and McMahon G.., An Implicit Enmumeration Algorithm for the Machine Sequencing Problem. Management Science, 1971,17:782-792
[5] Carlier J. and Pinson E., An Algorithm for Solving the Job-shop Problem. Management Science, 1989,35:164-176.
[6] Carlier J. and Pinson E., A Practical Use of Jachson’s Preemptive Schedule for Solving the Job-shop Problem. Annals of Operations Research, 1990,26:269-287.
[7] Carlier J. and Pinson E., Adjustment of Heads and Tails for the Job-shop Problem. Europen Journal of Operational Research, 1994,78:146-161.
[8] Panwalkar S.S. and Iskander W., A Survey of Schduling Rules. Operations Research , 1977,25:45-61.
[9] Chang Y.L., Sueyoshi T, and Sullivan R.S., Ranking dispatching rules by data envelopment analysis in a job-shop environment. IIE Tansactions, 1996,28:631-642.
[10] Adams J., Balas E. and Zawack D., The Shifting Bottleneck Procedure for Job-shop scheduling. Management Science, 1988,34:391-401.
[11] Norman B. A. and Smutnicki C., Randlom Keys Genetic Algorith for Job-shop Scheduling. Engineering Design and Automation, 1997,3:145-156.
[12] Goldberg D.E., Genetic Algorithm in Search, Optimization and Machine Learning. Addsion Wesley, Reading, 1989.
[13] Bertoni A. and Dorigo M., Implicit Parallelism in Genetic Algorithm. Arti.Intell., 1993, 61:307-314.
[14] De Jong K. A. , An Analysis of the Behavior of a Class of Genetic Adaptive Systems. Ph.D Dissertation, University of Michigan, 1975.
[15] Cheng R., Gen M. and Tsujimura Y., Atutorial survey of Job-shop scheduling problem uing genetic algorthm-I. Representation, Computers&Industrial Engineering, 1996, 30:983-989.
[16] Goldberg D.E. and Lingle R., Alleles, Lociand and the traveling salesman problem. Proceedings of an International Conference on Genetic Algorithms and Their Application, 1985:154-159.
[17] Biewirth C., A Generalized Permutation Approach to Job-shop Scheduling with Genetic Algorithm. OR Spectrum, 1995, 17:89-92.
[18] Croce F.D., Tadei R. and Volta G., A genetic algorithm for flow shop sequencing, Computers and Operations Research, 1995, 22:5-13.
[19] Potts C.N., Van Wassenhove L.N., A branch and bound algorithm for the total weighted tardiness problem, Operation Research, 1985, 33,363
[20] Dagli, C.H. and Sittisathanchai, S., Genetic neuro-scheduler-a new approach for job-shop scheduling, International Journal of Production Economics,1995,41(3).
[21] Jain A. S., and Meeran S. Job-shop scheduling using neural networks, International Journal of Production Research,1998,36(5),1249.
[22] Dubdek R.S. Panwalkar,and M.Smith, The Lessons of flow shop scheduling research, Operations Research, 1992,40,7-13.
[23] Biewar D.B. and Grossmann,I.E., Incorporation scheduling in the optimal design of multiproduct batch plants, Comput chem..Eng.1989,13(1),141
[24] Jung,J.H.,Lee H.K.,Yang D.R.,Lee I.B., Completion times and optimal scheduling for serial multi-product processes with transfer and set-up times in zero-wait policy, Comput.Chem.Eng,1994,18(6),537.
[25] Jian A.K., Elmaraghy H.A., Production scheduling/rescheduling in flexible manufacturing[J]. Int J of Prod Res, 1997,35(1):281-309.
[26] Huntley C L, Broun D E., Parallel genetic algorithms with local search[J]. Comput Oper Res,1996,23(6):559-571.
[27] Mayer M K. A network parallel genetic algorithm for the one machine sequencing problem[J]. Computers & mathmatics with applications , 1999,37(3):71-78
[28] MA TSUMURA T,NAKEMURAM,OKECH J,et al A Parallel and distributed genetic algorithm on bosely-couplemutliprocessor Commun Comput Sci, 1998,E81A(4):540-564.
[29] NAL NIK,R,ANIK,AFOON,J,C Clustering using a coarse-grained parallel genetic algorithm a preliminary study[J], IEEE 1995:241-253.
[30] Rudolph G.. Convergence Analysis of canonical Genetic Algorithms IEEE Trans. On Nerual Network, 1994,5(1):96-101
[31] 陈国良,遗传算法及其应用[M],人民邮电出版社,1996:192-194
[32] 吴明,陈国良,并行遗传算法在孤儿岛模型上的设计和分析[J],软件学报, 1996(增刊):67-71
[33] 张长水,沈刚,阎平凡,解 Job-Shop 调度问题的一个遗传算法,电子学报,1995,23(7):1-5.
[34] 曾国荪,丁春玲,并行遗传算法分析,计算机工程,2001,27(9):53-55
[35] 戴晓明,许超,龚向阳,邵惠鹤,并行遗传算法收敛性分析及优化运算,计算机工程,2002, 28(6):92-95
[36] 玄光男,程润伟,遗传算法与工程设计,科学出版,2000
[37] 张文修,梁怡,遗传算法的数学基础,西安交通大学出版社,2000
[38] 张晓馈,方浩等,遗传算法的编码机制研究,信息与控制,1997.4
[39] 史忠值,高级人工智能,科学出版社,1997
[40] 席裕庚,柴天佑等,遗传算法综述,控制理论与应用,1996.12
[41] 徐宗本,高勇,遗传算法过早收敛现象的特征分析及其预访,中国科学(E辑),4:364-375.
[42] 云中夏,黄光球,王战权,遗传算法和遗传规划,冶金工业出版社,1997
[43] 刘勇,康立山,陈毓屏,非数值并行算法—遗传算法,科学出版社,2002:4-14
[44] 周明,孙树栋,遗传算法原理及应用,国防工业出版社,1999
[45] 孙艳丰,王众托,遗传算法在优化问题中的应用研究进展,控制与决策,1996, 11(4):425-452.
[46] 徐金梧,刘纪文,基于小生境技术的遗传算法,模式识别与人工智能,1996, 12(1):104-108.
[47] 吴少岩,许卓群,遗传算法中遗传因子的启发式构造策略,计算机学报, 1998.11
[48] 孙晓云,高鑫,王鹏,新型并行遗传算法及其在参数估计中的应用,计算机工程与应用,2005,9,50-52
[49] 郭绚,石晓虹,并行遗传算法的性能分析,航天计算技术,1998,Vol28,No3
[50] 胡兰成,潘福成,梁英,辛彦秋,基于种群规模可变的粗粒度并行遗传算法,小型微型计算机系统,2003.3,vol 24,No .3
[51] 郭彤城,慕春棣,并行遗传算法的新进展,系统工程理论与实践,2002,vol2
[52] 郭彤城,慕春棣,自适应迁移并行遗传法在无线通信网优化中应用,清华大学学报,2002,vol42,No.9.
[53]王蓓蓓,王洪燕,并行遗传算法机理及其分类,2000 中国控制与决策学术年会论文集
[2] Conway R.w.,Maxwell W.L. and Miller L.W., Theory of Scheduling. Addison Wesley,Reading,Mass,1967.
[3] Jonhson S.M., Optimal Two-And-Three-Stage Production Scheduling with Set-up times Included. Naval Research Logistics Quarterly, 1954,1:61-6.
[4] Florian M., Trepant P. and McMahon G.., An Implicit Enmumeration Algorithm for the Machine Sequencing Problem. Management Science, 1971,17:782-792
[5] Carlier J. and Pinson E., An Algorithm for Solving the Job-shop Problem. Management Science, 1989,35:164-176.
[6] Carlier J. and Pinson E., A Practical Use of Jachson’s Preemptive Schedule for Solving the Job-shop Problem. Annals of Operations Research, 1990,26:269-287.
[7] Carlier J. and Pinson E., Adjustment of Heads and Tails for the Job-shop Problem. Europen Journal of Operational Research, 1994,78:146-161.
[8] Panwalkar S.S. and Iskander W., A Survey of Schduling Rules. Operations Research , 1977,25:45-61.
[9] Chang Y.L., Sueyoshi T, and Sullivan R.S., Ranking dispatching rules by data envelopment analysis in a job-shop environment. IIE Tansactions, 1996,28:631-642.
[10] Adams J., Balas E. and Zawack D., The Shifting Bottleneck Procedure for Job-shop scheduling. Management Science, 1988,34:391-401.
[11] Norman B. A. and Smutnicki C., Randlom Keys Genetic Algorith for Job-shop Scheduling. Engineering Design and Automation, 1997,3:145-156.
[12] Goldberg D.E., Genetic Algorithm in Search, Optimization and Machine Learning. Addsion Wesley, Reading, 1989.
[13] Bertoni A. and Dorigo M., Implicit Parallelism in Genetic Algorithm. Arti.Intell., 1993, 61:307-314.
[14] De Jong K. A. , An Analysis of the Behavior of a Class of Genetic Adaptive Systems. Ph.D Dissertation, University of Michigan, 1975.
[15] Cheng R., Gen M. and Tsujimura Y., Atutorial survey of Job-shop scheduling problem uing genetic algorthm-I. Representation, Computers&Industrial Engineering, 1996, 30:983-989.
[16] Goldberg D.E. and Lingle R., Alleles, Lociand and the traveling salesman problem. Proceedings of an International Conference on Genetic Algorithms and Their Application, 1985:154-159.
[17] Biewirth C., A Generalized Permutation Approach to Job-shop Scheduling with Genetic Algorithm. OR Spectrum, 1995, 17:89-92.
[18] Croce F.D., Tadei R. and Volta G., A genetic algorithm for flow shop sequencing, Computers and Operations Research, 1995, 22:5-13.
[19] Potts C.N., Van Wassenhove L.N., A branch and bound algorithm for the total weighted tardiness problem, Operation Research, 1985, 33,363
[20] Dagli, C.H. and Sittisathanchai, S., Genetic neuro-scheduler-a new approach for job-shop scheduling, International Journal of Production Economics,1995,41(3).
[21] Jain A. S., and Meeran S. Job-shop scheduling using neural networks, International Journal of Production Research,1998,36(5),1249.
[22] Dubdek R.S. Panwalkar,and M.Smith, The Lessons of flow shop scheduling research, Operations Research, 1992,40,7-13.
[23] Biewar D.B. and Grossmann,I.E., Incorporation scheduling in the optimal design of multiproduct batch plants, Comput chem..Eng.1989,13(1),141
[24] Jung,J.H.,Lee H.K.,Yang D.R.,Lee I.B., Completion times and optimal scheduling for serial multi-product processes with transfer and set-up times in zero-wait policy, Comput.Chem.Eng,1994,18(6),537.
[25] Jian A.K., Elmaraghy H.A., Production scheduling/rescheduling in flexible manufacturing[J]. Int J of Prod Res, 1997,35(1):281-309.
[26] Huntley C L, Broun D E., Parallel genetic algorithms with local search[J]. Comput Oper Res,1996,23(6):559-571.
[27] Mayer M K. A network parallel genetic algorithm for the one machine sequencing problem[J]. Computers & mathmatics with applications , 1999,37(3):71-78
[28] MA TSUMURA T,NAKEMURAM,OKECH J,et al A Parallel and distributed genetic algorithm on bosely-couplemutliprocessor Commun Comput Sci, 1998,E81A(4):540-564.
[29] NAL NIK,R,ANIK,AFOON,J,C Clustering using a coarse-grained parallel genetic algorithm a preliminary study[J], IEEE 1995:241-253.
[30] Rudolph G.. Convergence Analysis of canonical Genetic Algorithms IEEE Trans. On Nerual Network, 1994,5(1):96-101
[31] 陈国良,遗传算法及其应用[M],人民邮电出版社,1996:192-194
[32] 吴明,陈国良,并行遗传算法在孤儿岛模型上的设计和分析[J],软件学报, 1996(增刊):67-71
[33] 张长水,沈刚,阎平凡,解 Job-Shop 调度问题的一个遗传算法,电子学报,1995,23(7):1-5.
[34] 曾国荪,丁春玲,并行遗传算法分析,计算机工程,2001,27(9):53-55
[35] 戴晓明,许超,龚向阳,邵惠鹤,并行遗传算法收敛性分析及优化运算,计算机工程,2002, 28(6):92-95
[36] 玄光男,程润伟,遗传算法与工程设计,科学出版,2000
[37] 张文修,梁怡,遗传算法的数学基础,西安交通大学出版社,2000
[38] 张晓馈,方浩等,遗传算法的编码机制研究,信息与控制,1997.4
[39] 史忠值,高级人工智能,科学出版社,1997
[40] 席裕庚,柴天佑等,遗传算法综述,控制理论与应用,1996.12
[41] 徐宗本,高勇,遗传算法过早收敛现象的特征分析及其预访,中国科学(E辑),4:364-375.
[42] 云中夏,黄光球,王战权,遗传算法和遗传规划,冶金工业出版社,1997
[43] 刘勇,康立山,陈毓屏,非数值并行算法—遗传算法,科学出版社,2002:4-14
[44] 周明,孙树栋,遗传算法原理及应用,国防工业出版社,1999
[45] 孙艳丰,王众托,遗传算法在优化问题中的应用研究进展,控制与决策,1996, 11(4):425-452.
[46] 徐金梧,刘纪文,基于小生境技术的遗传算法,模式识别与人工智能,1996, 12(1):104-108.
[47] 吴少岩,许卓群,遗传算法中遗传因子的启发式构造策略,计算机学报, 1998.11
[48] 孙晓云,高鑫,王鹏,新型并行遗传算法及其在参数估计中的应用,计算机工程与应用,2005,9,50-52
[49] 郭绚,石晓虹,并行遗传算法的性能分析,航天计算技术,1998,Vol28,No3
[50] 胡兰成,潘福成,梁英,辛彦秋,基于种群规模可变的粗粒度并行遗传算法,小型微型计算机系统,2003.3,vol 24,No .3
[51] 郭彤城,慕春棣,并行遗传算法的新进展,系统工程理论与实践,2002,vol2
[52] 郭彤城,慕春棣,自适应迁移并行遗传法在无线通信网优化中应用,清华大学学报,2002,vol42,No.9.
[53]王蓓蓓,王洪燕,并行遗传算法机理及其分类,2000 中国控制与决策学术年会论文集