基于适应度地形的组合优化与作业车间调度问题研究

摘要

车间调度是影响制造业生产效率的关键因素。在制造环境中，调度就是对加工过程进行作业计划。采用高效的调度，可以“缩短工期、减少库存、按时交货、提高信誉”。随着全球市场竞争的加剧和客户需求的个性化，车间调度问题愈来愈受到重视。 大多数车间调度问题是NP难的，求解作业车间调度问题的最小加工时间是经典的组合优化问题之一。算法求解的效率与所要解决的问题特征密切相关，由于目前还缺乏对作业车间调度问题复杂性的深入研究，造成了目前求解组合优化问题时算法的选择和参数设置具有盲目性。 本文在研究背包问题和旅行商问题的适应度地形特征的基础上，分析了作业车间调度问题的复杂性，研究了作业车间调度问题的结构与适应度地形及其影响因素，研究了车间调度问题的Backbone，通过挖掘调度问题的内在结构与性质，为作业车间调度的研究提供一个新的理论支持；并在此基础上，提出了相应的调度框架与调度方法。为指导组合优化问题和作业车间调度问题的算法选择提供了一定的依据，并为建立衡量组合优化问题的近优算法效率的标准迈出了探索性的一步。 首先，介绍了组合优化问题的一般研究方法以及无免费午餐定理，针对背包问题和旅行商问题，研究了它们的适应度地形，并对这些问题的解的特征、影响适应度地形的因素进行了分析。 然后，研究了作业车间调度问题的数学模型和析取图模型，分析了作业车间调度问题的复杂性，针对该问题分析了解的特征、影响适应度地形的主要因素，以及适应度地形的不规则性，研究了作业车间调度问题的Backbone与解之间距离的关系。 其次，针对作业车间调度问题的适应度地形，分析了进化算法求解作业车间调度问题的机理，研究了算法中交叉和变异在求解作业车间调度问题时的作用，针对三种典型的适应度地形，提出了一种基于适应度地形的动态调整算法，可以高效、快速地求解三种典型的作业车间调度问题，并开发了相应的软件。采用作业车间调度问题的标准测试实例进行验证，验证了该算法的有效性。 最后，对全文进行了总结，并对基于适应度地形的作业车间调度这一研究方向进行了展望。