基于两种新型元启发式算法的作业车间调度问题研究

发布时间：2019-05-06 06:23

【摘要】：作业车间调度问题(Job shop scheduling problem,JSP)是制造领域内著名的车间调度问题,同时也是最困难的组合优化问题之一。它可描述为,车间内各工件都具备其特定的加工路径,且使用机器的顺序及每道工序的加工时间已知,目的是解决车间内各工件在机器上的加工顺序问题,以达到最优的预期性能。该问题的发展过程也是学者们认识问题本质、探索新型算法和改进已有算法的过程。考虑到问题求解的难度,元启发算法的提出为车间调度问题的求解提供了一种新的思路和手段,目前已得到了国内外学者们广泛的关注和兴趣。本论文在对作业车间调度问题进行分析的基础上,采用两种不同的新兴元启发式算法对作业车间调度问题进行研究,主要内容概括如下:(1)首先对JSP问题的基础知识进行简单的介绍,如JSP问题的描述、问题的特性、数学模型的建立、问题的表示、问题的分类、GT算法以及编码设计方法等。(2)将候鸟迁徙优化算法(Migrating birds optimization,MBO)应用到作业车间调度问题的求解当中。为了充分体现问题的特点,首先设计了合理的编码和解码机制,并给出了基于启发式算法的种群初始方案,用于保证初始种群中解的质量和多样性。其次,根据所研究的问题特点,设计了三种邻域结构对个体邻域解进行构造。此外,将变邻域搜索算法嵌入到候鸟优化算法中,以加强该算法的局部搜索能力。最后,使用五种基准算例对所提出的改进候鸟迁徙优化算法(Improved migrating birds optimization,IMBO)进行测试,并将计算结果与其他文献中算法结果进行比较,验证该算法的有效性。(3)将猫群算法(Cat swarm optimization,CSO)应用到作业车间调度问题的求解当中。考虑到问题特点和算法特性,首先设计了可行的编码和解码机制,实现了算法中离散问题的连续编码,并给出了基于启发式算法的种群初始方案,保证了该算法初始种群中解的质量和多样性。其次,设计了两种不同的搜寻模式和跟踪模式,并给出了一种自适应行为模式选择方法。此外,在算法搜索过程中引入了变邻域搜索策略,以增强猫群算法的局部搜索能力。最后,使用五种基准算例对所提出的改进猫群算法(Improved cat swarm optimization,ICSO)进行测试,并将计算结果与改进候鸟优化算法结果进行比较,验证该算法的有效性。
[Abstract]:......
【学位授予单位】：华北电力大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18;TB497

【参考文献】