柔性作業(yè)車間調度問題介紹

之前我們曾經做過車間調度問題（JSP）的內容，相關可以看這篇文章：

這里再簡單介紹一下FJSP：

集合表示一系列相互獨立的工件，任一工件需要經過等一系列工序的加工方可完成，工序之間按照固定的加工順序依次完成。集合表示可用的加工機器，表示工件的第道工序，可以在可用機器集合中的任意機器上進行加工。每道工序的加工時間與加工機器相關。

一道工序一旦開始加工，就不能中斷。每臺機器一次只能加工一道工序。在初始加工時刻，所有工件和機器都是可用的。

一般來說，該問題的目標是最小化Makespan，通常用L來表示，即從開始加工到所有工件加工完畢總的時長。

綜上所述，柔性車間調度問題和車間調度問題相似，在此之上改變了一個條件：對JSP，每道工序只能在某個特定的機器上加工；對FJSP，工序可能有多個可加工的機器（且不同機器上加工時間不同）。

所以，FJSP不光要選擇工序在機器上加工的順序，還要選擇在哪個機器上加工。這也意味著FJSP是比JSP更復雜的優(yōu)化問題。

根據小編這段時間的研究，學術界目前比較常用的啟發(fā)式求解算法是種群進化+鄰域搜索的混合算法，其中GA+TS是比較成熟的算法體系。接下來主要參考論文 An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem 的算法，介紹論文里的混合算法HA，以及小編自己復現的代碼。（代碼和論文可在文末下載）

算法總體的流程如上圖所示，簡單來說就是在GA的過程中，對每一個子代個體進行tabu search優(yōu)化。下面小編分別對GA部分和TS部分進行講解。

遺傳算法部分

大家知道，不同的啟發(fā)式算法在不同問題下效果會有很大的差別。過去小編在研究VRP問題時，GA的表現不是很好，編碼、解碼過程也相對復雜。但是GA在FJSP上表現的卻非常優(yōu)秀，因此大部分算法采取GA或類似GA的種群進化算法作為基礎。僅僅是GA部分，已經可以以相當快的速度得到還算不錯的解。

編碼解碼

FJSP的GA編碼采取兩行數字的方式。一串叫做OS（operation sequence），一串叫做MS（machine sequence）。之前我們提到過，求解FJSP需要做兩個選擇：工序加工順序的選擇；工序加工機器的選擇。顧名思義，兩串編碼分別對應這兩種選擇。上圖是一個FJSP算例的編碼和對應解。

表a代表算例。

表b的OS String和MS String代表染色體編碼。

MS String中也有N個數字，代表每個工件選擇的機器。MS的順序按照工件順序排列，如圖，J1、J2、J3都有2道工序，那么第一位數字“2”則代表O11，J1T1，需要安排在第二個可以加工的機器上。注意這里的數字不代表機器序號，代表的是可加工的機器。例如最后一位數字“2”，代表的不是machine2，因為J3T3無法在machine2上加工；它代表的是J3T3第二個可加工的機器，也就是machine3。

表c用甘特圖表示了表b中編碼解碼出的一個可行解。

這里介紹一下如何優(yōu)化decode。首先，我們設定 （allowing starting time），代表Oij的在工序約束（必須在同一工件上一道工序結束后才能開始加工）下的最早允許開始時間；代表Oij的結束時間。則我們得到公式。

從第一道工序開始按OS的順序，安排工序Oij：

1. 計算
2. 檢查工序所在加工機器中的所有空閑時間區(qū)間。例如對O22而言，其所在加工機器M1中的空閑時間區(qū)間有一個：。
3. ，則設置當前工序Oij的開始時間。其中表示Oij在機器k上加工的時間。
4. 否則，檢查下一個空閑時間區(qū)間。若所有區(qū)間都不滿足，放置機器最后。
5. 設置工序加工結束時間。

編碼的過程則比較簡單。MS編碼自不用說，按順序把機器需要排列好就行；OS編碼論文中沒提編碼方法，小編覺得可以對所有工序直接按照starting time排序，再按規(guī)則填入數字即可。簡單試驗后發(fā)現，對一串染色體進行這樣的解碼編碼后得到的染色體與原本的染色體是相同的。

