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

通过改进传统的遗传算法求解Job -Shop调度问题。为基于工序的编码提出了一种新的POX交叉算子 ,并与其他交叉算子进行了比较以显示其高效性。为了保留父代的优良特征和减少遗传算子的破坏性 ,设计了一种子代交替模式的交叉方式。将提出的改进遗传算法应用于muthandthompson’s基准问题的实验运行 ,显示该算法的有效性。

考虑工序相关性的动态Job shop调度问题启发式算法

提出一类考虑工序相关性的、工件批量到达的动态Job shop调度问题,在对工序相关性进行了定义和数学描述的基础上,进一步建立了动态Job shop调度问题的优化模型。设计了一种组合式调度规则RAN(FCFS,ODD),并提出了基于规则的启发式算法以及该类动态Job shop调度问题的算例生成方法。为验证算法和比较评估调度规则的性能,对算例采用文献提出的7种调度规则和RAN(FCFS,ODD)进行了仿真调度,对调度结果的分析表明了算法的有效性和RAN(FCFS,ODD)调度规则求解所提出的动态Job Shop调度问题的优越性能。

可动态生成具有优先级工序集的动态Job-Shop调度算法

为了在满足约束条件的前提下使不同时刻加入到作业集合中的全部作业所用的加工总时间尽可能地少,提出算法:根据动态的作业集合构造虚拟加工树,虚拟加工树上的叶结点代表最先加工的工序,虚拟根节点代表最后一道工序,边代表偏序关系;以层优先为虚拟加工树上的工序设置优先级,工序的优先级可作为调度过程中考虑的一个因素;除了在工序需要动态调整的情况下,在调度过程中始终遵循着机器忙原则.在调度过程中,首先根据虚拟加工树动态地生成备选工序集合,然后根据工序的优先级并且结合其它的调度策略从备选集合中调度工序,直到备选集合为空,即所有作业加工完毕.这里提到的调度策略包括短用时策略、长路径策略和动态调整策略.通过实例验证,该算法对于动态Job-Shop问题可以获得比较好的解.

多目标柔性Job Shop调度问题的技术现状和发展趋势

首先概述了多目标柔性Job Shop调度问题的基本概念,包括问题定义、常用假设条件、性能指标和问题的分类,讨论了其复杂性;其次,分别从建模、优化方法和原型系统研究方面综述了其发展过程和研究现状,对一类更加通用的多目标柔性Job Shop问题进行了简单的文献综述;最后指出了现有研究存在的问题与不足,并对未来的发展趋势进行了探讨。

基于ACPM和BFSM的动态Job-Shop调度算法

通过对不同时刻开始加工的产品加工树的分解 ,可将产品加工工序分为具有惟一紧前、紧后的相关工序和独立工序 在对这两类工序研究分批综合应用拟关键路径法 (ACPM )和最佳适应调度方法 (BFSM)调度时 ,考虑了关键设备的工序紧凑性 通过分析与实例验证 ,所提出的调度方法对解决动态的Job

免疫模拟退火算法及其在柔性动态Job Shop中的应用

针对车间作业调度问题,在深入分析免疫算法和模拟退火算法的基础上,将两种算法巧妙结合,提出免疫模拟退火算法。该算法引入了免疫记忆、抽取疫苗和接种疫苗等免疫机制,有助于优良个体和基因的保留和利用,提高了算法收敛性,而且其基于概率突跳特性的爬山性能可以避免早熟现象。针对西安航空发动机(集团)有限公司的柔性动态Job Shop,分别用模拟退火算法、免疫算法和免疫模拟退火算法进行了仿真和比较,研究结果表明,免疫模拟退火算法比单一算法性能更优,是求解柔性动态Job Shop问题的有效实用算法。

基于混合粒子群算法的多目标柔性Job-Shop调度方法

针对经典Job-Shop调度问题的局限性,提出了以时间、成本、质量三者综合为优化目标,具有柔性Job-Shop车间调度的优化模型。给出了优化目标的计算方法,并设计了混合粒子群算法,给出了使用此算法求解模型的具体实现过程。模型采用工序能力指数对质量目标进行量化,并采用综合评判线性加权模型解决柔性Job-Shop算法的权重选择问题,使决策者能够根据实际情况选择优化目标的偏好解。通过一个车间调度问题的实例验证了此调度模型和算法的有效性。

基于约束满足的Job-Shop调度算法研究

文章在分析Job-Shop调度问题的基础上,引入约束满足方法来研究Job-Shop的调度问题。首先建立基于CSP的JSS模型,然后针对该模型设计了调度算法框架,仿真结果证明该调度算法是可行和有效的。

用遗传算法解决生产线调度Job-Shop问题

在分析国内外各种解决生产线作业调度问题方法的基础上，引出生产线调度Ｊｏｂ－Ｓｈｏｐ问题的数学模型。针对该模型，用遗传算法对其进行优化调度。首先针对优化目标进行染色体编码，定义群体规模，然后设计适应度函数，最后通过选择、交叉、变异等操作，得到目标的全局较优解。本文针对某一工程实例，给出了此调度算法的仿真结果。

基于多Agent的Job Shop调度方法研究

针对JobShop调度问题 ,提出基于多Agent的车间调度模型 ,实现调度甘特图的自动生成。在此基础上 ,设计了多Agent分组协作机制 ;实现了多目标优化调度 ,提高了调度优化算法的实用性和优化效果 ;分析了车间调度中各类干扰因素的特点 ,实现动态调度 ,提高了系统的适应性和健壮性。最后给出了实例验证。

