基于改進(jìn)模擬退火算法的大規(guī)模置換流水車間調(diào)度

黎 陽，李新宇+，牟健慧

(1.華中科技大學(xué) 數(shù)字制造與裝備技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074；2.煙臺大學(xué) 機(jī)電汽車工程學(xué)院，山東 煙臺 264000)

0 引言

生產(chǎn)調(diào)度是在某些生產(chǎn)條件約束下，合理確定每個加工對象的加工路徑、加工時(shí)間和操作等，以實(shí)現(xiàn)某些生產(chǎn)目標(biāo)，可以定義為“把有限的資源在時(shí)間上分配給若干任務(wù)，以滿足一個或多個目標(biāo)”[1]。生產(chǎn)調(diào)度問題大量存在于制造業(yè)中，在智能制造的趨勢下，越來越多的生產(chǎn)企業(yè)將生產(chǎn)重點(diǎn)集中到生產(chǎn)調(diào)度問題上，通過開發(fā)更好的調(diào)度算法、努力追求更優(yōu)的解決方案，來實(shí)現(xiàn)降低成本、提高生產(chǎn)效益的目標(biāo)。傳統(tǒng)的“模型+算法”式車間調(diào)度已經(jīng)十分成熟[2]，人們在相關(guān)領(lǐng)域取得了非常豐富的成果。然而隨著智能化和柔性化車間的發(fā)展，車間數(shù)據(jù)量越來越龐大，相應(yīng)的啟發(fā)式算法和元啟發(fā)式算法的解空間變得越來越復(fù)雜，對算法本身的性能提出了更高的挑戰(zhàn)。

本文研究的置換流水車間調(diào)度問題(Permutation Flowshop Scheduling Problem, PFSP)屬于經(jīng)典的NP-hard問題，從問題的求解層面看，該問題具有指數(shù)爆炸、工序相關(guān)性等復(fù)雜性；從現(xiàn)實(shí)層面看，很多工廠都采用了PFSP的生產(chǎn)模式，因此其研究具有重要的學(xué)術(shù)意義和工程應(yīng)用價(jià)值。

起初對PFSP的研究集中在尋找精確的求解算法，如解析法[3]、分枝定界法[4]、整數(shù)規(guī)劃法[5]等，目的是找到該類問題的精確最優(yōu)解。精確算法只適用于求解某些特例或者小規(guī)模問題，隨著研究的深入，需要求解稍大規(guī)模的PFSP問題時(shí)，這類算法顯得無能為力。因此，對PFSP的研究重心逐漸轉(zhuǎn)移到尋找能夠快速得到近似最優(yōu)解的啟發(fā)式算法，如Palmer法、CDS(Campbell-Dudek-Smith)法[6]、Gupta算法[7]等。啟發(fā)式算法在求解PFSP時(shí)能夠快速求得問題的解，但是一般不能得到全局最優(yōu)解，這類方法適用于求解小規(guī)模問題，對大規(guī)模問題的求解效果通常較差。Nawaz在1983年提出NEH(Nawaz-Enscore-Ham)算法[8]，這是目前對PFSP求解性能最好的啟發(fā)式算法。

精確算法和啟發(fā)式算法在求解大規(guī)模調(diào)度問題上存在一定局限性，隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，智能優(yōu)化算法開始被引入求解調(diào)度問題，有效解決了啟發(fā)式算法的不足。此后，新的智能優(yōu)化算法不斷涌現(xiàn)，并得到了迅速發(fā)展，有力促進(jìn)了PFSP的研究。比較經(jīng)典的智能優(yōu)化算法包括遺傳算法[9](Genetic Algorithm, GA)、模擬退火[10](Simulated Annealing, SA)算法、禁忌搜索[11](Tabu Search, TS)算法、粒子群優(yōu)化[12](Particle Swarm Optimization, PSO)算法等，這類算法編碼簡單，可以很方便地應(yīng)用到其他優(yōu)化問題上，而不只局限于PFSP。智能優(yōu)化方法的出現(xiàn)為調(diào)度問題的求解提供了一個全新的思路[13]。

