一种用于PFSP节能优化的混合禁忌搜索算法

为了追求节能减排与净利润最大化,建立一种置换流水车间订单接受与调度模型。禁忌搜索是一类启发式全局搜索算法,传统禁忌搜索对初始解依赖较大,没有对考虑能效的置换流水车间调度问题进行更深入的优化。鉴于问题的复杂性,提出了一种节能混合禁忌搜索算法,结合了NEH构造启发式算法的优势,并在该算法中设计了订单接受与拒绝编码方式、能耗调整与交货期配置策略。最后采用大量随机实例对性能进行分析。实验结果表明,通过上述改进,改善了算法的全局搜索能力与解决复杂模型的寻优能力,节能混合禁忌搜索较单一算法而言性能更优,可以有效增加企业总净利润,降低能源消耗。     

求解批量流水线调度问题的改进和声搜索算法

针对以最大完工时间为目标的批量流水线调度问题,提出一种改进的和声搜索优化算法。该算法采用ROV规则的编码方式,使具有连续本质的和声搜索算法能直接应用于调度问题。对和声库的初始化和候选解的产生方式进行改进。针对该算法容易陷入局部最优的缺陷,将其与阈值接受算法结合,得到2种混合算法。仿真结果证明了该算法的有效性。     

基于深度强化学习与迭代贪婪的流水车间调度优化

流水车间调度是应用背景最为广泛的调度问题,其智能算法研究具有重要的学术意义和应用价值.以最小化最大完工时间为目标,提出求解流水车间调度的一种基于深度强化学习与迭代贪婪算法的框架.首先,设计一种新的编码网络对问题进行建模,解决了传统模型受问题规模影响而难以扩展的缺陷,并利用强化学习训练模型以获取优良输出结果;然后,提出一种带反馈机制的迭代贪婪算法,以网络的输出结果为初始解,协同利用多种局部操作提高搜索能力,并根据性能反馈调节各操作的使用,进而获得最终的调度解.仿真结果和统计对比表明,所提出的深度强化学习与迭代贪婪融合的算法能够取得更好的性能.     

求解能耗成本平衡的分布式阻塞流水线调度群体迭代贪婪算法

在经典分布式流水车间调度问题基础上, 本文构建了具有序列相关准备时间的分布式阻塞流水线调度问题(DBFSP SDST)的混合线性整数规划模型(MILP), 以均衡各工厂能耗成本为优化目标, 提出了基于群体优化的迭代贪婪算法 (PEIG). 该算法针对零缓冲区和多工厂生产模式, 设计了问题特性的启发式方法; 针对迭代贪婪算法(IGA)的优势和不足, 提出了基于群体的局部搜索策略、多邻域搜索结构和增强的跨工厂破坏重构方法, 以进一步平衡所提算法的全局探索和局部搜索能力. 通过270个测试算例的数值仿真, 以及与最新4种代表算法的统计比较,本文验证了所提PEIG算法的优越性, 能为中大规模的DBFSP SDST提供更优的调度方案.     

基于目标增量的无等待流水调度快速迭代贪婪算法

最小化总完工时间无等待流水调度是典型的NP-完全问题,广泛存在于实际生产系统.改变传统求解调度序列目标函数的模式,提出目标增量法,通过目标函数变化量判断新解的优劣,大大降低算法所需计算时间;通过证明启发式算法基本操作的目标增量性质,设计两种基本目标增量法以快速评估新产生解的质量.提出快速迭代贪婪算法FIG(Fast Iterative Greedy algorithm)求解该问题,构造初始解生成算法,提出分段式重构局部搜索方法和迭代改进全局搜索策略以进一步提高解的质量.基于110个经典Benchmark实例,将提出的FIG算法与目前求解该问题较好的启发式算法PHlp和元启发式算法SRTS、DPSOvnd进行比较,实验结果表明FIG在性能上优于SRTS和PHlp,略逊于DPSOvnd;在效率上优于SRTS和DPSOvnd,略逊于PHlp.     

求解阻塞混合流水车间调度的双层变异迭代贪婪算法

混合流水车间调度是制造业领域的前沿方向,而研究带有阻塞约束的问题更具有现实意义.针对阻塞混合流水车间调度问题(BHFSP),以最小化最大完工时间为优化目标建立BHFSP的数学模型并详细阐述其计算过程,在零缓冲区特性的基础上设计一种双层变异策略的迭代贪婪(IGDLM)算法求解BHFSP.分析传统迭代贪婪(IG)算法中的优势和不足,针对阻塞特性提出双层变异策略来提高解的多样性,进一步平衡所提算法的全局探索和局部搜索能力.通过100个测试算例的数值仿真以及与5种代表算法的统计比较,验证所提出的双层变异策略与IG融合的算法能够得到更好的目标值,并为中大规模的BHFSP提供更优的调度方案.     

基于混合遗传算法的资源受限的运输任务调度

