解决柔性车间作业调度问题的侦查包围搜索算法

车间作业调度算法是影响车间生产效率的重要因素之一。由于调度算法属于NP-难问题,至今仍然没有办法在有限时间内找到最优解。文章提出了一种元启发式搜索方法:侦查包围算法(PEA),通过局部搜索,旨在有限时间内最大可能的趋近于最优解。该算法吸取了禁忌搜索算法和模拟退火算法的优点,对其缺点进行改进。文中将此算法应用到柔性车间作业调度问题,阐述算法的实践。实验结果与遗传算法和禁忌搜索进行比较,证明在作业数目较大的情况下,具有良好的效果。

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

在多目标柔性车间作业调度问题的研究中,求解算法与多目标处理至关重要。因此,基于非支配排序遗传算法提出了改进遗传算法求解该问题,设计了相应的矩阵编码、交叉算子,改进了非劣前沿分级方法,并提出了基于Pareto等级的自适应变异算子以及精英保留策略。实例计算表明,该算法可以利用传统遗传算法全局搜索能力的同时可以防止早熟现象的发生。改进非劣前沿分级方法可以快速得到Pareto最优解集,进一步减小了计算复杂度,而且可以根据种群的多样性改变变异概率,有利于保持种群多样性、发掘潜力个体。

生物地理学算法求解柔性车间作业调度问题

针对加工设备和操作工人双资源约束的柔性作业车间调度问题,建立以生产时间和生产成本为目标函数的柔性作业车间调度模型,提出基于模糊Pareto支配的生物地理学算法,采用模糊Pareto支配的方法计算解之间的支配关系并对Pareto解集排序,进行全局最优值的更新,并采用余弦迁移模型来改善生物地理学算法的收敛速度。将该方法应用于某模具车间的柔性作业车间调度中,仿真结果验证了该方法的可行性和有效性。

考虑模糊质检时间的柔性作业车间动态调度问题

为解决更符合现实情形的模糊质检时间柔性作业车间动态调度问题,以最小化完工时间为目标,立足紧急插单、机器在空载运行时发生故障和机器在加工工件时发生故障的三种故障情形,建立了带模糊质检时间的机器故障、紧急插单重调度模型。设计了基于元胞自动机邻域搜索和随机重启爬坡算法的改进遗传算法求解模型,即针对车间调度问题中存在的订单排序和机器选择双决策问题特征,设计包含工序码和机器码的双层编码方案,并基于遗传算法思想对工序码和机器码设计相应的交叉、变异等遗传操作。同时,将遗传操作应用于基于元胞自动机的邻域搜索算法框架中以增强算法全局搜索能力,整合基于关键工序的随机重启爬坡算法以提高算法局部开发能力。实验选取10个柔性车间调度算例验证了所提算法的有效性,同时,测试1个模糊质检时间柔性车间调度算例验证了模型的有效性。另外,实验也测试了不同故障场景,得出该动态调度方法优于实际场景中常使用的“工件后移”调度策略。

基于改进生物迁徙算法的双资源柔性作业车间节能调度问题

节能调度是面向绿色制造的车间调度问题,已成为制造领域的研究热点。针对具有机器和工人双资源约束的柔性作业车间,综合考虑工人学习效应和工件运输时间的影响,以最小化车间能耗为目标,提出一种改进的生物迁徙算法(MBMA)。该算法采用基于工件-机器-工人的三段式编码方法表示调度解,并设计了一种种群初始化方法,以改善初始调度解的质量。考虑到基本生物迁徙算法无法直接应用于离散车间调度问题,提出一种基于交叉操作的离散迁徙算子,使算法能够直接在离散调度空间内进行搜索。此外,在迁徙算子中引入转换概率动态调整策略,以平衡算法探索与开发能力,另外增加了一种记忆池机制,避免算法过早收敛。对于个体更新算子,设计了一种局部搜索算法嵌入其中,以增强算法局部搜索能力。大量实验结果表明,MBMA算法的计算结果优于其他算法。

