并行模擬退火算法在智能調(diào)度中的應用

翟昌宇，李德禎，劉 博

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

1 引言

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

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

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

2 模擬退火算法

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

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

3 生產(chǎn)調(diào)度模型

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

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

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

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

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

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

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

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

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

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

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

4 面向智能調(diào)度的并行模擬退火算法

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

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

圖1 算法流程圖

基于模擬退火算法的智能調(diào)度問題數(shù)學模型如下：

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

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

所以目標函數(shù)定義為

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

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

5）接受準則。

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

5 仿真結(jié)果

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

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

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

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

圖2 最優(yōu)調(diào)度方案

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

6 結(jié)論

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

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

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

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

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