基于多目标遗传粒子群混合算法求解混合流水车间调度问题研究

发布时间：2019-03-01 10:35

【摘要】：随着全球性经济的飞速发展,制造产业面临着新的挑战,企业要想在激烈的竞争中立于不败之地,必须以最低的成本、最好的质量、最快的速度和最优的服务来响应市场。通过改善生产调度方案,可以有效地提高企业的生产效率,增强企业的市场竞争力,由此调度问题应运而生。车间调度问题就是要解决如何利用有限的资源在满足各种生产约束的前提下,确定工件和设备的加工顺序和时间,使性能指标最优。然而企业的实际生产调度过程中,一般不会单纯的只考虑一个目标,往往同时考虑多个目标,多目标优化问题就会普遍存在,因此多目标混合流水车间调度问题(Hybrid Flow-Shop Scheduling Problem, HFSP)的研究有重大意义。本文通过对遗传算法(Genetic Algorithm, GA)和粒子群算法(Particle Swarm Optimization, PSO)进行融合,提出了一种针对HFSP的多目标遗传粒子群混合算法。遗传算法具有较强的鲁棒性和群体寻优能力,但其存在过早收敛和后期搜索效率低的问题,粒子群具有计算简单和效率高的特点,但存在易早熟和陷入局部最优的缺点。在分别分析了遗传算法和粒子群算法优劣势的基础上,取长补短,利用遗传算法优秀的群体寻优能力,总体上把握进化的方向,根据粒子群算法计算简单、效率高的特点,首先进行多个粒子群的独立进化,快速地全面搜索出较优良的个体,各粒子群之间亦实行个体迁移,以扩大搜索领域,然后采集各粒子群的最优个体组成遗传算法的初始种群,进行遗传操作,随后用得到的优良个体代替种群中的较劣个体,如此循环,高效率地找到目标最优解。本文在详细分析了HFSP基础上,建立了一套完整的多目标遗传粒子群混合算法求解方案。本文实现了利用多目标遗传粒子群混合算法解决HFSP,首先根据企业生产中常见的优化目标建立了HFSP模型,在此基础上,利用HFSP中的经典实例进行测试,分析评估了算法的效率,并将该算法的结论与其他算法进行比较,结果表明,该算法有明显的优越性,可以有效地解决HFSP,具有良好的应用前景。
[Abstract]:With the rapid development of the global economy, the manufacturing industry is facing new challenges. In order to be invincible in the fierce competition, enterprises must respond to the market with the lowest cost, the best quality, the fastest speed and the best service. By improving the production scheduling scheme, the production efficiency of the enterprise can be effectively improved and the market competitiveness of the enterprise can be enhanced, thus the scheduling problem emerges as the times require. The problem of job-shop scheduling is to solve the problem of how to make use of limited resources to determine the processing order and time of workpieces and equipment under the premise of satisfying various production constraints, so as to optimize the performance index. However, in the actual production scheduling process of an enterprise, the multi-objective optimization problem will generally exist because it does not only consider only one goal, but also considers more than one goal at the same time. Therefore, the study of multi-objective hybrid flow shop scheduling problem (Hybrid Flow-Shop Scheduling Problem, HFSP) is of great significance. Based on the fusion of genetic algorithm (Genetic Algorithm, GA) and particle swarm optimization (Particle Swarm Optimization, PSO), a hybrid multi-objective genetic particle swarm optimization algorithm for HFSP is proposed in this paper. Genetic algorithm has strong robustness and population optimization ability, but it has the problems of premature convergence and low search efficiency in late stage. Particle swarm optimization has the characteristics of simple calculation and high efficiency, but it is easy to precocity and fall into local optimization. Based on the analysis of the advantages and disadvantages of genetic algorithm and particle swarm optimization algorithm, the advantages and disadvantages of genetic algorithm and particle swarm optimization algorithm are analyzed, and the excellent population optimization ability of genetic algorithm is used to grasp the direction of evolution in general. According to the characteristics of simple calculation and high efficiency of particle swarm optimization algorithm, First, the independent evolution of multiple particle swarm groups is carried out, and the better individuals are searched out quickly and comprehensively. The individual migration is also carried out among the particle swarm to expand the search field, and then the optimal individuals of each particle swarm are collected to make up the initial population of genetic algorithm. Genetic manipulation is carried out, and then the superior individuals are used to replace the inferior individuals in the population, so that the target optimal solution can be found efficiently in this cycle. In this paper, based on the detailed analysis of HFSP, a complete set of multi-objective genetic particle swarm hybrid algorithm is proposed. In this paper, a hybrid multi-objective genetic particle swarm algorithm is used to solve HFSP,. Firstly, the HFSP model is established according to the common optimization objectives in enterprise production. On this basis, the classical examples in HFSP are used to test, and the efficiency of the algorithm is analyzed and evaluated. The conclusion of the algorithm is compared with other algorithms, and the results show that the algorithm has obvious advantages and can effectively solve HFSP, has a good application prospect.
【学位授予单位】：大连交通大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP18;TB497

【相似文献】