基于问题结构特性的混合差分进化调度理论与方法研究

生产调度问题通常具有NP（Nondeterministic Polynomial, NP）难、大规模、多目标、不确定、强约束等复杂性，智能优化调度理论和高效算法的研究一直是学术界和工业界的热点课题。从复杂生产调度问题的研究现状来看，将问题结构的特有性质和智能优化算法有机结合是设计高效算法的关键。本项目将研究基于复杂生产调度问题结构特性的混合差分进化（Differential Evolution,DE）调度理论与方法：① 研究调度问题结构特性的相关理论；② 研究混合DE的统一框架、收敛性理论和高性能算法策略；③ 给出基于问题结构特性的复杂流水线系列调度问题、复杂作业车间系列调度问题、不确定调度问题和半导体生产调度问题的高性能混合DE算法。研究成果将丰富和深化已有的优化调度理论，还可对指导实际生产提供有益的帮助。

本项目取得了预定研究成果。项目的主要工作归纳如下：. 1、通过分析不同指标下带序相关设置时间和释放时间的零等待流水线调度问题的结构特性，提出了结合差分进化（Differential Evolution, DE）机制和问题解结构性质的一系列HDE算法，并探讨了不同操作和参数对算法性能的影响。基于算例的大量仿真结果和算法比较，验证了所提算法的高效性。. 2、针对加工时间不确定的有限缓冲区置换流水线调度问题，通过在DE算法中融合最优计算量分配（Optimal Computing Budget Allocation, OCBA）技术以及假设检验（Hypothesis Test, HT）策略，提出了一种鲁棒的混合DE算法，记作OHTDE算法，并基于Markov链理论分析了该算法的收敛性；针对工件动态到达设置时间序相关的零等待流水线调度问题，提出了滚动窗口策略和混合DE算法相结合的有效处理方法，并在理论上分析了所提策略的全局性能。. 3、在所提HDE算法基础上，有机融合针对具体问题的特性而设计的有效局部搜索操作，提出了解决m台机器可重入置换流水线调度问题的混合种群增量学习算法，以及解决带不同工件重入次数的可重入置换流水线调度问题的混合DE算法。基于算例的大量仿真结果和算法比较，验证了所提算法的有效性和鲁棒性。. 4、通过分析可重入多目标作业车间调度问题的解空间特点，结合拓展的活动化解码策略和变邻域搜索策略，设计了一种多目标混合DE算法。基于算例的仿真结果和算法比较，验证了所提算法的有效性。. 5、针对聚丙烯生产过程批调度问题，参与了实地调研和问题建模，将实际问题建模为一种复杂的多阶段柔性流水线调度问题；针对流水线调度问题，参与提出了一种概率混合进化算法。基于算例的大量仿真结果和算法比较，验证了所提模型和算法的有效性。. 以上的研究成果可丰富和深化已有的优化调度理论，还可对实际工程提供帮助。