求解柔性作业车间调度问题的两级邻域搜索混合算法

针对柔性作业车间调度问题(Flexible job shop scheduling problem,FJSP),以优化最大完工时间为目标,提出一种融合两级邻域搜索和遗传算法的混合算法。基于通过利用机器空闲时间来减小最大完工时间的想法,构造邻域结构,对关键路径上的关键工序进行移动,实现邻域搜索,以改进当前解;设计针对FJSP问题特点的两级邻域搜索方式,第一级邻域搜索为跨机器移动工序,将工序移动到除当前加工机器之外的其他可选机器上,第二级邻域搜索为同机器移动工序,将工序在当前加工机器上进行移动;给出两级邻域搜索相应的保证可行解工序移动条件;兼顾FJSP问题求解算法的全局搜索能力和局部搜索能力,利用遗传算法实现全局搜索,两级邻域搜索实现局部搜索;采用国际通用的FJSP问题基准算例进行测试,验证了所提方法的有效性。     

作业车间调度的空闲时间邻域搜索遗传算法

针对最小化最大完工时间的作业车间调度优化问题,提出一种基于空闲时间的邻域搜索遗传算法。通过对不同解码方式的分析,设计了一种基于空闲时间的邻域结构及其邻域搜索方法;分析了同一机器上相邻两工序间的空闲时间,给出最大限度查找关键工序相关机器空闲时间的方法;查找关键工序前后的机器空闲时间,在保证可行解的条件下,移动关键工序到空闲时间位置实现邻域搜索;给出同一台机器上任意两个工序位置相对移动时保证可行解的工序移动条件及证明。将基于机器空闲时间的邻域搜索方法融入遗传算法,采用典型算例进行测试,与文献中不同算法的求解结果进行比较,验证了所提方法的有效性。     

一种基于改进NSGA-Ⅱ的多目标绿色柔性作业车间调度方法

针对多目标绿色柔性作业车间调度问题,建立了以最小化最大完工时间、总负荷和总能耗为优化目标的多目标优化模型,提出了一种带有自适应交叉变异算子和学习机制的改进NSGA-Ⅱ多目标优化算法。该算法通过机器和工序的两级编码机制,使用基于全局、局部和随机选择的非支配排序选择策略得到初始种群;采用具有自适应算子的混合交叉变异策略进行迭代,提高算法的全局搜索能力;引入分布函数来改进精英保留策略提高种群的多样性;通过学习机制进行邻域搜索提高算法的局部搜索能力。最后,采用基准测试算例Brandimarte以及Kacem数据集对算法进行测试,结果表明采用改进的NSGA-Ⅱ算法求解多目标绿色柔性作业车间调度问题具有求解精度高、收敛速度快以及解集多样性好的优点。     

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

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

应用混合蚁群算法求解模糊作业车间调度问题

为解决蚁群算法求解时间过长和易陷入局部最优的问题,提出了一种求解模糊作业车间调度问题的混合算法,该算法将蚁群算法用于全局搜索.为了提高搜索效率,根据作业车间调度问题解的特征,提出一种基于关键工序的邻域搜索方法,并使用此邻域搜索方法的禁忌搜索算法嵌入蚁群算法.利用禁忌搜索算法较强的局部搜索能力,提高了蚁群算法的优化能力,改善了作业车间调度问题解的质量.实验结果验证了该混合搜索算法的有效性,其优化效果优于并行遗传算法和禁忌搜索算法.     

基于员工学习行为的多目标柔性车间调度

针对存在异质性员工的多目标柔性作业车间调度问题,构建了具有Dejong学习效应的调度模型,并提出变邻域杂草算法求解该问题。为解决工序排序、机器选择和员工指派3个子问题,基于随机键编码方式对杂草个体进行编码。采用灰熵关联方法给出杂草的适应度值,根据杂草之间的偏序关系对杂草群体的拥挤距离进行排序,从而产生新的父代群体。构造了3种邻域结构,在迭代后期对精英个体进行变邻域搜索。最后,将算法用于Kacem柔性作业车间基准问题和具有异质性员工的柔性作业车间调度问题求解。案例分析表明,算法可有效求解基准问题和多个"不可压缩因子"F值的柔性车间调度问题,其总完工时间对F值的敏感度更高。     

一种求解作业车间JIT调度问题的混合TS/MP算法

作业车间JIT调度属于一类典型的非正规性能指标调度问题,该类问题为每道工序设置了交货期约束,工序的提前或拖期完工均会产生相应的惩罚成本。采用禁忌搜索和数学规划相结合的混合调度方法进行求解。在算法的迭代搜索过程中,首先,由每个个体产生各机器上的工件加工序列,由此松弛了调度模型中的机器能力析取约束,然后,调用数学规划方法来优化各机器的空闲时间和各工序的开工时间。为提高禁忌搜索算法的计算效率,设计了一种包含交换和插入操作的邻域结构产生方案。最后,用JIT调度领域的32个标准测试算例验证了该调度算法的有效性。     

