混合遗传NEH算法在流水车间调度中的应用

针对流水车间调度问题提出一种混合遗传NEH算法,以提高求解效率。NEH算法是一种高效的构造性算法具有很强的邻域搜索能力,而遗传算法则能有效地提供全局搜索。据此,新算法首先通过选择、交叉和变异操作,经过迭代获得一个较好解,然后在这个解所在的特定邻域内进行改进的NEH搜索,以获得更好解,经过NEH搜索后求得的最好解作为一个新个体加入下一代种群中,继续进行遗传操作。通过对流水车间调度的最小化最大完成时间问题的仿真实验结果表明,新算法有明显改进。

NEH免疫算法求解带准备时间的流水作业车间调度问题

本文针对带准备时间的流水作业车间调度问题,提出了一种改进的免疫算法(NEH-IA),并与没有改进过的免疫算法进行对比。利用benchmark算例对文中设计的免疫算法进行验证,结果表明NEH免疫算法在求解带准备时间的流水作业车间问题中是有效的。

基于种群迭代贪婪算法无等待流水车间调度

针对无等待流水车间调度问题,提出一种基于种群迭代的改进贪婪算法解决以最小化最大完工时间为目标的此类问题。首先,采用改进NEH(Nawaz–Enscore–Ham)算法提升初始种群的质量,提高种群的多样性,并得出初始解,确定最优个体;其次,采用种群迭代贪婪算法对确定的种群序列进行破坏与重新构建,将新序列插入指定位置,并对获得的候选方案进行本地搜索,获得新的解决方案,同时取代劣势解决方案;最后,通过仿真实例将种群迭代贪婪算法与其他智能优化算法在平均相对偏差率、最佳相对偏差率、算法收敛性上进行对比,结果表明种群迭代贪婪算法求解所提问题的高效性和稳定性。

基于链接学习的生物地理学算法求解置换流水车间调度问题

针对置换流水车间调度问题的特性,提出了一种基于链接学习的生物地理学算法(Biogeography-based optimization based on linkage learning,LLBBO)来对其求解。算法以生物地理学算法为架构,使用反向学习方法(Opposition-based learning,OBL)生成初始解,依据群体适应度值将群体分为优秀群体和劣势群体,使用信息熵的概念以及数理统计方法通过对这两个群体进行统计,分别建立概率矩阵模型以构建一种链接学习模型称为链接区块,使用链接区块依照算法迁移率对群体进行迁移操作实现群体更新。为进一步改善算法的搜寻性,提出一种NEH序列重组法对解序列执行局部搜索以进一步提高适应度。最后运用所提的LLBBO算法通过对基准例题的仿真测试和算法比较验证了所提算法的有效性。

基于改进区块进化算法求解置换流水车间问题

为了求解以最小化最大完工时间(Cmax)为目标的置换流水车间调度问题,提出利用NEH思想改进基于关联规则的区块进化算法。算法在初始化种群阶段使用经贪婪迭代思想改进的NEH算法代替完全随机法,使算法初始种群具有多样性和竞争优势,以加快收敛速度;在母体重组阶段提出使用兼具多样性和全局搜索能力的NEH交换方法,并结合具有较强领域搜索能力的相邻交换方法分别应用于不同的进化阶段,以提高重组母体的质量和多样性,加快收敛效率。通过对OR-Library中Taillard与Reeves的基准问题进行测试,并将结果与原算法及其他算法进行比较,验证了该算法的鲁棒性和有效性。

客户满意度视角下面向产品服务系统订单的调度问题研究

本文基于客户的服务时间窗要求和最晚可接受交付时间,考虑服务型制造企业在交付产品服务系统(PSS)时的客户满意度,研究了一类典型PSS订单的调度优化问题。问题中每个PSS订单需先由多条生产线分别制造产品的各个部件,然后由一支安装团队为客户提供安装服务,以最大化客户满意度总和为目标建立了PSS订单调度问题的优化模型,根据问题特点分别设计了改编的NEH构造型启发式算法和DDE-SA混合元启发式算法来求解模型,在仿真实验中检验了不同调度规则下改编NEH算法和DDE-SA算法的有效性。结果表明,基于几何平均松弛时间递增调度规则的NEH算法的性能优于其他调度规则,适用于时间有限且规模较小的PSS订单调度问题;DDESA算法具有较强的鲁棒性且明显优于单纯的离散差分进化算法和模拟退火算法,适用于时间充足且有较高求解质量要求的大规模PSS订单调度问题。

新型混合改进遗传算法求解零等待流水车间调度问题