雖然這些算法簡單有效，但是在面臨大規(guī)模生產(chǎn)調(diào)度問題(工件數(shù)>100)時(shí)，依然普遍面臨參數(shù)敏感、容易早熟陷入局部最優(yōu)等缺陷，導(dǎo)致科研成果無法與實(shí)際生產(chǎn)結(jié)合，難以產(chǎn)生實(shí)際工程價(jià)值。為解決這一問題，本文針對大規(guī)模PFSP，在SA算法框架下，改進(jìn)該方法的初始參數(shù)設(shè)計(jì)和降溫函數(shù)，使算法精度大幅上升，能夠?yàn)閷?shí)際生產(chǎn)制造提供準(zhǔn)確的建議與指導(dǎo)。

1 問題描述

1954年，Johnson[14]首次提出PFSP，并對該問題做了初步研究。自此以后，PFSP得到廣泛關(guān)注，許多學(xué)者相繼對其進(jìn)行研究，并取得了豐碩的研究成果[15-16]，大量優(yōu)秀算法被提出以解決這類問題[17-18]。

PFSP研究n個工件在m臺機(jī)器上加工的過程，每個工件在各臺機(jī)器上的加工順序一致，同時(shí)限制每個工件只能在各臺機(jī)器上加工一次，每臺機(jī)器一次只能加工一個工件，各工件在各臺機(jī)器上的加工時(shí)間已知。調(diào)度的最終目的是求得各工件在機(jī)器上的加工順序，使某項(xiàng)優(yōu)化指標(biāo)達(dá)到最優(yōu)。PFSP在其基礎(chǔ)上增加了一個約束條件，即每臺機(jī)器上各工件的加工順序相同[19]。除此之外，流水車間調(diào)度問題還有一些其他的一般性假設(shè)條件：

(1)一個工件在同一時(shí)刻不能在兩臺或兩臺以上機(jī)器上加工。

(2)加工過程中，工件采用平行移動方式，即加工完上一道工序后立即將工件送去加工下一道工序。

(3)每個工件在每臺機(jī)器上的加工時(shí)間固定，與工件的加工順序無關(guān)。

(4)工件在加工過程中不允許中斷，即工件的某個工序一旦開始加工，就必須等到完工后才能離開，中途不能停止或插入其他工序。

(5)允許工件等待和機(jī)器閑置。

Cσ1,1=tσ1；

Cσ1,j=Cσ1,j-1+tij,j=2,3,…，m；

Cσi,1=Cσi-1,1+ti1,i=2,3,…，n；

Ci,j=max(Cσi-1,j,Cσi,j-1)+tij,

i=2,3,…，n,j=2,3,…，m。

(1)

最大完工時(shí)間Cmax=Cσn,m，置換流水車間調(diào)度的目標(biāo)是確定使Cmax最小的最優(yōu)工件加工順序π=(σ1,σ2,…,σn)[21]。

流水車間調(diào)度的根本目的是在約束條件的限制下，充分利用現(xiàn)有資源，合理安排資源調(diào)度，使成本最小化或者效益最大化，因此經(jīng)典的流水車間調(diào)度問題以最大完工時(shí)間為主要調(diào)度目標(biāo)。

盡管置PFSP是流水車間調(diào)度的特例，但是它仍然是一個非常復(fù)雜的組合優(yōu)化問題，本文改進(jìn)了現(xiàn)有SA算法的性能以求解PFSP。為了檢驗(yàn)和比較算法的精度，以最大完工時(shí)間作為唯一的優(yōu)化目標(biāo)。

2 基于改進(jìn)模擬退火優(yōu)化算法的PFSP方法

SA算法的思想起源于Metropolis等于1953年提出的Metropolis準(zhǔn)則，用于判斷SA算法的解是否被接受。1983年，Kirkpatrick等成功地將退火思想引入組合優(yōu)化領(lǐng)域。在之后的大量研究表明，SA算法是一種以概率1收斂于全局最優(yōu)解的全局優(yōu)化算法[22]，因此被廣泛應(yīng)用于組合優(yōu)化問題，如NP、旅行商問題(Traveling Salesman Problem，TSP)等，而且在實(shí)際生活的車輛路徑規(guī)劃[23]、樞紐選址[24]、光纖網(wǎng)絡(luò)設(shè)置[25]等眾多優(yōu)化問題中，SA算法均發(fā)揮了巨大的作用。

2.1 編碼和解碼

