基于免疫克隆算法的多目标flow shop生产调度的研究

发布时间：2017-12-31 09:17

本文关键词：基于免疫克隆算法的多目标flow shop生产调度的研究　出处：《华东理工大学》2011年硕士论文　论文类型：学位论文

【摘要】：生产调度问题的本质是一类优化排序问题,是运筹学的一个研究方向。该类问题一般可以描述为：在给定生产任务的前提下,按时间的先后顺序,将有限的人力、物力资源分配给不同的工作任务,以满足某些指定的性能指标。典型的调度问题包括需要完成的产品集合,每个产品的一系列工序操作集合,各个工序的加工需要占用的设备或其它资源,并必须按照一定的加工路线来进行加工。其目标是合理地安排产品加工次序和各产品加工开始时间,使得到的排列顺序满足约束条件,同时使一些性能指标得到优化。生产调度问题具有多个约束、多个目标、不确定性等特点,是典型的NP-hard问题,作为生产管理中的关键环节,研究其建模和优化,对提高生产效率有重要意义。针对多目标生产调度问题,本文深入研究多目标优化的相关理论,提出一种适应度共享策略,避免将多目标问题简单拟合为单目标问题。借鉴遗传算法和免疫克隆算法的基本原理和框架,结合生产调度问题进行改进,并将其成功应用于flow shop调度问题中。本文的主要贡献如下： (1)由于多目标优化问题并不存在一个唯一的最优解,而是需要找到Pareto意义下的非劣解。传统优化技术一般每次只能得到Pareto解集中的一个,而用进化算法求解,可以得到更多的Pareto非劣解。本文提出一种基于遗传算法的适应度共享策略,并成功应用于连续函数优化中,通过仿真实验验证了算法的可行性。 (2)免疫克隆算法借鉴生物免疫系统的相关原理和机制,对于解决工程优化问题具有良好效果。本文利用免疫克隆算法的基本原理和框架,针对多目标优化问题的特点,将其改进后引入到多目标问题中。免疫克隆策略对于Pareto非劣解的精英保留具有良好的作用。 (3)建立了基于最小化完成时间(makespan)和总流经时间(total flow time)的多目标flow shop调度模型。针对多目标flow shop问题,提出一种基于免疫克隆算法的非劣解分级和拥挤距离计算策略。通过适应度共享方式,对多目标问题的解进行评估。采用改进的免疫克隆策略,有效保留和利用了搜索到的非劣解信息；通过基因变异模式增加群体多样性,提高算法收敛性。大量仿真验证了调度模型的正确性和算法的优越性。
[Abstract]:The essence of the production scheduling problem is a kind of optimization scheduling problem, is a research direction of operational research. This kind of problem can be described as: given the production task, according to the time order, the limited manpower, material resources allocated to different tasks, to meet the specified performance index. Scheduling problem typically includes the need to complete the set of products, a set of operating procedures for each product, processing the various processes require equipment or other resources, and must be in accordance with certain processing route for processing. Its goal is to arrange the processing order and processing products of each product starting time, the order to meet the constraints, and make some performance indexes. The optimization production scheduling problem with multiple constraints, multiple objectives, characteristics of uncertainty, is a typical NP-hard problem, As the key link in production management, it is of great significance to study its modeling and optimization to improve production efficiency.
Aiming at the multi-objective scheduling problem, this paper studies the related theory of multi-objective optimization, proposes a fitness sharing strategy, avoid the multi-objective problem into single objective problem. A simple fitting from the basic principle and framework of the genetic algorithm and immune clone algorithm, combined with the production scheduling problem is improved, and applied it successfully flow shop scheduling problem.
The main contributions of this article are as follows:
(1) for multi-objective optimization problems is not only one optimal solution, but need to find non inferior solutions under Pareto. Traditional optimization techniques in general can only get a Pareto solution set, and evolutionary algorithm for solving non dominated solutions, can get more Pareto. This paper proposes a genetic algorithm the fitness sharing strategy based on, and successfully applied to continuous function optimization, simulation results verify the feasibility of the algorithm.
(2) the immune clonal algorithm reference principle and mechanism of the biological immune system, to solve engineering optimization problems with good results. This paper uses the basic principle and framework of the immune clonal algorithm for multi-objective optimization problems, the improvement is introduced to the multi-objective problem. Immune clone strategy has a good effect for Pareto Pareto elitist.
(3) is established to minimize the completion time based on (makespan) and total flow time (total flow time) multi-objective flow shop scheduling model for multi objective flow shop problem, this paper proposes a method to calculate the immune clonal algorithm Pareto classification and crowding distance. Through strategy based on fitness sharing method, solution evaluation for the multi-objective problem. By using the improved immune clonal strategy, effective retention and use of non inferior solutions to information search; through gene mutation patterns increase population diversity, improve the convergence of the algorithm. The simulation proved the superiority of the algorithm is correct and the scheduling model.

【学位授予单位】：华东理工大学
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：TH186

【引证文献】