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

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

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

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

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

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

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

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

求解作业车间调度问题的混合帝国主义竞争算法

针对最小化最大完工时间的作业车间调度问题（JSP）,提出一种结合帝国主义竞争算法（ICA）和禁忌搜索（TS）算法的混合算法。混合算法以帝国主义竞争算法为基础,在同化操作中融入遗传算法中的杂交算子和变异算子,使算法全局搜索能力更强。为了克服帝国主义竞争算法局部搜索能力弱的缺点,引入禁忌搜索算法进一步优化同化操作后的后代。禁忌搜索算法采用混合邻域结构和新型选择策略,使得算法能够更有效地搜索邻域解。混合算法兼具全局搜索能力和局部搜索能力,通过对13个经典的Benchmark调度问题进行仿真测试,并与近年4种新型混合算法进行对比分析,实验结果表明了所提算法求解Job Shop调度问题的有效性和稳定性。     

冷轧合同批量调度的模糊Job Shop模型及算法

针对冷轧薄板生产线机组设备多、产品种类多的特点,提出一种合同批量调度方法．该方法将生产合同按产品种类和交货期组批处理,建立了具有模糊处理时间的Ｊｏｂｓｈｏｐ调度模型来描述整个生产物流情况,并定义了分情况的合同批量加工时间推算规则．针对调度模型的求解,给出一种多子种群并行粒子群算法．利用宝钢冷轧薄板厂的实际生产数据进行了试运行,结果表明,该方法可大幅度提高合同交货期满意度,并能有效减少合同批量调度的工作时间。     

求解零空闲流水线调度问题的改进蚁群算法*

在研究蚁群算法的基础上,解决零空闲流水线调度问题的最大完工时间。改进了蚁群算法中信息素密度的初始化方法和更新规则,结合快速邻域搜索算法,解决算法易陷入局部收敛的缺点,提出了该算法解决零空闲调度问题的最佳求解策略。仿真实验表明,该算法具有高效性和优越性。     

基于自适应蚁群算法的作业车间模糊调度研究

在研究不确定生产调度问题的基础上,针对具有模糊加工时间和模糊交货期的调度问题给出了作业车间模糊调度模型,用三角模糊数表示模糊加工时间,梯形模糊数表示模糊交货期,以交货期平均满意度最大作为调度目标.针对模糊调度问题对基本蚁群算法作了改进,并给出了新的状态转移规则,同时采用自适应信息素更新策略使算法能快速跳出局部收敛,进行仿真结果验证了自适应蚁群算法求解作业车间模糊调度的有效性.     

基于正交实验的蚁群算法在车间调度问题中的应用

提出用正交实验的方法来设置蚁群算法在求解车间调度问题的参数。蚁群算法在求解车间调度问题时的性能大部分依赖于参数的设置,各参数的值不同,则蚁群算法的收敛速度和得到的解也不同,使用正交实验的方法来测试各个参数对蚁群算法性能的影响,通过对实验结果的分析可得出参数的最佳组合方案。用经典的JSP的样例对这种组合方案进行了测试,实验结果表明用正交实验法得到的蚁群算法的参数设置方案可以加快算法的收敛速度,使算法能够得到问题的最优解或近似最优解。     

蚁群算法在求解TSP问题上与遗传算法的对比研究

蚁群算法(ACA)与遗传算法(GA)都属于仿生型优化算法,是解决组合优化问题的强有力工具,并都分别成功应用于旅行商问题(TSP)问题中。本文通过实验验证了两种算法在解决TSP问题上各自的优缺点,并给出了未来的进一步研究方向。     

用带蚁群搜索的多种群遗传算法求解作业车间调度问题

结合遗传算法和蚁群算法的优点，提出一种带蚁群搜索的多种群遗传算法．多个种群各自遗传进化，用蚁群搜索得到的解替代各种群中的较劣个体，增加种群的多样性，提高种群的质量；根据各种群最优个体设定初始信息素，大大缩短信息素的累积过程，加快蚁群搜索的速度．利用算法对典型作业车间调度问题进行求解,仿真计算结果表明,该算法是有效的.     

基于蚁群算法的泊位调度问题

在集装箱港口的运作中,泊位调试系统是制约集装箱港口降低船舶在港时间和运营成本的主要瓶颈之一。泊位调度的目标就是确定集装箱港口船舶的停靠泊位和停泊时间。将码头看成离散泊位的集合,以船舶的在港时间最短为目标,应用蚁群算法对该问题进行优经研究,在满足各种约束条件的基础上,充分的利用好码头资源。利用蚁群算法的正反馈和并行搜索特点提高解的质量2和稳定性,通过对某集装箱码头的案例分析,说明该算法的有效性和实用性。     

基于蚁群算法的车间作业调度问题研究

对基于蚁群算法的车间作业调度问题求解进行了研究,在分析了传统蚁群算法求解车间作业调度问题容易出现早熟、收敛于局部最优解以及搜索速度慢的缺陷,提出了一种改进的混合蚁群算法。该方法在信息素更新规则上利用信息素局部更新策略和全局更新策略来进行信息素的更新,并将领域搜索与蚁群算法相结合,从而求得问题的可行解。最后,基于benchmarks问题进行了实验仿真,实验结果证明该改进混合算法的有效性及可行性。     

Local Search Genetic Algorithms for the Job Shop Scheduling Problem

In previous work, we developed three deadlock removal strategies for the job shop scheduling problem (JSSP) and proposed a hybridized genetic algorithm for it. While the genetic algorithm (GA) gave promising results, its performance depended greatly on the choice of deadlock removal strategies employed. This paper introduces a genetic algorithm based scheduling scheme that is deadlock free. This is achieved through the choice of chromosome representation and genetic operators. We propose an efficient solution representation for the JSSP in which the job task ordering constraints are easily encoded. Furthermore, a problem specific crossover operator that ensures solutions generated through genetic evolution are all feasible is also proposed. Hence, both checking of the constraints and repair mechanism can be avoided, thus resulting in increased efficiency. A mutation-like operator geared towards local search is also proposed which further improves the solution quality. Lastly, a hybrid strategy using the genetic algorithm reinforced with a tabu search is developed. An empirical study is carried out to test the proposed strategies.     

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

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

基于模糊遗传算法的模糊调度研究

就模糊调度问题的研究现状、研究方法进行了评述 ,探讨了加工时间与交货期的模糊化操作以及基于模糊遗传算法的模糊调度系统 ,归纳了模糊遗传算法中模糊数的操作和遗传算法的编码 ,并指出了存在的不足 .指出模糊生产环境下模糊加工时间与模糊交货期综合问题的研究是当今全球性市场竞争机制所带来的必然趋势.     

蚁群算法及其改进形式综述

蚁群算法是一种具有许多优良特性的模拟进化算法,已经成功地解决了许多复杂的组合优化问题。但是蚁群算法并不完善。本文介绍蚁群算法的模型及其存在的问题,并综述蚁群算法的多种改进形式,最后对蚁群算法将来的研究方向作出预测。