0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看技术视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

种群进化+邻域搜索的混合算法求解作业车间调度问题之算法原理

电子设计 来源:电子设计 作者:电子设计 2020-12-24 17:11 次阅读

前言

过去小编简单了解过作业车间调度问题(JSP),这两个月简单接触了柔性车间调度问题(FJSP),但是因为一些原因打算暂时研究到这里。在研究的时候,小编发现网上这方面的中文资源不多,那么秉持着普度众生的原则,就在这里和大家分享一下最近研究的一些成果。

柔性作业车间调度问题介绍

之前我们曾经做过车间调度问题(JSP)的内容,相关可以看这篇文章:

这里再简单介绍一下FJSP:

集合表示一系列相互独立的工件,任一工件需要经过等一系列工序的加工方可完成,工序之间按照固定的加工顺序依次完成。集合表示可用的加工机器,表示工件的第道工序,可以在可用机器集合中的任意机器上进行加工。每道工序的加工时间与加工机器相关。

一道工序一旦开始加工,就不能中断。每台机器一次只能加工一道工序。在初始加工时刻,所有工件和机器都是可用的。

一般来说,该问题的目标是最小化Makespan,通常用L来表示,即从开始加工到所有工件加工完毕总的时长。

综上所述,柔性车间调度问题和车间调度问题相似,在此之上改变了一个条件:对JSP,每道工序只能在某个特定的机器上加工;对FJSP,工序可能有多个可加工的机器(且不同机器上加工时间不同)。

所以,FJSP不光要选择工序在机器上加工的顺序,还要选择在哪个机器上加工。这也意味着FJSP是比JSP更复杂的优化问题。

根据小编这段时间的研究,学术界目前比较常用的启发式求解算法是种群进化+邻域搜索的混合算法,其中GA+TS是比较成熟的算法体系。接下来主要参考论文 An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem 的算法,介绍论文里的混合算法HA,以及小编自己复现的代码。

算法总体的流程如上图所示,简单来说就是在GA的过程中,对每一个子代个体进行tabu search优化。下面小编分别对GA部分和TS部分进行讲解。

遗传算法部分

大家知道,不同的启发式算法在不同问题下效果会有很大的差别。过去小编在研究VRP问题时,GA的表现不是很好,编码、解码过程也相对复杂。但是GA在FJSP上表现的却非常优秀,因此大部分算法采取GA或类似GA的种群进化算法作为基础。仅仅是GA部分,已经可以以相当快的速度得到还算不错的解。

编码解码

FJSP的GA编码采取两行数字的方式。一串叫做OS(operation sequence),一串叫做MS(machine sequence)。之前我们提到过,求解FJSP需要做两个选择:工序加工顺序的选择;工序加工机器的选择。顾名思义,两串编码分别对应这两种选择。

上图是一个FJSP算例的编码和对应解。

表a代表算例。

算例中有三个工件需要加工,每个工件分别有两道工序(不同工件加工工序不一定一样多)。除了J3的工序T2(task)外,所有工序都可以在三台机器上加工,对应的加工时间如表a所示。

审核编辑:符乾江
声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 编码
    +关注

    关注

    6

    文章

    942

    浏览量

    54821
  • 车间调度
    +关注

    关注

    0

    文章

    4

    浏览量

    6957
