柔性作業(yè)車(chē)間調(diào)度問(wèn)題介紹

之前我們?cè)?jīng)做過(guò)車(chē)間調(diào)度問(wèn)題（JSP）的內(nèi)容，相關(guān)可以看這篇文章：

這里再簡(jiǎn)單介紹一下FJSP：

集合表示一系列相互獨(dú)立的工件，任一工件需要經(jīng)過(guò)等一系列工序的加工方可完成，工序之間按照固定的加工順序依次完成。集合表示可用的加工機(jī)器，表示工件的第道工序，可以在可用機(jī)器集合中的任意機(jī)器上進(jìn)行加工。每道工序的加工時(shí)間與加工機(jī)器相關(guān)。

一道工序一旦開(kāi)始加工，就不能中斷。每臺(tái)機(jī)器一次只能加工一道工序。在初始加工時(shí)刻，所有工件和機(jī)器都是可用的。

一般來(lái)說(shuō)，該問(wèn)題的目標(biāo)是最小化Makespan，通常用L來(lái)表示，即從開(kāi)始加工到所有工件加工完畢總的時(shí)長(zhǎng)。

綜上所述，柔性車(chē)間調(diào)度問(wèn)題和車(chē)間調(diào)度問(wèn)題相似，在此之上改變了一個(gè)條件：對(duì)JSP，每道工序只能在某個(gè)特定的機(jī)器上加工；對(duì)FJSP，工序可能有多個(gè)可加工的機(jī)器（且不同機(jī)器上加工時(shí)間不同）。

所以，F(xiàn)JSP不光要選擇工序在機(jī)器上加工的順序，還要選擇在哪個(gè)機(jī)器上加工。這也意味著FJSP是比JSP更復(fù)雜的優(yōu)化問(wèn)題。

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

算法總體的流程如上圖所示，簡(jiǎn)單來(lái)說(shuō)就是在GA的過(guò)程中，對(duì)每一個(gè)子代個(gè)體進(jìn)行tabu search優(yōu)化。下面小編分別對(duì)GA部分和TS部分進(jìn)行講解。

遺傳算法部分

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

編碼解碼

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

表a代表算例。

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

MS String中也有N個(gè)數(shù)字，代表每個(gè)工件選擇的機(jī)器。MS的順序按照工件順序排列，如圖，J1、J2、J3都有2道工序，那么第一位數(shù)字“2”則代表O11，J1T1，需要安排在第二個(gè)可以加工的機(jī)器上。注意這里的數(shù)字不代表機(jī)器序號(hào)，代表的是可加工的機(jī)器。例如最后一位數(shù)字“2”，代表的不是machine2，因?yàn)镴3T3無(wú)法在machine2上加工；它代表的是J3T3第二個(gè)可加工的機(jī)器，也就是machine3。

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

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

從第一道工序開(kāi)始按OS的順序，安排工序Oij：

1. 計(jì)算
2. 檢查工序所在加工機(jī)器中的所有空閑時(shí)間區(qū)間。例如對(duì)O22而言，其所在加工機(jī)器M1中的空閑時(shí)間區(qū)間有一個(gè)：。
3. ，則設(shè)置當(dāng)前工序Oij的開(kāi)始時(shí)間。其中表示Oij在機(jī)器k上加工的時(shí)間。
4. 否則，檢查下一個(gè)空閑時(shí)間區(qū)間。若所有區(qū)間都不滿(mǎn)足，放置機(jī)器最后。
5. 設(shè)置工序加工結(jié)束時(shí)間。

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

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

下面我們分別介紹相關(guān)步驟。

初始解生成

初始解生成采用隨機(jī)生成的方式。

交叉

OS

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

先介紹POX。

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

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

JBX非常類(lèi)似：

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

MS

MS更簡(jiǎn)單，隨機(jī)選擇兩個(gè)位置，如圖所示，屬于范圍內(nèi)的P1部分放到O1中，不屬于范圍內(nèi)的P2部分放到O1中；屬于范圍內(nèi)的P2部分放到O2中，不屬于范圍內(nèi)的P1部分放到O2中。

變異

OS

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

交換式即隨機(jī)選擇兩點(diǎn)交換位置。

鄰域式則是選擇三個(gè)點(diǎn)，組成種情況，再隨機(jī)選擇其中一種。

選擇

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

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

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

論文里采用精英選擇+競(jìng)標(biāo)賽選擇的方法。

禁忌搜索算法部分

禁忌搜索算法部分是嵌套在GA中的。按原論文的說(shuō)法，對(duì)每一代子代的每一個(gè)個(gè)體，都需要decode成可行解，然后運(yùn)用禁忌搜索優(yōu)化解，再編碼回GA編碼，進(jìn)入下一代。（聽(tīng)起來(lái)就覺(jué)得時(shí)間復(fù)雜度蠻高的）

除了甘特圖外，JSP / FJSP還有自己的一套表示解的方法，稱(chēng)為析取圖。簡(jiǎn)單來(lái)說(shuō)，就是把工序作為點(diǎn)，前后加工關(guān)系作為邊，以此表示工序的加工順序。

如前文所說(shuō)，由于嵌套至每一個(gè)個(gè)體，算法的運(yùn)行時(shí)間很容易爆炸，多寫(xiě)一個(gè)循環(huán)都會(huì)產(chǎn)生不可估量的后果。同時(shí)，原論文在這一部分沒(méi)有很詳細(xì)的描述，因此小編在復(fù)現(xiàn)這一部分的時(shí)候也沒(méi)有處理的很好，來(lái)來(lái)回回寫(xiě)了多個(gè)Tabu Search。由于篇幅原因，這一部分暫時(shí)留到下期講，后續(xù)應(yīng)該還會(huì)對(duì)小編的代碼進(jìn)行簡(jiǎn)單講解，請(qǐng)大家多多關(guān)注！

關(guān)于甘特圖的畫(huà)法，可以參照：

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.