改进文化基因算法求解双资源约束柔性作业车间调度问题

针对具有机器和工人的双资源约束柔性作业车间调度问题,以最小化最大完工时间为目标构建调度模型,并设计一种改进文化基因算法对其进行求解。由于该调度问题需要同时考虑工序排序、机器选择及工人选择3个子问题,故采用三层序列编码。考虑传统解码方式存在收敛速度慢、收敛不完全的弊端,设计一种扩展型插入式主动解码方式,以提高算法的收敛速度;针对进化算法易陷入局部最优的缺陷,设计一种基于负载平衡的机器和工人再分配算子,增强算法的全局搜索能力,对种群中的优秀个体采用改进变邻域搜索以提高算法的局部寻优能力。最后,利用仿真算例及航空设备生产实例进行实验,验证所提算法求解双资源约束调度问题的有效性。

基于改进樽海鞘群算法的多目标柔性作业车间调度问题研究

针对多目标柔性作业车间调度问题,构建了以最小化总能耗、最小化生产成本及最小化惩罚值为优化目标的数学模型,并设计改进的多目标樽海鞘群算法(IMSSA)进行求解。改进算法主要由樽海鞘领导者和樽海鞘追随者两部分构成,其中,领导者位置更新结合正余弦算法来实现,追随者位置更新基于线性微分递减的惯性权重方法来完成。此外,引入食物源存储库用于保留非支配解。最后通过对比实验证明了所提策略及改进算法的有效性。

改进粒子群算法求解生产计划与柔性作业车间调度集成问题

为解决机加工企业制定的生产计划与车间调度方案不兼容的问题,建立以最小化最大完工时间、最小化加工成本为目标函数的生产计划与柔性作业车间调度集成模型。提出一种改进粒子群算法(IPSO)作为全局优化算法。在传统粒子群优化算法(PSO)的基础上,引入遗传算子交叉的方式改进群体进化,同时设计随机性的边界变异,提高种群多样性,避免局部最优,学习因子及惯性权重采用幂函数动态变化,增强其搜索能力,更快收敛。最后通过生产实例,验证了IPSO在解决生产计划与车间调度集成问题上的可行性。同时将PSO、灰狼优化算法(GWO)和遗传算法(GA)作为对比算法,在15个Brandimarte基本算例上开展实验,得到的结果均优于其他算法,证明了IPSO求解柔性作业车间调度问题时的有效性和优越性。

求解柔性作业车间调度问题的离散食肉植物算法

针对传统群智能优化算法求解柔性作业车间调度问题时易陷入局部最优且寻优能力不足的困境,以最小化最大完工时间为目标提出一种离散的食肉植物算法。首先,为提高初始种群的多样性,提出了3种初始化种群策略;其次,为提高算法各时期的搜索能力,为生长因子设计了一种自适应策略,并对植物执行了交叉以及基于4种邻域结构的贪婪变异操作;最后,通过对Brandimarte基准问题进行仿真并与其他文献算法进行对比,证明了所提算法在收敛速度和求解质量方面都具有较好的性能。

带有动态到达工件的分布式柔性作业车间调度问题研究

分布式柔性作业车间调度是生产调度的1个重要分支,工件的动态到达作为实际生产中的1种常见扰动情况,进一步增加了作业车间调度问题的复杂性和不确定性。针对带有工件动态到达的分布式柔性作业车间调度问题(DA-DFJSP),提出1种分批调度策略,将原本的动态调度问题转化成一系列连续调度区间上的静态调度问题,构建以最大完工时间为优化目标的混合整数规划模型;在此基础上,结合问题特征采用批次、工厂、工序、机器的4层染色体编码及快速贪婪搜索插入的解码方式改进遗传算法,同时引入多种交叉、变异算子来增强染色体的多样性;最后,基于FJSP标准算例构建DA-DFJSP测试算例进行仿真对比实验,验证所提策略和改进算法的求解优势。结果表明:相较于传统的重调度策略和改进前的遗传算法,采用分批调度策略和改进的遗传算法(IGA)所求调度方案具有更短的完工周期、更均匀的工厂加工负荷及更高的设备工作效率,IGA与分批调度策略之间有高度的契合性,能够有效提升生产效率。

