超启发式三维分布估计算法求解分布式流水线和车辆运输集成调度问题

针对一类广泛存在的分布式流水线和车辆运输集成调度问题(Distributed Permutation Flow-shop and Vehicle Transportation Integrated Scheduling Problem,DPFVTISP),本文建立问题模型,并提出一种超启发式三维分布估计算法(Hyper-Heuristic three-Dimensional Estimation of Distribution Algorithm,HH3DEDA)进行求解.首先,根据DPFVTISP的问题特性,采用贪婪策略设计一种新颖的编解码规则.其次,为实现对DPFVTISP问题解空间中不同区域的深入搜索,设计10种低层启发式操作(即10种有效的邻域操作),并将其所构成的排列作为高层个体;同时在高层采用三维分布估计算法(three-Dimensional Estimation of Distribution Algorithm,3DEDA)学习和积累优质高层个体中块结构及其位置信息,再通过采样3DEDA中的概率模型生成新的高层个体或排列;进而在低层将高层所生成的每个新个体所表征的一系列有序的启发式操作作为一种新的启发式算法,对问题解空间执行较深入的邻域搜索.最后,通过仿真实验与算法对比验证HH3DEDA可有效求解DPFVTISP.

超启发式交叉熵算法求解模糊分布式流水线绿色调度问题

针对实际生产过程中普遍存在的加工时间不确定性,采用模糊数表示工件的加工时间,以同时最小化模糊最大完工时间和模糊总能耗为优化目标,建立模糊分布式流水线绿色调度问题(green distributed permutation flow-shop scheduling problem with fuzzy processing time,GDPFSPFPT)的模型,进而提出一种超启发式交叉熵算法(hyper-heuristic cross-entropy algorithm,HHCE)进行求解.首先,HHCE采用一种新颖的三角模糊数排序准则合理计算个体的目标函数值,可在算法搜索过程中较准确发现优质解区域;其次,HHCE在高层利用基于贡献率的评价方法确定8种特定邻域操作所构成的各排列的优劣,同时采用交叉熵(cross-entropy,CE)方法学习较优排列的信息并生成新排列,进而在低层把高层生成的每个排列作为一种启发式算法,对低层相应个体执行一系列邻域操作,以实现对问题解空间较多不同区域的搜索;然后,HHCE将基于非关键路径的节能策略用于对低层每代种群中的较优个体执行局部搜索,从而进一步提高算法获取低能耗非劣个体或解的能力;最后,仿真实验与算法对比表明,HHCE可有效求解GDPFSPFPT.

求解区间数分布式流水线调度的混合离散果蝇优化算法

分布式调度是制造系统领域的前沿研究,而不确定调度问题的研究更具现实意义.针对不确定分布式置换流水线调度问题,采用区间数表示工序加工时间,以最小化区间最大完工时间为目标,利用问题特性在果蝇优化框架内提出一种混合离散果蝇优化算法.首先,通过改进启发式方法和随机方法混合初始化种群;然后,基于概率协同多搜索操作执行嗅觉搜索.为了平衡算法的全局探索与局部开发能力,设计基于学习机制的双种群协同搜索环节.为了进一步提升种群性能,针对优良解设计基于切换机制的双模式局部搜索.基于大量算例的仿真结果与统计对比,表明所提出算法能更有效求解区间数分布式流水线调度问题.

混合迭代贪婪算法求解准时生产分布式流水线调度问题

针对以最小化总延迟时间为优化目标的分布式置换流水线问题(distributed permutation flowshop scheduling problem,DPFSP),建立问题排序模型,并提出混合迭代贪婪算法(hybrid iterated greedy,HIG)进行求解.基于问题特点提出最小工期差值(smallest due date difference value,SDV)规则及3种工厂分配规则,同时结合问题性质提出两种工件插入各工厂内部时问题目标值的下界估计方法.首先,通过实验确定使用分配规则1将工件向各工厂进行分配,同时结合下界估计方法的NEH作为改进启发式算法以生成较高质量初始解;其次,为了增加解的多样性,提出一种关键工厂的移除策略和适用于问题的模拟退火机制;然后,设计基于4种有效邻域操作的两阶段变邻域下降搜索策略,用于在HIG每代中对问题解空间的不同区域进行较深入和细致的搜索;最后,通过仿真实验和算法比较验证了采用HIG求解所提出问题的有效性.

一类分布式零等待流水线自适应EDA调度