編碼方式采用自然數(shù)編碼，即對于n個工件，分別采用n個互不相同的自然數(shù)一一對應(yīng)進(jìn)行標(biāo)記和編號，其中最小值為1，最大值為n，從而方便簡潔地利用數(shù)字表示每個工件的序號。在解碼上，根據(jù)最開始的編碼順序，重新將自然數(shù)對應(yīng)為相應(yīng)的工件號。

2.2 初始化

SA算法的初始解狀態(tài)S為NEH算法生成的1～n序列。選擇控制參數(shù)初值時(shí)，一般要求初始值T0的值要充分大，一開始即處于高溫狀態(tài)，且Metropolis的接收率約為1。

常規(guī)SA算法的初始溫度均為隨機(jī)設(shè)定，但是常會影響算法的最終收斂性能。因此，本文隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差|Δmax|，然后根據(jù)差值，利用初始接受概率確定初溫，相關(guān)的表達(dá)式為

T0=-|Δmax|/p0。

(2)

式中p0為初始接受概率。其余各參數(shù)值的設(shè)定與標(biāo)準(zhǔn)方法相同。

2.3 新解的生成與終止條件

在大規(guī)模問題下，單一的搜尋方式極易陷入局部最優(yōu)解，從而使解的質(zhì)量下降。為了提升算法在大規(guī)模問題下的普適性，本文采用基于概率選擇的多鄰域搜索操作協(xié)同的方式生成新解。3種鄰域搜索操作如下：

(1)二交換 在編碼序列中隨機(jī)選擇兩點(diǎn)，顛倒兩點(diǎn)間所有工件的順序。

(2)三交換 在編碼序列中隨機(jī)選擇三點(diǎn)，交換三點(diǎn)之間的兩段序列位置。

(3)點(diǎn)交換 在編碼序列中隨機(jī)選擇兩點(diǎn)，交換這兩點(diǎn)的工件位置。

為了提升算法的運(yùn)算速度，若按照上述方法所生成新解的最優(yōu)適應(yīng)度在σ代內(nèi)仍未改變，則判定算法結(jié)束，完成當(dāng)前溫度下的搜索。

2.4 協(xié)同并行搜索

標(biāo)準(zhǔn)SA算法在同一溫度下僅采用單序列進(jìn)行循環(huán)搜索，缺少個體或種群間的協(xié)同，在大規(guī)模環(huán)境下很難得到最優(yōu)解。為了提高最終解的質(zhì)量，本文引用GA種群的思想，在同一溫度下對初始序列進(jìn)行3次獨(dú)立搜索，選擇最優(yōu)值進(jìn)入下一階段。

2.5 執(zhí)行Metropolis準(zhǔn)則與記憶功能

該步驟與標(biāo)準(zhǔn)SA一致，通過Metropolis準(zhǔn)則判斷是否接受新解。在判斷完后，額外設(shè)置變量E_best保存全局最優(yōu)解，該解不受Metropolis準(zhǔn)則判定的影響，以免在之后的迭代中被取代[26]。

2.6 溫度衰減函數(shù)

與標(biāo)準(zhǔn)SA算法不同，本文啟用多普勒型衰減函數(shù)代替原本的指數(shù)函數(shù)，這種新型衰減函數(shù)可以提升大規(guī)模環(huán)境下解的收斂速度。多普勒效應(yīng)型溫度遞減曲線表達(dá)式為[27]

(3)

式中：k為迭代次數(shù)，K為總降溫次數(shù)。利用該函數(shù)不斷衰減溫度T，達(dá)到終止溫度時(shí)停止迭代，溫度衰減完畢，返回最優(yōu)目標(biāo)函數(shù)值，結(jié)束程序。

2.7 算法流程

改進(jìn)SA算法流程如圖1所示，在初始化之后，算法通過新解生成、協(xié)同搜索、執(zhí)行Metropolis準(zhǔn)則與記憶功能、溫度衰減等多個階段的不斷循環(huán)完成退火，最終得到滿意解。

3 案例驗(yàn)證和分析

本文選擇兩個數(shù)值Benchmark案例集和一個工程實(shí)際案例，用于測試改進(jìn)SA算法的性能。兩個數(shù)值案例集主要用于評價(jià)該算法的性能，并將結(jié)果與最新算法進(jìn)行對比；工程案例用于驗(yàn)證該算法解決實(shí)際問題的能力。

