基于自适应遗传算法的Job Shop调度问题研究

求解Job Shop调度问题是个NP完全问题,为了提高遗传算法的性能,提出一种新的自适应遗传算法(NSGA)以解决Job Shop调度问题.采用活动调度解码方法、过滤个体适应度相同的筛选策略、改进自适应交叉变异概率等改进策略来提高算法性能,最后通过仿真比较分析证明该算法的先进性.     

一种求解Job Shop 调度问题的改进遗传算法

传统遗传算法在求解Job Shop调度问题时存在收敛速度慢,易于早熟的缺点。在病毒遗传算法(VEGA)和灾变遗传算法的基础上提出了一种带有灾变因子的病毒遗传算法(IVEGA-C)。该算法在传统遗传算法的基本结构上加入了病毒感染操作和灾变操作,病毒感染操作实现了同代个体之间横向传递进化信息,灾变操作采用灭绝操作。正是这种改进加快了遗传算法的收敛速度,避免了早熟现象和陷入局部最优解。通过仿真实验验证了IVEGA-C算法在解决Job Shop调度问题中的性能优于传统GA算法和VEGA算法。最后给出了应用该算法的一个实例。     

基于遗传算法求解Job Shop调度的编码新方法

针对Job Shop调度问题,提出了一种新的遗传算法编码新方法。该方法根据问题的特点,采用一种按工序用不同编号进行的染色体编码方案,每一个编号包含工件工序号、对应的机器号、加工时间等所有信息,此编码与调度方案一一对应,并且该编码方案有多种交叉操作算子可用,不需要专门设计算子。算例计算结果表明,基于该编码方案的遗传算法是有效的,能适用解决Job Shop调度问题。通过比较,用该编码方案的遗传算法优化Job Shop调度操作简单并且收敛速度快。     

基于遗传算法的Job-Shop调度问题求解

针对 Job Shop调度问题，详细讨论了遗传算法以及染色体编码方法，建立了算法模型。通过仿真实验，验证了该算法的有效性。     

基于多层遗传算法的柔性Job Shop调度问题的研究

介绍了柔性Job Shop调度问题的模型,并针对三级子问题,分别设计了相应的遗传算法,给出了其流程.通过实例证明,该算法的设计是行之有效的.     

模糊Job Shop调度中的混合搜索策略的研究

采用并行遗传算法作为全局搜索算法，提出一种混合搜索策略，用于求解模糊Job Shop调度问题．根据模糊Job Shop调度问题解的特征，提出基于关键工序的邻域选择方法，并将基于这种邻域选择方法的禁忌搜索算法作为局部搜索算法，加强了遗传算法局部搜索能力．针对13个困难benchmark问题的实验结果表明，在较短的时间内，混合搜索策略的算法得到的平均满意度比并行遗传算法提高4.67%，比TSAB算法提高5.76%．采用的禁忌搜索算法改善了遗传算法的局部搜索能力，说明提出的混合搜索策略是有效的．     

求解模糊Job Shop调度的遗传算法与蚁群算法融合研究

提出一种算法融合策略,解决单一算法求解模糊Job Shop调度问题存在的不足,提高这类问题的求解质量.算法融合策略中,采用遗传算法和蚁群算法进行并行搜索;根据模糊Job Shop调度问题解的特征,提出基于关键工序的邻域选择方法,并将基于这种邻域选择方法的禁忌搜索算法作为局部搜索算法,加强了遗传算法和蚁群算法的局部搜索能力.采用算法融合策略的混合优化算法对以13个难的benchmarks问题经模糊化得到实例进行求解,在较短的时间内,得到的平均满意度较并行遗传算法(PGA)提高5.24%、较TSAB算法提高8.40% .采用算法融合策略构造的混合算法具有较强的搜索能力,说明提出的混合搜索策略是有效的.     

求解Job Shop调度问题的混合蚁群算法研究

