侵权投诉
订阅
纠错
加入自媒体

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

2020-08-09 12:47
程序猿声
关注

前言

过去小编简单了解过作业车间调度问题(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所示。

1  2  3  下一页>  
声明: 本文由入驻维科号的作者撰写,观点仅代表作者本人,不代表OFweek立场。如有侵权或其他问题,请联系举报。

发表评论

0条评论,0人参与

请输入评论内容...

请输入评论/评论长度6~500个字

您提交的评论过于频繁,请输入验证码继续

暂无评论

暂无评论

电子工程 猎头职位 更多
扫码关注公众号
OFweek电子工程网
获取更多精彩内容
文章纠错
x
*文字标题:
*纠错内容:
联系邮箱:
*验 证 码:

粤公网安备 44030502002758号