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

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

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

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

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

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

混合算法的邻域结构变更研究及在排样问题上的应用

本文研究了全局搜索算法和局部搜索算法的混合机制,设计了基于邻域搜索和遗传算法的混合搜索算法。该算法结合了遗传算法的全局搜索特性和邻域局部贪婪搜索特性;在分析排样问题碰靠过程特征的基础上,构建了排样问题邻域假设,当邻域假设满足时,遗传算法+邻域搜索能很好发挥作用;当不能判断邻域结构是否满足邻域假设时,提出了建立遗传算法+匹配变邻域的搜索算法,该算法兼顾了组合优化中邻域搜索的局部搜索无效的情况,实现了匹配的变邻域混合算法在排样优化问题中的应用。实例结果标明,排样图形不一样,其求解难度不一样,该算法均搜索到了更好的排样模式,验证了算法的有效性。     

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

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

ACOCS:一种云环境下资源调度混合算法

蚁群算法在优化组合问题中有着重要的意义,传统的蚁群调度算法搜索速度慢、容易陷入局部最优。针对这种情况,结合布谷鸟搜索算法,提出一种基于蚁群算法与布谷鸟搜索算法的混合算法(ACOCS),用于云环境下的资源调度。该方法有效保留了蚁群算法求解精度高和鲁棒性的特性,并融入了布谷鸟搜索具有快速全局搜索能力的优势。仿真实验结果表明,提出的ACOCS调度算法有效减少了调度所需的响应时间,也在一定程度上提高了系统资源利用率。     

基于邻域搜索的改进最大最小蚁群算法

针对蚁群算法求解旅行商问题时易陷入局部最优的问题,提出一个改进的混合最大最小蚁群算法,并应用于求解旅行商问题.上述算法设计了一种新的信息素更新模型,单个蚂蚁每走一步就进行信息素局部更新,在所有的蚂蚁搜索一周后,最优路径蚂蚁进行全局信息素更新.提出一种新的邻域搜索模型,将邻域大小设置为原来的一半,提高了计算的效率.在每个蚂蚁的一个周期循环后,使用邻域搜索算法优化最优解的路径长度.仿真结果表明,改进算法具有较高的求解精度和收敛速度.     

一种基于遗传—蚁群算法的网格任务调度策略*

针对遗传调度算法局部求解能力不足、容易早熟和退化的问题,以及蚁群调度算法初始搜索阶段效率低下的缺陷,充分应用遗传算法全局搜索能力较好和蚁群算法求解精度较高的优势,提出了一种基于遗传-蚁群算法的网格任务调度策略.该方法集成了遗传算法和蚁群算法的双重优点.仿真测试结果表明,提出的网格任务调度方法总体上优于遗传算法和蚁群算法...     

蚁群算法和遗传算法融合及其在有时间窗的车辆路径问题中的应用

针对基本蚁群算法搜索时间长、易陷入局部最优的缺点,提出了一种蚁群算法和遗传算法相融合的混合算法.该算法利用遗传算法全局快速收敛的优点,将遗传算法融入到蚁群算法的每一次迭代中,以加快算法的收敛速度,提高求解效率.实例运行结果验证了算法的有效性.     

遗传算法在蚁群算法中的融合研究

提出一种新的求连续空间最优值的蚁群算法.结合遗传算法和蚁群算法的各自优点以及两种算法融合的基础,提出遗传算法融入到蚁群算法的两种新策略:第一种策略是先利用遗传算法具有比较强的全局搜索能力,在大范围内寻找一组解,然后以此为基础,用蚁群算法快速寻找最优解X*best;另一种策略是利用遗传算法的交叉操作产生蚁群算法的新的旅行路径,以此提高蚁群算法的全局搜索能力.用上述两种策略构造了两个基于遗传算法的混合蚁群算法.文中用测试函数Rosenbrock和Shubert从收敛速度、命中率、计算精度等方面验证了混合蚁群算法的正确性.     

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

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

求解工件车间调度问题的一种新的邻域搜索算法

