干貨 | Tabu Search求解作業(yè)車間調(diào)度問(wèn)題(Job Shop Scheduling)-附...
假期突然多出好多天，大家有沒(méi)有感覺(jué)特別無(wú)聊？
是在家擺瓜子呢：
還是在數(shù)羊呢：
還是在朋友圈里一邊喝著洗衣粉一邊計(jì)劃著晚上裸奔，想要出軌結(jié)果表白被拒，狠下心決定今晚誰(shuí)追自己就答應(yīng)誰(shuí)？
不如和小編一起，做一個(gè)安靜的美男子，
開 · 始?·?學(xué) · 習(xí) 吧！
有一個(gè)可惡的老板覺(jué)得一直寫TSP、VRP問(wèn)題非常無(wú)聊，打算引入一個(gè)新問(wèn)題：作業(yè)車間調(diào)度問(wèn)題(Job shop scheduling problem, JSP) 。前兩天其實(shí)已經(jīng)提到過(guò)JSP，這次小編再詳細(xì)解讀一下JSP，帶來(lái)一段禁忌搜索算法求解JSP的Java代碼，幫大家消磨這段 無(wú) · 聊 的時(shí)間~
01
作業(yè)車間調(diào)度問(wèn)題
問(wèn)題描述
一個(gè)加工系統(tǒng)共有m臺(tái)機(jī)器，需要加工n個(gè)加工順序不同的工件。
已知：(1) 工件集?,其中為第個(gè)工件,；
(2) 機(jī)器集為第j號(hào)機(jī)器,j=1,2,…,m；
(3) 工序集為工件的工序序列。為第i個(gè)工件的第k道工序使用的機(jī)器號(hào),表示工件在第k道工序不加工,
(4) 每個(gè)工件使用每臺(tái)機(jī)器的時(shí)間矩陣為第個(gè)工件使用第臺(tái)機(jī)器的時(shí)間。表示工件不使用機(jī)器j。
JSP需要滿足下列約束條件: (1) 每個(gè)工件使用每臺(tái)機(jī)器不多于1次; (2) 每個(gè)工件利用每臺(tái)機(jī)器的順序可以不同,即可以有; (3) 每個(gè)工件的工序必須依次加工，后工序不能先于前工序；(4) 任何工件沒(méi)有搶先加工的優(yōu)先權(quán),應(yīng)服從任何生產(chǎn)順序; (5) 工件加工過(guò)程中沒(méi)有新工件加入,也不臨時(shí)取消工件的加工。
調(diào)度目標(biāo)通常是最小化最大完工時(shí)間,即。式中表示工件的完工時(shí)間。對(duì)于以上描述的調(diào)度問(wèn)題,調(diào)度算法的任務(wù)就是在許可的計(jì)算時(shí)間內(nèi)得到最優(yōu)或是較優(yōu)的加工順序。
問(wèn)題模型
令表示作業(yè)的第個(gè)工序。和分別表示的加工起始時(shí)刻和加工時(shí)間。表示是否在第臺(tái)機(jī)器上加工：如果在第臺(tái)機(jī)器上加工，；否則，，為第臺(tái)機(jī)器的完工時(shí)間，則問(wèn)題的數(shù)學(xué)模型如下：
公式(1)為目標(biāo)函數(shù)，即優(yōu)化目標(biāo)，系統(tǒng)中使用總加工時(shí)間最短為優(yōu)化目標(biāo)。公式(2)表示1個(gè)作業(yè)只能在加工完成前一道工序后才可以加工后一道工序。公式(3)表示1個(gè)作業(yè)的第1道工序的起始加工時(shí)刻大于或等于0。公式(4)表示在1臺(tái)機(jī)床上不會(huì)同時(shí)加工1個(gè)以上的作業(yè)。
哎，小編看到數(shù)學(xué)公式就難受的毛病又犯了。
沒(méi)關(guān)系，我們接下來(lái)舉個(gè)栗子。
舉個(gè)栗子
假如此時(shí)有3個(gè)工件需要再3臺(tái)機(jī)器上加工，不同工件所需的加工工序及加工時(shí)間可以用以下公式表示：?
?
?
?
在這個(gè)例子中，作業(yè)有3道工序：它的第1道工序上標(biāo)注有(0,3)，表示第1道工序必須在第0臺(tái)機(jī)器上進(jìn)行加工，且需要3個(gè)單位的加工時(shí)間；它的第2道工序上標(biāo)注有(1,2)，其表示第2道工序必須在第1臺(tái)機(jī)器上進(jìn)行加工，且需要2個(gè)單位的加工時(shí)間；余下的同理?？偟膩?lái)說(shuō)，這個(gè)實(shí)例中共有8道工序。
下圖用甘特圖表示了一種可行解：
相信大家看了這個(gè)栗子后，大概能明白JSP要求的是什么了。這時(shí)候再注意一下前文問(wèn)題描述中的幾個(gè)點(diǎn)，就可以開始動(dòng)手解決啦！
02
禁忌搜索算法
有關(guān)禁忌搜索算法的內(nèi)容，公眾號(hào)內(nèi)有詳細(xì)教程：
干貨 |【算法】禁忌搜索算法(Tabu Search，TS)超詳細(xì)通俗解析附C++代碼實(shí)例
禁忌搜索算法求解帶時(shí)間窗的車輛路徑規(guī)劃問(wèn)題詳解（附Java代碼）
大家可以點(diǎn)擊超鏈接回顧相關(guān)知識(shí)，這里就不再細(xì)說(shuō)了。
一般而言，用禁忌搜索算法解決問(wèn)題時(shí)，需要注意的點(diǎn)無(wú)非就是以下幾個(gè)：初始解的生成；禁忌對(duì)象的選擇；鄰域動(dòng)作算子的選擇。
我們簡(jiǎn)單介紹代碼中使用的算子：
Neighbor1類：對(duì)同一機(jī)器上的兩道相鄰工序，交換兩道工序的前后順序。例如交換圖例中中和的順序。交換后，上的加工順序?yàn)椋?/p>
NeighborA類：對(duì)同一機(jī)器上的三道不同的工序，滿足和相鄰，或與相鄰。找到最早開始加工的工件的位置，按的順序加入處。例如圖例中的三道工序，交換后的加工順序?yàn)椋?/p>
禁忌表為「工序總數(shù)*工序總數(shù)」大小的二維表。對(duì)Neighbor1，禁忌邊（）；對(duì)NeighborA，禁忌邊。
如果所有邊都被禁忌，隨機(jī)選擇某一組工序進(jìn)行變換。
若執(zhí)行鄰域動(dòng)作后的新解優(yōu)于歷史最優(yōu)解，則不會(huì)被禁忌表禁忌。
03
代碼展示
代碼是github上的開源代碼，作者是Thiebout Dewitte。具體代碼比較長(zhǎng)，講解需要花很長(zhǎng)的篇幅，但是注解比較詳細(xì)，因此就不在此展示了。我們簡(jiǎn)單介紹一下輸入輸出，感興趣的朋友可以文末看到下載方式，自行下載研究。
輸入部分
輸入算例格式如下：
第一行為注釋部分，第二行數(shù)字分別為工件數(shù)、機(jī)器數(shù)。
輸出部分
運(yùn)行代碼時(shí)，可以多種運(yùn)行方式：
在Main.java文件內(nèi)選擇所需運(yùn)行模式，算例設(shè)置也在同一文件中。
測(cè)試單一算例：使用opendeurdagKulak()方法。將測(cè)試算例路徑放入Main.java中：
測(cè)試算例附帶在代碼內(nèi)。
結(jié)果生成在編譯器內(nèi)部：
前三行按照機(jī)器順序排列，cost表示總耗時(shí)，最后一行表示最長(zhǎng)耗時(shí)的加工順序。
測(cè)試多個(gè)算例，分別生成table1、2：
在上方輸入算例所在文件夾，下方輸入輸出部分文件名。
table輸出可放置在LaTeX環(huán)境中,在此就不展示了。
代碼下載
進(jìn)入公眾號(hào)輸入【JSPTS】不帶【】，即可下載對(duì)應(yīng)Java代碼。