为了解决单一算法求解Job Shop调度问题存在的不足，该文提出了一种混合算法，将蚁群算法用于全局搜索。针对蚁群算法易于陷入局部最优的情况，提出了一种基于关键工序的邻域搜索方法，将使用此邻域搜索方法的TS算法作为局部搜索策略。利用TS算法较强的局部搜索能力，提高了蚁群算法的优化能力，达到改善Job Shop调度问题解的质量。实验结果表明，混合算法在较短的时间内，找到了FT10、LA24、LA36等典型benchmarks问题的最优解，得到的makespan的平均值较并行遗传算法(PGA)和TSAB算法均有所提高。     

一种混合粒子群算法及其在Job Shop问题中的应用

粒子群算法是一种新颖的演化计算技术,具有思想简单、容易实现的优点,被广泛应用于连续空间的优化。结合遗传算法的思想提出一种新的进化方式并用于Job Shop离散空间优化,进一步结合粒子群算法的群体多样性和禁忌搜索算法的集中搜索性提出一种粒子群算法和禁忌搜索算法的混合策略。用Job Shop问题作为测试基准,仿真试验显示混合粒子群算法是可行和有效的。     

一种混合粒子群算法及其在Job Shop问题中的应用

粒子群算法是一种新颖的演化计算技术，具有思想简单、容易实现的优点，被广泛应用于连续空间的优化。结合遗传算法的思想提出一种新的进化方式并用于Job Shop离散空间优化，进一步结合粒子群算法的群体多样性和禁忌搜索算法的集中搜索性提出一种粒子群算法和禁忌搜索算法的混合策略。用Job Shop问题作为测试基准，仿真试验显示混合粒子群算法是可行和有效的。     

改进多种群杂交遗传算法在作业车间调度的研究

通过提出应用最广泛的混合型作业车间的调度问题以及遗传算法的基本原理,并结合生产车间调度问题的特点,对传统单种群遗传算法改进了改进。新遗传算法中加入辅助种群,保证种群的多样性,解决单个种群的遗传算法容易陷入局部收敛而出现早熟的情况。并应用实例对比分析,表明算法在车间调度系统的有效性和合理性。     

基于机床超低待机状态的流水车间能耗调度

为降低流水车间能源消耗,引入一种数控机床的超低待机状态,相比于将数控机床待机状态切换为停机状态的节能研究,可在不停机情况下降低数控机床加工间隔状态的功率,避免数控机床频繁启停.针对流水车间加工状态、待机状态及超低待机状态三元调度问题,提出基于工序平移的混合遗传算法,分别定义了不同的工序邻域移动操作,实现数控机床待机状态向超低待机状态和停机状态的转化,形成主动节能调度策略,提升遗传算法求解考虑超低待机状态的流水车间调度问题的优化能力.实验研究表明,启用超低待机状态能够降低流水车间10%以上的能耗,且基于工序平移的混合遗传算法求解考虑超低待机状态的流水车间调度问题性能优于遗传算法.     

多目标军用飞机维修作业调度优化研究

为提升维修作业与现代战机的适应程度,对军用飞机维修作业调度模型构建与调度优化算法设计进行探讨。在沿用柔性作业车间调度问题的形式化描述构建维修作业调度模型的基础上,选取遗传算法对执行步骤进行设计,引入耦合算子重新调整工序排序部分染色体以避免染色体违背耦合约束无法解码的情况发生,并采用维修作业调度案例与Brandimarte测试数据验证多目标调度优化算法的适用性与优化性。维修作业调度模型构建与调度优化算法的探讨促进维修管理的精细化,为调度相关领域的深入研究拓宽思路。     

基于改进的基因表达式编程算法在作业车间调度问题中的应用

文章提出一种新颖的方法一改进的基因表达式编程算法来求解作业车间调度问题。作业车间调度问题是许多实际生产调度问题的简化模型,基因表达式编程算法结合了遗传算法和遗传编程的优点,具有更强的解决问题能力,对基因表达式编程算法进行改进使其在作业车间调度问题的应用上更加有效;最后应用一个实例来验证提出方法的有效性。     

Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm

