種群進(jìn)化+鄰域搜索的混合算法求解作業(yè)車間調(diào)度問題之算法原理

前言

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

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

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

這里再簡單介紹一下FJSP：

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

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

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

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

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

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

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

遺傳算法部分

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

編碼解碼

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

上圖是一個FJSP算例的編碼和對應(yīng)解。

表a代表算例。

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