基于遗传算法的JobShop调度问题研究

在多平行工作站环境下,为使限定资源分配下的车间调度问题(Job Shop problem,JSP)具有最小总延迟时间;同时又可设定各订单具有不同的开工日(release date)及到期日,提出以可开工时间与结束时间为基础的分解解法,并在遗传算法的基础上构造混合遗传算法(hybrid genetic algorithm,HGA)来实现目标设定。实验结果表明,HGA在问题求解质量与Lingo解的最佳解差异在15%以内,并具备较基本型遗传算法更佳的稳定性。结果显示该算法可帮助管理人员实现智能资源配置与订单调度。

求解JobShop调度问题的一种新的邻域搜索算法

利用了混合邻域结构进行搜索来求解JobShop调度问题.算法使用的混合邻域结构不仅使邻域搜索具有效率,而且有助于搜索有效地跳出局部极小值的陷阱,让计算走向前景更好的区域.算法采用的“单机调度”和“同工件工序调整”的跳坑策略能够帮助搜索找到更好的局部极小值.采用国际文献中所有的10工件10机器算例以及另外7个难算例作为本算法的测试实验集,与目前国际上最好的近似算法和另外一种先进算法进行了比较.实算结果验证了算法的寻优性能.

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

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

具有紧时、高能耗特征的混合流水车间多目标调度优化问题

针对具有紧时、高能耗工序特征的混合流水车间调度问题,以优化产品暴露时间、最大完工时间和能源消耗为目标,建立混合流水车间调度模型,并提出一种改进的多目标粒子群算法进行有效求解。首先构建了基于ISDE指标的档案维护策略及局部邻域搜索策略,辅助算法跃出局部极值及减少生产阻塞。之后,提出一种基于模糊理论的决策分析方法选取最优调度方案。最后,通过仿真实验验证提出的多目标调度模型与算法的可行性和优越性。

分支定价算法求解携带医疗资源的家庭医护人员调度问题

针对携带医疗资源的家庭医护人员调度优化问题,综合考虑医疗资源、弹性服务时间窗、医患技能等级匹配等特征,以最小化运营成本和弹性时间窗惩罚成本为目标构建数学模型。并根据Dantzig-Wolfe分解原理将模型重构为基于访问路径的主问题和若干带资源约束的最短路子问题模型。根据问题特征设计了分支定价算法来求解该问题。小规模算例结果表明医疗资源特性对医护人员路径调度有重要影响,而弹性时间窗可以有效降低总成本;多种算例的运算结果证明了分支定价算法求解的高效性。

一类加工需要额外资源的平行机调度问题的算法设计

给出了一类加工需要额外资源的平行机调度问题的精确算法。针对在平行机上加工的工件,除需要机器资源外,还需要一个单位额外资源的问题,考虑额外资源的种类和数量有限,以给出问题的最优调度使工件的完工时间最小为目标。该问题源于地球观测卫星的数据下载,在智能制造和信息处理等领域亦有广泛应用。给出了该问题的整数规划模型、最优解下界和分支定界算法;给出了一种有效的分支策略以避免重复分支,设计了相应的定界方法以提高算法的收敛速度。通过小规模实例和大量的数值仿真实验,验证了算法的正确性和在不同参数配置下的有效性。

改进混合粒子群算法求解带时间窗的无人机与车辆协同路径调度问题

为提高物流配送效率,考虑时间窗、无人机换电以及无人机多点连续配送等因素,提出了一种带时间窗的车辆与无人机协同配送问题,并设计一种带局部搜索的混合粒子群算法进行求解。该算法以混合粒子群算法为核心,通过构建高效的编解码策略实现了问题解空间到算法搜索空间的转换。进一步,该算法融合单点插入策略、车辆更换策略、无人机更换策略组成局部搜索策略,以此提高算法寻优能力。实验结果表明:所提模型比纯车辆配送的模型效率更高,节省了31.51%的成本;所提算法优于四种对比算法,优化率最高达到82.08%。

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

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

扩展帝国竞争算法求解分布式不相关并行机车间调度问题

针对考虑加工约束的分布式不相关并行机车间调度问题,以总运输成本、工厂间并行机齐停评价函数和工件种类平均切换次数均衡评价函数为优化目标,提出一种扩展帝国竞争算法进行求解。该算法在原始帝国竞争算法的基础上,增加了适于工厂分配的初始化工厂-工件序列群;根据传统帝国竞争算法容易陷入局部最优的缺点,将较劣序列同化分为了外部同化机制和内部同化机制,采用局部和全局相结合的搜索方式实现扩展帝国竞争算法的智能搜索行为;采用部分匹配交叉和单点变异更新工厂-工件序列群,保证工厂-工件序列的多样性。最后设计3个不同规模12个算例,通过仿真实验验证所提算法的有效性,同时对比相关领域研究成果验证了该算法在求解分布式多目标不相关并行机调度问题方面的优越性。

考虑道路限制的建设场地内车辆调度问题研究

针对大型设备运输车辆进入建设场地后,在场内道路上的车辆调度和路径规划问题进行了研究。受场内道路宽度限制,车辆难以在同一道路上相向行驶;同时,由于不同车辆所运输的货物及运输任务的紧急程度不同,车辆的通行具有不同优先级。针对上述特性,利用时空网络技术构建整数规划模型,在考虑道路限制和不同车辆优先级情况下,对建设场地内的车辆进行调度和会车规避。模型的目标为最小化所有车辆在场内的总时间,包括行驶时间和会车等待时间;模型包含两类约束,即车辆流平衡约束和车辆会车避让约束。为快速有效地求解模型,设计基于时空网络的启发式算法得到各车辆的时空路径,为车辆的路径规划和会车避让提供指导。结合一个实际的大型风电场路网,构建多个算例,对模型和算法的有效性进行验证。结果表明,提出的算法能迅速对不同规模的问题进行求解;另外,算法可以在消除车辆时空冲突的同时,保证车辆在会车时不等待过长时间,最终的方案具有较高的车辆运输效率。

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

