基于EDA智能优化算法的复杂车间调度问题研究

发布时间：2018-08-04 13:07

【摘要】：生产制造系统中通常伴随有规模大、强约束、非线性、多目标、不确定、NP-hard等诸多复杂因素,因此针对智能优化算法和生产调度理论的应用与研究始终都是工业界与学术界的重要研究课题。流水线调度是一类非常典型且有广泛工程背景的复杂组合优化问题,其相关理论和算法的研究具有重要的科研价值与实际意义。分布估计算法借鉴机器学习中的统计学习进化思想,有较强的全局引导性,已成为优化领域的研究热点。本文研究两类典型的流水线生产调度问题,结合问题特性提出了有效的全局模型,并设计了高效的局部策略,提出的增强分布估计算法可为流水优化调度提供理论与算法支持。全面综述两类复杂流水调度问题和分布估计算法研究进展的基础上,本文的研究工作主要获得以下成果:(1)针对优化指标为最小化总完工时间的带序相关设置时间与释放时间的零等待流水线调度问题,提出了一种采用快速评价和基于问题性质的Insert局部搜索的有效混合分布估计算法。通过典型算例的大量仿真结果和算法比较,验证了所提算法的有效性与鲁棒性。(2)针对优化指标为最小化总体提前和滞后时间的带序相关设置时间和释放时间的零等待流水线调度问题,首次提出了一种有效的基于三维矩阵立方体的分布估计算法,能够有效学习解空间内优秀解的序关系和构造块信息,引导全局搜索方向;并设计了基于快速扫描方法和两种有效搜索策略的快速局部搜索方法,用于对已寻找到优势解区域进行深度搜索。此外,还进一步探讨了关键参数和操作对算法性能的影响。通过典型测试问题的仿真结果与比较,验证了所提算法的有效性和鲁棒性。(3)针对分布式两阶段装配流水线调度问题,给出了其数学描述并设计了考虑问题特性的有效编码与解码方法。通过基于三维矩阵立方体的分布估计算法最小化其最大完工时间,设计了关键路径搜索方法和变邻域搜索并应用于Insert和Interchange的局部搜索中,进而加速引导进化方向使其趋近于全局最优区域。通过国际标准问题集的大量仿真测试和算法比较,验证了所提方法的有效性、高效性和鲁棒性。
[Abstract]:Manufacturing systems are usually accompanied by large scale, strong constraints, nonlinear, multi-objective, uncertain NP-hard and many other complex factors. Therefore, the application and research of intelligent optimization algorithm and production scheduling theory is always an important research topic in industry and academia. Pipeline scheduling is a kind of complex combinatorial optimization problem with a very typical and extensive engineering background. The research of related theories and algorithms has important scientific research value and practical significance. The distribution estimation algorithm, which uses the evolutionary thought of statistical learning in machine learning for reference, has a strong global guidance and has become a hot research topic in the field of optimization. In this paper, two kinds of typical pipeline production scheduling problems are studied, and an effective global model is proposed based on the characteristics of the problem, and an efficient local strategy is designed. The proposed augmented distribution estimation algorithm can provide theoretical and algorithmic support for pipeline optimal scheduling. Based on a comprehensive review of the research progress of two kinds of complex pipeline scheduling problems and distribution estimation algorithms, The main achievements of this paper are as follows: (1) for the zero wait pipeline scheduling problem with order dependent setup time and release time, the optimization index is to minimize the total completion time. An efficient mixed distribution estimation algorithm based on fast evaluation and Insert local search based on problem properties is proposed. A large number of simulation results and algorithms are compared with typical examples. The effectiveness and robustness of the proposed algorithm are verified. (2) the zero-wait pipeline scheduling problem with sequence dependent setup time and release time is optimized to minimize the overall advance and delay time. For the first time, an effective distribution estimation algorithm based on 3D matrix cubes is proposed, which can effectively learn the order relation of excellent solutions in solution space and the information of construction blocks, and guide the global search direction. A fast local search method based on the fast scanning method and two effective search strategies is designed to search the region where the dominant solution has been found. In addition, the effects of key parameters and operations on the performance of the algorithm are also discussed. Simulation results of typical test problems show that the proposed algorithm is effective and robust. (3) for the distributed two-stage assembly pipeline scheduling problem, The mathematical description is given and an effective encoding and decoding method considering the characteristics of the problem is designed. The distribution estimation algorithm based on 3D matrix cube is used to minimize the maximum completion time. A critical path search method and variable neighborhood search are designed and applied to the local search of Insert and Interchange. Furthermore, it can accelerate the direction of evolution and make it approach the global optimal region. The effectiveness, efficiency and robustness of the proposed method are verified by a large number of simulation tests and algorithm comparisons of the international standard problem sets.
【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18;TB497

【参考文献】