遗传算法求解多目标柔性Job-shop问题

本文描述了基于可变机器约束的多目标柔性Job-shop调度问题模型,并应用一种改进的遗传算法进行求解。我们采用了表示工序先后顺序及机器选择的二维编码方式,以多目标优化函数为度量,通过三种遗传操作扩展后代的多样性和算法的搜索空间。仿真结果验证了该算法能有效解决多目标优化问题。

改进萤火虫算法求解多目标柔性作业车间调度

针对多目标柔性作业车间调度问题,以最小化最大完工时间、最小化机器总负荷、最小化机器最大负荷为目标,提出一种改进邻域结构的离散萤火虫算法。首先,采用多种策略相结合的方式初始化种群,提高算法初始解质量以及种群多样性;其次,通过改进关键路径的邻域结构并设计离散萤火虫算法的位置更新公式,以增强算法全局搜索和局部搜索能力;最后,将该算法应用于标准数据集,并将求解结果与其他算法进行对比,验证了所提算法的有效性。

基于改进的NSGA-II纺织生产车间柔性作业车间调度问题算法的研究

在纺织生产线调度领域,传统的人工调度方式已难以满足当前对高效利用机器和提升生产效率的迫切需求。鉴于此,本文建立了以最小化最大完工时间和机器总负载为优化目标的多目标柔性作业车间调度问题(flexible job shop scheduling problem,FJSP)数学模型,并提出了一种改进的NSGA-II算法(INSGA-II)用于求解。本文的主要特点是:(1)该算法采用基于工序和机器的两层编码方法;(2)采用混合种群初始化策略,目的是提高种群的初始质量;(3)设计了一种基于迭代次数的变领域搜索策略,在减少无效搜索的同时提高了局部搜索能力。本文在MK01-MK09和abz05-abz09的测试集上,将所提出的算法与其他算法(MOEA/D、MOEA/DD和NSGA-II)进行对比,并通过对14个标准算例的分析,证明了改进个NSGA-II算法在求解FJSP问题中的有效性。

混合粒子群算法求解多目标柔性作业车间调调度度问题

柔性作业车间调度问题是生产管理领域和组合优化领域的重要分支.本文提出一种基于Pareto支配的混合粒子群优化算法求解多目标柔性作业车间调度问题.首先采用基于工序排序和机器分配的粒子表达方式,并直接在离散域进行位置更新.其次,提出基于Baldwinian学习策略和模拟退火技术相结合的多目标局部搜索策略,以平衡算法的全局探索能力和局部开发能力.然后引入Pareto支配的概念来比较粒子的优劣性,并采用外部档案保存进化过程中的非支配解.最后用于求解该类问题的经典算例,并与已有算法进行比较,所提算法在收敛性和分布均匀性方面均具有明显优势.

基于Pareto优化的离散自由搜索算法求解多目标柔性作业车间调度问题

针对多目标柔性作业车间调度问题搜索空间的离散性和求解算法的收敛性,提出一种基于Pareto优化的离散自由搜索算法来求解多目标柔性作业车间调度问题。在建立基于Markov链数学模型的基础上,证明了算法以概率1收敛;引入首达最优解期望时间来分析算法收敛速度,并分析了算法时间复杂度。采用基于工序排序和机器分配的个体表达方式,在多目标柔性作业车间离散域,利用自由搜索算法在邻域小步幅精确搜索和在全局空间大步幅勘测进行寻优;通过自由搜索算法自适应赋予个体各异辨别能力和Pareto优化概念来比较个体优劣性,不仅保留优化个体,而且使个体寻优方向沿多目标柔性作业车间调度问题Pareto前沿逼近。通过对搜索过程中产生的伪调度方案进行可行性判定,以确保调度方案可行。采用10×10FJSP和8×8FJSP问题的实例进行寻优测试,验证了所提算法的可行性和有效性。

多目标柔性作业车间调度问题的混合差分算法

多目标柔性作业车间调度问题属于NP-hard问题。在对该问题进行分析的基础上,为之建立了数学模型,并改进了多目标函数,使其更符合实际需要。提出了一种求解该问题的混合差分演化算法,该算法针对差分演化算法易陷入局部最优现象,提出了算法早熟收敛判定方法,并且利用混沌搜索解决早熟收敛问题,突破了局部极值的限制以再次寻优计算。仿真结果表明,该算法效率高,寻优速度快,有效地解决了收敛性能和早熟之间的矛盾。

