姓名：米芃
學(xué)號(hào)：16040520018
［嵌牛導(dǎo)讀］Job-shop問(wèn)題全稱車(chē)間作業(yè)調(diào)度問(wèn)題（Job-shop scheduling problem），是生產(chǎn)運(yùn)營(yíng)管理領(lǐng)域研究的重要課題。進(jìn)行作業(yè)調(diào)度問(wèn)題的研究對(duì)于有效縮短產(chǎn)品加工時(shí)間，降低產(chǎn)品生產(chǎn)成本坝疼，提高企業(yè)生產(chǎn)效率等方面有重要的實(shí)際應(yīng)用價(jià)值。
［嵌牛鼻子］高效生產(chǎn)? 退火算法
［嵌牛提問(wèn)］如何利用數(shù)學(xué)進(jìn)行高效生產(chǎn)谆沃？
［嵌牛正文］
因此在該問(wèn)題研究過(guò)程中钝凶，逐漸形成一些基準(zhǔn)問(wèn)題，即Job-shop benchmark問(wèn)題唁影，目前許多學(xué)術(shù)論文都以這些基準(zhǔn)問(wèn)題作為對(duì)比耕陷，檢驗(yàn)自己的算法是否能夠達(dá)到最優(yōu)解，或者是擊中最優(yōu)解的效率是怎么樣据沈。
上文截圖中的問(wèn)題是FT06問(wèn)題哟沫，這個(gè)問(wèn)題的最優(yōu)解即總加工時(shí)間為55。因此锌介，如果要解FT06問(wèn)題嗜诀，只需確定總加工時(shí)間為55，甚至小于55的作業(yè)排序方案孔祸。
通俗來(lái)說(shuō)隆敢，也就是通過(guò)建模調(diào)度優(yōu)化工作流程，有效減少工作時(shí)間崔慧。
以FT06問(wèn)題為例拂蝎，F(xiàn)T06問(wèn)題實(shí)際上可以看作是有6個(gè)玩具需要在6臺(tái)機(jī)器上加工，求解最優(yōu)解惶室。而把FT06問(wèn)題中的數(shù)字翻譯一下温自，則變成下面兩個(gè)矩陣：加工順序矩陣和加工時(shí)間矩陣玄货。
除此之外，工廠對(duì)玩具的加工還有特殊的流程控制：
1掉盅、一臺(tái)機(jī)器在同一時(shí)刻只能加工一個(gè)玩具也拜；
2、一個(gè)玩具在同一時(shí)刻只能在一臺(tái)機(jī)器上加工趾痘。
好了慢哈，相信大家對(duì)問(wèn)題已經(jīng)有所了解，接下來(lái)我打算用模擬退火的方式來(lái)解答求解永票。
模擬退火算法：
1983 年卵贱，S. Kirkpatrick 等人嘗試將退火思想引入到組合優(yōu)化領(lǐng)域，沒(méi)想到產(chǎn)生奇效侣集，進(jìn)而創(chuàng)造出模擬退火算法键俱。事實(shí)上，模擬退火算法是基于蒙特卡羅思想的隨機(jī)尋優(yōu)算法世分，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性编振。
通俗點(diǎn)來(lái)說(shuō)，就是材料中粒子的不同結(jié)構(gòu)對(duì)應(yīng)于粒子的不同能量水平臭埋，在高溫條件下踪央，粒子的能量較高，可以自由運(yùn)動(dòng)和重新排列瓢阴。
如果從高溫開(kāi)始非常緩慢地降溫畅蹂，粒子在每個(gè)溫度下會(huì)達(dá)到熱平衡。當(dāng)系統(tǒng)完全被冷卻時(shí)荣恐，最終將形成處于低能狀態(tài)的晶體魁莉。
退火過(guò)程即固體物質(zhì)的降溫過(guò)程中，固體物質(zhì)內(nèi)部不斷進(jìn)行重新排列募胃，并逐漸排列成最低能量狀態(tài)的結(jié)構(gòu)旗唁。
算法上的優(yōu)化過(guò)程則是當(dāng)前解內(nèi)部不斷進(jìn)行重新排列，并逐漸排列成實(shí)現(xiàn)目標(biāo)函數(shù)最小值的解（求目標(biāo)函數(shù)最大值的問(wèn)題可以轉(zhuǎn)變?yōu)榍笞钚≈档膯?wèn)題）痹束。
所以會(huì)發(fā)現(xiàn)检疫，退火過(guò)程和優(yōu)化過(guò)程存在明顯的相似性。假設(shè)材料在狀態(tài)之下的能量為E(i)祷嘶，那么材料在溫度 T 時(shí)從狀態(tài) i 進(jìn)入狀態(tài) j 遵循如下規(guī)律：
如果 E(i) ≤ E(j)屎媳，則接受該狀態(tài)被轉(zhuǎn)換夺溢。
如果 E(i) > E(j)，則狀態(tài)轉(zhuǎn)換以如下概率被接受：
其中烛谊， K 是玻爾茲曼常數(shù)风响， T 是材料溫度。
在特定溫度下丹禀，經(jīng)過(guò)充分的轉(zhuǎn)換以后状勤，材料達(dá)到熱平衡。這個(gè)時(shí)候材料處于狀態(tài)i的概率滿足玻爾茲曼分布：
其中双泪， X 表示材料當(dāng)前狀態(tài)的隨機(jī)變量持搜， S 表示狀態(tài)空間集合。
那么焙矛，當(dāng)溫度非常高時(shí)葫盼，
而當(dāng)溫度下降到很低時(shí)，設(shè)：
其中：
E2 為僅次于 Emin 的最低能量狀態(tài)蟆盹，所以：
也就是說(shuō)：
當(dāng)溫度降到極低時(shí)脱盲，材料進(jìn)入最小能量狀態(tài)的概率為1！
因此日缨，如果我們運(yùn)用退火思想放在優(yōu)化問(wèn)題上钱反，在降溫過(guò)程中問(wèn)題的解進(jìn)行充分地“熱交換”，即進(jìn)行充分地重新排列匣距，同樣可以幫助我們尋找最優(yōu)解面哥，理論上也會(huì)具有達(dá)到全局最優(yōu)解的性能！
這個(gè)算法也就是我們常說(shuō)的“模擬退火算法”毅待。這個(gè)時(shí)候又遇到了一個(gè)問(wèn)題：怎么構(gòu)造工廠作業(yè)排序優(yōu)化問(wèn)題的解尚卫？
嘗試先構(gòu)造一個(gè)可行解，序列從左到右尸红，可以翻譯為吱涉，先加工玩具1的工序1，再到加工玩具2的工序1外里，……怎爵，再到加工玩具6的工序1，再到加工玩具1的工序2盅蝗，再到加工玩具2的工序2……如此類推鳖链。
理論上說(shuō)，假如沒(méi)有機(jī)器的限制墩莫，玩具1完成加工工序1的那一刻芙委，可以開(kāi)始加工玩具2逞敷。
但是，因?yàn)橛袡C(jī)器的限制灌侣，如果玩具1的某個(gè)步驟要在機(jī)器1上加工推捐，假設(shè)此時(shí)機(jī)器1正在加工別的玩具，那么只有等到機(jī)器1完成加工的那一刻侧啼，才可以開(kāi)始加工玩具1的下一步驟牛柒。
所以，玩具 i 的第 k 個(gè)工序在機(jī)器 m 上進(jìn)行加工慨菱，其開(kāi)始時(shí)間為：
我們運(yùn)用這個(gè)原則焰络，以自然循環(huán)數(shù)列為例戴甩，按照文章最開(kāi)頭的機(jī)器約束矩陣和加工時(shí)間矩陣符喝，作一個(gè)甘特圖，說(shuō)明這個(gè)數(shù)列實(shí)際上可以表示工廠作業(yè)排序優(yōu)化問(wèn)題的解甜孤。按照這個(gè)順序來(lái)執(zhí)行加工任務(wù)协饲，以甘特圖來(lái)印證：
Step1：執(zhí)行玩具1的工序1，由機(jī)器2來(lái)執(zhí)行缴川，時(shí)間為10分鐘茉稠，對(duì)應(yīng)甘特圖機(jī)器坐標(biāo)為M2，時(shí)間坐標(biāo)為0-10把夸。
Step2：執(zhí)行玩具2的工序1而线，由機(jī)器5來(lái)執(zhí)行，時(shí)間為3分鐘恋日，對(duì)應(yīng)甘特圖機(jī)器坐標(biāo)為M5膀篮，時(shí)間坐標(biāo)為0-3。
第3-6步基本類似岂膳。我們?cè)倬劢棺匀谎h(huán)列第7-10位：1234誓竿。按照這個(gè)順序繼續(xù)執(zhí)行加工任務(wù), 以甘特圖來(lái)印證：
Step7：執(zhí)行玩具1的工序2，由機(jī)器3來(lái)執(zhí)行谈截，時(shí)間為9分鐘筷屡。玩具1工序1的結(jié)束時(shí)間為10，而且機(jī)器3先前沒(méi)有其他任務(wù)安排簸喂，所以玩具1工序2任務(wù)的甘特圖機(jī)器坐標(biāo)為M3毙死，時(shí)間坐標(biāo)為10-19。
Step8：執(zhí)行玩具2的工序2喻鳄，由機(jī)器1來(lái)執(zhí)行规哲，時(shí)間為6分鐘。玩具2工序1的結(jié)束時(shí)間為3诽表，而且機(jī)器1先前沒(méi)有其他任務(wù)安排唉锌，所以玩具2工序2任務(wù)的甘特圖機(jī)器坐標(biāo)為M1隅肥，時(shí)間坐標(biāo)為3-9。
Step 9：執(zhí)行玩具3的工序2袄简，由機(jī)器5來(lái)執(zhí)行腥放，時(shí)間為9分鐘。玩具3工序1的結(jié)束時(shí)間為5绿语，機(jī)器5先前有任務(wù)安排秃症，加工的最后時(shí)間為8，所以玩具3工序2的開(kāi)始時(shí)間為 max(5, 8) = 8吕粹，甘特圖機(jī)器坐標(biāo)為M5种柑，時(shí)間坐標(biāo)為8-17。
Step10：執(zhí)行玩具4的工序2匹耕，由機(jī)器1來(lái)執(zhí)行聚请，時(shí)間為7分鐘。玩具3工序1的結(jié)束時(shí)間為14稳其，機(jī)器1先前有任務(wù)安排驶赏，加工的最后時(shí)間為9，所以玩具4工序2的開(kāi)始時(shí)間為 max(14, 9) = 14既鞠，甘特圖機(jī)器坐標(biāo)為M1煤傍，時(shí)間坐標(biāo)為14-21。
……
流程走到這里嘱蛋，相信大家對(duì)整個(gè)過(guò)程比較明朗了蚯姆。
按照這個(gè)過(guò)程，自然循環(huán)序列就轉(zhuǎn)變?yōu)橐粡埜侍貓D洒敏，進(jìn)而可以計(jì)算出整體的完成時(shí)間龄恋。
進(jìn)一步地而言，任何自然循環(huán)序列打亂以后的序列桐玻，都可以表示這個(gè)工廠作業(yè)生產(chǎn)優(yōu)化問(wèn)題的解篙挽。
此時(shí)，我們就應(yīng)該明白解的構(gòu)造方式了镊靴。那接下來(lái)這道問(wèn)題中另一關(guān)鍵點(diǎn)铣卡，那就是老解如何變換才能產(chǎn)生新解。
由于目前解的構(gòu)造方式是一組編碼偏竟，因此可以對(duì)這組編碼進(jìn)行重排煮落，即可產(chǎn)生新解，但也需要考慮到保留當(dāng)前解的有效成分踊谋。
考慮以最簡(jiǎn)單的方式來(lái)產(chǎn)生新解蝉仇，隨機(jī)調(diào)換：在當(dāng)前解中隨機(jī)選擇兩個(gè)位置，并對(duì)調(diào)它們的數(shù)值。算法思想轿衔、解的構(gòu)造沉迹、解的產(chǎn)生，這三大問(wèn)題終于解決了害驹，我們開(kāi)始設(shè)計(jì)模擬退火的實(shí)現(xiàn)過(guò)程了：
第1步鞭呕，初始化，取一個(gè)足夠大的初始溫度 T0宛官，令當(dāng)前溫度 T = T0葫松，給定一個(gè)初始解S1。
第2步底洗，隨機(jī)調(diào)換當(dāng)前解 S1 的兩個(gè)位置的數(shù)值腋么，產(chǎn)生一個(gè)新解 S2 。
第3步亥揖，計(jì)算增量珊擂，Δ = f(S2)– f(S1)，其中f為計(jì)算解的總生產(chǎn)時(shí)間的函數(shù)徐块。
第4步未玻，如果 Δ < 0 則接受 S2 作為新的當(dāng)前解灾而，S2 = S1 胡控。否則，計(jì)算 S2 的接受概率旁趟，即在 [0,1] 這個(gè)區(qū)間上面產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)rand昼激，如果>rand，則接受 S2 作為新的當(dāng)前解锡搜，否則保留當(dāng)前解 S1 橙困。
第5步，進(jìn)行溫度衰減耕餐，這里采取 T = α × T凡傅。
第6步，如果溫度沒(méi)有衰減到設(shè)定值 Tend? 以下肠缔，繼續(xù)執(zhí)行第2~5步夏跷。
最后，設(shè)定模擬退火算法的參數(shù) T0 = 1明未，α = 0.999槽华，Tend = 10-3，執(zhí)行模擬退火算法趟妥。
而這也正是模擬退火算法的應(yīng)用所在亲雪，通過(guò)不斷的內(nèi)部調(diào)整勇凭，使得結(jié)果不斷優(yōu)化，最后達(dá)到較佳的狀態(tài)义辕。
