双机流水车间外包与调度联合优化问题的混合变邻域搜索算法

针对最小化内部完工期与总外包费用的双机流水车间外包与调度联合优化问题,开发了一种混合变邻域搜索算法。在该算法中,采用工件剔除型启发式方法产生初始联合决策解;基于3种新型邻域结构提出了最佳改进式局部搜索规程;引入概率式准则来决定下轮迭代的目标搜索邻域。通过算法校准实验分析,探索出合适的邻域变更次序和温度参数的计算方式。通过与CPLEX软件、隐枚举测试程序对比显示,对于工件数不超过30的算例,校准后所提算法求得最优解的耗用时间更少。通过与遗传算法、模拟退火算法、和声搜索3种对比算法在工件数不少于100的算例上进行对比发现,所提算法经校准后,在求解质量和解的鲁棒性上均具有显著优势。     

带多处理器混合流水车间调度问题的混合鱼群算法

针对带多处理器的混合流水车间调度问题(hybrid flow shop scheduling with multiprocessor task problems),以最小化所有工件的最大完成时间(makespan)为优化目标,提出一种融合了改进的人工鱼群算法和禁忌搜索算法的混合算法。首先改进人工鱼群算法相关行为及实验优选算法参数,提高了人工鱼群算法收敛速度和精度;然后结合人工鱼群算法收敛快和禁忌算法局部搜索能力强的特点,利用改进的人工鱼群算法进行全局搜索,获得较好的优化解域,再通过禁忌算法在优化解域内进行局部寻优,得到一个最终满意的优化解。基于180个标准算例,算法实验结果表明混合算法的优化性能明显优于禁忌算法和粒子群算法,并且很接近改进的遗传算法。     

一种面向室内 AGV 路径规划的改进蚁群算法

针对传统蚁群算法在大规模和复杂环境中,全局搜索效率差,收敛速度慢,路径转弯次数过多且不够平滑等问题,本文提出一种改进蚁群算法。该方法通过动态更新不同等级蚂蚁路径上的信息素,加快算法的收敛速度;通过引入距离函数和方向函数作为启发因子,改善路径搜索质量;采用一种改进自适应伪随机转移策略,减小陷入局部最优解的概率;在最优路径的基础上引入三次均匀B样条曲线进行优化,提高路径的平滑性。通过在2种不同规模环境下的路径规划实验表明,本文算法相比传统算法在分别减少55.6%和59.4%转弯次数的基础上,提升87.5%和100%的收敛速度,验证了本文算法的优越性。最后,以QBot2e为平台,将本算法应用到室内自动导引车(AGV)路径规划中,进一步验证了算法的实用性。     

面向作业车间的自适应非均匀窗口蚁群算法

为纠正作业车间调度问题中蚁群算法搜索周期长、易陷入局部极小值的缺点,提出了一种改进的自适应非均匀窗口蚁群算法。首先,该算法通过自适应调整的非均匀窗口限制蚂蚁的移动范围,在缩短蚂蚁搜索周期的同时及时开辟新的解空间;然后,根据蚂蚁的多态性提出了蚂蚁跳跃窗口策略,赋予算法良好的跳出局部极小的能力;最后,鉴于作业车间调度中一个工件在多个机器上加工的特点,新算法对蚂蚁状态转移概率中的启发函数进行了改进,提高了路径的启发程度。通过对Muth and Thompson基准问题的仿真,验证了新算法的收敛性能。     

混沌压缩非线性粒子群算法求解车间调度问题

针对大规模车间调度问题,提出了一种混沌压缩非线性粒子群算法。首先运用多种群策略增加粒子多样性,结合混沌策略和非线性策略改进惯性权重,以平衡全局和局部搜索能力,加快算法后期收敛速度;再引入压缩因子改进算法速度更新公式,加大算法前期搜索范围,以防止算法陷入局部最优;最后用6种车间作业经典算例分别对粒子群算法、遗传算法、灰狼算法和混沌压缩非线性粒子群算法进行检验。实验结果表明,该方法可以显著提升粒子群算法的收敛精度和速度,对于实际大规模车间调度问题适应性较好,能有效提高车间的生产效率。     