考虑可再生能源的多目标柔性流水车间调度问题

为了节能减排、保护环境,针对可再生能源的柔性流水车间调度问题(FFSP-RE),提出集成低碳调度策略的快速非支配排序遗传算法。根据可再生能源的发电特性建立了可再生能源供电模型,在此基础上构建了FFSP-RE的数学优化模型;给出快速非支配排序遗传算法,其中提出基于操作的编码方法,设计了考虑可再生能源特性的低碳调度策略,线性次序交叉和基于位置交叉采用随机选择方法,变异算子采用反转逆序法,根据拥挤度和非支配等级选择进入下一代种群的个体;通过多个数值实验证明了所提算法能够有效求解FFSP-RE,可再生能源能够在保证完工时间的前提下有效降低碳排放量。

求解多目标柔性作业车间调度问题的离散人工蜂群算法

作业车间调度问题是一类典型的组合优化问题,要求多个作业在不同的机器上进行加工,目的是获得最好的作业加工序列,以满足特定的性能指标。柔性作业车间调度问题是对传统的作业车间调度问题的进一步扩展,由于求解的复杂性,使得传统方法很难在有效的时间内获得问题的最优解。人工蜂群算法是近年来提出的一种受生物行为启发的优化算法,该算法主要通过模拟蜜蜂的觅食来实现问题的求解。提出了一种离散的人工蜂群算法于求解柔性作业车间调度问题,算法通过交叉方式来搜索潜在的更好的蜜源,并采用自适应的变异策略来降低早熟收敛的可能性。最后通过对比实验证明算法对于求解多目标柔性作业车间调度问题是有效的。

一种求解多目标柔性作业车间调度问题的改进元胞遗传算法

针对最小化最大完工时间、最大机床负荷及总机床负荷的多目标柔性作业车间调度问题,提出一种带有局部搜索策略的自适应元胞遗传算法。该算法在每完成一次种群迭代后,对种群的平均收敛速度进行计算,确定出合适的选择压。根据种群选择压的大小对种群的拓扑结构进行自适应改变。为了减小邻域搜索空间,结合车间调度问题的特点,借鉴正交设计思想设计了基于正交规则的局部搜索策略。通过4个经典多目标柔性车间调度问题的仿真实验以及与其他算法的比较,说明了该算法的有效性和可行性。

求解柔性Job-shop调度问题的混合粒子群算法

针对柔性Job-shop调度问题,提出了一种混合粒子群算法,该算法对设备分配和工序调度采用不同的编码方法和更新方式,提出了基于设备的初始化算法和基于工件序列的初始化算法来提高PSO初始种群的质量,同时提出了4种不同的邻域结构,分别实现了基于此四种邻域结构的模拟退火搜索算法,将它与粒子群算法进行有效混合来提高粒子群算法的局部搜索能力,实验表明HPSO的有效性.

求解多目标柔性作业车间调度问题的两层遗传算法

多目标柔性作业车间调度是复杂加工系统中一类重要的调度问题。针对大多数算法求解多目标柔性作业车间调度问题所存在的稳定性差、搜索深度不够、无法对多目标中单一目标进行深入搜索的问题,对传统遗传算法作出改进,设计了一套新的交叉策略,并舍去选择算子,在此基础上提出了一种求解多目标问题的双层遗传算法。引入了信息熵的概念对所提算法优化后的种群进行了分析,并从最大完工时间、最大机器负载、机器总负载三个方面对经典案例进行测试。与其他同类算法相比,该双层遗传算法共获得了31个可支配其他算法所求解的非支配解,和96个新的支配解。实验结果表明,所提算法在保留种群多样性的同时,仍拥有较好的深度搜索能力和跳出局部最优的能力,体现了算法的可靠性。

混合多目标算法用于柔性作业车间调度问题

