一种改进粒子群的多机批调度求解方法

为解决并行多机批调度过程中效率过低的问题,提出一种改进粒子群的多机批调度求解方法。该方法借助随机权重、惯量权重对粒子群算法进行改进;构建一种适合调度问题的疫苗接种模型,并将其用于求解调度问题的免疫系统中,通过疫苗接种以提升调度问题求解的效率。以纺织企业的环锭纺为场景,试验结果表明,该求解方法的提升率达到77%,而且对多工件、多批次且加工时间长的批调度求解效果显著,充分说明该方法有利于解决多机批调度过程中效率过低的问题。

基于CiteSpace的差异尺寸作业批调度研究现状与发展趋势分析

为探讨差异尺寸作业批调度研究现状和进展,以发表在2000~2021年、收录于Web of Science(WOS)数据库的相关文献为研究对象,借助CiteSpace软件对这些文献的期刊共被引、主要研究力量的发文与合作、关键词共现与突现等情况进行可视化分析。文献计量结果表明,尽管我国的研究机构在差异尺寸作业批调度上的文献产出量大,但产出文献的整体学术影响力还有待提升;高频关键词集中在加工环境、优化目标、问题求解技术3方面;截至2021年仍保持高突现强度的关键词有增材制造、恶化作业、能源消耗、多目标优化。最后给出差异尺寸作业批调度研究的未来发展方向,以期为后续研究提供有益参考。

极小化总完工时间批调度问题的两种蚁群算法

针对考虑工件尺寸不同,求解目标为极小化总完工时间的批调度问题,考虑不同的编码方式,提出了基于工件序列的蚁群算法和基于批序列的蚁群算法。基于工件序列的蚁群算法算法采用传统的工件序列编码,需要启发式规则进行分批;基于批序列的蚁群算法算法利用蚁群算法构建性编码的特点,不需要启发式规则,而采取直接分批的方式编码,充分发挥蚁群算法自身的搜索能力。针对总完工时间的优化目标,基于批序列的蚁群算法算法引入批权重构建启发式信息;针对批调度特有性质,基于批序列的蚁群算法算法加入新的信息素更新变量,设置不同的信息素初始值,并采用局部优化技术等改进措施,以克服传统蚁群算法收敛速度慢,易陷入局部最优的缺点。通过对比实验验证了所提算法的有效性。

两机flow-shop类型模具热处理车间批调度算法

总结模具热处理车间生产调度的特点,在工件动态到达的情况下,研究了两阶段均为批处理机、各批次加工时间为定值的流水车间批调度问题。以最小化最大完成时间为目标建立混合整数规划数学模型,证明问题是NP难并给出最优目标函数值的下界,构建并证明一种求解大规模问题最优解的算法。算法首先求解分批数量上下界,然后构造数学模型并求解在给定分批数量下对应的最优解,最后通过对比各给定分批数量下得到的解并得到全局最优解。对于小规模问题,通过与传统分枝定界法得到的最优解相比较,说明所提算法能得到问题的最优解且计算时间更短;对于大规模问题,在不同生产状况下随机产生多组数据、对所提算法进行验证,结果显示该算法是有效的。

同类机环境下不同尺寸工件的分批调度问题

为了有效地利用批处理机,提高生产效率,提出了同类机加工环境下具有不同尺寸工件的批处理机调度问题并进行了求解。由于该问题是NP难解的,给出了一个下界以衡量近似算法的性能,并证明了该下界的有效性。提出了批的隐性加工时间的概念,并以此为基础给出了一种新的局部优化算法,对最大最小蚁群算法进行了改进。使用启发式算法最终对同类机环境下分批调度问题进行求解。通过仿真实验将该蚁群算法与遗传算法、微粒群优化算法及BFLPT等进行比较和性能分析。

含不一致任务重量的同型熔炼炉批调度优化

为求解含不一致任务重量的同型熔炼炉批调度问题,建立了最小化最大任务完工时间优化模型,设计了一种混合粒子群算法(HPSO)。算法使用随机生成的任务序列作为粒子,采用批首次匹配(BFF)规则对任务序列分批,最长加工时间(LPT)规则将批分配到批处理机,并提出了一种最小完工时间差(MCD)规则对LPT调度结果进行优化;为避免早熟,算法引入交叉和变异操作搜索最优解。通过仿真实验与SA、GA算法对比,实验结果表明算法具有良好的性能。