多加工路径柔性作业调度方法

为了提高企业生产效率,降低生产成本,以仪器仪表制造业为背景,针对某企业流量计生产车间的特点,建立优化目标函数,提出了多加工路径柔性作业车间调度模型(MPFJSP)。为了避免该模型中非可行解的干扰,采用新的顺序编码方式和在非可行解周围搜索可行解并代替之的方法;且为提高收敛速度,将粒子分为若干小段分别更新和扰动,以保留优秀基因,由此形成分段多目标粒子群优化算法(PMOPSO)。通过算法对比,发现所提方法能在工件的每一条加工路径中寻优,验证了其性能更优越,也验证了MPFJSP相对于传统柔性作业车间调度(FJSP)更灵活,得到的解也更优,在流量计生产车间的实验性生产中,违约成本约下降了12%,生产效率提升约10%。     

模糊分布式柔性作业车间调度优化

针对考虑工件加工时间不确定性的模糊分布式柔性作业车间调度问题(fuzzy Distributed Flexible Job Shop Scheduling Problem, fDFJSP),将加工时间用三角模糊数表示,以最小化最大模糊完工时间为优化目标,提出一种改进的人工蜂群算法进行求解。针对fDFJSP的分布式特点,设计了基于车间-工序-机器的三层编码方式,针对不同编码层,采用多种混合搜索策略,以提升算法的邻域和全局搜索能力。为测试算法的性能,设计了2组实验对5个算例进行测试,并与代表性算法进行对比。结果表明,所提算法结果总体优于其他对比算法,能够有效求解具有模糊加工时间的模糊分布式柔性作业车间调度问题。     

改进的遗传算法在机加车间排产优化的研究

机加车间排产优化是降低生产成本,提高加工效率,增强企业市场竞争力的重要措施,遗传算法作为一种高效的优化算法在求解排产问题中得到广泛应用。以加工时间最短为目标,对机加车间工件加工问题建立数学模型。针对标准遗传算法(SGA)求解存在的早熟收敛、求解精度低等问题,提出一种改进的遗传算法。为获得更好的基因结构,以个体适应度值为参照自动调节交叉概率和变异概率。为避免无效解,根据加工任务高度值划分基因段来改善交叉操作。为增强算法的全局搜索能力,引入混沌理论优化变异算子。仿真结果表明改进的遗传算法较SGA有更好的收敛性和全局搜索能力,对机加车间排产优化效果明显。     

分区协作遗传算法及其在大规模TSP问题中的应用

针对传统遗传算法(Genetic Algorthm,GA)在求解大规模路径优化问题时容易陷入局部最优问题,提出一种分区协作优化模型,以提升种群多样性及局部搜索能力。首先,根据拟分区的规模基本相同,以代价函数为依据提出一种自适应聚类分区方法,将大规模路径优化划分为若干分区,采用传统GA算法获得局部的最短路径排列;然后,按照就近原则将分区最短路径进行拼接,获得大规模路径优化问题的最优解,并利用4个TSPLIB标准集进行试验验证。最后,利用Rat195TSP实例探究分区数目对优化结果的影响。结果表明,分区数目相同时,路径规模与优化结果具有明显正相关关系。Rat195TSP实例拟合表明,分区数与最优解满足凹函数特性,当分区数目在8～12时,获得的最优解效果最好。     

求解多目标混合流水车间调度的改进NSGA-Ⅱ