Most flexible job shop scheduling models assume that the machines are available all of the time. However, in most realistic situations, machines may be unavailable due to maintenances, pre-schedules and so on. In this paper, we study the flexible job shop scheduling problem with availability constraints. The availability constraints are non-fixed in that the completion time of the maintenance tasks is not fixed and has to be determined during the scheduling procedure. We then propose a hybrid genetic algorithm to solve the flexible job shop scheduling problem with non-fixed availability constraints (fJSP-nfa). The genetic algorithm uses an innovative representation method and applies genetic operations in phenotype space in order to enhance the inheritability. We also define two kinds of neighbourhood for the problem based on the concept of critical path. A local search procedure is then integrated under the framework of the genetic algorithm. Representative flexible job shop scheduling benchmark problems and fJSP-nfa problems are solved in order to test the effectiveness and efficiency of the suggested methodology. Received: June 2005 /Accepted: December 2005     

考虑工件移动时间的柔性作业车间调度问题研究

分析生产车间的实际生产状况,建立了考虑工件移动时间的柔性作业车间调度问题模型,该模型考虑了以往柔性作业车间调度问题模型所没有考虑的工件在加工机器间的移动时间,使柔性作业车间调度问题更贴近实际生产,让调度理论更具现实性。通过对已有的改进遗传算法的遗传操作进行重构,设计出有效求解考虑工件移动时间的柔性作业车间调度问题的改进遗传算法。最后对实际案例进行求解,得到调度甘特图和析取图,通过对甘特图和析取图的分析验证了所建考虑工件移动时间的柔性作业车间调度问题模型的可行性和有效性。     

遗传算法解柔性作业车间调度问题应用综述

柔性作业车间调度问题是典型的NP难问题,对实际生产应用具有指导作用。近年来,随着遗传算法的发展,利用遗传算法来解决柔性作业车间调度问题的思想和方法层出不穷。为了促进遗传算法求解柔性作业车间调度问题的进一步发展,阐述了柔性作业车间调度问题的研究理论,对已有改进方法进行了分类,通过对现存问题的分析,探讨了未来的发展方向。     

求解多目标流水车间调度Pareto最优解的遗传强化算法

针对多目标流水车间调度Pareto最优问题, 本文建立了以最大完工时间和最大拖延时间为优化目标的多目标流水车间调度问题模型, 并设计了一种基于Q-learning的遗传强化学习算法求解该问题的Pareto最优解. 该算法引入状态变量和动作变量, 通过Q-learning算法获得初始种群, 以提高初始解质量. 在算法进化过程中, 利用Q表指导变异操作, 扩大局部搜索范围. 采用Pareto快速非支配排序以及拥挤度计算提高解的质量以及多样性, 逐步获得Pareto最优解. 通过与遗传算法、NSGA-II算法和Q-learning算法进行对比实验, 验证了改进后的遗传强化算法在求解多目标流水车间调度问题Pareto最优解的有效性.     

最优子种群遗传算法求解柔性流水车间调度问题

为了验证最优子种群遗传算法在解决柔性流水车间调度问题时相比于传统遗传算法的优越性,分析了柔性流水车间调度问题的特点,并运用一种新的编码方法和新的遗传算法求解了该问题。考虑到最优个体保护策略法对复杂问题容易使种群收敛陷入局部最优解,为了提高精度、加快较优个体的产生并避免陷入局部最优解,首先提出了一种合理、全面的编码方法,并运用最优子种群遗传算法来求解柔性流水车间调度问题。最后运用实例验证了最优子种群遗传算法的有效性、优越性和编码方式的合理性。     

基于遗传算法的作业车间调度优化求解方法

针对 job shop调度问题 ,提出了一种遗传算法编码方法和解码方法。该方法根据问题的特点 ,采用一种按工序用不同编号进行的染色体编码方案 ,并采用矩阵解码方法。此编码与调度方案一一对应 ,并且该编码方案有多种交叉操作算子可用 ,无须专门设计算子。算例计算结果表明 ,该算法是有效的 ,适用于解决 job shop调度问题 ,通过比较 ,该遗传算法优化 job shop调度操作简单并且收敛速度快。