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

張富強, 李植新, 張金源

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

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

云制造智能車間是在云制造的環(huán)境下,對原有的車間進行數(shù)字化、網(wǎng)絡(luò)化和智能化升級重構(gòu)。由于云環(huán)境下資源類型更加多樣化,資源管理形式更加合理,資源分布更加廣泛,資源實時共享性強,云制造技術(shù)與傳統(tǒng)車間相結(jié)合形成云制造智能車間,利用智能優(yōu)化算法對其進行優(yōu)化處理,獲得更好的調(diào)度方案,在經(jīng)濟和效益上都得到很大的提升。

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

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

1 機床資源再分配服務(wù)問題描述

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

2 機床資源再分配服務(wù)模型

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

2.1 變量定義

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

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

2.2 目標函數(shù)

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

(1)

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

(2)

(3)機器的總負荷F3:

(3)

2.3 約束函數(shù)

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

2.4 綜合評判函數(shù)

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

(4)

3 多目標教與學(xué)算法

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

3.1 編碼與解碼

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

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

圖1 一個學(xué)生編碼Fig.1 A student code

圖2 學(xué)生解碼結(jié)果Fig.2 Student decoding results

3.2 外部檔案

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

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

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

3.3 非支配排序

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

3.4 擁擠距離機制

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

3.5 MOTLBO流程

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

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

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

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

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

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

步驟5 教學(xué)階段。

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

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

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

(5)

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

(6)

式中:Di,j,k為現(xiàn)有各科平均成績與教師對應(yīng)各科成績的差值,Xj,kbest,i為j學(xué)科中的最好學(xué)習者；Mi,j為j學(xué)科的平均成績,ri是區(qū)間[0,1]中的隨機數(shù)。

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

步驟6 學(xué)習階段。

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

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)評估學(xué)員的學(xué)習成績,選取成績好的進行更新。

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

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

4 案例仿真

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

4.1 初始條件與參數(shù)

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

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

表2 機器對應(yīng)的加工成本Table 2 Processing costs corresponding to the machine

4.2 仿真結(jié)果與分析

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

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

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

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

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

表4 算法對比Table 4 Algorithm comparison

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

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

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

5 結(jié)論

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