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

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，以及小编自己复现的代码。