针对混合流水车间调度问题,以最小化能耗和最小化最大完工时间为求解目标,建立混合整数线性规划模型,提出求解该问题的改进快速非支配排序遗传算法(NSGA-Ⅱ)。算法染色体采用首阶段工件加工顺序码和设备分配码相结合的编码方式,最大程度确保算法在问题的整个解空间搜索Pareto前沿解。针对染色体编码设计了3种不同解码方法,其中两种解码方法与问题目标密切相关,用于引导算法搜寻方向;设计了一种贪婪变异算子,在提高种群多样性的同时兼顾算法的局部搜索能力。为确保Pareto前沿解集的分布性和收敛性,避免算法陷入局部最优,在采用精英保留策略的基础上提出一种全新的选择算子,并通过实验证明了该选择算子的有效性。为进一步节约能源,针对调度方案提出先右移再左移的调整策略,在不改变总完工时间的前提下大大节约了设备的待机和开关机能量。最后通过实验验证了改进NSGA-Ⅱ的有效性。     

基于改进鸟群算法的双资源约束离散智能车间调度问题研究

针对双资源约束的离散智能车间调度问题,提出改进鸟群算法对该问题进行求解。根据离散智能车间的特点,以最小化最大完工时间为目标,建立了工人仅负责工序中工件上、下料操作的车间调度模型;根据鸟群算法的搜索特点,对算法的位置更新公式进行离散化改进,以适用于求解该车间调度问题;采用三条链组合编码方式,简化算法的寻优过程;改进了基于时间窗口比较的活动化解码;引入模拟退火算法增强算法跳出局部最优解的能力。最后通过具体实例验证了改进后的算法具有良好的性能。     

柔性作业车间调度多策略果蝇优化算法研究

针对柔性作业车间调度问题,提出了融合多种策略的果蝇优化算法,以最小化最大完工时间为目标,生成合适的调度方案。在该算法中,采用反向学习策略进行种群初始化,改善初始解的质量。其次引入变邻域搜索算法作为果蝇的嗅觉搜索策略,提升局部搜索能力;在此基础上,提出能够增加种群多样性的位置重构策略,根据嗅觉搜索后种群的平均适应度值将果蝇动态地划分为先进子种群和普通子种群,普通子种群以先进子种群为目标进行位置重构,先进子种群相互为目标进行位置重构,避免搜索陷入局部最优。最后,设计正交实验探究变邻域搜索参数对算法性能的影响,并确定相关参数合适值;通过计算多个标准测试集基准算例,得到每个测试集的最优解及平均解,并与现有算法的计算结果进行对比,验证了改进策略的有效性及所提算法的优越性。     

考虑设备周期性维护的流水车间生产调度优化算法

针对流水线车间,在考虑周期预防性维护的基础上,以最小化最大完工时间为优化目标,分别建立了置换车间与非置换车间两种不同情形下的数学优化模型。设计了结合增量式进化策略、局域搜索机制、种群密度管理的混合遗传算法,对问题进行优化求解。提出了以NEH思想为基础的快速启发式算法,该算法结合了邻域搜索与基于解序列破坏重组的广度搜索机制。在不同问题规模下,混合遗传算法的解与CPLEX精确解的对比结果表明:混合遗传算法可有效求解此类问题,而所提出的启发式算法可在保证解的较优性的基础上大幅度提高运算速度。随着工件数量和维护频次的增加,非置换车间的柔性使得其表现相比置换车间更加优异。     

基于改进非支配排序遗传算法的多目标柔性作业车间调度

采用多目标进化算法解决具有工件释放时间、工件目标差异的柔性作业车间调度问题。依据实际制造系统中存在较多的最大完工时间、平均流经时间、总拖期时间、机器总负荷、瓶颈机器负荷和生产成本性能指标,建立多目标柔性作业车间调度模型。针对柔性作业车间调度问题的特点,设计一种扩展的基于工序的编码及其主动调度的解码机制,以及初始解产生机制和有效的交叉、变异操作;针对非支配排序遗传算法(Non-dominated sorting genetic algorithm II,NSGA-II)在非支配解排序和精英选择策略方面的不足,设计一种改进的非支配排序遗传算法,应用改进的算法求解柔性作业车间调度问题得到一组Pareto解集,并运用层次分析法选出最优妥协解。通过测试基准和模拟实际生产的实例,验证提出算法的可行性和有效性。     

