鲸鱼优化算法及其在阻塞流水车间调度中的研究

作     者：包海 

作者单位：兰州理工大学 

学位级别：硕士

导师姓名：赵付青

授予年度：2022年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0802[工学-机械工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：阻塞流水车间调度 鲸鱼优化算法 启发式方法 序列相关准备时间 分布式调度 

摘      要：复杂车间调度优化是制造执行系统的重要组成部分,而制造执行系统又是连接整个制造业系统的中枢和纽带,因此提升调度优化效率是智能制造系统高效运行的关键技术,是提高企业制造执行能力的核心环节,也是我国从制造大国走向制造强国的重中之重。生产调度作为一类典型的组合优化问题,通常具有复杂性、多约束性、多目标等特点,而大多数生产调度问题也属于NP(Non-deterministic Polynomial)难问题,因此此类问题也成为学术界亟待解决的关键问题。车间调度的任务是在一定的资源(包括生产物料资源、能源动力资源、加工设备资源、资金技术资源等)约束条件下,合理地安排工件在各个机器上的加工次序,使一个或多个生产目标达到最优。流水车间调度问题作为车间调度问题的重要分支,广泛地存在于冶金、机械、电子、化工等制造领域。与传统流水车间调度问题相比,阻塞流水车间调度问题考虑了在无缓冲区场景下的调度问题,更贴近实际生产场景,具有更重要的理论意义和实际应用价值。鲸鱼优化算法(Whale Optimization Algorithm,WOA)是一种模拟海洋中座头鲸捕食行为的群智能优化算法。该算法具有结构简单、参数少、搜索能力强等特点。此外,还因其独特的学习机制和高效的全局搜索能力使得鲸鱼优化算法备受关注。本文结合实际生产中面临的几种约束,对阻塞流水车间调度问题及其扩展进行了深入研究。通过设计协同学习型的鲸鱼优化算法,提出了五种改进算法,本文的主要研究内容和工作如下:(1)针对鲸鱼优化算法局部搜索能力弱、易陷入局部最优等缺点,本文提出了一种基于两阶段正交学习的多种群合作协同演化的鲸鱼优化算法(Multi-population Cooperative Coevolutionary Whale Optimization Algorithm with a Two-Stage Orthogonal Learning Mechanism,MCCWOA),求解复杂连续实值优化问题。该算法通过建立邻域结构预测模型,在第一阶段的正交学习过程中指导子代个体的搜索方向。在第二阶段的正交学习过程中,通过辅助向量池使得陷入停滞状态的个体快速有效地跳出局部最优位置。此外,还通过多种群合作协同演化策略增加了种群的多样性。使用DOE(Design of Experiments Method)方法对算法参数进行校验,还通过构建适应度地形的方法检验了算法中各类算子的不同作用。基于CEC2017基准测试集上的实验结果表明MCCWOA算法优于鲸鱼优化算法及其先进变体算法。(2)针对分布式阻塞流水车间调度问题(Distributed Blocking Flow-shop Scheduling Problem,DBFSP),本文设计了一种协同离散鲸鱼优化算法(Cooperative Discrete Whale Optimization Algorithm,CDWOA)。该算法结合分布式阻塞流水车间调度的问题特征,设计了一种基于负载均衡的初始化方法提高种群的质量。在搜寻猎物阶段,提出了一种两阶段邻域插入算子来保持种群的多样性。在包围捕食阶段,采用了一种基于迭代贪心的方法进行深度局部搜索,以提高解的质量。在气泡捕食阶段,嵌入了基于关键工厂的局部搜索策略,增强了算法的收敛能力。同时,采用类似模拟退火的接受准则来保持群体的多样性。基于720个标准测试用例的仿真实验表明,所提出的构造启发式方法显著地优于7种文献中的初始化方法,所提出的算法显著地优于10种文献中的算法。(3)针对带序列相关准备时间的阻塞流水车间调度问题(Blocking Flowshop Scheduling Problem with Sequence-dependent Setup Times,SDST/BFSP),本文设计了一种离散鲸鱼优化算法(Discrete Whale Optimization Algorithm,DWOA)。该算法设计了一种基于问题特定知识的启发式方法缩短阻塞时间和空闲时间。在搜寻猎物阶段,提出了插入邻域的算子来保持种群的多样性。在包围捕食阶段,采用了一种块移动的方法进行局部搜索,以提高解的质量。在气泡捕食阶段,嵌入了一种邻域交换的局部搜索策略,增强了算法的收敛能力。基于480个标准测试用例的仿真实验表明,所提出的算法显著性地优于5种文献中的算法。(4)针对带序列相关准备时间的分布式阻塞流水车间调度问题(Distributed Blocking Flow-shop Scheduling Problem with Sequence-dependent Setup Times,SDST/DBFSP),本文设计了一种基于问题特定知识的离散鲸鱼优化算法(Discrete Whale Optimization Algorith