具有零等待约束条件的流水车间调度问题是一类典型的NP难问题,针对该问题提出一种新型混合改进遗传算法进行优化求解。首先,采用改进NEH算法强化初始种群质量,提高种群的多样性。结合关联规则理论挖掘种群中的优势块,借助优势块进行人工染色体组合,以降低问题复杂度。交叉操作采用单段交叉、双段交叉和三段交叉3种交叉机制,改善算法全局搜索能力;变异过程引入水平集和种群分割的思想,将种群分割成两部分,并赋予不同的变异概率,提高算法局部搜索能力。为进一步提高遗传算法的求解性能,提出了基于NEH的邻域搜索机制,增加种群多样性,进一步提高种群质量。最后,通过实验结果和算法比较,验证了所提算法的求解性能。

混合共生生物搜索算法求解置换流水车间调度问题

为了求解置换流水车间调度问题,提出基于共生生物搜索(SOS)算法与局部搜索策略结合的混合共生生物搜索算法.采用最大排序值的优先规则,处理离散的搜索空间.在初始化阶段结合NEH启发式算法以提高初始种群的质量.在优化过程中引入交换变异来改善种群内的多样性,插入-倒转区增加算法跳出局部最优的能力;采用局部搜索策略提升算法的全局探索能力,有效避免了共生生物搜索算法易早熟、后期搜索效率低、易陷入局部最优等缺陷.通过3个最常用、最专业的标准测试集Carlier、Rec和Taillard对算法性能进行测试.与其他多种算法进行比较,验证了提出的混合SOS算法的优越性和稳定性.

改进的萤火虫算法求解阻塞流水线调度问题

为了提高阻塞流水线调度问题的求解性能,提出了一种改进的萤火虫算法来求解阻塞流水线调度问题.首先,提出一种离散机制把个体的实数编码形式转换成离散的作业序列,从而使算法能够应用于离散问题求解;其次,设计一种双重初始化方法,并将NEH启发式方法应用到初始化中来,使算法有一个较优的初始化环境,提高初始种群的解的质量;此外,重新设计了算法中个体的移动方式来增大搜索域;最后,以一定概率对种群中的个体进行局部搜索,加强算法的局部搜索性能.通过对Taillard数据集中部分实例进行求解,实验结果验证了新算法的有效性.

可重入混合流水车间调度的改进遗传算法

研究了可重入多阶段混合流水车间调度问题,其中至少有一个加工阶段有多台同构并行机。考虑工件在相邻两阶段间的运输时间和工件动态到达等实际生产特征,以最小化最大完工时间为目标建立数学模型。在传统遗传算法的基础上,结合NEH启发式算法产生工件初始加工顺序,令遗传参数随进化代数和个体适应函数值2个方面进行自适应调节,以避免算法陷入早熟,提出改进遗传算法用以求解该NP-hard问题。分别利用所提出的改进遗传算法与传统遗传算法、NEH启发式算法对不同规模的问题进行仿真测试,结果表明,改进遗传算法在较短的计算时间内能够获得较好的近优解。

基于和声搜索的阻塞流水车间调度问题的算法优化

针对以最大完工时间为目标的阻塞流水车间调度问题,提出了一种通过混合和声搜索改进遗传算法的优化求解算法。构建了阻塞流水车间调度原理图并描述了运算方法;详细论述了混合算法的实施流程和关键问题,并使用NEH方法和局部搜索对混合算法进行了改进。仿真结果表明,改进后的混合算法能显著提高优化阻塞流水车间调度问题的解。

蝙蝠算法在PFSP调度问题中的应用研究

针对新生的启发式智能算法蝙蝠算法求解离散型生产调度问题存在的局限性,利用对蝙蝠算法重新编码以及初始化的方式来求解离散型生产调度问题。通过对经典的生产调度基准数据进行测试,并同较成熟的标准粒子群算法进行比较。结果表明,蝙蝠算法在解决离散的生产调度问题时,具有较好的优化性能。验证了蝙蝠算法求解离散性问题的有效性以及可行性。

置换流水车间调度问题的两阶段分布估计算法

针对置换流水车间调度问题,以最小化总流水时间为目标,提出了一种新颖的两阶段分布估计算法。第一阶段先利用NEH(Nawaz-Enscore-Ham,NEH)启发式构造一个较优的初始个体,然后随机生成初始种群,为保留种群的多样性,提出一种择优机制来选择个体并建立概率模型,同时在当代种群中利用精英机制保留当代种群中的最优解,最后利用概率模型采样并生成下一代种群。第二阶段采用插入、互换操作算子对第一阶段得到的最优解进行邻域搜索,来提高分布估计算法的全局搜索能力,阻止其陷入局部最优解。通过对算例进行实验、对比和分析,证明该算法的可行性和有效性。

