前言

過(guò)去小編簡(jiǎn)單了解過(guò)作業(yè)車(chē)間調(diào)度問(wèn)題（JSP），這兩個(gè)月簡(jiǎn)單接觸了柔性車(chē)間調(diào)度問(wèn)題（FJSP），但是因?yàn)橐恍┰虼蛩銜簳r(shí)研究到這里。在研究的時(shí)候，小編發(fā)現(xiàn)網(wǎng)上這方面的中文資源不多，那么秉持著普度眾生的原則，就在這里和大家分享一下最近研究的一些成果。

柔性作業(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或類似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代表算例。

算例中有三個(gè)工件需要加工，每個(gè)工件分別有兩道工序（不同工件加工工序不一定一樣多）。除了J3的工序T2（task）外，所有工序都可以在三臺(tái)機(jī)器上加工，對(duì)應(yīng)的加工時(shí)間如表a所示。