在生产调度领域,柔性作业车间调度问题是一个非常重要的优化问题。大多数研究通常优化的目标只是最大完工时间,而在实际中,往往要考虑多个目标。因此,提出了一种新的混合多目标算法用于解决柔性作业车间调度问题,其中考虑了3个目标,分别是:最大完工时间、机器总负载和瓶颈机器负荷。算法设计了有效的编码方式和遗传算子,并采用非支配近邻免疫算法求解非支配最优解。为了提高算法性能,提出了3种不同的局部搜索策略,并将其结合在多目标算法中。在多个数据集上的实验对比结果表明,所提算法优于其它代表性的算法。此外,实验结果还验证了局部搜索技术的有效性。

利用有限制稳定配对策略求解双目标柔性作业车间调度问题

实际生产中,以最小完工时间和最低成本为目标的调度是柔性作业车间最常见的问题。提出了一种有限制稳定配对策略的双目标柔性作业车间调度问题的求解方法。该方法将双目标优化问题分解为一系列的标量优化子问题,并利用多目标进化算法对子问题进行优化求解;同时,将有限制稳定配对策略用于进化过程中各子问题解的协调选择,以保证解的收敛性和分布性。仿真数据和应用实例表明:该方法可以获得收敛和分布性能更优的调度方案。

基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题

柔性作业车间调度问题(FJSP)是一类应用广泛的组合优化问题。针对多目标FJSP求解过程复杂、算法易陷入局部最优的问题,提出了一种基于多区域采样策略的混合粒子群优化算法(HPSO-MRS),以同时优化最大完工时间和总机器延迟时间这两个目标。多区域采样策略能够区分粒子所在Pareto前沿面的位置,根据不同区域进行采样重组,并为采样后位于Pareto前沿面多个区域的粒子规划相应的运动方向,从而有针对性地调整粒子在多个方向上的收敛能力,并带来一定程度的均匀分布能力的提升。此外,编解码方面使用带插空机制的解码策略来消除可能存在的局部左移;粒子更新方面将传统粒子群优化(PSO)算法的粒子更新方式与遗传算法(GA)的交叉变异算子相结合,提升了算法搜索过程的多样性并避免算法陷入局部最优。把所提算法在Benchmark问题Mk01~Mk10上进行测试,与传统的HPSO、NSGA-Ⅱ、基于适应度分配策略的多目标进化算法(SPEA2)和基于分解的多目标进化算法(MOEA/D)进行算法效力和运行效率对比。显著性分析的实验结果表明,HPSO-MRS在收敛性评价指标HV和IGD上分别在85%和77.5%的对照组中显著优于对比算法,而该算法在35%的对照组中的分布性指标Spacing显著优于对比算法,且均不存在所提算法显著差于对比算法的情况。可见相较于对比算法,所提出的算法具备较好的收敛与分布性能。

基于改进多目标水母算法的低碳柔性作业车间调度方法

针对柔性作业车间调度问题中多个目标之间相互冲突、难以求解的问题,设计了一种基于Pareto和改进多目标水母搜索算法的柔性作业车间调度方法。首先,建立了以最小化最大完工时间、最小能耗以及最小机器总负荷为优化目标的车间调度模型;其次,使用了一种基于完工时间和机器负荷均匀分布的初始化方式,有效地提升了初始种群的质量;考虑到连续水母算法在求解离散问题时存在效率低等问题,设计了离散水母算法,提出了基于Pareto等级的被动运动方式,进一步提高了搜索效率,引入了学习的概念引导种群向Pareto前沿移动;最后,为了验证多目标改进水母算法在求解柔性作业车间调度的有效性,与NSGAII算法进行了仿真实验对比。实验结果表明:利用该算法求解MK06算例完工时间为76、机器负荷为424、能耗为565.8支配的NSGAII的结果,解的质量整体较高。研究结果表明:采用均匀分布初始化方式以及学习型引导的离散化水母算法,其初始种群分布均匀、收敛速度快、解的质量高,具有较强的寻优能力,能够有效地处理多目标柔性作业车间调度问题。

FPD-GA求解多目标柔性作业车间调度问题

