论文部分内容阅读
智能制造是“中国制造2025”计划的五大工程之一,是现阶段制造系统的重要研究内容。制造系统的调度策略与控制算法是提高企业生产力,满足市场需求的关键和瓶颈问题。流水车间调度问题(Flow Shop Scheduling Problem,FSP)作为一种典型的生产调度问题,在现代生产系统、制造系统中发挥着重要的作用,是制造行业关键支撑技术之一。在经典的流水车间调度问题中,连续机器之间具有无限的缓冲区容量。但是,在许多现实世界问题中,由于技术要求或工件的加工特性,机器间的缓冲容量有限甚至为零。此时,流水车间调度问题将转换为阻塞流水车间调度问题(Blocking Flow Shop Scheduling Problem,BFSP)。同时,随着现代生产技术的不断发展,企业中的生产模式从单一工厂变为多个工厂,具有多个工厂的分布式阻塞流水车间调度问题(Distribute Blocking Flow Shop Scheduling Problem,DBFSP)已经成为调度领域的热点问题之一。DBFSP作为一种经典的NP-Hard问题,其求解难度随着问题规模的增加呈指数式增加,传统数学方法已经无法有效的求解该问题。因此,无论从现实问题的应用层面,还是在调度问题的理论研究层面,寻求一种高效且精确的求解方法对解决分布式阻塞流水车间调度问题都有着重要意义。差分进化(Differential Evolution,DE)作为一种基于群体的启发式搜索算法,具有原理简单,易实现等优点并因此备受关注。然而由于传统DE算法通过采用浮点矢量进行编码生成种群个体,因此不能直接用于解决具有离散特征的组合优化问题。本文在深入研究了DE算法的运行机制,分析了其运行原理后,对算法的框架和算法的更新机制进行了改进,提高了算法的搜索性能和效率,并将改进的算法应用于解决单目标实值优化问题和不可分离问题中。同时,针对DBFSP问题的特性及DE算法的特性,对DE算法进行了调整,并成功的将其应用到调度问题中。本文的主要研究内容和成果主要包含以下几方面:(1).通过对传统DE算法及其变体算法的研究分析和大量经典文献的阅读之后,发现DE具有易陷入局部最优、进化初期过早收敛、对控制参数的敏感性高等缺点。为了解决上述问题,本文提出了一种具有广泛学习机制的协同LSHADE算法(A collaborative LSHADE algorithm with comprehensive learning mechanism,LSHADE-CLM)来解决单目标实值优化问题。在LSHADE-CLM算法中,提出了一种包含两种不同变异策略“DE/current to pbetter/r”和“DE/current to pbest w/1”的协同突变操作。其中,在具有学习机制的“DE/current to pbetter/r”策略中,使用基于种群的协方差矩阵去生成候选解并指导搜索方向。同时,为了解决算法对控制参数敏感性高的问题,使用带有竞争性的奖励机制去从两个不同的正弦池中自适应的调整突变因子。此外,种群的多样性在维度层面被重新考虑,当在特定的维度上发现种群处于停滞状态时,使用维度重启策略来增强种群在维度层面上的多样性。所提出的方法在标准测试集上的仿真结果和两个严格的假设检验结果表明LSHADE-CLM算法对于解决单目标实值优化问题和不可分离问题是有效的。(2).针对DE算法的理论分析匮乏的问题,本文对LSHADE-CLM算法的收敛性和时间复杂度进行了分析。通过使用有限齐次马尔科夫链模型,来证明所提LSHADE-CLM算法能够以概率1收敛到全局最优。同时,通过LOV规则将LSHADE-CLM映射到离散域中,提出了DLSHADE-CLM(Discrete LSHADECLM,DLSHADE-CLM)算法并用于解决阻塞流水车间调度问题。通过使用标准测试集得出的实验结果表明,所提出的DLSHADE-CLM是解决BFSP的有效算法。(3).通过对具有分布式的阻塞流水车间调度问题的研究,本文提出了一种基于最小化完工时间准则的集成离散差分进化算法去解决分布式阻塞流水车间调度问题(An Ensemble Discrete Differential Evolution for the Distributed Blocking Flowshop Scheduling with Minimizing Makespan Criterion,EDE)。在EDE算法中,候选解被表示为离散的工序排列,传统DE中的变异,交叉,选择操作符被重新设计,以帮助EDE算法可以直接在离散空间进行计算。同时,针对DBFSP的问题特点,通过考虑前置延迟(Front Delay)、阻塞时间(Blocking Time)、和空闲时间(Idle Time)对完工时间的影响,设计了两种不同的启发式方法和一种随机策略去生成初始的种群序列。此外,在EDE算法框架中引入精英保留策略,以平衡算法的全局搜索能力和局部搜索能力。所提出的算法在标准测试集进行了测试,并与一些先进算法进行了比较,实验结果和分析表明,所提出的EDE算法是解决DBFSP的有效算法。