除了編碼解碼外，其他交叉、變異、選擇部分與一般的GA算法沒有太大差別。對一串合法的OS序列，無論進行怎樣的交換、插入運算，都可以解碼成可行解。對MS序列，在同一工件范圍內任意交換順序，也可以保證得到可行解。所以后續(xù)處理相對常規(guī)。

下面我們分別介紹相關步驟。

初始解生成

初始解生成采用隨機生成的方式。

交叉

OS

OS String介紹兩種crossover方法，分別為POX（precedence operation crossover ）和JBX（job-basedcrossover ），每次迭代分別以50%的概率選擇其中一個實行。

先介紹POX。

記父代為P1，P2，子代為O1，O2。

1. 將工件隨機分配成兩組，Jobset1和Jobset12；
2. 將P1中屬于JS1的部分插入O1相同位置處，將P2中屬于JS1的部分插入O1相同位置處；
3. 將P1中屬于JS2的部分按順序插入O1的空余位置中（如圖所示），P2同。

JBX非常類似：

1. 將工件隨機分配成兩組，Jobset1和Jobset12；
2. 將P1中屬于JS1的部分插入O1相同位置處，P2中屬于JS2的部分插入O2相同位置中；
3. 將P2中屬于JS2的部分按順序插入O1的空余位置中（如圖所示），P1則插入O2中。

MS

MS更簡單，隨機選擇兩個位置，如圖所示，屬于范圍內的P1部分放到O1中，不屬于范圍內的P2部分放到O1中；屬于范圍內的P2部分放到O2中，不屬于范圍內的P1部分放到O2中。

變異

OS

OS的變異有兩種方法，交換式和鄰域式。

交換式即隨機選擇兩點交換位置。

鄰域式則是選擇三個點，組成種情況，再隨機選擇其中一種。

選擇

選擇可以有多種方法。精英選擇，錦標賽選擇，輪盤賭選擇。這里介紹論文里使用的前兩種。（小編的代碼中三種都有寫）

精英選擇：直接按適應度排序，取最優(yōu)的幾個。

錦標賽選擇：每次隨機選擇k個子代（k一般在2~6之間，論文里采用k=2），選出其中最優(yōu)的一個。

論文里采用精英選擇+競標賽選擇的方法。

禁忌搜索算法部分

禁忌搜索算法部分是嵌套在GA中的。按原論文的說法，對每一代子代的每一個個體，都需要decode成可行解，然后運用禁忌搜索優(yōu)化解，再編碼回GA編碼，進入下一代。（聽起來就覺得時間復雜度蠻高的）

除了甘特圖外，JSP / FJSP還有自己的一套表示解的方法，稱為析取圖。簡單來說，就是把工序作為點，前后加工關系作為邊，以此表示工序的加工順序。

如前文所說，由于嵌套至每一個個體，算法的運行時間很容易爆炸，多寫一個循環(huán)都會產生不可估量的后果。同時，原論文在這一部分沒有很詳細的描述，因此小編在復現這一部分的時候也沒有處理的很好，來來回回寫了多個Tabu Search。由于篇幅原因，這一部分暫時留到下期講，后續(xù)應該還會對小編的代碼進行簡單講解，請大家多多關注！

關于甘特圖的畫法，可以參照：

10分鐘用Python或MATLAB制作漂亮的甘特圖（Gantt）

參考

[1]Li, Xinyu , and L. Gao . "An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem." International Journal of Production Economics 174.Apr.(2016):93-110.

[2]Zhang, Chao Yong , P. G. Li , and Y. R. Zailin Guan . "A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem." Computers & Operations Research 34.11(2007):3229-3242.

[3]Mastrolilli, Monaldo , and L. M. Gambardella . "Effective Neighbourhood Functions for the Flexible Job Shop Problem." Journal of Scheduling 3.1(2015):3-20.

[4]Zhang, Guohui , L. Gao , and Y. Shi . "An effective genetic algorithm for the flexible job-shop scheduling problem." Expert Systems with Applications 38.4(2011):3563-3573.