基于模擬退火粒子群算法的釬焊爐調度優化

蔡志端，毛建華

（湖州師范學院 信息與工程學院，湖州 313000）

0 引言

釬焊爐是機械、冶金等行業零部件熱處理加工中的重要設備，熱處理設備能耗巨大[1,2]。對工業生產過程調度優化可降低能耗，提高生產效率，所采用的調度優化算法也獲得了廣泛的研究[3～5]。目前對釬焊爐的研究主要集中在爐內溫度控制問題，而針對釬焊爐生產調度優化問題的研究沒有涉及到。釬焊爐的生產調度水平影響著其生產加工的質量、產量和生產過程的能耗。釬焊爐生產過程能耗主要包括所耗電能及氮氣量。

近年，智能搜索算法在解決調度優化問題成效顯著[6]，主要有蟻群算法、遺傳算法、模擬退火算法、粒子群算法等等。這些算法在調度優化問題求解中都有其各自優缺點。粒子群算法有概念簡單、容易實現，快速收斂的優點，但其容易陷入局部最優，使得精度降低[7]。為彌補這一缺點，學者們進行了廣泛的研究，其中，將粒子群優化算法（Parti- cle Swarm Optimization，PSO）與具有跳出局部最優能力的模擬退火算法（simulated annealing ,SA）相結合，提出模擬退火粒子群算法（SAPSO）改進系統性能，取得了較好的應用[8,9]。論文在借鑒前人研究成果基礎上研究SAPSO在釬焊爐調度優化的具體應用，以達到良好的優化效果。論文在考慮降低釬焊爐生產能耗和提高生產效率下，建立了釬焊爐調度優化數學模型，并結合粒子群算法和模擬退火算法的優點，設計了求解模型的算法。

1 過程描述及建模

1.1 生產過程描述

在一般企業生產中，由于釬焊爐開爐溫升階段耗能大，周期長，所以釬焊爐常采取訂單定期計劃開爐，多品種分批次批量統一加工生產等方式，以保證企業利益最大化。釬焊爐生產工藝流程如圖1所示，待加工的工件擺放至釬焊爐傳送機帶后，進入噴淋釬焊劑區對工件噴淋焊劑液，然后在空氣吹落區吹落工件上多余的多釬焊劑，通過干燥區烘干釬焊劑和工件表面水分后再進入加熱區[10]。工件在加熱區要通過多個不同溫度環境的加熱段進行加熱焊接。工件從加熱區出來，最后進入冷卻區進行水冷、風冷區進行冷卻后取下，完成加工。由于企業常按訂單定期計劃開爐進行生產，在生產計劃安排中，企業按訂單所要求的加工產品的種類進行分類，將相同或相近的產品作為一類，統一加工。圖中D1，D2，D3分別代表三個不同的工件類別。

從圖1可知，每個加工工件都要經歷5個加工單元，每一個加工單元又對應不同的加工設備。釬焊爐調度問題優化目標就是在確定的加工工件類別的基礎上，合理設計不同類別工件的加工順序使其在不同加工設備上的駐留時間最小，從而縮短全部產品的加工時間，降低能耗，提高生產效率。

圖1 釬焊爐生產基本流程

釬焊爐調度過程，需要考慮以下七個約束條件1）待加工工件各類有i種，且都需要經歷5個連續生產單元；2）第i類工件第j個工件在第m個生產單元中加工時開始加工的時間為Bijm，加工完成的時間為Eijm；3）工件加工最小時間，根據其種類不同都有其規定的加工時間及加工溫度。每一類工件在每個加工單元駐留時間需要達到其在該單元滿足加工工藝要求的最小駐留時間（該時間為已知），加工溫度滿足加工工藝要求，且每一類加工工件加工最小時間相同；4）每類工件在各個加工單元中按先進先出的順序執行，只有當前一類加工工件離開加工單元時，新的工件才能進入；5）不考慮釬焊爐停機等待情況；6）每一個加工單元，同一時刻只能加工同一類工件；7）在加工初始時刻，任意一類工件都有可能被選擇加工。

1.2 釬焊爐調度的數學模型

根據1.1節描述，可建立釬焊爐調度問題的數學模型，模型中主要的參數定義如下：

i：待加工工件類別編號，i=1,2,3,…；

