摘要
随着经济规模的不断扩大,生产规模越来越大,复杂性也越来越高,对企业的管理和大规模的生产过程的监控都提出了更高的要求。对生产调度问题的研究已有十几年的历史,提出了大批的调度方法,但是仍没有形成一套系统的理论与方法。差分进化算法(Differential evolution algorithm, DE)作为一种新颖的智能算法,首先由Storn K和Price P在1995年提出。后经过实践证明,差分进化算法是解决多项式问题的有效方法。但差分进化算法本身存在缺陷,如容易出现早熟收敛,陷入局部最优。本文对基本差分进化算法进行了一些改进,以便更好的解决调度问题。本文的研究内容主要包括:
(1)差分进化算法的改进。提出一种混合差分进化算法(Hybrid Differential Evolution Algorithm, HDE)。通过标准benchmark问题仿真结果分析,改进后的算法收敛速度快,全局收敛能力更强。
(2)置换流水车间调度问题。通过标准FSP调度问题和实际化工车间调度问题仿真结果分析,验证了混合差分进化算法在解决FSP单目标和多目标调度问题上的有效性和优越性。
(3)作业车间调度问题(Job Shop Scheduling Problem,JSP)。差分进化算法在JSP问题中的应用目前还很少。通过针对JSP单目标和多目标问题的仿真结果分析,验证了HDE在解决JSP问题中的可行性和有效性。
(4)基于HDE的离子膜车间调度问题。本文调度方案采用基于统一时间离散化的方法,满足多项约束条件的基础上,建立以产值效益最大化为调度目标的调度模型。通过分析DE和HDE算法仿真结果,验证了HDE在解决实际车间调度问题上的优越性。最后对本文进行总结分析,并对以后的工作进行展望。
With the continuous expansion of economic scale, bigger production scale and a higher complexity requirements, putting forward higher requirements on management and monitoring of large-scale production processes. The study of production scheduling problem has underwent more than ten years of history and a large number of scheduling methods has been put forward, but still no systematic theory and method has been formed. Differential evolution algorithm as a novel intelligent algorithm first proposed by Storn K, and Price P made in 1995. Later it’s found that the differential evolution algorithm is an effective way to solve polynomial problems. But the basic differential evolution algorithm itself is flawed, for it’s prone to premature convergence into local optimum. In this paper, the basic differential evolution algorithm made some improvements in order to better solve the scheduling problem. This study should include:
(1) An improved of differential evolution algorithm. Proposing a hybrid differential evolution algorithm (Hybrid Differential Evolution Algorithm, HDE). Through the simulation results of standard benchmark problems, the improved algorithm has fast convergence capability and excellent global convergence capability.
(2) The permutation of flow shop scheduling problem. Through the simulation results about the standard FSP scheduling problem and the actual chemical scheduling problem, the hybrid differential evolution algorithm is effective and superior in solving the scheduling problem on a single and multiple objectives.
(3) Job-shop scheduling problem. At present, differential evolution algorithm has not been widely applied to JSP scheduling problems. Through the simulation results about multi-objective and single- objective JSP scheduling problems, HDE is proved to be feasibility and effectiveness in resolving the JSP scheduling problem.
(4) The resolution of lizimo workshop scheduling problem based on HDE. Based on time discretion, this scheduling scheme is a unified approach to meet a number of constraints and to establish a scheduling model with the scheduling objective of the value of maximum benefit. By analyzing the simulation results in using DE and the HDE algorithm, it verifies that the HDE has advantages in settling the practical scheduling problem.
Finally, this paper ends with a summary and the work of the future outlook.
引文
[1]王万良,吴启迪.生产调度智能算法及其应用[M].北京:科学出版社,2007.
[2] R. Graham, E. Lawler, J. Lenstra, A. Kan. Optimization and approximation in deterministic sequencing and scheduling: A survey[J]. Annals of Discrete Mathematics, 1979, 5(2): 287-326.
[3]乔佩利,张宏芳,李小平,高祥. FLOW SHOP调度问题的启发式算法[J].电机与控制学报, 2008, 12(001): 109-112.
[4]贾兆红.粒子群优化算法在柔性作业车间调度中的应用研究[D].安徽:中国科技大学, 2008.
[5] M. Fox. Constraint-guided scheduling- a short history of research at CMU[J]. COMP. IND., 1990, 14(1): 79-88.
[6]冯欣,唐立新,王梦光. BAB算法中集成CPT求解job-shop调度问题[J].管理科学学报, 2005, 8(003): 81-89.
[7]宋晔,杨根科.基于分支定界和神经网络的实时调度策略[J].微型电脑应用, 2008, 24(004): 10-12.
[8] M. Kim, J. Jung, I. Lee. Intelligent scheduling and monitoring for multi-product networked batch processes[J]. Computers and Chemical Engineering, 1996, 1149-1154.
[9] M. Fox, Constraint-directed search: a case study of job-shop scheduling[M], Carnegie-Mellon University, 1983.
[10]石柯,李培根.基于多Agent和合同网的敏捷制造单元调度[J].华中科技大学学报:自然科学版, 2001, 29(007): 32-34.
[11]饶运清,谢畅,李淑霞.基于多Agent的Job Shop调度方法研究[J].中国机械工程, 2004, 15(010): 873-877.
[12] S. Smith, M. Fox, P. Ow. Constructing and maintaining detailed production plans: Investigations into the development of knowledge-based factory scheduling systems[J]. AI Magazine, 1986, 7(4): 45-61.
[13] S. Yang, D. Wang. A new adaptive neural network and heuristics hybrid approach for job-shop scheduling* 1[J]. Computers & Operations Research, 2001, 28(10): 955-971.
[14] D. Dubois, H. Fargier, H. Prade. Fuzzy constraints in job-shop scheduling[J]. Journal of Intelligent Manufacturing, 1995,6(4): 215-234.
[15]王凌,车间调度及其遗传算法[M].北京:清华大学出版社, 2003.
[16] M. Kolonko. Some new results on simulated annealing applied to the job shop scheduling problem[J]. European Journal of Operational Research, 1999,113(1): 123-136.
[17]莫宏伟.人工免疫系统原理与应用[M].哈尔滨:哈尔滨工业大学出版社, 2002.
[18] R. Storn, K. Price. Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces[J]. International computer science institute-publications-TR,1995.
[19] G. Onwubolu, D. Davendra. Scheduling flow shops using differential evolution algorithm[J]. European Journal of Operational Research, 2006, 171(2): 674-692.
[20] B. Qian, L. Wang, D. Huang, W. Wang, X. Wang. An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers[J]. Computers and Operations Research, 2009, 36(1): 209-233.
[21] L. Wang, L. Zhang, D. Zheng. An effective hybrid genetic algorithm for flow shop scheduling with limited buffers[J]. Computers and Operations Research, 2006, 33(10): 2960-2971.
[22] M. Gourgand, N. Grangeon, S. Norre. Markovian analysis for performance evaluation and scheduling in m machine stochastic flow-shop with buffers of any capacity[J]. European Journal of Operational Research, 2005, 161(1): 126-147.
[23] A. Agnetis, F. Rossi, G. Gristina. An exact algorithm for the batch sequencing problem in a two-machine flow shop with limited buffer[J]. Naval Research Logistics (NRL),45(2): 141-164.
[24] R. Daniels, R. Chambers. Multiobjective flow-shop scheduling[J]. Naval Research Logistics (NRL),37(6): 981-995.
[25] M. Pranzo. Batch scheduling in a two-machine flow shop with limited buffer and sequence independent setup times and removal times[J]. European Journal of Operational Research, 2004, 153(3): 581-592.
[26] T. Sawik. An exact approach for batch scheduling in flexible flow lines with limited intermediate buffers[J]. Mathematical and Computer Modelling, 2002, 36(4-5): 461-471.
[27] E. Nowicki. The permutation flow shop with buffers: A tabu search approach[J]. European Journal of Operational Research, 1999, 116(1): 205-219.
[28]颜学峰,余娟,钱锋.自适应变异差分进化算法估计软测量参数[J].控制理论与应用, 2006, 23(005): 744-748.
[29]吴亮红,王耀南,袁小芳,周少武.自适应二次变异差分进化算法[J].控制与决策, 2006, 21(008): 898-902.
[30]胡桂武.基于迁徙差分进化算法集成的模体识别[J].计算机工程, 2008, 34(11): 12-14.
[31]孟红云,张小华,刘三阳.用于约束多目标优化问题的双群体差分进化算法[J].计算机学报, 2008, 31(2): 228-235.
[32]吴亮红,王耀南,周少武,袁小芳.双群体伪并行差分进化算法研究及应用[J].控制理论与应用, 2007, 24(003): 453-458.
[33]谈峰,王伟.多种群差分进化算法及在柔性车间作业调度中的应用[J].湖南农业大学学报:自然科学版, 2008, 34(001): 105-108.
[34]韩琳,贺兴时.基于人工免疫系统的二进制差分进化算法[J].哈尔滨工程大学学报, 2006, 27(B07): 278-282.
[35]贺安坤,苗良.差分进化微粒群优化算法-DEPSO[J].微计算机信息, 2006(12X): 284-286.
[36]刘波,王凌,金以慧.差分进化算法研究进展[J].控制与决策, 2007, 22(007): 721-729.
[37] K. Price, R. Storn. Differential evolution[J]. Dr. Dobb’s Journal, 1997, 22(4): 18-24.
[38]周艳平,顾幸生.差分进化算法研究进展[J].化工自动化及仪表, 2007,34(003): 1-6.
[39] A. Nobakhti, H. Wang. A simple self-adaptive Differential Evolution algorithm with application on the ALSTOM gasifier[J]. Applied Soft Computing Journal, 2008, 8(1): 350-370.
[40]孙玲,李铁克,刘瑞伟.求解Flow shop调度问题的启发式方法[J].统计与决策, 2007(017): 141-142.
[41] J. Grabowski, M. Wodecki. A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion[J]. Computers and Operations Research, 2004, 31(11): 1891-1909.
[42] C. Reeves, T. Yamada. Genetic algorithms, path relinking, and the flowshop sequencing problem[J]. Evolutionary Computation, 1998, 6(1): 45-60.
[43] D. Zheng, L. Wang. An effective hybrid heuristic for flow shop scheduling[J]. The International Journal of Advanced Manufacturing Technology, 2003, 21(1): 38-44.
[44] A. Allahverdi, T. Aldowaisan. New heuristics to minimize total completion time in m-machine flowshops[J]. International Journal of Production Economics, 2002, 77(1): 71-83.
[45] F. Al-Anzi, A. Allahverdi. A self-adaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times[J]. European Journal of Operational Research, 2007, 182(1): 80-94.
[46] J. Bean. Genetic algorithms and random keys for sequencing and optimization[J]. Ann Arbor,100148109-42117.
[47] M. Garey, D. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness[M] New York, 1990.
[48] J. Carlier. Ordonnancements a contraintes disjonctives[J]. RAIRO Recherche operationelle/Operations Research, 1978, 12(4): 333-351.
[49] C. Reeves. A genetic algorithm for flowshop sequencing[J]. Computers and Operations Research, 1995, 22(1): 5-13.
[50]王小芹,王万良,徐新黎.一种求解Flow-Shop调度问题的混合量子进化算法[J].机电工程,2009, 26(009): 5-8.
[51] R. Rosenberg. Stimulation of genetic populations with biochemical properties: I. The model[J]. Mathematical Biosciences, 1970, 7(3-4): 223-257.
[52] I. Das, J. Dennis. A closer look at drawbacks of minimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problems[J]. Structural and Multidisciplinary Optimization, 1997, 14(1): 63-69.
[53] J. Schaffer. Some experiments in machine learning using vector evaluated genetic algorithms (artificial intelligence, optimization, adaptation, pattern recognition)[J]. 1984.
[54] N. Srinivas, K. Deb. Muiltiobjective optimization using nondominated sorting in genetic algorithms[J]. Evolutionary Computation, 1994, 2(3): 221-248.
[55] E. Zitzler, L. Thiele. Multiobjective evolutionary algorithms: a comparative case studyand the strength Pareto approach[J]. IEEE transactions on Evolutionary Computation, 1999,3(4): 257-271.
[56] E. Zitzler, M. Laumanns, L. Thiele. SPEA2: Improving the strength Pareto evolutionary algorithm[A], Citeseer, 95–100.
[57] L. Davis. Job shop scheduling with genetic algorithms[A], L. Erlbaum Associates Inc. Hillsdale, NJ, USA, 136-140.
[58] J. Biegel, J. Davern. Genetic algorithms and job shop scheduling[J]. COMP. IND. ENG., 1990, 1981-91.
[59] J. Kanet, V. Sridharan. Progenitor: A genetic algorithm for production scheduling[J]. Wirtschafts Informatik, 1991, 33(4): 336.
[60] E. Falkenauer, S. Bouffouix. A genetic algorithm for job shop[A], Citeseer, 824-829.
[61]朱旭东.改进遗传算法解Job-Shop问题[J].安徽大学学报:自然科学版, 2008,32(005): 33-36.
[62]宋晓宇,朱云龙,尹朝万,李富明.求解模糊Job Shop调度问题的改进禁忌搜索算法[J].沈阳建筑大学学报:自然科学版, 2006,22(005): 841-845.
[63]付振奥,刘心报,程浩,周谧.求解作业车间调度问题的混合QPSO算法[J].合肥工业大学学报:自然科学版, 2009,32(003): 369-373.
[64] D. Kiranmai, A. Jyothirmai, C. Murty. Determination of kinetic parameters in fixed-film bio-reactors: an inverse problem approach[J]. Biochemical Engineering Journal, 2005,23(1): 73-83.
[65] M. Kapadi, R. Gudi. Optimal control of fed-batch fermentation involving multiple feeds using differential evolution[J]. Process Biochemistry, 2004,39(11): 1709-1721.
[66] M. Chaitali, M. Kapadi, G. Suraishkumar, R. Gudi. Productivity improvement in xanthan gum fermentation using multiple substrate optimization[J]. Biotechnology progress, 2003,19(4): 1190-1198.
[67] N. Chakraborti. Genetic algorithms in materials design and processing[J]. International Materials Reviews, 49, 2004,3(4): 246-260.
[68]余建军,张定超,周铭新.生产调度研究综述[J].中国制造业信息化, 2009,38(17): 13-17