并行模擬退火算法在智能調度中的應用

翟昌宇，李德禎，劉 博

（上海船舶電子設備研究所，上海 201108）

1 引言

智能制造是“中國制造2025”的主攻方向，是人工智能技術深度融入制造業的產物[1]。越來越多的制造型企業，通過引入人工智能技術和智能化管理手段，逐步實現精益化管理以及企業資源最優化配置。生產調度是生產管理活動的指揮中心，伴隨著數字化、網絡化、信息化廣泛而深入的普及和應用，智能化、精益化的生產調度，也就是智能調度將會更合理地安排生產工序，縮短產品生產周期，成為企業增強核心競爭力的主要途徑。智能調度指利用人工智能技術，依靠具備自主感知、自主決策、自主控制和自主學習能力的智能化設備，結合大數據、云計算和物聯網技術，對人員、設備、任務、物料、工裝和物流等進行動態調度，提出最佳的調度方案[2]。

生產調度是一種組合優化問題，它沒有有效的多項式時間算法，被證明是一種多項式復雜程度的非確定性問 題（Non-deterministic Polynomial，NP）。1982年，Kirkpatrick等人將固體模擬退火思想引入組合優化領域，提出一種用于解大規模組合優化問題的模擬退火算法[3]。1992年，Peter J.M第一次提出采用模擬退火算法來求解作業車間調度問題[4]，近年來不斷涌現出各種改進算法用于解決車間調度問題[5-7]。

傳統模擬退火算法存在收斂速度慢和求解質量低等問題，很難直接將其嵌入現代化制造企業的生產過程執行系統（Manufacturing Execution System，MES），有必要優化設計一種高效的模擬退火算法，使其可以在運行MES的硬件平臺上，實時完成生產任務的智能調度。基于GPU的異構系統成為現階段高性能計算體系的一種主流設計方法，與同時期的中央處理器（Central Processing Unit，CPU）相比，GPU具備高度并行、多線程等特點，其主要用途由圖形渲染已經過渡到通用計算方面[8-9]。

2 模擬退火算法

模擬退火算法來源于對固體退火過程的模擬，是一種基于概率的算法。在實際求解運算過程中，模擬退火算法從某個初始解和控制參數出發，求得給定控制參數值時相對最優解，然后減小控制參數t，對當前解重復持續“產生新解-判斷-接受/舍棄”迭代過程，每經過這一過程就執行了一次蒙特卡羅（Monte-Carlo）算法。隨著控制參數t趨于零，算法終止最終求解得到組合優化問題的整體最優解。

模擬退火算法主要計算步驟：初始化參數，給定初始溫度和終止溫度；計算目標值增量通過轉移概率Pt確定是否接受從當前解i到新解j的轉移。

3 生產調度模型

生產調度工作要以生產計劃為主線開展，通過監控感知設備實時掌握生產計劃執行情況，能夠及時快速地發現生產線出現的偏差，并采取有效地應對調度策略，以減少生產過程等待時間。通過對企業資源及生產任務的合理配置和優化，保證生產過程順利高效運行，發揮最大生產效率，創造更大企業價值。

在采用模擬退火算法解決生產調度問題之前，首先建立生產調度問題數學模型。本課題生產調度問題可抽象為一條生產線由m臺機器組成，經過多道工序加工n個工件，且工序的順序是不變的。調度算法為各工件分配在各機器上的加工時間，使某些性能達到最優。假設有n項相互獨立的任務T1，…，Tn，由m臺機械設備完成各項任務的m道工序。

定義：M為機器編碼矩陣，mi，j是任務Ti的第j道工序所用的機器編號，即。T為工序時間矩陣，ti，j為作業Ti的第j道工序所需時間，即ti，j∈T，其中。

本文從機器、時間以及工序等方面進行約束，并對生產調度問題做出以下假設：

1）按照特定工序加工，只有當一道工序結束之后方可進入下一道工序；

2）各工序時間可控，根據設計需求選擇對應加工速度；

3）同一時刻，一臺設備只能加工一個工件；

4）不可多臺設備同時加工一個工件；

5）開始加工后不能中斷，直至完成一個工件加工；

6）不考慮工件送往加工設備的運輸時間。

生產調度的目標是通過優化各項任務在機器上的加工順序，使得m臺機器上的n項任務在完成時間盡量接近或等于最小值，即找對n項任務的一個調度，使完成所有任務的時間f(n，m)最短。

4 面向智能調度的并行模擬退火算法

產品生產調度時，根據設備、人員、任務以及生產線情況，通過智能調度算法對每種產品進行生產排序，為每一個子批選擇合適的加工設備，同時確定該子批開始加工時間。通過對各加工設備和開始工作時間的最優調度，最終使得完成生產任務所需要的加工時間最短。

基于模擬退火算法的生產調度，從確定問題的目標函數開始，再將初始解代入目標函數，在控制降溫系數遞減過程中，重復進行“產生新解-判斷-接受/舍棄”的迭代過程，相當于執行了一次Monte-Carlo算法過程，隨著控制參數趨于零時，得到最優智能調度方案，算法流程如圖1所示。