分布式多柔性装配作业车间调度问题研究

针对分布式柔性装配作业车间环境，综合考虑了调度过程中的机器选择柔性、工人安排柔性和工序顺序柔性，构建了以最小化最大完工时间和最小化总能耗为优化目标的分布式多柔性装配作业车间调度问题(DMFAJSP)的数学模型。为求解DMFAJSP模型，提出了一种以分布估计算法为全局搜索组件、以邻域搜索算子为局部搜索组件的多维模因算法(MDMA)。最后，将所提出的算法与其他算法进行了对比试验，结果表明MDMA算法在求解DMFAJSP模型方面具有显著优势。     

求解作业车间JIT调度问题的VNS/MP混合算法

针对作业车间准时制调度这类复杂的非正规性能指标调度问题,基于机器加工序列和工序开工时间的两阶段优化策略,提出一种结合变邻域搜索和数学规划的混合调度算法。在变领域搜索的每次迭代过程中,通过在Swap和Insertion两类邻域结构内跳转搜索获得较优的机器加工序列,由此松弛了调度模型中最难满足的机器析取约束;然后调用数学规划方法对当前机器加工序列上的各工序开工时间进行优化计算。以引导工序向各自交货期靠拢为邻域设计原则,提出以紧邻工序对为移动对象的Swap和Insertion邻域结构;为增加搜索空间的多样性,变领域搜索中的局域搜索算法采用基于调度目标值容许偏差的阈值接受策略。对72个准时制调度的Benchmark算例的仿真结果表明,变领域搜索/数学规划混合算法获得了35个算例的已知最好解,并且更新了其中25个算例的已知最好解。     

混合蜂群算法求解柔性作业车间调度问题

为解决柔性作业车间调度问题,提出一种基于蜂群模型的混合群智能优化算法.在算法初始化阶段提出了蜂群优化算法结合随机方法的种群初始化方法,提高了初始种群质量;为提高算法搜索精度,在观察蜂阶段采用模拟退火算法更新观察蜂群,并以退温系数调节邻域规模,随算法进程细化搜索范围;针对柔性作业车间调度问题特点,建立了可控规模的邻域更新方法.采用柔性作业车间标准算例,通过仿真编程和与其他算法的比较,验证了算法的有效性和优越性.     

改进细菌觅食算法求解柔性作业车间调度问题

针对柔性作业车间调度问题的NP难特性,提出一种改进的细菌觅食优化算法。采用集成法策略同时求解柔性作业车间调度问题的机器分配和工序调度子问题。将细菌个体表示为工序串,建立问题和算法的映射关系;分别针对普通细菌个体和当前最优个体设计了多重趋化操作,以增强算法的局部搜索能力;复制操作设置繁殖阈和死亡阈,以提高对历史经验的继承程度;迁移/驱散操作中,结合改进的LPT启发式规则,提出带倾向性的迁移/驱散操作方式。采用正交试验对算法的重要参数进行了优化配置,通过搜索算子优化效果对比实验证明了正交试验的结论;进行了收敛性能对比实验,证明算法具有优秀的全局开发能力和局部探索能力;典型算例实验结果表明,该算法能够有效求解柔性作业车间调度问题。     

基于混合遗传鲸鱼优化算法的柔性作业车间自动导引车融合调度方法

针对柔性作业车间调度问题,考虑自动导引车(AGV)在车间制造过程中只参与装卸和搬运工作,提出一种实现AGV路径规划与柔性作业车间调度集成优化的融合调度模型。采用基于工序排序与机器选择两个子问题的二维向量编码方案,并在解码过程中提出基于最先服务原则的AGV安排策略。对鲸鱼优化算法进行离散化改进,针对性地设计了多种种群初始化策略,引入遗传算法的交叉、变异操作以提升鲸鱼优化算法的全局搜索能力,并嵌入局部搜索算法以达到全局搜索和局部搜索的平衡,构建了一种混合遗传鲸鱼优化算法（HGWOA）来求解该融合调度模型。通过经典测试算例验证了算法性能,并使用正交试验优化了算法参数。研究结果表明,HGWOA算法用于求解柔性作业车间AGV融合调度问题可以获得较好的效果。     

考虑工件分批的柔性作业车间调度及求解算法

针对柔性作业车间分批调度问题,建立了考虑工件分批的柔性作业车间调度模型,并提出混合遗传算法用于模型求解。首先,采用改进试探法确定划分的具体批次、柔性批量划分方法确定各个批次的实际批量;其次,采用双层编码机制对工序排序及机器选择同时进行优化,利用GLR机器选择法生成初始解;最后,混合遗传算法利用GA鲁棒性强与ABC算法对初始解依赖性不高、适应性强的特点在解空间内充分搜索较优解,并结合SA出色的局部搜索能力快速收敛到全局最优解。分析表明,改进试探法批次划分与柔性批量划分方法可明显缩短生产周期,同时也证明了所提算法的有效性和可行性。     

基于新型邻域结构的混合算法求解作业车间调度