具有提前/拖期惩罚的热轧钢管批调度问题研究

建立了具有提前/拖期惩罚的热轧钢管批调度问题的混合整数非线性规划模型,提出并证明了给定合同排序下的最优组批方式,从而将原问题转化为易求解的合同排序问题.同时,建立了转化问题的数学模型并设计了遗传算法.仿真实验验证了模型和算法的有效性.

面向两客户的差异工件单机批调度问题

将差异工件批调度问题扩展到多客户生产环境,建立了优化两客户各自生产时间跨度的差异工件单机批调度模型。不同客户的工件集合具有自己的优化目标,为了满足不同客户的要求,需要多种不同的生产方案。针对该特点提出了一种面向两客户的单机批调度问题的多目标蚁群算法(MOACO),通过存储算法每次迭代产生的非支配解集,对人工蚁的搜索和信息素的更新提供指导,保证了搜索的效率。实验结果表明,与经典的多目标问题求解算法NSGA-II和SPEA2算法相比,多目标蚁群算法具有较好的求解效果,且随着问题规模的增大,算法的优势更加明显。

优化差异工件单机批调度问题的改进蚁群算法

研究了单机环境下工件尺寸有差异的批调度问题,设计了一种改进蚁群算法对问题的制造跨度进行优化。首先引入了Metropolis准则的概率选择机制作为路径激励策略,避免蚁群算法过早收敛的问题;然后采用了BatchFirstFit算法对蚁群的路径进行解码,以产生可行的分批方案。最后选取了问题的所有24类算例,将改进的蚁群算法和遗传算法及模拟退火算法进行了全面的对比实验,结果验证了改进的蚁群算法的有效性。

基于MMAS算法的带到达时间批调度问题研究

研究了工件带到达时间的目标为极小最大完工时间(C_(max))的单机批调度问题,采用最大-最小蚂蚁系统(max-min ant system,MMAS)进行求解。针对问题带到达时间以及分批的特性,提出了两种候选列表(candidate list)构建批序列,有效地缩小了搜索空间的维度;考虑两种候选列表的工件对构造解具有不同的影响,针对不同的候选列表设计了相应的启发式信息.仿真实验部分从求解质量和时间性能两方面比较了本文提出的算法和标准的蚂蚁系统(ant system,AS)算法以及使用不同候选列表的MMAS算法.结果表明,本文的算法在质量和时间两方面均全面优于标准的AS算法,而提出的候选列表使得该算法在大幅度提高时间性能的同时,仍然能够取得近似最优解,从而在求解质量和时间性能两方面取得平衡.

含不同到达时间和尺寸的批调度优化算法

研究了工件含不同到达时间且差异尺寸的单机批调度问题,优化目标为极小化最大完工时间Cmax。首先建立了该问题的混合整数规划模型,并使用运筹学软件CPLEX求解。针对问题构建性的特性,提出了蚁群优化算法求解该问题。通过分析到达时间和工件尺寸等约束对优化目标的影响,提出了空闲空间的概念Cmax,并证明极小化等价于极小化批空闲空间,基于此设计了动态的启发式信息以更精确地指导蚂蚁的行为。同时,引入候选列表策略,有效地减少了蚂蚁的寻优空间,提高了算法的收敛速度。仿真实验采用了文献中的测试算例,通过与CPLEX软件以及文献中的启发式算法和遗传算法的对比分析,验证了算法的有效性。

半导体炉管区批调度问题的粒子群优化算法研究

为改善粒子群算法对大规模问题求解的性能,提出了一种基于文化进化的并行粒子群算法,详细阐述了该算法的原理和具体实施方案。针对半导体炉管区批调度问题,设计了双层粒子群算法,外层应用基于文化进化的并行粒子群算法进行批量计划问题的求解,内层采用传统的粒子群算法求解调度问题。通过对其他文献中的仿真实例进行计算和结果比较表明,该算法优于文献中的启发式算法和蚂蚁算法。

Flow shop下批调度与设备维护的联合优化

批调度属于经典的调度问题之一,但在目前的批调度研究过程中,并未考虑到设备维护与批调度之间的相互干扰。以flow shop下批调度为研究对象,同时兼顾设备维护对调度的影响,建立了批调度与设备维护的联合优化模型。同时依据问题的特性,采用改进的遗传算法对问题进行求解。最后通过数值仿真实验验证了本模型和算法的有效性。

