论文研究-一种基于遗传算法的作业车间调度问题的解决方案 .pdf


-
一种基于遗传算法的作业车间调度问题的解决方案,陈浩哲,王晨升,作业车间调度问题(job shop scheduling problem,JSP)是复杂调度问题类型之一,有十分重要的研究意义和工程价值。本文以标准遗传算法为基础�
山国武技论文在线 针对这问题,本文提岀使用神经网络对了代适应度数据进行记录。神经网络在 记录大量数据方面拥有着巨大的优势。以单点父叉为例,我们只需要将两父代的基因输入神 经网络,再将某一交叉点所生成子代的适应度作为神经网络对应位置的输出,用此输入和输 出作为训练神经网终的数据,神经网终就能记录两父代,某一交叉点下子代的适应度。如此 遗传算法的每次迭代中都有种群数量个训练数据,而神经网络就能对这些子代适应度数据进 行记录。使用神经网络后,我们不需要用人规模的表格冇储和査找数据,只需要对网络的进 行训练,再将数据带入网络计算结果即可。 开妗 广生初始种群 解码 计算适应度 川练神经网络 是否到 达终 Y公 条件 N 近择 变异 红选取两个父 神经网络计算 子代适应度 交叉 代步数k自增1 图改走算法的流程 改进算法的流程如图一所示,改进算法的流程与传统遗传算法有点不同,其一,计算 适应度后添加了训练神经网络的步骤;其,交叉之前需要使用训练好的网络计算子代适应 度;最后,为了保证上次循环巾交叉操作和下次循环中训练网终之间种群不会发生改变,原 本放在交叉操作之后的变异操作提前到了选择操作之后。 本算法除神经网络步骤外,其他步骤与传统的遗传算法基本一致,所以,本章着重讲解 神经网络部分。要使用袒经网络首先需要决定输入和输出的形式。以的作业车间调度问 题为例,使用基于工序的编码后,一个作业车间的调度方案需要个数字表小,即一个父 代拥有个基因。而进行交叉操作需要两个父代,因此,网络需要使用两个父代作为输入 山国武技论文在线 计算了代的适应度,那么,神经网络的输入单元个数应该是 个。交叉方式选择单点 交叉,那么两个父代每个基因都可能被选为交叉点,因此对于任意两父代来说,总共有 种交叉方式,所以,神经网络的输出单元数应该是个。现在,神经网络的输入和输出 都已确定,输入时两个父代的基因,共个数字;输出对于两父代,所有交叉情况下的子 代适应度,共个数字 为了使网络记录的子代适应度与交叉点对应,需要使用二维数组记录适应度。改进算法 需要将子代适应度放入和交叉点对应的位置,原本传统遗传算法计算适应度后会将适应度放 入一个一维数组,而现在,我们需要将适应度放入一个二维数组,如表所示。横向来看 二维数组中,每行仍然只有一个适应度,且每行的适应度与原本一维数组中每行的适应度相 对应。不同的是每行适应度都多了个列标号,这是为了将适应度储存在与交叉点对应的位 置。例如,如果两父代在第个交叉点交叉后得到了适应度,就将这个适应度放入记录 适应度的二维数组中的第列。二维数组中这一行的其他数字可置为。 表存放适应度的二维数组 使用二维数组记录的适应度不能直接作为神经网终训练集的输出,因为它除上一轮交叉 位置有适应度外,其他位置均为,如果使用其作为网络训练集的输岀,就会将原本神将网 终训练的参数覆盖,导致网终不收敛,神将网络也就不能记录子代适应度了。为了使神经网 终能够记录子代适应度,我们需要将记录适应度的二维数组做一定的变换。首先我们将神经 网络训练集的输入送入神经网络,得到一行数字。这列数组是神经网络根据之前训练的结果 输出的子代适应度,命名为数组一。然后提取出二维数组中与输入对应行的适应度,命名为 数组二。将数组二中唯不为的适应度复制到数组中的对应位置,这样就完成了神经网 络训练集的输出数组二。 为确保算法对调度方法的充分探索,进行父叉操作时,算法将以一定的概率选择子代适 应度最大的位置作为交叉点,其余情况下随机选择交叉点。 仿真结果 以 问题的某次调度方案为例,该调度方案编码结果为 ,该方案的调度结果如图所示,该调度方案 的最大完成时间如横坐标所示为,且已知的最大完成时间为 现将交叉概率设置为,变异概率设置为 把算法的结果代后仍然没有改进 作为收敛条件,每步打印一次结果,将改进算法和标准遗传算法各次的运行结果进 行对比: 山国武技论文在线 3[6264 □2[546,3 M4 _1[2 M3 Mz461图 山[43匚25 调度结果 表两种算法各结果次数对比 次数个 改进后的遗传算法 标准遗传算法 最大完成时间 如表所示,改进后的遗传算法的次运行结果中,有次结果收敛于,有次 收敛于,有次收敛于;而标准遗传算法的次运行结果巾,有次结果收敛于, 有次收敛于,有次收敛于次收敛于。 图与图表明改进算法和标准遗传算法各结果次数与结果总数之闫的比例关系,由图 可知改进算法的绝大多数结果取得」问趣的最优解,且取得最优解的比例远髙于标准遗传算 法。而标准遗传算法大多数结果没有取得最优解,说明标准遗传算法存在严重的早熟问题。 在算法求解质量方面,改进算法明显优」标准遗传算法。 8 04 02 0 最大完成时间 图改达算法各结果次数与结果总数之间的比例关系 山国武技论文在线 04 030 25 c 24 015 10 005 00 最大充成时间 图标准遗传算法各结果次数与结果总数之间的比例关系 图、图和图分别说明了改进算法的结果为 和时,每次结果的达代步数 与步数的平均值。橫线的纵坐标代表步数的平局值。改进算法没有取得过结果为的解, 因为取得结果为越多,说明算法的性能就越不够理想,所以文章后续图表中的改进算法 无法展示结果为的数据。改进算法迭代步数的平均值分别为 和 2000 1500 5 第次结果(次〕 图改进算法结果为的步数平均值 第次结果次〕 图改进算法结果为的步数平均值 山国武技论文在线 第次结果(次〕 图改进算法结果为的步数平均值 图、图、图和图分别说明了改进算法的结果为 和时,每次结 果的迭代步数与步数的平均值。标准遺传算法迭代步数的平均值分别为 和。标准遗传算法迭代步数的平局值四舍五入到了个位数。 第次结果(次 图标准遗传算法结果为的步数平均值 2000 1000 第次结果【次 图标准遗传算法结果为的步数平均值 山国武技论文在线 500 1500 结果(筑) 图标准遗传算法结果为的步数平均值 第次结果(次) 图标准遗传算法结果为的步数平均值 将两算法迭代步数的平局值绘制成折线图,并展示在图中。如图所示,蓝色虚线 代衣的改进算法的平均达代步数在橙色线代茯的标准遗传算法的下方,这衣明改进算法在更 小的达代步数内收敛到了该结果。因此,相比于标准遗传算法,改进算法拥有更快的收敛速 度 00 改进算法 传统算法 1400 200 10 4 最大完成时间 图改进算法与标准遗传算法的平均迭代步数对比 山国武技论文在线 表标准遗传算法次结果 表改进算法次结果 表和表分别是标准遗传算法和改进算法的次运算结果。因为每步打印一次 结果,所以结果都已整数倍表示。 实验结果分析与评估 从求解质量的角度进行分析,我们希望算法每次运行结果都能最终收敛于最优解,即 由表可知,改进后的遗传算法的次运行结果中,有次结果收敛于,有次 收敛于,有次收敛于,没有取得过;改进算法的结果绝大多数收敛于该问题的最 优解,而没有一次收敛于较差的解 而标准遗传算法的次运行结果中,有次结 果收敛于,有次收敛于,有次收敛于次收敛于。其结果分布的较为分散, ∏大部分收敛于,只有的结果收敛于该问题的最优解。综上所述,能够明显看出在 求解质量方面,改进算法大幅优于标准遗传算法 从收敛效率的角度进行分析,我们希望算法每个结果的平均迭代步数越小越好。由图 可知,改进算法在结果为 和的达代步数平均值分别为 和 与之 相比的是,标准遗传算法结果为 和的达代步数平均值分别为 和因为改进算法没有取得过,所以我们只对、和的迭代步数平局值进 行对比。通过比较可知,改进算法每个结果的迭代步数平均值均小于标准遗传算法。综上所 述,改进算法在收敛效率方面也是由于标准遗传算法的。 结论 本文提出一直用基于遗传算法的改进算法用于解决作业车间调度问题,经过理论分析和 实践表明它在可以得到最优解或高质量的次优解,具有实用意义。相较于标准遗传算法,改 进算法不论是在求解质量还是收敛效率方面都能看到明显的提升。为进一步改进该方法的性 能,将遗传算法和神绎网络以合适的方法结合是极为有意义的硏究方向。 山国武技论文在线 致谢 感谢王晨升老师在理论研究方面与论文写作方面给子的指导; 参考文献 王波张群王飞,等 排序问题鮮空间定量分析控制与决策 韩继业排序问题的一个判别条件和一类特殊的排序问题应用数学学报 张长水阎平凡解 调度问题的神经网络方法自动化学报 张朝勇邵新宇作业车间调度理论与算法武汉华中科技大学出版社 王明蔡劲草王雷基于改进遺传算法的作业车间调度铜仁学院学报

-
2019-08-14
701KB
论文研究-基于免疫遗传算法的车间天车调度仿真模型.pdf
2019-09-20论文研究-基于免疫遗传算法的车间天车调度仿真模型.pdf, 研究了多机多任务的车间天车调度问题, 提出了一种结合免疫遗传算法的仿真模型 解决方案. 该方案建立了能反映天车实际工作环境运行特征的仿真模
90KB
论文研究-基于遗传算法的作业车间调度优化求解方法.pdf
2019-07-22针对 job shop调度问题 ,提出了一种遗传算法编码方法和解码方法。该方法根据问题的特点 ,采用一种按工序用不同编号进行的染色体编码方案 ,并采用矩阵解码方法。此编码与调度方案一一对应 ,并且该编
579KB
论文研究-基于遗传算法的JobShop调度问题研究.pdf
2019-07-22在多平行工作站环境下, 为使限定资源分配下的车间调度问题(Job Shop problem, JSP)具有最小总延迟时间; 同时又可设定各订单具有不同的开工日(release date)及到期日, 提
994KB
论文研究-混合蝗虫优化算法求解作业车间调度问题.pdf
2019-09-12作为新兴的智能算法,蝗虫优化算法在作业车间调度问题中的应用符合智能制造的趋势。但由于全局寻优能力不足,基本蝗虫优化算法(GOA)在解决作业车间调度问题(JSP)时容易陷入局部最优,导致收敛精度较低。为
720KB
论文研究-改进蝙蝠算法柔性作业车间调度问题研究.pdf
2019-09-08针对柔性作业车间调度问题,提出了一种改进的离散蝙蝠算法。该算法采用双层编码序列方式,利用均衡机器负载分配策略和插入式解码方案初始化种群,同时设计了离散蝙蝠算法的速度、位置更新的相关算子和操作,引入了平
654KB
论文研究-最优子种群遗传算法求解柔性流水车间调度问题.pdf
2019-07-23为了验证最优子种群遗传算法在解决柔性流水车间调度问题时相比于传统遗传算法的优越性,分析了柔性流水车间调度问题的特点,并运用一种新的编码方法和新的遗传算法求解了该问题。考虑到最优个体保护策略法对复杂问题
1.52MB
论文研究-量子鲸鱼优化算法求解作业车间调度问题.pdf
2019-07-22为了克服基本鲸鱼优化算法(WOA)在解决作业车间调度问题时存在收敛精度低、容易陷入局部最优的缺陷,利用量子计算与优化思想提出了一种量子鲸鱼优化算法(QWOA),并对其进行了计算复杂度分析、全局收敛性证
981KB
论文研究-基于规则导向的柔性作业车间多目标动态调度算法.pdf
2019-09-20论文研究-基于规则导向的柔性作业车间多目标动态调度算法.pdf, 设计了一种具有柔性资源约束的多目标集成优化方法,建立了包括最小完工时间、最小生产成本、最大设备利用率、最大交货满意度和最优人工分配在
955KB
论文研究-基于改进紧致遗传算法的柔性流水车间组批排产优化问题研究.pdf
2019-09-20论文研究-基于改进紧致遗传算法的柔性流水车间组批排产优化问题研究.pdf, 为了解决柔性流水车间组批排产优化问题(flexible flow shop scheduling problem with
538KB
论文研究-基于遗传算法的混合流水线车间调度多目标求解.pdf
2019-07-22为了解决传统的多目标优化算法难以很好实现企业的实际决策需要问题,针对混合流水线车间调度(HFSP)的多目标优化调度问题,提出了一种新的多目标遗传算法。根据企业实际需求,采用分模块两层建模的思想,将多目
649KB
论文研究-多目标等量分批柔性作业车间调度集成优化方法.pdf
2019-09-08针对多目标等量分批柔性作业车间调度问题,提出了一种集成优化方法。构建了一种以完工时间最短、生产成本最低为优化目标的多目标等量分批柔性调度集成优化模型。提出并设计了一种改进的非支配排序遗传算法对模型加以
2KB
遗传算法解决车间调度问题
2017-12-19本文讨论的任务车间调度问题是一个典型的NP完全问题,也是最难解的组合优化问题之一。虽然本题给出的工件(墙纸)数n、机器数m及工序(印刷颜色)数l较小,但可以看到,利用经典整数规划的方法求解该问题还是存
455KB
论文研究-基于改进BPSO算法求解一类作业车间调度问题 .pdf
2019-09-20论文研究-基于改进BPSO算法求解一类作业车间调度问题 .pdf,
684KB
论文研究-基于模拟植物生长算法的车辆调度问题.pdf
2019-09-20论文研究-基于模拟植物生长算法的车辆调度问题.pdf, 基于配送企业车辆资源的限制和客户需求时间窗的要求, 在考虑外包车辆和配送人员加班的情况下, 对带时间窗的车辆调度问题进行扩展研究. 根据客户需
541KB
论文研究-面向柔性工艺的作业车间调度问题混合遗传算法.pdf
2019-07-22针对离散制造业的许多产品采用柔性工艺设计增加作业计划调度的复杂性这一问题,对传统的FJSP进行了工序顺序柔性的扩展,将问题抽象为柔性工艺的作业车间调度问题(flexible process Job-S
374KB
论文研究-基于遗传算法供水系统优化调度模型.pdf
2019-09-20论文研究-基于遗传算法供水系统优化调度模型.pdf,
811KB
论文研究-求解置换流水车间调度问题的改进遗传算法.pdf
2019-09-13针对置换流水车间调度问题的基本特征和传统遗传算法易早熟的缺陷,设计了改进遗传算法来求解此问题。采用NEH和Palmer启发式算法进行种群初始化,以提高初始解的质量;根据Metropolis准则对染色体
729KB
论文研究-一种基于改进遗传算法的网格资源调度策略.pdf
2019-09-12首先对网格资源调度的特点、现有遗传算法的局限性进行了分析,在此基础上对遗传算法进行改进;提出一种基于改进遗传算法的网格资源调度策略(GRSS_IGA),该算法综合考虑资源任务分配量、任务截止时间、任务
2.1MB
论文研究-精英进化策略求解柔性作业车间调度问题.pdf
2019-07-22柔性作业车间调度问题允许一道工序可以在多个可选机器上进行加工,减少了机器约束,增加了求解难度,是典型的NP难问题。结合其特点,设计了一种精英进化策略遗传算法求解柔性作业车间调度问题。提出了解阈值的指标
13KB
遗传算法的车间调度问题
2018-06-13智能车间调度问题,利用遗传算法更好的解决车间调度问题
8KB
matlab遗传算法解决作业车间调度问题
2018-06-04用matlab程序解决作业车间调度问题的小例子,程序可运行,可画出进化图与甘特图。内附算例与程序说明。
797KB
论文研究-求解零空闲置换流水车间调度问题的离散烟花算法.pdf
2019-09-20论文研究-求解零空闲置换流水车间调度问题的离散烟花算法.pdf, 针对以最小化最大完工时间为目标的零空闲置换流水线调度问题,提出了一种带有局部搜索的离散烟花算法.首先,结合调度问题的置换特征,定义了
598KB
论文研究-基于Bayesian统计推理的分布估计算法求解, 柔性作业车间调度问题.pdf
2019-09-20论文研究-基于Bayesian统计推理的分布估计算法求解, 柔性作业车间调度问题.pdf, 在Bayesian统计推理理论的基础上, 提出一种新的求解柔性车间调度问题的分布估计算法.首先, 根据所有
11KB
遗传算法GA车间调度Matlab代码
2019-05-08该代码用于解决具有机器柔性的柔性作业车间调度问题,工件数量与工序数量可自行调节,采用了传统遗传算法,编码方式为三维实数编码。
8.91MB
C++遗传算法解决柔性作业车间调度(附测试数据及优解)
2019-08-21用c++写的遗传算法解决柔性作业车间调度问题,主要参考论文 张国辉, 高亮, 李培根, et al. 改进遗传算法求解柔性作业车间调度问题. 机械工程学报, 2009, 45(7):145-151.
624KB
论文研究-生产能力约束条件下的柔性作业车间调度优化.pdf
2019-09-20论文研究-生产能力约束条件下的柔性作业车间调度优化.pdf, 柔性作业车间调度问题是经典作业车间调度问题的深化,为解决实际生产系统中作业车间调度资源受限问题提供了方案.从生产能力约束条件出发构建柔性
665KB
论文研究-一种求解车间作业调度问题的免疫算法.pdf
2019-09-08人工免疫系统是基于生物免疫系统特性而发展的新兴智能系统。基于免疫系统的克隆选择机制,提出一种求解车间作业调度问题的免疫算法。利用免疫算法较强的搜索能力可以实现全局寻优。通过使用克隆、高频变异和抗体抑制
442KB
论文研究-一种基于遗传—蚁群算法的网格任务调度策略.pdf
2019-07-22针对遗传调度算法局部求解能力不足、容易早熟和退化的问题,以及蚁群调度算法初始搜索阶段效率低下的缺陷,充分应用遗传算法全局搜索能力较好和蚁群算法求解精度较高的优势,提出了一种基于遗传—蚁群算法的网格任务
8.91MB
基于混合遗传算法车间调度优化(论文+程序)
2010-06-08车间作业调度问题(Job Shop Scheduling Problem)是一个著名的NP难题,具有很强的条件约束,当问题规模较大时很难找到全局最优解。因此作业车间调度是一类求解困难的组合优化问题。近
385KB
论文研究-柔性作业车间调度问题的一种启发式算法.pdf
2019-07-22为了研究多目标柔性作业车间调度问题,基于甘特图和搭积木经验进行了分析,提出了一种组合优先规则和基于此优先规则的启发式算法。组合优先规则面向完工时间、关键机床负荷和总负荷三个指标,改变规则中各数据项的比
-
下载
喉关节的建模及数值模拟研究
喉关节的建模及数值模拟研究
-
下载
ntbackup全备与增备指南.docx
ntbackup全备与增备指南.docx
-
学院
精通编译Makefile,Nina, 从底层uboot到Android
精通编译Makefile,Nina, 从底层uboot到Android
-
下载
UserGreedy:利用激活集解决影响最大化问题
UserGreedy:利用激活集解决影响最大化问题
-
博客
IEC 60335标准介绍
IEC 60335标准介绍
-
下载
CDASH文档.pdf
CDASH文档.pdf
-
下载
高级3DSurface WSN中基于连接性的空间填充曲线构建算法
高级3DSurface WSN中基于连接性的空间填充曲线构建算法
-
学院
MySQL 数据类型和运算符
MySQL 数据类型和运算符
-
博客
硬核干货!阿里架构师手写740页分布式微服务手册,吊打面试官
硬核干货!阿里架构师手写740页分布式微服务手册,吊打面试官
-
博客
关于软考,你可能还不知道的一些事儿
关于软考,你可能还不知道的一些事儿
-
下载
喉关节重建与建模的研究
喉关节重建与建模的研究
-
学院
PowerBI重要外部工具详解
PowerBI重要外部工具详解
-
下载
文件夹-源码
文件夹-源码
-
博客
tree shaking
tree shaking
-
下载
2021年健身服务行业深度报告
2021年健身服务行业深度报告
-
博客
【刷题基础知识】-二叉树
【刷题基础知识】-二叉树
-
博客
【mimics,ansys】医学三维重建及血流动力学
【mimics,ansys】医学三维重建及血流动力学
-
学院
MySQL 查询与高级查询(多表、嵌套和正则表达式)
MySQL 查询与高级查询(多表、嵌套和正则表达式)
-
下载
网络安全设计规范.docx
网络安全设计规范.docx
-
学院
Python函数库深度详解(1)
Python函数库深度详解(1)
-
博客
手把手教你写Hive&Impala的UDF
手把手教你写Hive&Impala的UDF
-
博客
ORA-00001: 违反唯一约束条件 的解决办法
ORA-00001: 违反唯一约束条件 的解决办法
-
下载
3D聚乳酸-乙醇酸共聚物支架治疗脊髓损伤,
3D聚乳酸-乙醇酸共聚物支架治疗脊髓损伤,
-
博客
uniapp图片编辑器,支持自定义尺寸、缩放、拖动、裁剪
uniapp图片编辑器,支持自定义尺寸、缩放、拖动、裁剪
-
博客
【转】肺小结节就诊指南:4种CT的区别及如何选择?
【转】肺小结节就诊指南:4种CT的区别及如何选择?
-
博客
2021-03-03
2021-03-03
-
下载
有色噪声引起的置位复位锁存器逻辑操作
有色噪声引起的置位复位锁存器逻辑操作
-
博客
复旦教授打800次车,发现越贵的手机打车越贵
复旦教授打800次车,发现越贵的手机打车越贵
-
下载
使用RGBD相机自动进行3D室内场景更新。
使用RGBD相机自动进行3D室内场景更新。
-
博客
关于L5的问题
关于L5的问题