改进细菌觅食算法求解流水线调度问题

发布时间：2018-03-22 18:29

本文选题：流水线调度　切入点：细菌觅食算法　出处：《西南交通大学》2014年硕士论文　论文类型：学位论文

【摘要】：进入21世纪以来,市场竞争越来越激烈,人们的需求也越来越多样化,因此结合多种方法与技术而产生的先进制造系统已经成为现阶段企业共同关注的一种重要的生产制造模式。生产调度作为先进制造系统中的一个关键的模块,是企业提高生产率、降低生产成本、提高综合实力的基础和关键。流水线调度问题是生产调度领域研究得最广泛的问题之一,相关资料表明：约有四分之一的生产制造系统或组装线都可以简化成流水线模型,具有很强的工业应用背景；再加上该问题的NP-hard性质,常规方法难以求解,因此对该问题的研究也具备理论价值。论文首先研究了混合流水线调度问题,对其研究背景、分类以及研究方法进行了分析,为论文的研究做好理论准备；然后结合流水线调度问题的特点以及细菌觅食优化算法求解组合优化问题的优势,提出运用一种改进的细菌觅食优化算法求解流水线调度问题。其次在深入研究标准细菌觅食优化算法的基础上,针对算法的不足,提出引入交叉优化算子、混合复制策略以及基于健康度和适应度共同作用的自适应迁徙概率以改进算法的策略。最后针对混合流水线调度问题中的置换流水线调度问题和零空闲流水调度问题,分别从编码方式、初始化、适应度函数、主要操作算子以及终止条件五个方面进行改进细菌觅食优化算法的设计,并通过Matlab编程实现算法对典型流水线调度问题的求解,以验证算法的有效性；同时通过标准算法和改进算法的对比体现了改进算法的优化性能,并对比了两种初始化方法对改进算法的影响，以验证算法的初始解鲁棒性。结果表明：在中小规模的流水线调度问题中,改进细菌觅食优化算法的性能优于标准算法,能获得问题的最优解,并且具有良好的初值鲁棒性。
[Abstract]:Since the beginning of the 21st century, market competition has become more and more intense, and people's needs have become more and more diversified. Therefore, advanced manufacturing system (AMS) combined with many methods and technologies has become an important mode of production and manufacturing that enterprises are paying close attention to at present. Production scheduling is a key module in AMS. Pipeline scheduling is one of the most widely studied problems in the field of production scheduling. The related data show that about 1/4 manufacturing systems or assembly lines can be simplified into pipeline model, which has a strong industrial application background, and the NP-hard properties of the problem make it difficult to solve the problem by conventional methods. Therefore, the study of this problem also has theoretical value. Firstly, the mixed pipeline scheduling problem is studied, the research background, classification and research methods are analyzed, and the theoretical preparation for the research is made. Then combined with the characteristics of pipeline scheduling problem and the advantages of bacterial foraging optimization algorithm to solve combinatorial optimization problem, An improved bacterial foraging optimization algorithm is proposed to solve the pipeline scheduling problem. Secondly, based on the in-depth study of the standard bacterial foraging optimization algorithm, a crossover optimization operator is proposed to solve the deficiency of the algorithm. Hybrid replication strategy and adaptive migration probability based on health and fitness are used to improve the algorithm. The improved bacterial foraging optimization algorithm is designed from five aspects of coding mode, initialization, fitness function, main operator and termination condition, and the solution of typical pipeline scheduling problem is realized by Matlab programming. In order to verify the effectiveness of the algorithm, the optimization performance of the improved algorithm is reflected by the comparison between the standard algorithm and the improved algorithm, and the influence of the two initialization methods on the improved algorithm is compared. The results show that the performance of the improved bacterial foraging optimization algorithm is better than that of the standard algorithm in the small and medium scale pipeline scheduling problem, and the optimal solution of the problem can be obtained, and it has good initial robustness.
【学位授予单位】：西南交通大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TB497;TP18

【参考文献】