基于深度强化学习的柔性作业车间调度问题

针对多目标柔性作业车间调度问题的复杂度高,以及求解算法对历史数据利用不足和解策略单一的问题,提出一种基于值的深度强化学习算法,通过引入最大熵方法在策略空间中获得多个较优策略。首先,将调度过程视为多阶段决策过程,提出单工序时间特征表示方法,并以此为基础设计了11个归一化的状态表征函数作为输入;其次,利用改进的带噪声的对抗网络拟合值函数;再次,在基础规则上通过复合组成24条调度规则;最后,提出了分层单步奖励以解决稀疏奖励问题。算例测试结果表明,所提算法的性能优于深度Q网络(deep Q network,DQN)和非支配排序遗传算法Ⅱ(non-dominated sorting genetic algorithmⅡ,NSGA-Ⅱ)等其他算法。

改进NSGA-III求解高维多目标绿色柔性作业车间调度问题

为解决NSGA-III在求解上述模型存在初始解质量差与局部搜索效率低的问题,提出一种改进的NSGA-III(NSGA-III-TV)。基于MSOS编码,分别对OS和MS染色体采取不同混合初始化策略以提高初始解质量;基于关键路径,采用改进N6邻域结构进行邻域搜索,有效缩短完工时间并降低搜索盲目性,同时采用3种有效变异算子扩大算法搜索空间,提高后期收敛能力。结果表明:NSGA-III-TV在求解高维多目标柔性作业车间调度问题上具有较好的性能以及实用性,为企业生产制造车间的智能绿色转型升级提供了有力支持。

改进近邻人工蜂群算法求解柔性作业车间调度问题

为了更好地解决以最小化最大完工时间为目标的柔性作业车间调度问题,提出了一种改进的人工蜂群算法。首先,采用随机选择和反向学习策略来提高初始蜜源的质量。同时,设计了一种新颖的特征表示方式,用于计算蜜源之间的距离。在引领蜂阶段,通过引入交叉和变异策略来优化种群中的近距离蜜源。在探索蜂阶段,引入了六种变邻域方法,以扩大解空间的搜索范围。而在侦查蜂阶段,则根据蜜源的潜力值剔除局部最优个体。在15个数据集上进行了广泛实验,实验结果表明,该改进算法性能明显优于其他四种著名的群智能优化算法。该研究为解决柔性作业车间调度问题提供了一种新的有效方法,对于实际生产调度具有重要的实用价值。

基于改进灰狼优化算法的柔性作业车间分批调度问题研究

针对以最小化最大完工时间为目标的柔性作业车间分批调度问题(Flexible Job shop Batch Scheduling Problem,FJBSP),提出了一种改进灰狼优化(Improved Grey Wolf Optimization,IGWO)算法,优化对象为工件的分批方案。首次将流体模型应用于FJBSP的求解,提出了一种基于流体模型的解码方法,用于获得更好的子批调度方案;然后改进了狼群的等级制度,避免了算法过早收敛;其次设计了一种全新的适应可变长编码的交叉方法,深入交流2个个体之间的分批信息,增强了算法的搜索能力和稳定性;再次,提出了能够动态更新个体游走率的自适应灰狼游走策略,兼顾了算法的搜索质量和收敛速度;此外,对领头狼使用自适应邻域搜索动态调整每种工件选择各邻域的概率,提高算法的局部搜索能力;最后,设计了9个算例和3组实验,验证了所提出的IGWO算法的有效性和优越性。

基于改进灰狼算法的柔性作业车间动态节能分批调度问题

