云制造智能車間機床資源的再分配服務模型與解算

張富強, 李植新, 張金源

(1.長安大學道路施工技術與裝備教育部重點實驗室, 西安 710064; 2.長安大學智能制造系統研究所, 西安 710064)

云制造是一種使用云計算技術和物聯網,面向服務的網絡化智能制造新模式,通過滿足客戶的需求,來為他們所需的產品找到合適的服務[1-3]。依據中國中小型制造企業數目眾多、資源利用率不高、地理位置分散、資金投入不足和供需信息不對稱等困境,云制造模式鼓勵企業將閑置制造資源共享實現涵蓋產品全生命周期的設計、制造、物流、服務和管理等網絡化協作,變革傳統工業生產運營方式,重構產業價值鏈,提高企業核心競爭力。當前,各個企業也開始智能制造轉型的探索實踐,同時,海爾COSMOPlat、航天云網INDICS+CMSS平臺等工業物聯網平臺已經落地實施,推動著工業體系的網絡化變革。因此,基于云制造模式下的智能車間管控問題顯得尤為重要[4]。

云制造智能車間是在云制造的環境下,對原有的車間進行數字化、網絡化和智能化升級重構。由于云環境下資源類型更加多樣化,資源管理形式更加合理,資源分布更加廣泛,資源實時共享性強,云制造技術與傳統車間相結合形成云制造智能車間,利用智能優化算法對其進行優化處理,獲得更好的調度方案,在經濟和效益上都得到很大的提升。

針對云制造智能車間的研究,魯建廈等[5]考慮混流裝配與零部件加工的集成優化以及外協云任務與自制任務的協同調度,設計了一種兩級遞階結構的混合生物地理學優化算法。董海等[6]考慮柔性車間零件加工的優化及云任務與自生產任務的協同調度,提出一種改進的煙花算法來進行多目標求解。許春安等[7]構建了云環境下代表制造資源需求企業和云平臺運營方利益的多目標優化資源配置模型,并提出一種改進的NSGA-Ⅱ算法對該模型進行求解。Gao等[8]提出一種基于Pareto的分組離散和聲搜索算法優化最大完工時間和提前和延誤的時間平均值,并嵌入基于關鍵路徑和截止日期的兩種局部搜索方法,以提高開發能力。綜上,當前關于智能車間的混流生產研究較多,但對線下/線上訂單共存情況下的產線均衡問題研究較少。

結合云環境下的智能化制造車間特點,本文以線下/線上訂單共存情況下機床資源再分配為對象進行研究,以各工件在機床上加工的最大完工時間最短、機器總負荷最小、加工成本最低為多目標函數,以機床均衡率為綜合評判函數,構建了一種機床資源再分配服務模型,并采用基于Pareto外部檔案的多目標教與學優化(multi-objective teaching and learning based optimization,MOTLBO)算法對上述模型進行了多目標優化。

1 機床資源再分配服務問題描述

云制造智能車間機床資源再分配服務問題可描述為:假設K個線下/線上批次零件在M臺機床上加工,每個批次零件都有N道加工工序,每道加工工序都有多臺性能不同的候選機床可以選配。并假設以下條件成立:①每臺機床每次只能加工一個批次零件；②不同批次零件的工序之間相互獨立,沒有先后約束；③每個批次零件都是從指定的原材料庫存運輸至待加工機床緩存處,加工完畢后運至指定的成品庫；④每臺機床前后的批次零件存放緩沖區的容量都足夠大；⑤如果機床有加工任務沖突,則機床完成當前加工任務后,才能執行下一道加工任務。

2 機床資源再分配服務模型

機床資源再分配服務的目標為在給定的上述假設條件下,找到一種可行的方案,使各批次零件加工任務的最大完工時間最短、機器總負荷最小、加工成本最低。根據該規劃目標,其具體的數學模型描述如下。

2.1 變量定義

線下/線上批次零件個數設為K；工件加工工序設為N；候選機床個數設為M。

①加工任務集N={J1,J2,…,JK},i表示線下/線上批次零件的標識(1≤i≤K)；②加工任務Ji包含JNi道工序,j表示批次零件i加工工序的標識(1≤j≤JNi)；③加工工序Pi,j為任務Ji的第j道工序,則Pi={Pi,1,Pi,2,…,Pi,JNi}；④候選機床集M={M1,M2,…,Mm},m表示被選中的候選機床標識(1≤m≤M)；⑥Mti,j(fm)表示加工任務Ji的工序Pi,j在機床fm上的耗費時間；⑦Fk表示第m臺機器的動態耗費率,即每臺機器加工工件的運行成本;⑧工件i未在工序j的第m臺機床上加工時Xijm=0,工件i在工序j的第m臺機床上加工時Xijm=1。

2.2 目標函數

(1)Fti表示任務i的最后完工時間,F1表示最小化最大完工時間:

(1)

(2)加工過程所使用的生產成本F2:

(2)

(3)機器的總負荷F3:

(3)

2.3 約束函數

①K>M表示批次零件任務數大于加工機床數；②Sti,j(fm) ≥Stx,y(fm)+Mtx,y(fm)表示同一時間兩道不同的工序不能在同一機床上加工；Stx,y(fm)表示此機床前加工任務的開始加工時間節點；③Ftk≤Ltk表示最終規劃時間不能超過批次零件k的交貨期。

2.4 綜合評判函數

加工機床m再分配均衡率MTum=機床m的有效加工時間/加工任務最大完工時間,即

(4)

3 多目標教與學算法

云制造智能車間機床資源再分配服務問題屬于典型的組合優化問題,可采用智能算法進行求解。當前主流的基于進化和群體智能的優化算法都需要共同的控制參數,如種群大小、世代數、精英大小等,而不同的算法除了一般的控制參數外,還需要各自特定的算法參數。例如,遺傳算法使用變異概率、交叉概率和選擇算子；粒子群算法使用慣性權重和社會認知參數；ABC算法使用蜜蜂數量(偵察、旁觀者和使用)和限制；NSGA-Ⅱ需要交叉概率、變異概率和分布指數。適當地調整這些算法的參數是影響算法性能的一個非常關鍵的因素。對特定于算法的參數進行不適當的調整,要么會增加計算工作量,要么產生局部最優解。除了對特定于算法的參數進行調優外,還需要對常用的控制參數進行調優,從而進一步提高工作效率。而教與學優化(teaching and learning based optimization,TLBO)算法是一種基于迭代的全局搜索技術,不需要任何特定于算法的參數且求解效率高。因此,采用教與學算法對工序物流集成規劃多目標模型進行求解。

3.1 編碼與解碼

涉及的問題是在智能車間中多個線下/線上批次零件的多個工序在多臺機床上加工的問題,其中涉及的問題是工序和機床兩方面,采用分層的方式,第一層為工序層,其長度代表工件的工序數,第二層為機器層,代表每個工序所需的機器,如圖1所示,第一層的第一個數字2即表示該工件的工序2的第一道工序,第二個數字2表示工序2的第二道工序,第二層即表示加工工序所需的機器。

解碼就是將每個學生所包含的信息轉化為對應的解,上述的學生編碼中,假設每道工序所需時間相同,即可得到如圖2所示,橫坐標表示加工時間,縱坐標為機器數。

圖1 一個學生編碼Fig.1 A student code

圖2 學生解碼結果Fig.2 Student decoding results

3.2 外部檔案

外部檔案用于保存和更新獲得的最佳解決方案[9]。為適當控制外部存檔的解集空間及解集的多樣性與分布性,MOTLBO算法采用非支配排序和擁擠距離機制,對學員進行更新和比較挑選出優秀的精英個體。外部存檔的具體步驟如下。

在初始階段,隨機生成一個初始種群,其中包含N個解(成員)。然后根據非優勢概念和擁擠距離機制對初始種群進行排序。將所得解集保存在外部檔案中, 用Li(i=1,2,…,n)表示成員在檔案中的位置數組,在歸檔過程開始時,當前填充的第一個非支配前沿被添加到外部歸檔中。 在隨后的迭代中,將檔案成員a的位置數組La與當前總體中的個體b的位置數組Lb進行比較。 根據以下規則,比較結果更新存檔。

①如果位置數組La支配Lb,則保持a存檔并拒絕b；②如果Lb支持任何檔案成員的La,然后b替換外部存檔中的a；③當Lb對所有檔案成員的La不支配時,b被接受為新的檔案的成員; ④當a和b具有相同的位置向量,兩個人占據相同的存儲。 檢驗了兩種解決方案之間的優勢關系,并且刪除了已解決的解決方案,將其他解決方案保留在存檔中。

3.3 非支配排序

非支配排序用每一個解決方案與其他的解決方案想比較,以確定他們之間的主導地位,通過主導地位對所有解決方案進行排序[9]。對于每個解i,需要計算三個數值:它的主導地位Zi,支配i的解集Si,它的基數Ni。這個過程執行結束后,處在第一等級非支配前沿(Rank=1)的所有的解所對應的Ni=0。然后,對于每個對應的Ni=0的解,將其支配的解集中的每一個解所對應的Ni設置為-1。如果有任何一個解所對應的Ni變為零,就把這一個解放入一個單獨的集合F中。F中的這些解就屬于第二等級的非支配前沿(Rank=2),上述過程對集合F中的每一個解依次執行得到第三等級的非支配前沿(Rank=3)。該過程持續循環,直到確定所有前沿。

3.4 擁擠距離機制

在非支配排序操作完成后,將所有解按照升序在同一個非支配前沿進行排序目標函數值的次序。然后將任意維上目標函數值最大或最小的解距離設置為無窮大。對于其他中間解,計算每個目標函數的絕對歸一化差值作為距離值,并對兩邊的兩個相鄰解進行估計。這些絕對歸一化差異在所有客觀函數中的總和就是一個解的擁擠距離值。在計算擁擠距離之前,對每個目標函數進行歸一化。