改進(jìn)SA算法采用MATLAB編程，運(yùn)行環(huán)境為2.2 GHz主頻的CPU，Intel Core i7處理器。為了便于比較算法性能，數(shù)據(jù)集的評價(jià)指標(biāo)為平均相對百分偏差A(yù)RPD，

(4)

式中：n為算法運(yùn)行次數(shù)，Ci為算法第i次運(yùn)行結(jié)果，UB為當(dāng)前已知最優(yōu)解。

3.1 TA數(shù)據(jù)集測試

Taillard教授在1993年提出了TA數(shù)據(jù)集，其中包括260個不同的車間調(diào)度案例[28]，如今已經(jīng)成為調(diào)度領(lǐng)域應(yīng)用最廣的測試集之一。因?yàn)楸疚闹饕鉀Q的是大規(guī)模PFSP，所以選擇案例集中工件數(shù)大于100的所有案例進(jìn)行測試(TA61～TA120)。所有問題的確定加工時(shí)間及其已知最優(yōu)解請參考網(wǎng)址http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html。

本文選擇的對比算法有混合遺傳算法(Hybrid Genetic Algorithm, HGA)[29]、利用禁忌搜索改進(jìn)的貪婪迭代法(Tabu-Mechanism Improved Iterated Greedy, TMIIG)[30]、離散的自組織遷移算法(Discrete Self-Organizing Migrating Algorithm, DSOMA)[31]、離散水波算法(Discrete Water Wave Optimization algorithm, DWWO)[32]、改進(jìn)的貪婪迭代算法(Improved Iterated Greedy Algorithm, IIGA)[33]、反向差分進(jìn)化算法(Opposition based Differential Evolution algorithm, ODDE)[34]、擴(kuò)展的人工染色體遺傳算法(extended Artificial Chromosomes Genetic Algorithm，eACGA)[35]，具體結(jié)果如表1所示。

表1 TA數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

續(xù)表1

續(xù)表1

3.2 VRF數(shù)據(jù)集測試

VRF數(shù)據(jù)集由Vallada等于2015年提出[36]，是目前最新的測試集，一共包括48個不同規(guī)模的PFSP。相對于TA數(shù)據(jù)集而言，VRF數(shù)據(jù)集包含的規(guī)模種類更多，問題規(guī)模也更加龐大，其最大規(guī)模問題可達(dá)800個工件60臺機(jī)床。因?yàn)楫?dāng)前針對VRF數(shù)據(jù)集的文獻(xiàn)均未給出每一個案例的計(jì)算結(jié)果，所以本文僅給出每一種規(guī)模問題下的ARPD值。所有問題的確定加工時(shí)間及其已知最優(yōu)解請參考網(wǎng)址http://soa.iti.es/problem-instances。針對數(shù)據(jù)集中240個大規(guī)模算例，利用改進(jìn)SA算法計(jì)算10次，求得相應(yīng)的ARPD值，然后將相同規(guī)模算例的ARPD值合并求平均值。

本文選擇的對比算法有NEH，TBD，TBKK1，TBKK2，TBFF，TBLJP1(算法均為Liu等于2017改進(jìn)后的結(jié)果[37])，具體結(jié)果如表2所示。表中PRSKE和PRD+為Liu等[37]使用的初始化算法。

表2 VRF數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

續(xù)表2

綜合表1和表2可見，本文所提改進(jìn)SA算法在整體精度上優(yōu)于其他算法，在大規(guī)模車間調(diào)度問題下，本算法能夠給出相應(yīng)的滿意解，具有實(shí)際工程價(jià)值。

3.3 車間調(diào)度優(yōu)化實(shí)例中的應(yīng)用

3.3.1 連桿部件制造的置換流水車間調(diào)度問題