在利用串行调度启发式方法解决资源受限的运输任务调度问题（RCTTSP）的基础之上,提出了一种混合遗传算法（HGA）。该算法通过对运输任务执行优先次序进行基因编码,利用串行调度方法获得初始种群,并在遗传个体调度目标值与适应值确定的过程中使用了局部搜索启发式规则,从而充分地结合了遗传算法的全局搜索与启发式方法的局部搜索能力。首先对RCTTSP进行了描述,给出了混合遗传算法的基本原理,然后针对测试案例进行实现,并与单纯使用串行调度方法进行了比较。结果显示,该混合遗传算法能有效地改进调度效果。     

文化基因算法在多约束背包问题中的应用

文化基因算法是一种启发式算法,与一些经典数学方法相比,更适于求解多约束背包问题.文化基因算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体,针对多约束问题,提出采用贪婪策略通过违反度排序的方法处理多约束条件,全局搜索采用遗传算法,局部搜索采用模拟退火策略,解决具有多约束条件的0-1背包问题.通过对几个实例的求解,表明文化基因算法与标准遗传算法相比,具有更优的搜索性能.     

差异工件流水车间批调度问题的求解

针对流水车间批调度问题,提出一种基于群智能算法的求解思路。结合问题具体特点,给出工件集合的分批策略,设计了将Palmer和Best Fit（BF）分批规则相结合的分批方法;在批排序阶段,提出了一种改进的微粒群算法;在粒子初始生成阶段,通过引入NEH启发式算法改进了粒子的初始化质量;在全局最佳位置更新前,通过变邻域搜索优化了算法的局部搜索能力,避免了算法陷入局部最优。仿真实验表明,改进后的算法优于传统的微粒群算法和NEH启发式算法。     

自适应混合粒子群算法求解置换流水车间调度问题

为更有效地解决以最大完工时间最小化为目标的置换流水车间调度问题,提出了一种自适应混合粒子群算法（SHPSO）。该算法结合Q学习设计了参数自适应更新策略,以平衡算法的探索和开发;同时引入粒子停滞判断方法,使用平局决胜机制和Taillard加速算法改进基于迭代贪婪的局部搜索策略,对全局极值进行局部搜索,帮助粒子跳出局部最优。实验结果表明,SHPSO算法取得的平均相对百分偏差（RPDavg）对比其他四种改进PSO算法至少下降了83.2%,在求解质量上具有明显优势。     

基于改进粒子群算法的无线传感器网络节点定位

针对传统距离矢量-跳数(DV-Hop)算法中最小二乘法的估计误差过大、粒子群(PSO)算法易陷入局部最优的问题,提出了一种改进粒子群算法与DV-Hop的融合算法。首先从粒子速度、惯性权重、学习策略、变异方面对粒子群算法进行改进,增强算法跳出局部最优的能力,提高迭代后期算法的搜索速度;然后在DV-Hop算法第三阶段采用改进粒子群算法优化节点的定位结果。仿真结果表明:相比传统DV-Hop算法、基于混沌粒子群算法的DV-Hop改进算法(MPSO1-DV-Hop)和基于改进型粒子群优化的DV-Hop算法(MPSO2-DV-Hop),该算法的定位精度高,稳定性好,适用于定位精度和稳定性要求较高的场景。     

一种改进的求解柔性作业车间调度问题的灰狼算法

柔性作业车间调度问题是智能制造领域的一类典型调度问题,它是制造流程规划和管理中最关键的环节之一,有效的求解方法对提高生产效率具有重要的现实意义。本文基于经典灰狼算法进行改进,以优化最大完工时间为目标,提出一种改进的灰狼算法来求解柔性作业车间调度问题。算法首先采用基于权值的编码形式,实现对经典狼群算法中连续性编码的离散化;其次在迭代优化过程中加入随机游走策略,以增强局部搜索能力;然后在种群更新过程中加入尾部淘汰策略,在避免局部优化的同时增加种群多样性,合理扩大算法的广度搜索范围。在标准算例上的仿真实验结果表明,改进的灰狼算法在求解FJSP时比经典灰狼算法在寻优能力方面具有明显的优势,相比其它智能优化算法,本文所提算法在每种算例上均具有更好的优化性能。     

基于任务分配与调度的GSAT算法求解3-SAT问题

基于不同分配策略的云计算任务调度以及任务分配与调度的主要目的,提出了一种新的算法—求解3-SAT问题的基于任务分配与调度的GSAT算法。该算法将3-SAT问题中的每一个变量形成一个任务,在GSAT算法的基础上,引入任务分配与调度指导贪心搜索;同时,在保留原有贪心搜索的前提下,根据任务分配与调度的思想和3-SAT问题的特点,设计了两种新的策略—分配策略和调度策略共同完成整个贪心搜索过程。以标准的SATLAB库中变量个数从 20～250的3 700个不同规模的标准Uniform Random 3-SAT 问题对新的算法的性能进行了合理的测试,并与高效和普通性能改进的GSAT算法的结果作了比较,结果表明,该算法具有更高的成功率和更少的翻转次数。     

