基于改进蛙跳算法的生产调度问题研究

发布时间：2018-10-14 19:21

【摘要】：生产调度问题作为企业生产管理和计算机集成制造系统的核心部分,近年来一直受到广大学者的密切关注。其主要任务是分配有限的企业资源,达到经济或性能上的需求目标。显而易见,系统、全面、合理、优化的生产调度方案不仅有助于提高企业的综合管理水平,而且可以为企业带来显著的经济效益。生产调度问题己被证明属于NP-hard问题,因此传统的优化方法己不能有效地求解大规模复杂的调度问题。基于此,近年来各种不同的人工智能方法逐渐被引入到调度领域中,取得了很大进展。其中随着计算机技术以及人工智能技术的迅猛发展,群智能优化算法应运而生。它可以在较短的时间内得到令人满意的近似最优解,已经成为了一类能够有效解决生产调度问题的新型方法。本文深入研究了经典的和带阻塞的流水车间调度问题,建立了相应的数学模型,提出了两种群智能优化算法并成功应用到这些问题中。本文的主要研究成果如下： (1)针对带阻塞流水车间调度问题(Blocking Flowshop Scheduling Problem, BFSP),提出了一种离散群搜索优化算法(New Modified Shuffled Frog Leaping Algorithm, NMSFLA)用来最小化最大完工时间。NMSFLA在基本蛙跳算法的局部搜索步骤中引入带约束的交叉变异思想,针对调度问题对青蛙的跳跃规则做出了改进,有效地解决了传统蛙跳算法局部搜索易出现不合法解导致算法效率不高的问题。基于标准算例的大量仿真测试结果表明,提出的NMSFLA算法具有明显的可行性和有效性。 (2)针对流水车间调度问题(Flowshop Scheduling Problem, FSP)提出了一种极值蛙跳算法(EO-SFLA)用来最小化总流水时间。在EO-SFLA算法中,细化了分配子种群个体的规则；对于局部搜索过程,简化了传统蛙跳算法的跳跃公式；同时引入了τ-EO算法的思想；最后,引入了新的叠加跳跃公式,认为每个个体都会保留他们自己前一时刻的跳跃状态。基于Taillard标准算例的仿真实验表明,提出的EO-SFLA算法具有明显的优越性。
[Abstract]:As the core part of enterprise production management and computer integrated manufacturing system, production scheduling problem has been paid close attention by many scholars in recent years. Its main task is to allocate limited enterprise resources to achieve economic or performance requirements. It is obvious that the systematic, comprehensive, reasonable and optimized production scheduling scheme can not only help to improve the comprehensive management level of the enterprise, but also bring remarkable economic benefits to the enterprise. Production scheduling problem has been proved to be a NP-hard problem, so the traditional optimization method can not effectively solve large-scale complex scheduling problem. Based on this, various artificial intelligence methods have been gradually introduced into the field of scheduling in recent years, and great progress has been made. With the rapid development of computer technology and artificial intelligence technology, swarm intelligence optimization algorithm emerges as the times require. It can obtain a satisfactory approximate optimal solution in a short time. It has become a new method which can effectively solve the production scheduling problem. In this paper, the classical and blocked flow shop scheduling problems are studied in depth, the corresponding mathematical models are established, and a two-species intelligent optimization algorithm is proposed and successfully applied to these problems. The main results of this paper are as follows: (1) A discrete group search optimization algorithm (New Modified Shuffled Frog Leaping Algorithm, NMSFLA) is proposed to minimize the maximum completion time for (Blocking Flowshop Scheduling Problem, BFSP), with blocking flow scheduling problem. The idea of crossover mutation with constraints is introduced into the local search steps of the basic leapfrog algorithm. The jumping rules of frog are improved to solve the problem that the local search of the traditional leapfrog algorithm is easy to produce illegal solution which leads to the low efficiency of the algorithm. A large number of simulation results based on standard examples show that, The proposed NMSFLA algorithm is feasible and effective. (2) an extremum leapfrog algorithm (EO-SFLA) is proposed to minimize the total running time for the flow shop scheduling problem (Flowshop Scheduling Problem, FSP). In the EO-SFLA algorithm, the rules of assigning individual subpopulations are refined; for the local search, the jumping formula of the traditional leapfrog algorithm is simplified; at the same time, the idea of 蟿-EO algorithm is introduced. Finally, a new superposition jump formula is introduced. Think that each individual will retain their own jumping state of the previous moment. The simulation results based on Taillard standard examples show that the proposed EO-SFLA algorithm has obvious advantages.
【学位授予单位】：华东理工大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TB497

【参考文献】