一种基于改进遗传算法的柔性流水车间调度问题研究

发布时间：2018-10-23 07:18

【摘要】：柔性流水车间调度问题(Flexible Flowshop Scheduling Problem, FFSP)属于现实生产调度领域抽象出的简化模型,该问题是并行机与排序问题的扩展,它的主要特征是在某些工序或者全部工序上存在并行的机器,广泛存在于流程制造业中,在企业生产管理中占有核心地位。企业只有根据需求利用合理的调度方案分配制造资源才能够有效的提高生产效率,从而提高自身的竞争力。但是目前还没有一个行之有效的智能算法来解决该问题,因此,对于该问题的智能算法研究具有十分重要的理论意义与现实价值。遗传算法(Genetic Algorithm)是自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。其特点是简单通用、鲁棒性强、适合于并行处理等,如今已作为一种新的被广泛应用的全局优化智能搜索算法,尤其是在解决生产调度问题中取得了很大的突破。但是在算法发展的过程中,简单的遗传算法还有一些缺点存在,主要存在搜索效率低下、过早地收敛、容易陷入局部极值等等问题。基于以上原因,需要对简单的遗传优化算法进行了改进,从而能够应用于实际的柔性流水车间调度问题求解。本文主要做了以下工作：首先,针对目前国内外车间调度的研究现状以及存在的问题,本文对柔性流水车间调度问题进行了详细地研究。其次,以某铝厂的生产车间的调度问题为原型提出了带调整时间的柔性流水车间调度问题,并建立了数学模型。之后根据该数学模型的特点提出了一种基于三元矩阵的新型编码方法,以最小生产时间为目标,对于传统遗传算法存在的收敛速度慢、易陷入局部最优的缺点进行了改进,设计了一种采用精英保留策略的自适应的改进遗传算法,该算法改进了交叉算子和变异算子,使其随着适应度函数的变化而自适应变化从而提高了算法的效率。最后,对于本文提出的算法以一个实例进行验证并与传统遗传算法进行了对比,实验结果表明本文算法得到了一个较好的调度结果,同时无论是调度的结果还是算法的收敛速度上本文提出的算法都有明显的优越性。
[Abstract]:Flexible flow shop scheduling problem (Flexible Flowshop Scheduling Problem, FFSP) is an abstract simplified model in the field of real production scheduling. It is an extension of parallel machine and scheduling problem. Its main feature is that there are parallel machines in some or all processes. Widely exist in the process manufacturing industry, in the enterprise production management occupies the core position. Only when enterprises allocate manufacturing resources according to their needs can they improve their production efficiency and improve their competitiveness. However, there is not an effective intelligent algorithm to solve the problem, so the research of intelligent algorithm has very important theoretical significance and practical value. Genetic algorithm (Genetic Algorithm) is a computational model of biological evolutionary processes based on natural selection and genetic mechanism. It is a method to search for optimal solutions by simulating natural evolutionary processes. Its characteristics are simple and general, strong robustness, suitable for parallel processing, etc. It has been a new and widely used global optimization intelligent search algorithm, especially in the production scheduling problem has made a great breakthrough. However, in the process of the development of the algorithm, the simple genetic algorithm still has some shortcomings, such as low search efficiency, premature convergence, easy to fall into local extremum and so on. For the above reasons, it is necessary to improve the simple genetic optimization algorithm, so that it can be applied to the practical flexible flow shop scheduling problem. The main work of this paper is as follows: firstly, aiming at the present situation and existing problems of job shop scheduling at home and abroad, the flexible flow shop scheduling problem is studied in detail in this paper. Secondly, a flexible flow-shop scheduling problem with adjustment time is proposed based on the scheduling problem of a production shop in an aluminum plant, and a mathematical model is established. Then, according to the characteristics of the mathematical model, a new coding method based on ternary matrix is proposed. Aiming at the minimum production time, the traditional genetic algorithm has the disadvantages of slow convergence speed and easy to fall into local optimum. An adaptive genetic algorithm with elite reservation strategy is designed. The algorithm improves the crossover operator and mutation operator and makes them change adaptively with the change of fitness function so as to improve the efficiency of the algorithm. Finally, the proposed algorithm is verified by an example and compared with the traditional genetic algorithm. The experimental results show that the proposed algorithm has a better scheduling result. At the same time, both the scheduling results and the convergence rate of the algorithm presented in this paper have obvious advantages.
【学位授予单位】：广东工业大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP18;TB497

【参考文献】