该文提出了一种新的求解工件车间调度(job shop scheduling)问题的邻域搜索算法．问题的目标是：在满足约束条件的前提下使得调度的makespan尽可能地小．定义了一种新的优先分配规则以生成初始解;定义了一种新的邻域结构;将邻域搜索跟单机调度结合在一起;提出了跳坑策略以跳出局部最优解并且将搜索引向有希望的方向．计算了当前国际文献中的一组共58个benchmark问题实例,算法的优度高于当前国外学者提出的两种著名的先进算法．其中对18个10工件10机器的实例,包括最著名的难解实例ft10,在可接受的时间内都找到了最优解．这些实例是当前文献中报导的所有规模为10工件10机器的实例．     

改进多目标进化算法求解柔性作业车间调度问题

针对加工时间为模糊数的柔性作业车间调度问题,考虑最小化模糊最大完工时间、模糊机器总负荷、模糊关键机器负荷为优化目标,提出一种有效求解该类优化问题的多目标进化算法。算法采用一种混合不同机器分配和工序排序策略的方法产生初始种群,并采用插入空隙法对染色体进行解码。定义一种新的基于可能度的个体支配关系和一种基于决策空间的拥挤算子,并将所提支配关系和拥挤算子运用于快速非支配排序。接着,提出一种基于移动模糊关键工序的局部搜索策略对种群中的优势个体进行局部搜索。通过试验研究关键参数对算法性能的影响并将所提算法与3种不同的优化算法作对比。结果表明,所提算法能够比其它算法更有效解决多目标模糊柔性作业车间调度优化问题。     

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     

A hybrid Jaya algorithm for solving flexible job shop scheduling problem considering multiple critical paths

As an extension of the classical job shop scheduling problem, flexible job shop scheduling problem (FJSP) is considered as a challenge in manufacturing systems for its complexity and flexibility. Meta-heuristic algorithms are shown effective in solving FJSP. However, the multiple critical paths issue, which has not been formally discussed in the existing literature, is discovered to be a primary obstacle for further optimization by meta-heuristics. In this paper, a hybrid Jaya algorithm integrated with Tabu search is proposed to solve FJSP for makespan minimization. Two Jaya operators are designed to improve solutions under a two-vector encoding scheme. During the local search phase, three approaches are proposed to deal with multiple critical paths and have been evaluated by experimental study and qualitative analyses. An incremental parameter setting strategy and a makespan estimation method are employed to speed up the searching process. The proposed algorithm is compared with several state-of-the-art algorithms on three well-known FJSP benchmark sets. Extensive experimental results suggest its superiority in both optimality and stability. Additionally, a real world scheduling problem, including six instances with different scales, is applied to further prove its ability in handling large-scale scheduling problems.     

一种改进的求解柔性作业车间调度问题的灰狼算法

柔性作业车间调度问题是智能制造领域的一类典型调度问题,它是制造流程规划和管理中最关键的环节之一,有效的求解方法对提高生产效率具有重要的现实意义。本文基于经典灰狼算法进行改进,以优化最大完工时间为目标,提出一种改进的灰狼算法来求解柔性作业车间调度问题。算法首先采用基于权值的编码形式,实现对经典狼群算法中连续性编码的离散化;其次在迭代优化过程中加入随机游走策略,以增强局部搜索能力;然后在种群更新过程中加入尾部淘汰策略,在避免局部优化的同时增加种群多样性,合理扩大算法的广度搜索范围。在标准算例上的仿真实验结果表明,改进的灰狼算法在求解FJSP时比经典灰狼算法在寻优能力方面具有明显的优势,相比其它智能优化算法,本文所提算法在每种算例上均具有更好的优化性能。     

基于基因表达式的克隆选择算法求解JSP问题

针对作业车间调度问题的特征,提出一种基于基因表达式的克隆选择算法。在这个方法中,采用基因表达式编程算法中的编码方式来表示调度方案,同时为了提出的方法具有更强的全局搜索能力,运用克隆选择算法作为搜索引擎。最后,验证提出的方法的有效性,对7组Benchmark实例进行测试。实验结果表明,基于基因表达式的克隆选择算法在求解作业车间调度问题中是非常有效的。     

相关工件车间调度问题的拓扑算法

针对加工装配型离散制造企业实际生产的特点,提出了一类用于表示工序之间偏序关系的相关工件车间调度问题。为了利用已有的求解表示工序之间的线序关系的传统车间调度算法求解相关工件车间调度问题,设计了一种拓扑算法,该算法能够将工序之间的偏序关系转化为线序关系,将相关工件车间调度问题转化为传统的车间调度问题,通过实证研究,结果表明了拓扑算法是可行和高效的。