蛙跳算法及其在置换流水车间调度中的应用研究
发布时间：2018-12-14 12:08
【摘要】：流水车间生产模式广泛应用于现代制造企业中,因此流水车间调度成为实际生产制造车间中十分常见且重要的一类排产方式,也是车间调度研究的一个热点问题。在实际生产中,一个优秀的调度排序,能够保证生产活动的稳步进行,提高资源利用率,保证交货完工时间,满足客户多样化的需求。在理论上,该问题代表了一类组合优化问题,如能有效的求解对于解决其他优化问题有很强的指导意义。本文针对置换流水车间调度问题(Permutation Flow-shop Scheduling Problem, PFSP),以最小化最大完工时间make span为目标,提出了一种改进蛙跳算法求解。为了使研究的问题更具有普遍性与代表性,深入系统地研究了多目标置换流水车间调度问题(Multi-objective PFSP,MPFSP),提出了与之适应的多目标改进蛙跳算法进行求解。 首先,系统阐述了蛙跳算法的优化原理与操作流程,以及在各个优化领域的应用情况。针对蛙跳算法局部搜索能力较弱的问题,通过结合粒子群算法的个体更新策略,提出了改进蛙跳算法。通过对连续函数优化问题求解,验证了算法改进的有效性,新的算法在优化结果与收敛速度上明显优于标准蛙跳算法与粒子群算法。其次,针对以最小化make span为目标的PFSP,应用改进蛙跳算法进行求解。为使算法适用于离散组合优化问题的求解,采用基于随机键表示法的规则设计了算法编码。同时,为提高初始解的质量,采用改进的NEH启发式算法生成多样性的初始解。在减少计算时间方面,充分利用该问题的可逆性原理计算make span。采用基准测试集进行测试,其结果与其他算法求解该类问题的较好结果相比较,验证了算法的有效性。 最后,针对多目标PFSP,建立以最小化总流经时间、最大完工时间以及最大拖后时间为优化目标的数学模型,设计了多目标蛙跳算法求解。算法采用四种启发式算法生成高质量的初始解,并建立精英解集储存Pareto解,通过自适应小生境方法对精英解集进行维护。采用基准测试集进行测试,算法与解决多目标问题较优的改进强度Pareto进化算法进行比较,验证了算法的有效性。
[Abstract]:The flow shop production model is widely used in modern manufacturing enterprises, so the flow shop scheduling has become a very common and important scheduling method in the actual production shop, and it is also a hot issue in the research of shop scheduling. In actual production, an excellent scheduling and sorting can ensure the steady progress of production activities, improve the utilization of resources, ensure the delivery completion time, and meet the diversified needs of customers. In theory, the problem represents a class of combinatorial optimization problems, such as effective solution to other optimization problems have a strong guiding significance. In this paper, an improved leapfrog algorithm is proposed to solve the replacement flow shop scheduling problem (Permutation Flow-shop Scheduling Problem, PFSP), which aims at minimizing the maximum completion time (make span). In order to make the studied problem more universal and representative, the multi-objective permutation flow shop scheduling problem (Multi-objective PFSP,MPFSP) is studied systematically, and a multi-objective improved leapfrog algorithm is proposed to solve the problem. Firstly, the optimization principle and operation flow of leapfrog algorithm and its application in various optimization fields are systematically described. In order to solve the problem of weak local search ability of leapfrog algorithm, an improved leapfrog algorithm is proposed by combining the individual updating strategy of particle swarm optimization (PSO). The effectiveness of the improved algorithm is verified by solving the continuous function optimization problem. The new algorithm is superior to the standard leapfrog algorithm and particle swarm optimization algorithm in the optimization results and convergence speed. Secondly, the improved leapfrog algorithm is applied to minimize make span for PFSP,. In order to make the algorithm suitable for solving discrete combinatorial optimization problems, the algorithm coding is designed based on the rules of stochastic key representation. At the same time, to improve the quality of the initial solution, the improved NEH heuristic algorithm is used to generate the diversity of the initial solution. In order to reduce the computation time, the reversible principle of this problem is fully used to calculate make span.. The benchmark set is used to test, and the results are compared with the better results of other algorithms to solve this kind of problem, and the validity of the algorithm is verified. Finally, a multi-objective leapfrog algorithm is designed to solve the mathematical model of multi-objective PFSP, which is to minimize the total flow time, the maximum completion time and the maximum delay time. Four heuristic algorithms are used to generate high quality initial solutions, and an elite solution set is built to store Pareto solutions, and an adaptive niche method is used to maintain the elite solution sets. The benchmark set is used to test, and the algorithm is compared with the improved strength Pareto evolutionary algorithm, which is better for solving multi-objective problems. The validity of the algorithm is verified.
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：TH186
本文编号：2378587
[Abstract]:The flow shop production model is widely used in modern manufacturing enterprises, so the flow shop scheduling has become a very common and important scheduling method in the actual production shop, and it is also a hot issue in the research of shop scheduling. In actual production, an excellent scheduling and sorting can ensure the steady progress of production activities, improve the utilization of resources, ensure the delivery completion time, and meet the diversified needs of customers. In theory, the problem represents a class of combinatorial optimization problems, such as effective solution to other optimization problems have a strong guiding significance. In this paper, an improved leapfrog algorithm is proposed to solve the replacement flow shop scheduling problem (Permutation Flow-shop Scheduling Problem, PFSP), which aims at minimizing the maximum completion time (make span). In order to make the studied problem more universal and representative, the multi-objective permutation flow shop scheduling problem (Multi-objective PFSP,MPFSP) is studied systematically, and a multi-objective improved leapfrog algorithm is proposed to solve the problem. Firstly, the optimization principle and operation flow of leapfrog algorithm and its application in various optimization fields are systematically described. In order to solve the problem of weak local search ability of leapfrog algorithm, an improved leapfrog algorithm is proposed by combining the individual updating strategy of particle swarm optimization (PSO). The effectiveness of the improved algorithm is verified by solving the continuous function optimization problem. The new algorithm is superior to the standard leapfrog algorithm and particle swarm optimization algorithm in the optimization results and convergence speed. Secondly, the improved leapfrog algorithm is applied to minimize make span for PFSP,. In order to make the algorithm suitable for solving discrete combinatorial optimization problems, the algorithm coding is designed based on the rules of stochastic key representation. At the same time, to improve the quality of the initial solution, the improved NEH heuristic algorithm is used to generate the diversity of the initial solution. In order to reduce the computation time, the reversible principle of this problem is fully used to calculate make span.. The benchmark set is used to test, and the results are compared with the better results of other algorithms to solve this kind of problem, and the validity of the algorithm is verified. Finally, a multi-objective leapfrog algorithm is designed to solve the mathematical model of multi-objective PFSP, which is to minimize the total flow time, the maximum completion time and the maximum delay time. Four heuristic algorithms are used to generate high quality initial solutions, and an elite solution set is built to store Pareto solutions, and an adaptive niche method is used to maintain the elite solution sets. The benchmark set is used to test, and the algorithm is compared with the improved strength Pareto evolutionary algorithm, which is better for solving multi-objective problems. The validity of the algorithm is verified.
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：TH186
【参考文献】
相关期刊论文 前8条
1 李英海;周建中;杨俊杰;刘力;;一种基于阈值选择策略的改进混合蛙跳算法[J];计算机工程与应用;2007年35期
2 周鹏;;求解置换流水车间调度问题的混合蚁群算法[J];计算机工程与应用;2009年17期
3 王亚敏;潘全科;冀俊忠;包云;;基于蛙跳算法的零空闲流水线调度问题优化[J];计算机工程与应用;2010年17期
4 唐云岚;赵青松;高妍方;陈英武;;Pareto最优概念的多目标进化算法综述[J];计算机科学;2008年10期
5 刘延风;刘三阳;;改进微粒群优化求解置换流水车间调度问题[J];计算机集成制造系统;2009年10期
6 杨建国,丁慧敏,李蓓智;解决多目标Flow-shop问题的生物免疫调度算法[J];机械设计与研究;2002年04期
7 李宁,邹彤,孙德宝;带时间窗车辆路径问题的粒子群算法[J];系统工程理论与实践;2004年04期
8 徐宁,李春光,张健,虞厥邦;几种现代优化算法的比较研究[J];系统工程与电子技术;2002年12期
相关博士学位论文 前1条
1 胡成玉;面向动态环境的粒子群算法研究[D];华中科技大学;2010年
，本文编号：2378587
本文链接：https://www.wllwen.com/kejilunwen/jixiegongcheng/2378587.html