某汽車發(fā)動機(jī)零部件公司的生產(chǎn)車間準(zhǔn)備制造100種不同型號的發(fā)動機(jī)連桿部件，該連桿部件的加工工藝主要有9道加工工序，不同型號的連桿部件在不同工序上的加工時(shí)間不同，相關(guān)的加工參數(shù)見文獻(xiàn)[38]。加工過程中，工件采用平行移動方式，即加工完上一道工序后立即加工下一道工序；工件在加工過程中不允許中斷，即工件的某個工序一旦開始加工，就必須等到完工后才能離開，中途不能停止或插入其他工序；所有工件必須依次完成9道工序。表中給出的加工時(shí)間已經(jīng)包括運(yùn)輸、等待、機(jī)器準(zhǔn)備和調(diào)試等全部相關(guān)時(shí)間。因?yàn)樵搶?shí)例是采用試制樣件進(jìn)行具體型號的發(fā)動機(jī)研發(fā)測試，所以暫不考慮批量生產(chǎn)的問題。

根據(jù)上述工程實(shí)例分析可知，該連桿部件制造為經(jīng)典的PFSP。將加工數(shù)據(jù)整理為加工時(shí)間矩陣T(見附錄)，目標(biāo)是求解這100種不同型號連桿的加工順序，使得總完成時(shí)間最短。

3.3.2 優(yōu)化分析

在未進(jìn)行優(yōu)化前，加工順序?yàn)?～100,依次加工，總完工時(shí)間為6 284 s。利用本文提出的改進(jìn)SA算法優(yōu)化后，調(diào)度方案的總完工時(shí)間均為5 333 s，最優(yōu)調(diào)度序列為S2，最優(yōu)調(diào)度方案的部分甘特圖如圖2所示。

S2=[69 46 65 98 62 95 24 12 60 57 27 49 54 35 87 20 73 90 96 72 66 64 50 61 59 45 34 26 86 33 48 53 11 16 89 19 40 32 77 83 28 17 52 7 43 23 21 42 99 84 18 37 82 3 1 88 67 8 29 25 55 6 80 58 13 38 91 85 81 51 92 5 30 9 74 70 56 14 71 76 44 31 68 22 36 15 10 75 39 78 93 94 41 63 2 47 97 100 4 79]。

因此在進(jìn)行工序調(diào)整優(yōu)化后，總加工時(shí)間縮短了15.1%左右，大幅提高了車間的生產(chǎn)效率，增強(qiáng)了企業(yè)的核心競爭力。

3.4 算法改進(jìn)分析

相對于元啟發(fā)式算法SA，本文所提改進(jìn)SA算法的主要優(yōu)勢是，通過參數(shù)控制達(dá)到全局搜索與局部搜索相結(jié)合的目的。正是因?yàn)閮煞N搜索方式并行推進(jìn)，所以算法在數(shù)值和工程案例中都取得了較好的結(jié)果。其中，設(shè)置初始溫度及設(shè)計(jì)溫度衰減曲線是為了增強(qiáng)算法的全局搜索能力，溫度越低，Metropolis算法保留劣解的概率就越低，這樣不利于跳出局部最優(yōu)解。因此通過臨時(shí)提升劣解的接受概率來提高算法的全局搜索能力。

協(xié)同并行搜索和記憶機(jī)制是為了提升局部搜索能力。以同一個初始解為基礎(chǔ)，進(jìn)行策略不同的并行搜索可以提升找到滿意解的概率，記憶功能是為了避免后續(xù)劣解覆蓋已經(jīng)生成的滿意解。

4 結(jié)束語

本文提出一種改進(jìn)的SA優(yōu)化算法，通過設(shè)計(jì)初始溫度的計(jì)算公式、采用基于概率選擇機(jī)制的多操作協(xié)同搜索、加入記憶功能保存最優(yōu)解及改進(jìn)溫度衰減函數(shù)等方法，提升了算法在大規(guī)模問題下的性能。通過分別對TA算例和VRF算例進(jìn)行統(tǒng)計(jì)分析，驗(yàn)證了算法在大規(guī)模調(diào)度問題下的優(yōu)勢。在工程應(yīng)用方面，將算法引入實(shí)際生產(chǎn)，結(jié)合具體的PFSP案例進(jìn)行優(yōu)化，成功提高了車間的生產(chǎn)效率，證明該算法具有實(shí)際工程意義。該算法未來可以在解決大規(guī)模問題及其他調(diào)度指標(biāo)的優(yōu)化、多個調(diào)度目標(biāo)的協(xié)同優(yōu)化等方面做進(jìn)一步研究。