作者:翟昌宇,李德禎,劉博(上海船舶電子設(shè)備研究所)
引言
智能制造是“中國制造2025”的主攻方向,是人工智能技術(shù)深度融入制造業(yè)的產(chǎn)物。越來越多的制造型企業(yè),通過引入人工智能技術(shù)和智能化管理手段,逐步實(shí)現(xiàn)精益化管理以及企業(yè)資源最優(yōu)化配置。生產(chǎn)調(diào)度是生產(chǎn)管理活動的指揮中心,伴隨著數(shù)字化、網(wǎng)絡(luò)化、信息化廣泛而深入的普及和應(yīng)用,智能化、精益化的生產(chǎn)調(diào)度, 也就是智能調(diào)度將會更合理地安排生產(chǎn)工序,縮短產(chǎn)品生產(chǎn)周期,成為企業(yè)增強(qiáng)核心競爭力的主要途徑。智能調(diào)度指利用人工智能技術(shù),依靠具備自主感知、自主決策、自主控制和自主學(xué)習(xí)能力的智能化設(shè)備,結(jié)合大數(shù)據(jù)、云計(jì)算和物聯(lián)網(wǎng)技術(shù),對人員、設(shè)備、任務(wù)、物料、工裝和物流等進(jìn)行動態(tài)調(diào)度,提出最佳的調(diào)度方案。
生產(chǎn)調(diào)度是一種組合優(yōu)化問題,它沒有有效的多項(xiàng)式時(shí)間算法,被證明是一種多項(xiàng)式復(fù)雜程度的非確定性問題(Non-deterministic Polynomial,NP)。1982 年, Kirkpatrick 等人將固體模擬退火思想引入組合優(yōu)化領(lǐng)域, 提出一種用于解大規(guī)模組合優(yōu)化問題的模擬退火算法。1992 年,Peter J.M 第一次提出采用模擬退火算法來求解作業(yè)車間調(diào)度問題,近年來不斷涌現(xiàn)出各種改進(jìn)算法用于解決車間調(diào)度問題。
傳統(tǒng)模擬退火算法存在收斂速度慢和求解質(zhì)量低等問題,很難直接將其嵌入現(xiàn)代化制造企業(yè)的生產(chǎn)過程執(zhí)行系統(tǒng)(Manufacturing Execution System,MES),有必要優(yōu)化設(shè)計(jì)一種高效的模擬退火算法,使其可以在運(yùn)行MES 的硬件平臺上,實(shí)時(shí)完成生產(chǎn)任務(wù)的智能調(diào)度。基于GPU 的異構(gòu)系統(tǒng)成為現(xiàn)階段高性能計(jì)算體系的一種主流設(shè)計(jì)方法,與同時(shí)期的中央處理器(Central Processing Unit, CPU)相比,GPU 具備高度并行、多線程等特點(diǎn),其主要用途由圖形渲染已經(jīng)過渡到通用計(jì)算方面。
模擬退火算法
模擬退火算法來源于對固體退火過程的模擬,是一種基于概率的算法。在實(shí)際求解運(yùn)算過程中,模擬退火算法從某個初始解和控制參數(shù)出發(fā),求得給定控制參數(shù)值時(shí)相對最優(yōu)解,然后減小控制參數(shù)t,對當(dāng)前解重復(fù)持續(xù)“產(chǎn)生新解- 判斷- 接受/ 舍棄”迭代過程,每經(jīng)過這一過程就執(zhí)行了一次蒙特卡羅(Monte-Carlo)算法。隨著控制參數(shù)t 趨于零,算法終止最終求解得到組合優(yōu)化問題的整體最優(yōu)解。
模擬退火算法主要計(jì)算步驟:初始化參數(shù),給定初始溫度和終止溫度;計(jì)算目標(biāo)值增量;通過轉(zhuǎn)移概率Pt 確定是否接受從當(dāng)前解i 到新解j 的轉(zhuǎn)移。?
生產(chǎn)調(diào)度模型
生產(chǎn)調(diào)度工作要以生產(chǎn)計(jì)劃為主線開展,通過監(jiān)控感知設(shè)備實(shí)時(shí)掌握生產(chǎn)計(jì)劃執(zhí)行情況,能夠及時(shí)快速地發(fā)現(xiàn)生產(chǎn)線出現(xiàn)的偏差,并采取有效地應(yīng)對調(diào)度策略, 以減少生產(chǎn)過程等待時(shí)間。通過對企業(yè)資源及生產(chǎn)任務(wù)的合理配置和優(yōu)化,保證生產(chǎn)過程順利高效運(yùn)行,發(fā)揮最大生產(chǎn)效率,創(chuàng)造更大企業(yè)價(jià)值。
在采用模擬退火算法解決生產(chǎn)調(diào)度問題之前,首先建立生產(chǎn)調(diào)度問題數(shù)學(xué)模型。本課題生產(chǎn)調(diào)度問題可抽象為一條生產(chǎn)線由m 臺機(jī)器組成,經(jīng)過多道工序加工n 個工件,且工序的順序是不變的。調(diào)度算法為各工件分配在各機(jī)器上的加工時(shí)間,使某些性能達(dá)到最優(yōu)。假設(shè)有n 項(xiàng)相互獨(dú)立的任務(wù)T1,…,Tn,由m 臺機(jī)械設(shè)備完成各項(xiàng)任務(wù)的m 道工序。
定義:M 為機(jī)器編碼矩陣,mi,j 是任務(wù)Ti 的第j 道工序所用的機(jī)器編號,即。T 為工序時(shí)間矩陣,ti,j 為作業(yè)Ti 的第j 道工序所需時(shí)間,即ti,j ∈ T,其中。
本文從機(jī)器、時(shí)間以及工序等方面進(jìn)行約束,并對生產(chǎn)調(diào)度問題做出以下假設(shè):
1)按照特定工序加工,只有當(dāng)一道工序結(jié)束之后方可進(jìn)入下一道工序;
2)各工序時(shí)間可控,根據(jù)設(shè)計(jì)需求選擇對應(yīng)加工速度;
3)同一時(shí)刻,一臺設(shè)備只能加工一個工件;
4)不可多臺設(shè)備同時(shí)加工一個工件;
5)開始加工后不能中斷,直至完成一個工件加工;
6)不考慮工件送往加工設(shè)備的運(yùn)輸時(shí)間。
生產(chǎn)調(diào)度的目標(biāo)是通過優(yōu)化各項(xiàng)任務(wù)在機(jī)器上的加工順序,使得m 臺機(jī)器上的n 項(xiàng)任務(wù)在完成時(shí)間盡量接近或等于最小值,即找對n 項(xiàng)任務(wù)的一個調(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)線情況,通過智能調(diào)度算法對每種產(chǎn)品進(jìn)行生產(chǎn)排序, 為每一個子批選擇合適的加工設(shè)備,同時(shí)確定該子批開始加工時(shí)間。通過對各加工設(shè)備和開始工作時(shí)間的最優(yōu)調(diào)度,最終使得完成生產(chǎn)任務(wù)所需要的加工時(shí)間最短。
基于模擬退火算法的生產(chǎn)調(diào)度,從確定問題的目標(biāo)函數(shù)開始,再將初始解代入目標(biāo)函數(shù),在控制降溫系數(shù)遞減過程中,重復(fù)進(jìn)行“產(chǎn)生新解- 判斷- 接受/ 舍棄” 的迭代過程,相當(dāng)于執(zhí)行了一次Monte-Carlo 算法過程, 隨著控制參數(shù)趨于零時(shí),得到最優(yōu)智能調(diào)度方案,算法流程如圖1 所示。
基于模擬退火算法的智能調(diào)度問題數(shù)學(xué)模型如下:
1)解空間。一次調(diào)度即是一個正數(shù)集, 其中1 ≤ iw ≤ n,1 ≤ w ≤ m×n,n 是任務(wù)數(shù),m 是工序數(shù)。
2) 目標(biāo)函數(shù)。調(diào)度問題是要使各機(jī)械設(shè)備完成n 項(xiàng)任務(wù)所用時(shí)間ti,j 之和最大值為最小, 即需求, 其中;j=1,2,...,m;,ti,j 可根據(jù)一次調(diào)度查表確定。易證其最小值對應(yīng)于的最小值。
所以目標(biāo)函數(shù)定義為
3)新解的產(chǎn)生。對完成任務(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ù)級并行、數(shù)據(jù)級并行和線程級并行。采用兩塊圖形存儲器分別參與機(jī)器編碼矩陣M 和工序時(shí)間矩陣T 的存儲和運(yùn)算。線程級并行是根據(jù)模擬退火算法的數(shù)學(xué)模型,結(jié)合圖形處理器并行計(jì)算的硬件特點(diǎn),將數(shù)值計(jì)算以及邏輯判斷映射到圖形處理器細(xì)粒度并發(fā)線程的具體實(shí)現(xiàn)過程。
仿真結(jié)果
本課題設(shè)計(jì)的智能調(diào)度算法能夠適用于多品種機(jī)器零件的加工任務(wù),目的是通過并行模擬退火算法求解得到最優(yōu)調(diào)度方案。下面以鋁合金薄壁耐壓殼體加工過程為例,來驗(yàn)證算法的應(yīng)用效果。鋁合金薄壁耐壓殼體加工一般需要經(jīng)過配料、粗車、熱處理、精車、銑床和鉗床工藝流程,是6 道相互獨(dú)立的工序。假定本課題有5 個不同規(guī)格的鋁合金薄壁耐壓殼體需要加工,生產(chǎn)線上有6 臺工藝設(shè)備,不考慮各工序之間的等待時(shí)間。仿真時(shí)采用的硬件平臺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。
定義機(jī)器編碼矩陣M 和工序時(shí)間矩陣T:
式中:矩陣T 的單位為min。
當(dāng)對一個解進(jìn)行解碼后,根據(jù)每個機(jī)器上所對應(yīng)作業(yè)工序的先后順序,確定同一機(jī)器上各作業(yè)對應(yīng)工序的先后順序,再根據(jù)每項(xiàng)作業(yè)工序之間先后的關(guān)系及作業(yè)時(shí)間,計(jì)算出每臺機(jī)器上進(jìn)行各項(xiàng)作業(yè)相關(guān)工序的開始時(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ù)序號,后者表示工序順序。
采用本文提出的并行模擬退火算法運(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。通過OpenMP+CUDA 的多任務(wù)調(diào)度機(jī)制,對多個串并行計(jì)算任務(wù)進(jìn)行粗粒度的任務(wù)分割與調(diào)度,提高了任務(wù)間的并行率,從而使得模擬退火算法計(jì)算效率得到較大提升,使算法在執(zhí)行數(shù)秒后返回一個近似最優(yōu)解, 即通過基于GPU 的并行模擬退火算法使可實(shí)時(shí)完成生產(chǎn)調(diào)度問題的解算。
結(jié)論
生產(chǎn)調(diào)度問題在實(shí)際生產(chǎn)中具有廣泛的應(yīng)用,是計(jì)算機(jī)集成制造系統(tǒng)中的一個關(guān)鍵環(huán)節(jié)。智能調(diào)度是制造系統(tǒng)運(yùn)行優(yōu)化的核心,通過智能調(diào)度能逐漸降低制造企業(yè)的生產(chǎn)成本,提升排產(chǎn)效果,提高經(jīng)濟(jì)價(jià)值。本文在分析模擬退火算法的基礎(chǔ)上,將基于GPU 的并行模擬退火算法用于解決生產(chǎn)調(diào)度問題。通過仿真試驗(yàn),實(shí)現(xiàn)了不同任務(wù)的智能化生產(chǎn)排序,并為每道工序選擇最優(yōu)的加工機(jī)器。該算法思路清晰、原理簡單,證實(shí)了該算法解決生產(chǎn)調(diào)度問題的有效性,同時(shí)該算法具有較高的運(yùn)行效率,有望應(yīng)用于MES 中實(shí)時(shí)完成生產(chǎn)任務(wù)的智能調(diào)度。
為確保智能調(diào)度算法在實(shí)際生產(chǎn)系統(tǒng)中取得更好效果,考慮下一步將重點(diǎn)圍繞以下兩方面繼續(xù)開展研究:
1)優(yōu)化目標(biāo)函數(shù),目前的研究成果在解決車間調(diào)度問題時(shí),所要優(yōu)化的目標(biāo)基本都是最大完工時(shí)間最小化, 這僅僅是企業(yè)關(guān)注的一項(xiàng)指標(biāo),實(shí)際需求還需要考慮到工時(shí)偏差、零件報(bào)廢等問題。因此,未來在對車間調(diào)度問題的研究中,可以考慮更傾向于多目標(biāo)優(yōu)化。
2)改進(jìn)模擬退火算法,傳統(tǒng)模擬算法由于前期遍歷解空間范圍有限,導(dǎo)致過早收斂不能得到全局最優(yōu)解。通過改進(jìn)Monte-Carlo 準(zhǔn)則,使算法具備跳出局部極值能力和避免參數(shù)敏感、過早收斂的問題。
3)借助大數(shù)據(jù)、云計(jì)算和物聯(lián)網(wǎng)技術(shù)發(fā)展,通過信息化手段將企業(yè)ERP 系統(tǒng)、MES、知識管理及IT 資源等整合互聯(lián),實(shí)現(xiàn)數(shù)據(jù)信息和計(jì)算能力的共享,更好地適應(yīng)企業(yè)多業(yè)務(wù)融合、協(xié)同高效的智能調(diào)度需求。
編輯:黃飛
-
云計(jì)算
+關(guān)注
關(guān)注
39文章
7782瀏覽量
137379 -
gpu
+關(guān)注
關(guān)注
28文章
4735瀏覽量
128917 -
物聯(lián)網(wǎng)
+關(guān)注
關(guān)注
2909文章
44608瀏覽量
373052 -
智能制造
+關(guān)注
關(guān)注
48文章
5556瀏覽量
76329
原文標(biāo)題:上海船舶電子設(shè)備研究所:并行模擬退火算法在智能調(diào)度中的應(yīng)用
文章出處:【微信號:CADCAM_beijing,微信公眾號:智能制造IMS】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
相關(guān)推薦
評論