基于改进蛙跳算法和AGA的flow shop调度问题研究

发布时间：2018-02-27 20:15

本文关键词： flow shop调度蛙跳算法不确定性异步进化　出处：《华东理工大学》2011年硕士论文　论文类型：学位论文

【摘要】：生产计划和调度处于计算机集成制造系统的核心位置,它向上对企业的经营战略决策层负责,向下对监控控制层发出控制指令,确保生产的有序进行,是CIMS成功实施与否的关键。生产调度问题关系着企业成本的控制和利益的最大化,对于促进我国的制造业走向全球化、信息化、集成化有着深远的影响。Flowshop调度是一个典型的调度问题,本文着重研究通过设计和改进智能优化算法来解决flow shop调度问题,并通过大量的仿真实验,验证了所提算法的可行性和有效性。对于以Makespan为目标的置换flow shop问题,引入了一种新的智能优化算法蛙跳算法,蛙跳算法融合了SCE (Shuffled Complex Evolution)算法和离散粒子群算法的优良思想,实现了全局的信息共享。针对蛙跳算法容易产生非法调度的问题,设计了一种新青蛙跳跃规则来改善基本蛙跳算法的算法性能,仿真实验表明改进的蛙跳算法比基本的蛙跳算法和遗传算法更加有效。对于加工时间不确定的flow shop调度问题,通过模糊数学的方法来描述加工时间的不确定性,在基本蛙跳算法的基础上,借鉴交换子和交换序的概念,提出了“交换序构造的初始位置随机机制”和“交换子的随机插入机制”这两种追踪策略。通过与遗传算法比较,仿真实验结果验证了改进蛙跳算法在解决具有不确定性加工时间的flow shop问题上的有效性。对于以总流经时间为目标的置换flow shop问题,提出了一种全新的遗传算法,异步遗传局部搜索算法AGA (Asynchronous Genetic Local Search Algorithm)。AGA包含三个阶段：在第一个阶段产生随机的初始种群,其中的一个解由构造型的启发式算法产生；在第二个阶段,种群内的个体两两配对,进行异步进化操作,其中运用了一个简单的交叉算子和一个加强的邻域搜索策略；在最后一个阶段,采用一个重启策略来防止算法陷入局部极小。仿真实验表明,AGA比一些经典的算法和两个最近提出的后启发式算法更加有效,同时对于90个Benchmark问题,AGA得到了89个目前已知的最优解,其中54个是由AGA最新得到的。
[Abstract]:Production planning and scheduling is the core of the computer integrated manufacturing system, which is responsible for the management strategy decision level of the enterprise, and issues control instructions to the monitoring and control layer to ensure the orderly production. Production scheduling is the key to the successful implementation of CIMS. The problem of production scheduling is related to the control of enterprise cost and the maximization of benefits. Integration has far-reaching influence. Flow shop scheduling is a typical scheduling problem. This paper focuses on the design and improvement of intelligent optimization algorithm to solve flow shop scheduling problem, and through a large number of simulation experiments. The feasibility and effectiveness of the proposed algorithm are verified. For the permutation flow shop problem with Makespan as the target, a new intelligent optimization algorithm is introduced. The leapfrog algorithm combines the excellent ideas of SCE Shuffled Complex Evolution algorithm and discrete Particle Swarm Optimization algorithm. The global information sharing is realized. A new frog jump rule is designed to improve the performance of the basic frog jump algorithm. Simulation results show that the improved leapfrog algorithm is more effective than the basic leapfrog algorithm and genetic algorithm. For the flow shop scheduling problem with uncertain processing time, the uncertainty of processing time is described by fuzzy mathematics. Based on the basic leapfrog algorithm, the concepts of commutator and exchange order are used for reference. In this paper, two kinds of tracking strategies are proposed, namely, the initial position random mechanism of commutative order construction and the random insertion mechanism of commutator. The simulation results show that the improved leapfrog algorithm is effective in solving the flow shop problem with uncertain processing time. For the permutation flow shop problem with total flowing time as the target, a new genetic algorithm is proposed. The asynchronous genetic local search algorithm AGA / Asynchronous Genetic Local Search Algorithm).AGA consists of three stages: generating random initial population in the first stage. One of the solutions is generated by a constructive heuristic algorithm, and in the second stage, the individuals in the population are paired together to perform asynchronous evolutionary operations, in which a simple crossover operator and an enhanced neighborhood search strategy are used. In the final phase, a restart strategy is adopted to prevent the algorithm from falling into local minimization. The simulation results show that the algorithm is more effective than some classical algorithms and two recently proposed post-heuristic algorithms. At the same time, 89 known optimal solutions are obtained for 90 Benchmark problems, 54 of which are obtained by AGA.
【学位授予单位】：华东理工大学
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：TH166

【参考文献】