Di：第i類待加工工件集合，設不同類別加工工件集合交集為空；

j：Di中待加工工件的編號，j=1,2,3,…,;

m：釬焊爐加工單元編號，m=1,2,3,4,5;

Hm：第m號加工單元可同時加工的工件數量；

Bijm：第i類第j個工件進入第m個加工單元的起始時間；

Eijm：第i類第j個工件加工完畢后離開第m個加工單元的時間；

STim：第i類工件在第m個加工單元中滿足加工工藝需要的最小加工時間;

Tijm：第i類第j個工件在第m個加工單元駐留時間；

Φim：第i類工件在第m個加工單元中加工狀態，為1表示在加工，為0表示不在加工；

δijm：第i類工件第j個工件在第m個加工單元中加工狀態，為1表示在加工，為0表示不在加工；

基于上述定義，調度模型如下[5]：

以上模型中，目標函數（1）表所示有待加工工件加工時間最小化；約束條件（2）表示每一次中能選擇同一類加工工件進行加工；約束（3）表示每一件加工工件都可被選擇到每個加工單元加工且只能選擇一次；約束（4）表示每一個加工工件在某個加工單元的駐留時間不能小于額定最小加工時間； 約束（5）只有當前加工工件離開加工單元時，新的工件才能進入。

2 求解釬焊爐調度的SAPSO算法

PSO算法是一種模擬鳥群覓食行為的群體智能優化計算技術，是一種基于迭代的并行優化搜索工具[11]。在PSO算法中，設置一群“粒子”并將每個粒子看作是優化問題的一個可行解。被優化的函數確定每個“粒子”的適應度值，以此評價粒子的好壞。“粒子”根據自己的速度和位置變量計算其在可行解空間中運動的方向和距離；粒子將跟蹤自身迄今為至找到的最優解和整個種群迄今為止至找到的最優解更新自己的位置與速度；通過多次迭代運算找到最終最優解。粒子i在第t次迭代的狀態屬性可由其位置與速度變量表示。位置變量表示為：別為搜索空間的下限及上限。速度變量表示為：別為粒子在可行解空間運動時速度的最小值與最大值。算法中粒子的速度和位置更新公式分別為

其中ω為慣性權重，合適的慣性權重可平衡全局搜索和局部搜索能力，實現在更少迭代次數下提高尋優性能，目前常采用線性策略、非線性策略兩種ω調整策略；c1和c2為學習因子，它反映了粒子間信息交流強度，通過取 c1=c2∈ [1，2，5]；r1和r2為0到1之間均勻分布的隨機數；Pid為個體最優位置；Pgd為全局最優值。

將模擬退火算法應用于PSO中粒子的速度和位置更新過程。PSO每次迭代中的適應度值根據模擬退火算法中的Metropolis準則按一定概率允許接收非優化解，使算法從局部極值區域中跳出，最終收斂于全局最優解，按下以步聚實現SAPSO算法，搜索最優解[12]：

1）參數初始化，包括粒子數m，慣性權重ω，迭代次數t，學習因子c1和c2,搜索空間的下限及上退火速度α，隨機設置粒子的位置初始值xi(t)和速度初始值Vi(t)，個體最優值pid和全局最優值pgd；

2）根據被優化的函數及其約束條件，計算每個粒子的適應度值f ()，并分別與個體最優值和全局最優值比較，選擇更優值，以對pid和pgd進行更新；

3 實驗與結果分析

3.1 粒子編碼與適應度函數

SAPSO應用于釬焊爐調度，首先要建立位置矢量與調度方案之間的映射，即尋找一種表達方式，使粒子與解對應。考慮到釬焊爐加工過程是流水作業，同一加工單元只加工同類別的工件，且待加工工件數量，加工單元最大加工數量和最小加工時間已知。對粒子采用矩陣編碼[13]，如下所示：

矩陣A是所有待加工工件對應5個加工單元的編碼。矩陣中每一個元素值aij表示第i個工件在第j個加工單元中加工的順序號，為一整數。A矩陣每一行為某一類中某個工件在各加工單元加工順序，每一列對應著一個加工單元。由于釬焊爐各加工單元是流水線作業，故矩陣A中每一列的數值就代表所有工件加工的順序，且對于同一行，各列的值相等。解碼時，提取矩陣A中的任何一列的數值，其值表示元件加工順序。在搜索矩陣A最優值時，從第二個生產單元開始，必須考慮工件在前后兩個個生產單元的最小加工時間差，將該時間差與工件加工順序相結合。由于各工件在某加工單元標準加工時間確定，所有待加工工件在各加工單元的標準加工時間表示為：

