基于GPU 的并行模擬退火算法調度應用

作者：翟昌宇，李德禎，劉博（上海船舶電子設備研究所）

引言

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

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

傳統(tǒng)模擬退火算法存在收斂速度慢和求解質量低等問題，很難直接將其嵌入現代化制造企業(yè)的生產過程執(zhí)行系統(tǒng)（Manufacturing Execution System，MES），有必要優(yōu)化設計一種高效的模擬退火算法，使其可以在運行MES 的硬件平臺上，實時完成生產任務的智能調度?；?a href="http://www.wenjunhu.com/tags/gpu/" target="_blank">GPU 的異構系統(tǒng)成為現階段高性能計算體系的一種主流設計方法，與同時期的中央處理器（Central Processing Unit， CPU）相比，GPU 具備高度并行、多線程等特點，其主要用途由圖形渲染已經過渡到通用計算方面。

模擬退火算法

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

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

生產調度模型

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

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

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

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

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

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

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

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

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

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

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

即求解

，其中j=1,2,...m。

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

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

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

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

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

2） 目標函數。調度問題是要使各機械設備完成n 項任務所用時間ti，j 之和最大值為最小， 即需求， 其中；j=1,2,...,m;，ti，j 可根據一次調度查表確定。易證其最小值對應于的最小值。

所以目標函數定義為

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

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

5）接受準則。

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

仿真結果

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

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

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

當對一個解進行解碼后，根據每個機器上所對應作業(yè)工序的先后順序，確定同一機器上各作業(yè)對應工序的先后順序，再根據每項作業(yè)工序之間先后的關系及作業(yè)時間，計算出每臺機器上進行各項作業(yè)相關工序的開始時間和完工時間。仿真結果：得到最優(yōu)粒子為[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。仿真得到的最優(yōu)調度方案如圖2 所示，圖中進度條下方的標注數字，前者表示任務序號，后者表示工序順序。

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

結論

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

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

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

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

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

編輯：黃飛