圖1 算法流程圖

基于模擬退火算法的智能調度問題數學模型如下：

1）解空間。一次調度即是一個正數集 ，其中1≤iw≤n，1≤w≤m×n，n是任務數，m是工序數。

2）目標函數。調度問題是要使各機械設備完成n項任務所用時間ti，j之和最大值為最小，即需求其中；可根據一次調度

所以目標函數定義為

3）新解的產生。對完成任務先后順序進行調整，即集合 中元素重新排列，形成新的調度其中 ，n是任務數，m是工序數。

4）目標差函數。由目標函數可得，伴隨于新解的目標函數差為

5）接受準則。

6）并行策略。本文建立的模擬退火算法并行計算模型分為任務級并行、數據級并行和線程級并行。采用兩塊圖形存儲器分別參與機器編碼矩陣M和工序時間矩陣T的存儲和運算。線程級并行是根據模擬退火算法的數學模型，結合圖形處理器并行計算的硬件特點，將數值計算以及邏輯判斷映射到圖形處理器細粒度并發線程的具體實現過程。

5 仿真結果

本課題設計的智能調度算法能夠適用于多品種機器零件的加工任務，目的是通過并行模擬退火算法求解得到最優調度方案。下面以鋁合金薄壁耐壓殼體加工過程為例，來驗證算法的應用效果。鋁合金薄壁耐壓殼體加工一般需要經過配料、粗車、熱處理、精車、銑床和鉗床工藝流程，是6 道相互獨立的工序。假定本課題有5個不同規格的鋁合金薄壁耐壓殼體需要加工，生產線上有6臺工藝設備，不考慮各工序之間的等待時間。仿真時采用的硬件平臺CPU為Intel i5-8300，GPU為Nvidia Tesla C2050，軟件平臺為Matlab2013，CUDA8.0。選取模擬退火初始溫度為1 000℃，終止溫度為0.001℃，循環迭代次數為2 000，降溫系數為0.98，回火迭代系數為0.15，馬爾科夫鏈長度為260。

定義機器編碼矩陣M和工序時間矩陣T：

式中：矩陣T的單位為min。

當對一個解進行解碼后，根據每個機器上所對應作業工序的先后順序，確定同一機器上各作業對應工序的先后順序，再根據每項作業工序之間先后的關系及作業時間，計算出每臺機器上進行各項作業相關工序的開始時間和完工時間。仿真結果：得到最優粒子為[4 4 5 3 1 3 2 5 1 2 4 5 3 5 2 3 4 4 5 2 1 1 2 3 5 2 3 1 1 4]，最大完工時間為45min。仿真得到的最優調度方案如圖2所示，圖中進度條下方的標注數字，前者表示任務序號，后者表示工序順序。

圖2 最優調度方案

采用本文提出的并行模擬退火算法運行1 000次求解最優粒子，算法平均運行時間為3.43 s；采用傳統模擬退火算法運行1 000次求解最優粒子，算法平均運行時間為25.27 s。通過OpenMP+CUDA的多任務調度機制，對多個串并行計算任務進行粗粒度的任務分割與調度，提高了任務間的并行率，從而使得模擬退火算法計算效率得到較大提升，使算法在執行數秒后返回一個近似最優解，即通過基于GPU的并行模擬退火算法使可實時完成生產調度問題的解算。

6 結論

生產調度問題在實際生產中具有廣泛的應用，是計算機集成制造系統中的一個關鍵環節。智能調度是制造系統運行優化的核心，通過智能調度能逐漸降低制造企業的生產成本，提升排產效果，提高經濟價值。本文在分析模擬退火算法的基礎上，將基于GPU的并行模擬退火算法用于解決生產調度問題。通過仿真試驗，實現了不同任務的智能化生產排序，并為每道工序選擇最優的加工機器。該算法思路清晰、原理簡單，證實了該算法解決生產調度問題的有效性，同時該算法具有較高的運行效率，有望應用于MES中實時完成生產任務的智能調度。

為確保智能調度算法在實際生產系統中取得更好效果，考慮下一步將重點圍繞以下兩方面繼續開展研究：

1）優化目標函數，目前的研究成果在解決車間調度問題時，所要優化的目標基本都是最大完工時間最小化，這僅僅是企業關注的一項指標，實際需求還需要考慮到工時偏差、零件報廢等問題。因此，未來在對車間調度問題的研究中，可以考慮更傾向于多目標優化。

2）改進模擬退火算法，傳統模擬算法由于前期遍歷解空間范圍有限，導致過早收斂不能得到全局最優解。通過改進Monte-Carlo準則，使算法具備跳出局部極值能力和避免參數敏感、過早收斂的問題。

3）借助大數據、云計算和物聯網技術發展，通過信息化手段將企業ERP系統、MES、知識管理及IT資源等整合互聯，實現數據信息和計算能力的共享，更好地適應企業多業務融合、協同高效的智能調度需求。