作业车间调度问题该如何解决?种群进化+邻域搜索的混合算法

程序猿声
关注

过去小编简单了解过作业车间调度问题(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算例的编码和对应解。

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

下载OFweek,一手掌握高科技全行业资讯

还不是OFweek会员,马上注册
打开app,查看更多精彩资讯 >
  • 长按识别二维码
  • 进入OFweek阅读全文
长按图片进行保存