基于GPU 的并行模擬退火算法調(diào)度應(yīng)用

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

引言

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

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

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

模擬退火算法

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

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

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

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

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

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

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

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

2）各工序時(shí)間可控，根據(jù)設(shè)計(jì)需求選擇對(duì)應(yīng)加工速度；

3）同一時(shí)刻，一臺(tái)設(shè)備只能加工一個(gè)工件；

4）不可多臺(tái)設(shè)備同時(shí)加工一個(gè)工件；

5）開(kāi)始加工后不能中斷，直至完成一個(gè)工件加工；

6）不考慮工件送往加工設(shè)備的運(yùn)輸時(shí)間。

生產(chǎn)調(diào)度的目標(biāo)是通過(guò)優(yōu)化各項(xiàng)任務(wù)在機(jī)器上的加工順序，使得m 臺(tái)機(jī)器上的n 項(xiàng)任務(wù)在完成時(shí)間盡量接近或等于最小值，即找對(duì)n 項(xiàng)任務(wù)的一個(gè)調(diào)度，使完成所有任務(wù)的時(shí)間f (n，m) 最短。

即求解

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

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

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

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

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

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

2） 目標(biāo)函數(shù)。調(diào)度問(wèn)題是要使各機(jī)械設(shè)備完成n 項(xiàng)任務(wù)所用時(shí)間ti，j 之和最大值為最小， 即需求， 其中；j=1,2,...,m;，ti，j 可根據(jù)一次調(diào)度查表確定。易證其最小值對(duì)應(yīng)于的最小值。

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

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

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

5）接受準(zhǔn)則。

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

仿真結(jié)果

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

定義機(jī)器編碼矩陣M 和工序時(shí)間矩陣T：

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

當(dāng)對(duì)一個(gè)解進(jìn)行解碼后，根據(jù)每個(gè)機(jī)器上所對(duì)應(yīng)作業(yè)工序的先后順序，確定同一機(jī)器上各作業(yè)對(duì)應(yīng)工序的先后順序，再根據(jù)每項(xiàng)作業(yè)工序之間先后的關(guān)系及作業(yè)時(shí)間，計(jì)算出每臺(tái)機(jī)器上進(jìn)行各項(xiàng)作業(yè)相關(guān)工序的開(kāi)始時(shí)間和完工時(shí)間。仿真結(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]，最大完工時(shí)間為45min。仿真得到的最優(yōu)調(diào)度方案如圖2 所示，圖中進(jìn)度條下方的標(biāo)注數(shù)字，前者表示任務(wù)序號(hào)，后者表示工序順序。

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

結(jié)論

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

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

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

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

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

編輯：黃飛