一种求解Job Shop问题的合作型协同进化算法

针对Job Shop调度问题,提出了一种改进的合作型协同进化算法。根据机器数量"自然"分割种群,每个种群对应一台机器,个体以机器前工件的优先列表为编码;将静态繁殖理论引入遗传算子,并通过三种共生伙伴选择方式,利用改进的基于优先列表的G&T算法解码来评价个体;最后采用一种更新技术和动态群体更新策略来加快算法收敛。通过对Job Shop基准问题的优化,该算法获得了比传统的遗传算法更好的结果。

基于遗传算法的Job Shop调度研究进展

Job Shop是典型的调度问题 ,遗传算法一直是计算智能的主要研究对象 ,因此基于遗传算法的Job Shop研究在学术界和工程界受到极大的关注。对近年来这方面的研究情况进行了较全面的综述 ,其中涉及编码、算法改进和比较、特征分析、混合算法、拓宽性、实际应用和调度器开发等 。

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

调度问题是许多计算机应用领域的重要问题，Ｊｏｂ－Ｓｈｏｐ调度是其中的一类典型的困难问题，它通常包含多个可并行实现的目标以及实现这些目标的多种方法与资源．本文以一类实用的Ｊｏｂ－Ｓｈｏｐ问题模型为基础，给出了用遗传算法求解调度问题应采用的染色体表示方法，并针对问题的特点，给出了面向资源空间与面向规划空间的遗传操作的设计思想与方法．实验结果表明，基于遗传算法的Ｊｏｂ－Ｓｈｏｐ调度问题求解方法具有较好的性能，同时也表明，对于求解过程中可能出现的提前收敛问题可通过改变遗传操作概率及调节适应度等方法予以解决．

基于遗传算法求解Job Shop调度优化的新方法

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

扰动环境下Job Shop瓶颈识别方法研究

针对Job Shop作业管理层面的瓶颈识别,改变传统将瓶颈识别独立于调度优化方案的做法,先进行瓶颈充分利用再进行瓶颈系统辨识,不仅保证了瓶颈的有效识别,而且保证了瓶颈的充分利用。笔者给出了工序级瓶颈识别指标,提出了瓶颈分级识别策略,采用遗传算法和优化仿真结合的方法实现瓶颈的充分利用,其中,利用遗传算法优化零件的投料顺序,采用Plant-Simulation建立模拟仿真模型,设置设备故障率、平均故障修复时间、缓冲容量等实际扰动,经过大量的生产过程仿真,基于瓶颈出现率进行瓶颈识别,并输出优化调度方案。算例验证表明了瓶颈识别方法的有效性。

解决JOB SHOP问题的粒子群优化算法

设计了2种解决Job shop问题的粒子群算法,即实数编码的粒子群调度算法和工序编码的粒子群调度算法。工序编码的粒子群调度算法更符合Job shop问题的特点,优化性能相对高。但粒子群调度算法容易陷入局部最优。为了提高优化性能,将粒子群算法和模拟退火算法结合,得到了粒子群-模拟退火混合调度算法。仿真结果表明了算法的有效性。

基于遗传算法的Job-shop调度问题研究

Job -shop调度问题是一个强NP -难问题 .为此提出了一种简单、易操作的遗传算法对该问题进行求解 .采用一种插入式贪婪解码算法保证生成的调度是活动调度 (activeschedule) .通过几个著名的MuthandThomp son测试例子及与目前较好的遗传算法的比较实验 ,以验证这一算法的有效性 .

一类解决Job Shop问题的改进遗传算法

将遗传算法与模拟退火算法相结合,提出一种有效的混合调度算法。采用4-2选择代替传统的转轮选择方法,既保留了优秀个体又维持了群体的多样性;采用具有较强突跳能力的模拟退火算法代替传统遗传算法的变异算子,增强了全局探索能力,减小了陷入局部极小值的机会;采用基于关键路径的状态产生函数,缩小了搜索邻域,提高了算法的效率。仿真结果表明,该算法具有较高的求解质量和效率。

求解Job Shop调度问题的改进禁忌搜索算法

提出一种改进的禁忌搜索算法,解决传统禁忌搜索算法优化效果对运行次数和初始解依赖的不足,提高这类问题的求解质量。根据Job Shop调度问题解的特征,提出基于关键工序的邻域选择方法,采用此邻域选择方法构造禁忌搜索算法,当无邻域时,重新产生初始解进行禁忌搜索,将传统的禁忌搜索算法从单起始点搜索改进成多起始点搜索。采用改进的禁忌搜索算法对13个难的benchmarks问题进行10次求解,得到的平均值8个优于TSAB算法,得到的最优解6个优于TSAB算法、4个与TSAB算法相同。采用基于关键工序的邻域结构构造的改进TS算法具有较强的搜索能力。

免疫进化算法求解静态Job shop调度

基于克隆选择原理与细胞超变异思想构造了一种免疫进化算法CHIEA(Clonal selection and hyper mutations based immune evolution algorithm)求解静态JSP问题(Job shop scheduling problem)。随机混排变异算子的构造和抗体连续累积变异的实施丰富了细胞超变异的内容,基于优先列表编码方式的采用和免疫进化算子的构造提高了搜索效率,加速了算法收敛并提高了解的质量。通过与COELLO的AIS(Artificial immune system)算法的全面比较得出,CHIEA求解不同类型中小规模的静态JSP问题时具有更好的优化性能。