3.5 MOTLBO流程

算法的基本流程如下,流程圖如圖3所示。

圖3 MOTLBO流程圖Fig.3 MOTLBO flow chart

步驟1 輸入:人口規模N,最大函數評估g,目標函數信息Q。

步驟2 初始化學生、設計變量和設計終止條件,在目標空間內隨機生成第一個總體。

步驟3 計算各設計變量的均值(學習成績)。

步驟4 對學生規模N進行非優勢概念和擁擠距離機制對初始種群進行排序。將所得解集保存在外部檔案中。

步驟5 教學階段。

(1)選取總體成績最好的Xtotal-kbest,i作為教師。

(2)利用式(5)、式(6)進行教學：

Di,j,k=ri(Xj,kbest,i-TfMi,j)

(5)

Tf=round[1+rand(0,1){2-1}]

(6)

式中:Di,j,k為現有各科平均成績與教師對應各科成績的差值,Xj,kbest,i為j學科中的最好學習者；Mi,j為j學科的平均成績,ri是區間[0,1]中的隨機數。

(3)評估學員的學習成績,選取成績好的進行更新。

步驟6 學習階段。

(2)利用式(7)、式(8)進行對比學習：

X″j,P,i=X′j,P,i+ri(X′j,P,i-X′j,Q,i),

IFX′total-P,j

(7)

X″j,P,i=X′j,P,i+ri(X′j,Q,i-X′j,p,i),

IFX′total-Q,j

(8)

(3)評估學員的學習成績,選取成績好的進行更新。

步驟7 基于擁擠度和非支配排序,在當前學習者群體與外部精英檔案中選擇N個學習者。

步驟8 若算法沒有滿足終止條件,則轉到步驟5。

4 案例仿真

為驗證所提出MOTLBO算法求解多目標機床資源再分配服務模型的正確性,設計如下實例進行仿真、驗證與分析。

4.1 初始條件與參數

以文獻[10]中的標準問題作為算例,簡化為一個8×7的車間調度問題。表1所示為6個線下批次零件和2個線上批次零件在7臺機器上的加工時間數據,8個批次零件各具有2道或者3道加工工序,每個批次零件都對應著不同的加工路徑。表2為每臺加工機床所需的成本。參數設置如下:學生數取100,迭代次數200,目標函數設置為3,采用最大生成作為停止準則。基于MATLAB軟件,通過GA和MOPSO算法最終進行比較,來驗證MOTLBO算法的有效性。

表1 各加工任務的工藝路線Table 1 Process route for each processing task

表2 機器對應的加工成本Table 2 Processing costs corresponding to the machine

4.2 仿真結果與分析

MOTLBO算法運行的25組pareto解集如表3所示。選取1組解展示甘特圖,如圖4所示。

p(i,j)為第i個工件的第j道工序圖4 序號1對應的甘特圖Fig.4 Gantt chart corresponding to serial number 1

表3 25組pareto解集Table 3 25 sets of pareto solution set

圖5描述了25組pareto求解結果的平均資源再分配均衡率評價。可知除了機床6的資源再分配均衡率較低外,其他資源的再分配均衡率都滿足再分配均衡性要求。原因是機床6屬于特種加工機床,只滿足特定工序的加工要求,不適于通用加工。綜合來看,MOTLBO算法具有較好的相對適應性。

圖5 平均資源再分配均衡率評價Fig.5 Average resource redistribution equalization rate evaluation

表4 算法對比Table 4 Algorithm comparison

為了驗證MOTLBO算法的性能,與其他算法進行對比分析。運行25次取平均值。它們的平均值比較結果如表4 所示。

從表4結果看,MOTLBO算法對比與GA算法有很大的提升,對比MOPSO算法有較小提升,最大完工時間分別縮短4.5、0.54 h,機器總負荷分別減少30.1、1.06 h,加工成本分別節約402.84、16.6元/h,由于是三個目標函數優化,pareto解集構成一個三維曲面,可用圖直觀地表示可行解,如圖6所示。對比GA算法,MOTLBO的搜索空間較廣,對比MOPSO算法,MOTLBO的pareto前沿較好。

圖6 3種算法的最佳結果可視化Fig.6 Visualization of the best results of the three algorithms

5 結論

提出并建立了一種支撐多品種、小批量、強交貨期的柔性生產方式下云制造智能車間機床資源再分配服務模型。以各加工任務最短完工時間、機器加工成本、機器總負荷為多目標,以資源再分配均衡率為評價因素,并采用多目標教與學優化算法進行了求解。其中,MOTLBO的核心思路是在確定學生情況下(即確定工藝路線),搜索出較優的學生(即教師),進而對其他學生進行迭代搜索出全局最優。仿真案例的結果表明MOTLBO算法在收斂性和求解效率等方面具有較大優勢,為云制造智能車間的生產規劃提供了一種有效的解決方法。