随着经济的发展,在各行各业中分布式生产变得越来越普及,故将更多的注意力放在分布式生产模型之上。为求解带有序相关设置时间和到达时间的零等待分布式流水线调度问题(No-wait Distributed Flow Shop with Sequence Dependent Setup Times and Arrival Times,NDPFSP with SDSTs and RDs),提出了一种自适应的分布估计算法(Adaptive Estimation of Distribution Algorithm, AEDA),用于最小化最大完成时间。首先,提出了更加适合于带到达时间问题的最早完成工厂问题的带有到达时间的最早完成工厂(the Earliest Completion Factory with Arrival Time, ECFAT)规则,使得解的生成过程有适当的判断,更加快速地提高当前代生成解的质量。其次,针对不同的问题规模进行局部搜索的深度做出相应的调整,使得在不同的规模下算法都能有很好的局部搜索能力。

混合交叉熵算法求解模糊分布式装配流水线低碳调度问题

本文针对实际生产过程中普遍存在的不确定性,采用模糊数表示工件的加工时间与产品的装配时间,以同时最小化模糊最大完工时间和模糊总能耗为优化目标,建立模糊分布式装配流水线低碳调度问题(FDAPFLSP)的模型,进而提出一种混合交叉熵算法(HCEA)进行求解.首先,通过分析现有三角模糊数排序准则特点,并考虑生产调度问题的基本约束,设计一种实用的三角模糊数排序修正准则.其次,为增强算法性能,设计一种自适应变邻域局部搜索以实现对解空间不同区域的有效搜索.最后,仿真实验与算法对比验证HCEA可有效求解FDAPFLSP.

求解分布式混合流水线调度问题的改进双层嵌套式遗传算法

针对分布式混合流水线生产的生产调度问题,模拟实际排产中的排产到线和排产到时的排产策略,提出了基于改进双层嵌套式遗传算法的两层优化模型。外层依据流水线分配平衡和准时交货等基本原则总体上解决生产订单在流水线之间的分配问题,内层以最小生产时间为主要目的求解流水线的生产订单生产次序问题。考虑到双层嵌套式遗传算法的时间复杂性,基于模糊逻辑理论设计了一种模糊控制器来动态调整遗传算子,并采用主动检测停止方法,提高算法效率。使用某空调工厂的实际生产数据验证了算法的可行性、计算结果的准确性及排产策略的有效性,为高级计划与排程(Advanced Planning and Scheduling,APS)中大规模复杂供应链调度问题提供了可借鉴的方法。

分布式有限缓冲区流水车间混合EDA调度

在实际工业生产背景下,针对具有NP难特性的分布式有限缓冲区流水车间调度问题,提出了一种混合分布估计算法,用于最小化最大完成时间。首先,由于已有算法无法保证局部搜索后概率模型对优质个体分布统计的准确性,提出了反最小完成工厂映射规则;然后,引入基于Swap邻域和基于Insert邻域的局部搜索,进一步加强算法的局部搜索能力,从而对HEDA全局搜索得到的优质解区域进行细致搜索;最后,通过仿真实验和算法的比较验证HEDA的有效性。

一种分布式高性能的飞行器设计优化框架

在飞行器设计优化过程中,为了在不改变现有学科专业计算模块的前提下,充分发掘粗粒度并行度,为了适应特有的计算逻辑,提出一种基于多学科设计优化(MDO)理念及分布式流水线的并行计算框架,该框架既能方便地融合异构的计算资源,又能发掘计算中的并行度,提高计算效率.实验表明该框架在中小规模的分布式环境中具有良好的性能和扩展性,能缩短设计周期、降低成本.

混合离散人工蜂群算法求解含不相关并行机的分布式柔性流水线调度

研究每阶段含不相关并行机的分布式柔性流水线调度问题.考虑顺序相关准备时间和工件动态到达时间,以最小化总加权提前/拖期惩罚为目标建立整数规划模型,提出一种融合离散差分进化算法、变邻域下降算法和局域搜索的混合离散人工蜂群算法以获取近优解.该算法采用基于工厂-工件号的编码以及基于机器最早空闲时间的动态解码机制,通过随机规则和均衡分派策略生成初始工厂-工件序列群,在引领蜂阶段引入离散差分进化算法产生优质工厂-工件序列,在跟随蜂阶段利用变邻域下降算法在被选择序列附近继续搜索以得到邻域序列,在侦察蜂阶段设计基于关键/非关键工厂间插入的局域搜索提高算法搜索能力.通过仿真实验测试不同规模的算例,实验结果表明,所提出的混合离散人工蜂群算法表现出较好的求解性能.