前言

過去小編簡單了解過作業車間調度問題（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所示。