收藏 人收藏

    评论

    相关推荐

    求LabVIEW程序代做,关于噪声测量方面,需要matlab与labview混合编程,涉及优化算法、PID控制等,可带价联系

    求LabVIEW程序代做,关于噪声测量方面,需要matlab与labview混合编程,涉及优化算法、PID控制等,可带价联系QQ2789223947
    发表于 12-11 17:27

    【「从算法到威廉希尔官方网站 —数字芯片算法的威廉希尔官方网站 实现」阅读体验】+内容简介

    内容简介这是一本深入解读基础算法及其威廉希尔官方网站 设计,以打通算法研发到数字IC设计的实现屏障,以及指导芯片设计工程师从底层掌握复杂威廉希尔官方网站 设计与优化方法为目标的专业技术书。任何芯片(如WiFi芯片、5G芯片
    发表于 11-21 17:14

    【「从算法到威廉希尔官方网站 —数字芯片算法的威廉希尔官方网站 实现」阅读体验】+介绍基础硬件算法模块

    作为嵌入式开发者往往比较关注硬件和软件的协调。本书介绍了除法器,信号发生器,滤波器,分频器等基本算法的威廉希尔官方网站 实现,虽然都是基础内容,但是也是最常用到的基本模块。 随着逆全球化趋势的出现,过去的研发
    发表于 11-21 17:05

    请问GDE中的NR算法反应慢怎么解决?

    我在使用NR(NoiseReduction)算法时发现算法起作用的时间太长,输入1K正弦波测试,大约是在输入40秒以后出现下图转变 再过段时间又变成下图的样子。 但是播放器重新开始的短暂停止也
    发表于 10-29 07:42

    U盘存储并联,算法交互输出

    FreeRTOS),负责任务调度和资源管理。 使用C/C++语言编写数据管理、算法和通信模块,确保代码的高效性和可靠性。 利用现有的库和框架(如TensorFlow Lite Micro)来实现轻量级的机器
    发表于 10-28 07:36

    需要同时播放4路WAV文件,在一个DAC输出,这样需要什么算法混合4路音频啊?

    求教4路WAV文件播放混合问题,我需要同时播放4路WAV文件,在一个DAC输出,这样需要什么算法混合4路音频啊?
    发表于 10-21 07:25

    量子计算场景实用秘籍:开物SDKsubQUBO算法分解

    subQUBO算法是一种将大规模组合优化问题分解为若干个小规模问题以便能在当前中小规模量子计算机上实现求解的方法。
    的头像 发表于 08-13 11:05 1171次阅读
    量子计算场景实用秘籍:开物SDK<b class='flag-5'>之</b>subQUBO<b class='flag-5'>算法</b>分解

    中伟视界:矿山智能化安全生产,未戴自救器检测AI算法助力保护作业人员安全

    矿山作业环境复杂危险,确保作业人员佩戴自救器是重要措施之一。未戴自救器检测AI算法通过图像识别和人工智能技术,实时监控井下人员的自救器佩戴情况,有效避免了安全事故。本文详细解析该算法
    的头像 发表于 07-17 13:10 320次阅读
    中伟视界:矿山智能化安全生产,未戴自救器检测AI<b class='flag-5'>算法</b>助力保护<b class='flag-5'>作业</b>人员安全

    揭秘谷歌搜索算法工作原理,与官方声明存在矛盾

    有着十多年搜索引擎优化经验的兰德·菲什金,近日透露他收到一份长达2500页的文件,据称这是对谷歌搜索算法工作原理的真实揭示,而非谷歌官方所声称的那样。
    的头像 发表于 05-29 16:00 599次阅读

    浅析FreeRTOS任务调度器的三种调度算法和应用

    FreeRTOS在MCU领域应用非常广泛,今天就给大家讲解一下FreeRTOS调度器中的三种调度算法,以及在瑞萨RZ/T2L MPU中的应用。
    的头像 发表于 05-10 14:02 7359次阅读
    浅析FreeRTOS任务<b class='flag-5'>调度</b>器的三种<b class='flag-5'>调度</b><b class='flag-5'>算法</b>和应用

    FreeRTOS任务调度器的三种调度算法讲解(下)

    配置如下时,调度算法就会变成不带时间片的抢占式调度
    的头像 发表于 03-21 13:46 2794次阅读
    FreeRTOS任务<b class='flag-5'>调度</b>器的三种<b class='flag-5'>调度</b><b class='flag-5'>算法</b>讲解(下)

    Spring Boot和飞腾派融合构建的农业物联网系统-改进自适应加权融合算法

    接上集: 上次实验我们已经完成多传感器融合算法的设计,本次实验注意完成改进自适应加权融合算法设计。 一、背景 通过利用温室控制系统来管理温室内的各种设备并控制温度、湿度,可以更好地探索和掌握环境因素
    发表于 01-06 12:18

    FPGA图像处理CLAHE算法

    在FPGA图像处理--CLAHE算法(一)中介绍了为啥要用CLAHE算法来做图像增强。
    的头像 发表于 01-04 12:23 2523次阅读
    FPGA图像处理<b class='flag-5'>之</b>CLAHE<b class='flag-5'>算法</b>

    MATLAB程序算法实例

    什么是算法算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。
    的头像 发表于 12-29 09:33 477次阅读
    MATLAB程序<b class='flag-5'>算法</b>实例

    【飞腾派4G版免费试用】Spring Boot和飞腾派融合构建的农业物联网系统-数据融合算法

    本帖最后由 sda12138 于 2024-1-6 12:00 编辑 接上集: 上次实验我们已经完成个人中心的设计,本次实验主要完成内容是完成多传感器融合算法的设计。 一、背景 在智慧农业中农
    发表于 12-26 20:59