无成组技术条件下流水车间调度的多目标优化

针对有工件组调整时间的流水车间调度问题,提出了无成组技术假设条件下的多目标优化模型,并设计了一种进化计算与局部搜索结合的混合遗传算法.模型的目标函数是最小化最大完工时间和最大拖期.在局部搜索过程中,根据问题的特征定义了两种邻域结构,采取两阶段搜索策略,以提高算法的优化搜索效率.进化过程中,采用基于个体的累计排序数和密度值的适应度分配方法,以保持群体多样性,并采取精英保留策略,以保证解的收敛性.通过测试问题和实际问题的实验以及与其他算法的比较,验证了所提模型和算法的有效性.     

基于改进蛙跳算法的鲁棒性车间布局

为了避免动态环境下频繁进行车间布局,降低车间运行成本,针对设施面积不等的车间类型,将静态布局中的面积费用指标引入鲁棒性车间布局中,建立以车间物料搬运费用和面积费用最小化为目标的多目标鲁棒性布局优化模型;改进现有鲁棒性指标,设计了一种鲁棒性布局约束以提高最终方案的鲁棒性;提出一种改进蛙跳算法求解该模型,通过系统布置设计得出部分较优的初始解以提高初始解集的整体质量,利用差分变异算子替代蛙跳算法中的局部搜索策略以提高寻优速度;通过基准算例及实例问题验证了模型和算法的有效性。     

混合布谷鸟算法求解绿色流水车间调度问题

为协同考虑经济因素和环境因素,求解了优化目标为最小化最长完工时间和碳排放总量的多目标置换流水线车间调度问题(MOPFSP)。提出了一种混合布谷鸟算法(HCS)求解2台机器以上的MOPFSP问题。采用LOV规则将HCS算法中的个体从实数向量转换成工件排序,使其可在MOPFSP的解空间中进行搜索;设计了一种自适应步长控制因子,用于控制算法进化阶段的搜索范围;提出一种多邻域局部搜索,用于对HCS算法全局搜索发现的优质解区域进行细致搜索。由于融合了基于布谷鸟算法的全局搜索和多邻域局部搜索,故HCS算法可有效求解MOPFSP。仿真实验和算法对比验证了HCS算法求解MOPFSP的有效性。     

基于Memetic算法的车间动态调度策略研究

针对车间动态调度问题的求解,提出了一种基于Memetic算法的车间动态调度策略。该策略结合滚动窗口机制,并采用基于周期和事件的混合驱动策略,运用Memetic算法对每个滚动窗口工件集进行重调度。该算法采用顺序交叉算子和基于邻域搜索的新型变异算子,在交叉和变异后均采用改进的模拟退火策略进行局部搜索。通过对改进后的基准实例进行实验,验证了该策略的有效性。
     

求解过道布置问题的一种改进分散搜索算法

为更好地反映实际布置情况,针对现有研究在求解过道布置问题时忽略通道宽度、未设置总流量入口等不足,构建了考虑通道宽度和总流量入口的混合整数规划模型,提出一种改进分散搜索算法进行求解。该算法将禁忌搜索操作嵌入分散搜索的解改进方法中,可以进一步优化参考集中的解,提高获得全局最优解的概率。设计了包含高质量和多样性解的双层参考集、动态参考集更新方法、子集产生方法等多种改进机制。对不同规模(9~49个设施)的测试问题进行了验算与对比,结果表明:针对小规模问题,所提算法均求得了与Lingo软件相同的最优解;对大规模问题的求解质量明显优于基本分散搜索算法和禁忌搜索算法。     

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

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