其中，STim表示第i個加工工件在第m個加工單元上的標準加工時間。則所有待加工工件在加工過程中，相鄰兩個加工單元加工時間差總和可表示為：

調度優化則可轉換成求U的最小極值。對于調度數學模型中的約束項，可在目標函數中增加一項可以映射約束條件的懲罰像，構成一個無約束的廣義目標函數。因此論文中釬焊爐調度優化的適應度函數即轉換成是一種對B矩陣排序的問題。

3.2 實驗結果

將論文中的算法應用于釬焊爐調度優化。算法中主要參數進行適當設置：最大迭代次數為800，群體粒子數為50；學習因子C1和C2取1.8，慣性權重ω∈[0.9, 0.4]，

模擬退火中退火起至溫度T和T0分別取8000和0.03，退火速度α取0.9。采用某企業釬焊爐加工工件數據進行仿真實驗，針對不同批次數據分別按標準PSO算法和SAPSO算法仿真，并與無調度優化前加工時間進行對比，結果如表1所示。

表1結果表明SAPSO算法達到優化目的。當工件類別量多，加工時間較長時，SAPSO算法比標準PSO算法效果更好。

表1 不同批次工件的調度結果

4 結論

1）將模擬退火粒子群算法應用于釬焊爐生產調度。該混合算法在PSO算法中應用模擬退火機制，提高搜索過程中跳出局部極值的能力。

2）研究SAPSO算法在釬焊爐生產調度中的實際問題，給出粒子編碼，目標函數及約束條件以及SAPSO具體實現步驟。

3）通過數值仿真實驗驗證論文中SAPSO算法的可行性和有效性，為工業熱處理設置生產過程調度優化提供一種有效的方法。

[1] 管根笙. 熱處理電爐的節能技術[J]. 熱處理技術與裝備,2007, (4): 58-60.

[2] 鐘建安, 艾楠, 戴惠良, 周澤斌. 基于DCS的大型大型真空釬焊爐監控系統開發[J]. 機床與液壓, 2009, 37 (4):109-111.

[3] 劉小華, 林杰, 鄧可. 基于遺傳粒子群混合的可重入生產調度優化[J]. 同濟大學學報, 2011, 39 (5): 726-730.

[4] 寧樹實, 王偉, 劉全利. 鋼鐵生產中的加熱爐優化調度算法研究[J]. 控制與決策. 2006, 21. (10): 1138-1141.

[5] 譚園園, 寧健海, 劉士新. 加熱爐優化調度模型及算法研究[J]. 控制理論與應用. 2011, 28: (11): 1149-1557.

[6] 唐海波, 葉春明. 仿生群智能算法在生產調度中的應用綜述[J]. 工業工程, 2010, 13(3): 1- 5.

[7] Lotfi K G, Sherif A M,A shraf ON. A partic-le swarm-based genetic algorithm for schedul-ing in an agile environment[J].Computers&Industrial Engineering, 2008, 55 (3): 707.

[8] 王華秋, 曹長修. 基于模擬退火的并行粒子群優化研究[J].控制與決策, 2005, 20(5): 500-504.

[9] 焦巍, 劉光斌, 張艷紅. 求解約束優化的模擬退火PSO算法[J]. 系統工程與電子技術, 2010, 32(7): 1532-1536.

[10] 魏東. NB式全自動氮氣保護釬焊爐的結構及含氧量的控制[J]. 機械設計與制造, 2007, 2(3): 47-49.

[11] kennedy James, Eberhart Russell. Particle swarm optimization[C] //IEEE International Conference on Neural Networks, Perth, Austr-alia: 1995: 1942-1948.

[12] 李麗, 牛奔. 粒子群優化算法[M]. 北京: 冶金工業出版社, 2009: 88-89.

[13] 張建軍, 彭來麗, 張利, 劉小平. 基于改進粒子群算法的多目銅卷加工生產調度研究[J]. 中國機械工程, 2011, 22(17):2061-2066.