论文部分内容阅读
生产调度问题通常具有NP难、大规模、强约束等特性。生产调度有效算法的研究日益受到工业界和学术界的重视。差分进化(Differential Evolution, DE)作为一种简单有效的智能算法,已受到广泛关注并在多个领域得到了成功应用。因此,本论文对三类重要生产调度问题进行基于混合DE的求解算法研究。论文的主要工作归纳如下：(1)针对总体完成时间(the total completion time)指标下的带序相关设置时间和释放时间的零等待流水线调度问题,通过分析问题的结构特性,设计了一种基于快速评价解方法的有效局部搜索,进而与DE的全局搜索有机结合,得到混合DE算法,通过仿真实验和比较验证了算法的有效性。(2)针对总体加权提前/拖后完成时间(the total weighted earliness/tardiness)指标下的带序相关设置时间和释放时间的零等待流水线调度问题,根据问题模型的结构特性,将(1)中的快速评价解方法拓展运用于该问题,同时采用基子邻域分解策略和"first move"策略的interchange邻域快速搜索来构造局部搜索,进而结合DE的全局搜索机制,提出了一种高效混合DE算法,仿真实验和比较验证了算法的高效性和鲁棒性。(3)针对最大完成时间(makespan)指标下的作业车间调度问题,利用活动化解码机制来减少搜索空间,同时将已有的离散化DE算法和基于interchange邻域的小却有效的局部搜索有机融合,进而得到一种有效混合离散DE算法,仿真实验验证了混合的必要性和算法的有效性。由于对广泛存在于流程工业的带序相关设置时间和释放时间的零等待流水线调度问题尚无基于DE的调度算法研究,本论文主要针对该类问题研究如何设计基于混合DE的有效调度算法,同时针对离散混合DE在JSP中的应用研究屈指可数的现状,本论文也对如何将已有的离散化DE算法和自行设计的局部搜索有机融合进行了探讨,故对其研究具有重要的学术和工程价值,并具有一定的创新性。