针对作业车间调度问题(Job shop scheduling problem,JSP),以优化最大完工时间为目标,提出一种融合新型邻域结构的混合求解方法。混合算法由具有全局搜索能力的遗传算法和基于邻域结构的邻域搜索算法构成。在邻域结构的设计中,研究了基于甘特图的工序头尾长度计算方法,以及关键工序查找方法。通过分析已有各种邻域结构及相关理论性质,指出邻域结构的根本在于引导关键工序对机器空闲时间进行利用,并将利用方式分为两种情况:直接利用和间接利用。综合两种利用方式,科学指导关键工序的移动,根据关键工序的类型定义相应的移动操作,使其移动范围突破了工序块的内部、紧前、紧后位置限制,扩大了有效移动范围。结合43个基准算例进行测试分析,验证了所提算法具有良好的求解性能。此外,所设计的邻域结构可以进一步融合其他智能算法求解JSP问题。     

基于改进候鸟算法的柔性作业车间分批调度问题

为了将可变批次的调度策略应用于生产,以提高大规模柔性作业车间的生产效率和设备利用率,针对柔性作业车间可变子批问题的特点,建立了以最小化完成时间和最小化批次数目为优化目标的多目标柔性作业车间调度模型和析取图模型,提出一种改进的候鸟算法求解该问题.算法设计了精英分批和可行邻域结构两种策略用于提高算法的搜索效率.通过对比实验验证了可变批次划分策略的优势和所提算法的有效性.     

融合路径重连的混合算法求解作业车间调度问题

针对作业车间调度问题,以优化最大完工时间为目标,提出一种融合路径重连、邻域结构和遗传算法的混合算法。邻域结构能够指导工序的移动,大大减少搜索时间,提高搜索能力;路径重连作为邻域结构的一种有效弥补方式,通过探索高质量解及其逆解之间的差异,生成一系列路径解,对路径解进行评价,选择较好的解进入下一代,可以进一步提升算法性能。结合作业车间调度问题的43个基准算例进行仿真分析,验证了所提算法具有良好的求解性能。     

基于机器故障的车间调度研究

针对柔性车间调度下的机器故障问题,构建了基于粒子群优化算法的多目标柔性车间调度模型。加工机器发生故障后,用重新调度方法对未加工的所有工序进行重调度安排,以减少机器故障对优化指标的影响。同时给出一种稳定性指标来评价重调度的效果,以及机器发生故障的概率去预防机器出故障的情况,提高算法的有效性和稳定性。然后引入了淘汰机制改进算法,提高算法的全局收敛效率,并运用改进算法对具有故障机器的多目标柔性车间调度问题模型进行仿真实验。最后验证了该算法在车间调度中发生机器故障的可行性。     

元胞遗传算法求解柔性作业车间调度问题

针对柔性作业车间调度问题的特点,采用基于工序和基于机器分配的两部分编码方式,在交叉变异时对两部分基因串分别进行操作。与其它优化算法的结果进行对比分析,利用该算法求解经典柔性作业车间调度问题具有有效性。     

求解低碳车间调度问题的改进鲸鱼算法

针对传统柔性作业车间调度问题只考虑完工时间,设备利用率,完工成本等因素的局限,构建了以碳排放成本和完工时间成本加权和最小为目标的低碳柔性作业车间调度问题模型,并设计了一种改进的鲸鱼优化算法对其进行求解。首先,采用等长的两段式编码方式来表示柔性作业车间调度问题,引入基于ROV规则的转换机制,实现鲸鱼个体位置向量与调度解之间的相互转换。其次,采用基于一定比例的全局搜索、局部搜索和随机搜索的混合式种群初始化方法,生成一定质量的初始种群,同时设计了非线性收敛因子和自适应惯性权重系数来加强算法协调全局搜索和局部寻优的能力。再次,引入自适应调整搜索策略以提高算法跳出局部最优的能力。最后,通过实验数据验证了改进鲸鱼算法在求解低碳柔性作业车间调度问题方面的有效性。     

基于分布估计—蚁群混合算法的柔性作业车间调度方法研究

针对柔性作业车间调度问题,对其优化方法进行了研究,建立了多目标柔性作业车间调度问题的函数模型,提出了分布估计—蚁群混合算法。该算法首先采用分布估计算法快速得到了全局较优解,然后通过选择部分较优解对蚁群算法信息素初始化进行了改进,最后利用蚁群算法正反馈机制快速寻找到了全局最优解;在改进的分布估计算法中,结合了多种方法进行机器选择和工序排序的初始化,给出了相应概率模型和种群更新方式;在改进的蚁群算法中,通过建立两个路径节点集合进行了状态转移规则的描述,并对信息素更新机制进行了分阶段局部更新和全局更新,有利于蚁群算法快速收敛到全局最优解;通过两个柔性作业车间调度实例进行了仿真分析以及和其他算法的对比。研究结果表明:分布估计—蚁群混合算法在求解柔性作业车间调度问题具有较好优化效果和高效求解能力。