一种基于Levy飞行的改进蝗虫优化算法

蝗虫优化算法是一种元启发式优化算法,能够用于解决任务调度问题。已有的改进蝗虫优化算法缺乏随机性,跳出局部最优的能力较弱,改进效果不够显著。针对这一问题,本文提出一种基于Levy飞行的改进蝗虫优化算法（LBGOA）。该算法引入基于Levy飞行的局部搜索机制增强算法的随机性,并采用基于线性递减参数的随机跳出策略来提高算法跳出局部最优的能力。CEC测试实验结果表明,所提出的算法拥有较强的搜索能力,在30个测试函数结果中能够获得17个最优解和6个次优解。将所提出的改进算法应用于边缘计算中的任务调度问题。任务调度仿真实验结果表明,所提出的算法能够有效提高搜索效果,相比GOA、OBLGOA、WOA、ALO、DA和PSO算法,LBGOA的搜索效果分别提升7.4%、7.5%、4.8%、27.7%、29.9%和20.7%。     

改进的离散型萤火虫优化算法求解柔性作业车间调度问题

针对传统的群智能优化算法在求解柔性作业车间调度问题(FJSP)时,存在寻优能力不足且易陷入局部最优等缺点,本文以最小化最大完工时间为目标,将萤火虫算法(FA)用于求解柔性作业车间调度问题,提出一种改进的离散型萤火虫算法(DFA)。首先,通过两段式编码建立FA连续优化问题与FJSP离散优化问题之间的联系;其次,设计一种群初始化方法,以确保初始解的质量以及多样性;然后,提出改进离散型萤火虫优化算法并引入局部搜索算法,加强算法的全局搜索能力和局部搜索能力;最后,对标准算例进行仿真,验证DFA算法求解FJSP的有效性。通过与遗传算法和粒子群优化算法进行仿真对比,表明了DFA求解FJSP的优越性。     

基于混合遗传算法的订单生产调度在机车车辆行业中的应用

机车车辆行业作为典型的面向订单的机械制造企业,优化的生产调度方法能提高订单的准时交货,缩短产品的生产周期,提高企业的市场竞争力。订单生产调度问题是典型的NP-hard问题。遗传算法(Genetic Algorithms)为求具有多个约束的复杂问题提供了有效的方法。但是遗传算法的局部搜索能力比较差,在解决订单生产调度问题中存在着明显的不足。本文引入了局部搜索能力很强的禁忌搜索算法,用遗传算法和禁忌搜索算法相结合的混合遗传算法来解决机车车辆行业中面向订单生产调度问题。     

求解独立任务调度的离散粒子群优化算法

针对独立任务调度问题,提出一种改进的离散粒子群算法,采用基于任务的编码方式,对粒子的位置和速度更新方法进行重新定义。为防止粒子群算法的早熟收敛,给出利用模拟退火算法的局部搜索能力在最优解附近进行精细搜索,以改善解的质量。仿真结果表明,与遗传算法和基本粒子群算法相比,该混合算法具有较好的优化性能。     

A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops

Obtaining an optimal solution for a permutation flowshop scheduling problem with the total flowtime criterion in a reasonable computational timeframe using traditional approaches and optimization tools has been a challenge. This paper presents a discrete artificial bee colony algorithm hybridized with a variant of iterated greedy algorithms to find the permutation that gives the smallest total flowtime. Iterated greedy algorithms are comprised of local search procedures based on insertion and swap neighborhood structures. In the same context, we also consider a discrete differential evolution algorithm from our previous work. The performance of the proposed algorithms is tested on the well-known benchmark suite of Taillard. The highly effective performance of the discrete artificial bee colony and hybrid differential evolution algorithms is compared against the best performing algorithms from the existing literature in terms of both solution quality and CPU times. Ultimately, 44 out of the 90 best known solutions provided very recently by the best performing estimation of distribution and genetic local search algorithms are further improved by the proposed algorithms with short-term searches. The solutions known to be the best to date are reported for the benchmark suite of Taillard with long-term searches, as well.     

An improved iterated greedy algorithm with a Tabu-based reconstruction strategy for the no-wait flowshop scheduling problem

This paper proposes a Tabu-mechanism improved iterated greedy (TMIIG) algorithm to solve the no-wait flowshop scheduling problem with a makespan criterion. The idea of seeking further improvement in the iterated greedy (IG) algorithm framework is based on the observation that the construction phase of the original IG algorithm may not achieve good performance in escaping from local minima when incorporating the insertion neighborhood search. To overcome this limitation, we have modified the IG algorithm by utilizing a Tabu-based reconstruction strategy to enhance its exploration ability. A powerful neighborhood search method that involves insert, swap, and double-insert moves is then applied to obtain better solutions from the reconstructed solution in the previous step. Empirical results on several benchmark problem instances and those generated randomly confirm the advantages of utilizing the new reconstruction scheme. In addition, our results also show that the proposed TMIIG algorithm is relatively more effective in minimizing the makespan than other existing well-performing heuristic algorithms.