改进二元分布估计算法求解置换流水车间调度问题

针对置换流水车间调度这类组合最优化问题的求解,提出了一种改进二元分布估计算法(Improved binary estimation distribution algorithm,I-EDA)。算法以二元分布估计算法为架构,使用NEH(Nawaz-Enscore-Ham)启发式算法生成初始解,提高了初始解的质量;通过对优势解的统计采样构建位置矩阵模型和链接矩阵模型,依照两个矩阵模型的合并概率组合链接区块产生子代。提出了NEH插入式重组策略和基于位置概率的交换策略和两种全新局部搜索机制替代原二元分布估计算法的相邻交换法,以进一步筛选优势解。最后通过对Reeves标准测试集的仿真实验和算法比较验证了所提出算法的有效性。

混合流水车间调度问题的两阶段启发式算法

针对以最小化makespan为目标的混合流水车间调度问题,提出了一种两阶段启发式算法。在算法设计中,借鉴求解常规流水车间调度问题的经验,定义了一种相邻交换的邻域结构。算法的第一阶段利用基于排列排序的Nawaz-Enscore-Ham(NEH)算法求得一个较好的初始解,第二阶段通过邻域搜索来提高解的质量。基于benchmark算例的仿真实验结果表明该算法的有效性,与NEH相比,77个算例的平均偏差降低了2.004%,且其运行时间不超过0.031 s。

一种解决有限缓冲区流水车间调度问题的复合启发式算法

针对以最大完工时间为目标的有限缓冲区流水车间调度问题,提出了一种新的复合启发式算法.算法设计中首先使用PF-NEH算法进行解空间的搜索,并采用基于插入邻域和交换邻域的可变邻域搜索算法来增强局部搜索.仿真实验表明,该算法具有高效性和优越性.

改进蝙蝠算法在Job-shop调度问题上的应用

针对蝙蝠算法求解Job-shop调度问题的局限性,采用字符串编码、NEH初始化种群粒子和增加随机扰动的方法,对现有蝙蝠算法进行改进。通过对Job-shop调度问题基准算例的求解,并和模拟退火算法、标准遗传算法和粒子群算法进行比较,验证了该算法操作简单,收敛速度快,结果精度高,能有效求解Job-shop调度问题。

求解置换流水线调度问题的改进萤火虫优化算法

针对最小化最大完成时间的置换流水线调度问题,提出了一种改进的离散萤火虫优化算法。在传统萤火虫优化算法的基础上,采用基于升序排序的随机键编码方式对萤火虫种群进行离散化处理,使用NEH算法对萤火虫种群进行初始化处理,结合遗传算法的交叉变异思想改进位置更新策略,采用个体变异方式解决孤立个体问题,提高算法的寻优能力。最后通过典型算例对改进算法进行仿真测试,实验结果表明该算法求解置换流水线调度问题时具备很强的寻优能力和鲁棒性,明显优于传统萤火虫优化算法和遗传算法,是解决置换流水线调度问题的一种有效算法。

改进细菌觅食算法解决零空闲流水线调度问题

针对零空闲流水线调度问题,建立以最大完成时间为目标的数学模型,并提出了解决问题的改进细菌觅食优化算法。在标准细菌觅食优化算法的基础上,引入了交叉优化算子、混合复制策略以及一种基于健康度和适应度共同控制的自适应迁徙概率,以加速算法的收敛过程,并有效抑制精英个体的逃逸,防止解发生退化。采用路径编码方式,通过MATLAB算例试验,表明了改进细菌觅食优化算法在求解零空闲流水线调度问题上的可行性和有效性;同时,运用两种方式产生初始解:随机方式和NEH方法,进一步验证算法的鲁棒性。

变邻域改进遗传算法求解混合流水车间调度问题

针对混合流水车间调度问题的NP难特性,提出一种改进的混合变邻域搜索的遗传算法。建立了数学模型,提出了算法的总体流程,设计了基于操作的编码和解码方法,并采用NEH启发式算法产生初始种群。随机采用基于位置的交叉和线性次序交叉,选用反转逆序的变异算子,交叉变异后合并子代与父代,保留较优个体,对当前最优个体执行变邻域搜索,以增强遗传算法的局部搜索能力。通过初始对比实验,证明了NEH启发式算法能够产生质量更好的初始解,随机采取两种交叉算子能够提高算法的搜索效率,标准算例实验结果表明所提算法能够有效求解混合流水车间调度问题。