针对柔性作业车间动态节能分批调度问题,建立了以优化车间生产成本、机床能耗成本和动静态调度方案差异成本为目标的数学模型,接着针对实际生产过程中的动态扰动设计了动态调度方案,针对动态扰动导致工件工艺路线变化的问题设计了重组批技术,针对动态调度方案的求解则设计了改进灰狼算法,采用层级位置更新方法进行狼群的位置更新,提高算法的搜索效率,最后通过标准算例库验证了算法求解柔性作业车间动态节能分批调度问题的有效性与优越性。

基于改进灰狼算法的柔性作业车间重调度问题研究

【目的】在工厂实际加工中,由于各机器的健康状态参差不一,可引起机器故障继而影响加工施工时间。针对带有机器扰动的柔性作业车间的问题,为减小机器故障对生产计划的影响,提出了机器扰动、寻找断点的重调度模型,以最小加工时间、最短总延迟时间为优化目标构建了数学模型。【方法】提出改进灰狼优化算法(GWO-GA)作为全局优化搜索算法求解,为提高其灰狼算法的收敛速度,引入了工件编码迭代并加入自适应算子,使用遗传算法的POX交叉对机器编码进行迭代。【结果】针对钢琴制造企业实木车间数据进行验证,结果表明相对于遗传算法(genetic algorithm,GA)、NSGA、PSO-GA,改进灰狼算法求解本调度问题效率高,精度好,具有较好的实用价值。

改进GWO算法求解柔性作业车间调度问题

针对以最小化最大完工时间为目标的柔性作业车间调度问题,设计一种改进的邻域搜索灰狼算法。设计一种适于灰狼算法的基于工序和机器的双层编码方案,改进种群初始化策略、灰狼变异操作以及种群更新机制;通过两点交叉操作、插入操作以及PR操作,得到GWO算法的全局搜索邻域,提出设计禁忌搜索邻域以增强GWO算法的局部开发能力。最后将所提算法在已知算例上进行仿真实验,并与其他算法进行对比。实验结果验证了改进GWO算法具有一定的优越性。

基于CNN的深度强化学习算法求解柔性作业车间调度问题

在使用深度强化学习(DRL)算法解决柔性作业车间调度(FJSP)问题时,状态和动作的表示具有复杂多变的特性,这导致算法的求解质量不高,为了得到更优解,对状态和动作的表示进一步研究,以最大完工时间最短为优化目标,采用卷积神经网络(CNN)和近端策略优化(PPO)方法设计了一种深度强化学习算法。针对柔性作业车间环境的复杂性,特别设计了双通道状态表示方法,第一通道表示每道工序选择的机器,第二通道表示每道工序在所选机器上的加工次序。在动作设置中设计了一种机器选择算法,能够根据当前状态选取最佳的机器,搭配深度强化学习算法共同组成动作的选择。通过Brandimarte算例验证表明,该算法具有可行性,比常用深度强化学习算法求解质量更优,在不同规模算例的性能表现更好。

改进人工蜂群算法求解柔性作业车间调度问题

柔性作业车间调度问题(Flexible Job-shop Scheduling Problem,FJSP)是生产调度的一个经典问题,目前对FJSP的研究主要集中在单目标方向,因此针对多目标FJSP,本文提出一种使用多策略的多蜂群算法(MCMSABC)求解问题.该算法提出数据预处理方法,缩小搜索空间;改进非支配解的判断条件和提出加快发掘蜜源潜力的更新策略;根据繁殖能力选用不同交叉算子和变异策略对个体进行更新;观察蜂阶段提出3种基于关键路径的小邻域结构,重定义两种选择策略提高蜂群个体的竞争水平;侦察蜂阶段使用两种基于学习机制的策略替换较差个体.采用两组测例和车间实例进行多组仿真实验并与多个算法进行对比,在单目标和多目标方向上均搜索到更优解,结果表明该算法所提改进策略的有效性.

基于改进的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问题中的有效性。