具有学习-遗忘效应的半导体批调度问题研究

半导体生产制造系统具有大规模、工艺繁杂、随机性大、可重入等显著特点。以半导体最终测试阶段批处理调度为基础,把学习-遗忘效应应用到典型半导体批调度问题中,构建基于学习-遗忘效应的批调度模型。分别结合调度问题和调度模型对双层算法(粒子群算法&萤火虫算法)进行设计,通过仿真实验检验了双层算法在求解具有学习遗忘效应的批调度模型方面的可行性和有效性,并对比分析以最大完工时间为优化目标的实验结果,探讨学习遗忘效应对半导体批调度问题的影响程度,对实际半导体生产具有重要指导意义。

不相容工件族柔性流水车间批调度算法

热处理是模具生产过程的瓶颈工序。在由淬火和回火两道工序组成的模具热处理柔性流水车间中,工件存在材料类型、到达时间、交货期、重量和优先级差异。在存在差异工件和不相容工件族的条件下,以最小化加权总拖期量为调度目标,提出两种改进启发式算法和一种新的构建启发式算法。并构建另一种典型规则算法对比说明所提算法的有效性。通过大量实验数据验证,结果显示新的构建启发式算法有较好的运算性能,满足企业实际应用需求。

流水作业批调度问题优化算法研究

为解决流水作业环境作业尺寸有差异的批调度问题,建立了基于混合整数规划方法的最大时间跨度模型,分析问题的计算复杂性,给出设备数、作业数既定情况下的可行解规模.设计一种混合蚁群算法对最大时间跨度进行优化,结合算法的搜索机制和批调度启发式规则,实现了最小化最大时间跨度.利用模拟退火方法改进蚁群算法路径选择,避免算法陷入局部最优和过早收敛.实验设计随机算例,对各类不同规模的算例进行仿真实验,实验结果表明混合蚁群算法在最优解、平均运行时间和最大时间跨度等方面优于其他同类算法.

并行多机批调度的混合粒子群算法研究

针对调度目标为最小化最大完工时间的并行多机批调度问题,提出了改进的基于批序列编码的混合粒子群算法。在基本粒子群算法的基础上,引入了学习因子二阶振荡、随机权重、最大速度线性递减及自然选择等方法,改善了算法本身易陷入局部最优及早熟收敛等问题,并解决了因引入新的方法造成算法收敛速度慢及寻优能力差等问题。由仿真结果可知:改进的算法均优于常规的粒子群算法,且根据批序列编码的改进算法更优于常规基于工件序列编码的改进算法。

混合粒子群算法求解单机批调度问题

设计了一种混合粒子群算法(Hybrid Particle Swarm Optimization,HPSO)以求解基于工件动态到达的最小化最大拖期时间单机批调度问题。该算法在标准粒子群算法的基础上引入了惯性权重正弦调整,以改善标准粒子群算法的收敛速度和全局收敛性,然后采用自适应变异全局极值算法增强粒子群优化算法跳出局部最优解的能力,防止算法陷入局部最优。应用改进的算法对实验设计问题进行求解,证明了改进算法的有效性。

面向两客户的差异工件平行机批调度问题

将差异工件的批调度问题扩展到两客户生产环境,建立了两个客户分别以最小化制造时间跨度和最小化最大工件延迟时间为生产目标的差异工件平行机批调度模型.首先提出了一种启发式算法TSEDD(two-set earliest due date)对分批方案进行排序并安排到平行机,然后设计了一个多目标蚁群优化算法MOACO(multi-objective ant colony optimization)对不同客户中的工件进行分批并结合TSEDD完成对问题Pareto最优解集的求解.实验结果表明,与经典的多目标问题求解算法NSGA-Ⅱ和SPEA2算法相比,MOACO具有较好的求解效果,且随着问题中工件规模的增大,算法的优势更加明显.

提前/拖期惩罚的单机批调度优化问题研究

针对准时生产意义下加工设备的单机作业准时生产方式,研究了提前/拖期惩罚的批调度问题,目标是使得加工总成本最小,目标函数不仅考虑了提前/拖期惩罚,还考虑了机器的加工费用。为了确定任务的最优分批与各批次的开始时间,给出了批调度优化应具有的4个特性,并根据这4个特性提出了两个启发式算法:按序搜索算法和对折搜索算法使得目标函数为最小。最后对两种算法的特点进行了分析。