针对柔性制造车间调度问题的特点,提出一种求解该类问题的定点扰动-遗传算法(Fixed Point DisturbanceGenetic Algorithm,FPD-GA)。根据车间生产实际构建以完工时间、机床负荷和设备使用率为目标函数的多目标优化模型。针对遗传算法局部搜索能力差、易早熟收敛的缺点,设计定点扰动策略,增强局部寻优能力,并改进传统的遗传选择操作,保持种群的多样性,提高遗传算法的进化效率。以车间生产计划为实例测试改进算法,并与典型遗传算法的测试结果相比较,验证新算法的可行性与有效性。

两阶段重调度策略求解柔性作业车间动态调度问题

区别于传统作业车间调度问题,研究一种工件之间具有优先约束的柔性作业车间问题。首先建立多目标静态调度模型,利用JAYA方法进行求解,通过实验得到变异因子的最佳值。其次,提出一种新的两阶段的动态调度策略,在静态调度结果上进行调整,同时对短期和长期恢复的扰动问题重调度。实验证明,提出的动态调度方法能同时有效减少完工时间和机器偏移情况。

考虑工件运输时间的分布式柔性作业车间调度

为求解考虑工件在机器间运输时间的分布式柔性作业车间调度问题(DFJSPTW),提出了一种基于延迟接受爬山算法(LAHC)的改进算法,并建立起以最大完工时间为优化目标的数学模型。针对DFJSPTW的几个耦合性子问题,工序排序和机器选择、工厂分配采用了基于工序、机器、工厂的三层染色体编码方式去解决,而小车分配则提出了一种考虑负载均衡化的调度规则;为提高生成解的质量,初始化染色体时工厂和机器序列分别考虑了负载平衡;局部搜索过程中,算法设计了4种邻域搜索算子并提出了一种符合DFJSPTW的变邻域搜索策略,在变换邻域搜索算子时还引入了化学反应算法中的单分子反应搜索机制,用于加强算法的综合搜索能力。通过数值实验验证了变邻域搜索策略和引入单分子反应搜索机制的有效性,同时通过改进算法与GA_OP、GA_JS算法的对比实验,进一步验证了所提算法求解DFJSPTW问题的优越性。

改进灰狼算法求解多目标柔性作业车间调度问题

柔性作业车间调度问题(Flexible Jobshop Scheduling Problem,FJSP)是经典的NP-hard(Non-deterministic Polynomial-time hard)问题,针对该复杂问题,需要建立一个多目标的数学模型,采用灰狼优化算法对柔性作业车间的加工完成时间、总耗能和总机器负荷这三个目标进行优化,以加工完成时间、总耗能和总机器负荷作为研究目标。灰狼优化算法(GWO)是一种具有较高的寻优精度和收敛速度的算法,在此基础上对灰狼优化算法的初始化种群进行改进,为了使灰狼算法适用于多目标问题,与非支配排序遗传算法结合,引入非支配排序与拥挤度的概念,用于灰狼算法对种群的更新。对柔性作业车间调度算例进行测试,结果表明改进的灰狼算法针对多目标柔性作业车间调度可以找到最优解,以较少的迭代次数找到最小加工时间、最小总耗能及最小总机器负荷,对车间调度问题进行了优化。

基于改进MOEA/D的模糊柔性作业车间调度算法

针对实际生产车间中加工时间的不确定性,将加工时间以模糊数的形式表示,建立以最小化模糊最大完工时间和模糊总材料消耗为优化目标的多目标模糊柔性作业车间调度问题数学模型,提出一种改进基于分解的多目标进化算法(IMOEA/D)进行求解。该算法基于机器和工序两层编码并采用混合的初始化策略提高初始种群的质量,利用插入式贪婪解码策略对机器的选择进行解码,缩短总加工时间;采用基于邻域和外部存档的选择操作结合改进的交叉变异算子进行种群更新,提高搜索效率;设置邻域搜索的启动条件,并基于4种邻域动作进行变邻域搜索,提高局部搜索能力;通过田口实验设计方法研究关键参数对算法性能的影响,同时得到算法的最优性能参数。在Xu 1~Xu 2、Lei 1~Lei 4和Remanu 1~Remanu 4测试集上将所提算法与其他算法进行对比,结果表明,IMOEA/D算法的解集数量和目标函数值均较优,在Lei 2算例获得的解集个数为对比算法的2倍以上。