配网调度管理中的问题与优化策略

配网调度管理是电力系统运行中不可或缺的关键环节,涉及电力供需平衡、设备调度、故障处理等多个方面。然而,在实际应用中,配网调度管理也面临着一些问题和挑战。本文将探究配网调度管理中存在的问题,并提出相应的优化策略,旨在提高调度管理的效率和质量,确保电力系统的安全稳定运行。

基于层次分析法加权处理的地震应急物资调度问题优化算法

地震通常具有巨大的破坏性,制订有效的地震应急物资调度和决策方案,对于高效有序地完成应急救援工作至关重要。基于地震中应急物资调度的特性,文章建立由时效性、经济性和伤亡性构成的多目标函数,经过阈值法的无量纲处理和层次分析法的加权处理,将复杂的多目标函数转化为单目标函数,进而运用匈牙利算法得到最优资源调度的决策方案。

引黄入冀补淀工程水资源调度存在问题及对策

按照2022年3月水利部下达的《关于组织开展典型调水工程水资源调度专题评估工作的函》(调管函〔2022〕3号)要求,我厅组织相关单位,以及引黄入冀补淀工程沿线市、县水行政主管部门,在全面调查引黄水量、水质、水费、调度管理等工作基础上,对引黄入冀补淀工程水资源调度情况进行全面评估。针对水资源调度过程中发现的问题,提出解决对策。

融合模拟退火参数的自适应遗传算法求解柔性作业车间调度问题

柔性作业车间调度问题是NP难问题,一般使用最大完工时间最短的评价指标来衡量加工顺序和机器选择的优劣,最短的完工时间意味着最快的生产速度。为了减小计算量并快速找到车间调度的最优解,提出了融合模拟退火参数的自适应遗传算法,详述了该算法的关键过程,并通过数据集的仿真实验验证了该算法的有效性。

基于带容量约束的着色旅行商问题的多机器人调度

电商仓储的高速发展对多拣选机器人的任务调度分配问题提出了更高的要求,着色旅行商问题在城市任务上的定性描述已经逐渐无法满足实际问题中的定量分析的需求。为了降低综合成本,提高拣选效率,拟在着色旅行商问题的基础上结合有容量限制的车辆路径问题,提出一种带容量约束的着色旅行商问题,来更好地构建以总路径成本最小为目标的多拣选机器人的调度模型,并设计相应的变邻域搜索算法对模型进行求解。实验结果表明,相较于基于遗传算法及其改进算法,变邻域搜索算法在求解带容量约束的着色旅行商问题上更具优越性,该模型及其求解算法具有一定实用价值。

35kV断路器调度遥控问题的改进粒子群优化算法求解

35kV断路器调度遥控问题在电力系统中具有重要价值和意义,但传统优化方法存在效率低、质量差等问题。针对35kV断路器调度遥控问题在电力系统中存在的复杂性、不确定性、多目标性等问题,本文提出了一种基于改进粒子群优化算法的求解方法。

基于改进多种群遗传算法的多目标资源受限项目调度问题研究

多目标资源受限项目调度问题普遍存在于生产经营活动中,具有较高的实用价值。本文提出了一种改进的多种群遗传算法以解决多目标资源受限项目调度问题,为改变现有算法计算步骤理解困难、不易推广的特点,巧妙地通过平移工作解决此类问题,算法首先对工作的优先级进行随机编码,然后根据工序约束进行解码,并根据解码结果安排工作调度,同时为防止无效迭代,融合了禁忌搜索的思想。最后,通过PSPLIB标准算例库中算例进行实验,实验结果表明该算法在具备较高精度的同时,兼顾了快捷性和简洁性。

结合FJSP问题的跨层穿梭车仓储系统作业调度研究

为提高跨层穿梭车仓储系统的作业效率,通过分析系统内设备的服务时间,创新性地将柔性作业车间调度问题(FJSP)模型应用于解决跨层穿梭车仓储系统作业调度问题中,将穿梭车仓储系统中的出入库作业转化为FJSP中待加工的工件,同时考虑设备预先移动及并行情况,建立结合FJSP的跨层穿梭车仓储系统作业调度模型,并借助一种改进的灰狼算法,与传统的基于复合作业的调度模型进行对比。结果表明,所提出的结合FJSP问题的跨层穿梭车仓储作业调度出入库时间更短,模型通用性更高,能够有效地提高穿梭车仓储系统的作业效率。

基于离散混合蛙跳算法的地震应急物资调度

建立震后应急物资调度数学模型。该模型根据各灾区的受灾情况评估其救援紧急程度,并设计一种需求拆分供应的运输机制,提高车辆的利用效率。为求解该模型,提出一种多源信息学习的离散混合蛙跳算法。所提算法引入多种信息源以扩展算法的搜索方向,降低种群的同化速度。同时,让子组最差个体学习种群中的有效信息,提高算法的收敛精度。实验结果表明,所提算法能够搜索到精度更优的调度方案,对问题规模具有良好的可扩展性。