三層虛擬工作流模型的非線性制造工藝多目標優(yōu)化算法研究

羅智勇 王靜遠 謝志強 孫廣路 楊 旭

伴隨著第四次工業(yè)革命的步伐,中國的制造業(yè)已經(jīng)進入供給側(cè)改革和產(chǎn)業(yè)升級的關鍵時期.產(chǎn)品的制造由傳統(tǒng)的簡單線性工藝粗加工逐漸向現(xiàn)代的復雜非線性即反饋工藝細加工轉(zhuǎn)變,其制造過程更具復雜性、多變性和高效性等特點[1].復雜產(chǎn)品的非線性細加工涉及生產(chǎn)車間、工藝設計及調(diào)度等多部門的協(xié)同控制,其過程具有反復性,必將產(chǎn)生大量的動態(tài)信息,若不能及時優(yōu)化這些信息勢必會降低產(chǎn)品的競爭力.提高產(chǎn)品的競爭力,其核心是解決制造工藝的多目標動態(tài)優(yōu)化問題.生產(chǎn)時間、產(chǎn)品質(zhì)量和費用成本是制造工藝的重要參數(shù),如何動態(tài)平衡這些參數(shù)使其最優(yōu)本身就是一個NP (Non-deterministic polynomial)難題[2],若增加工藝的多次反饋,即非線性等因素,則其優(yōu)化過程將變得更加困難.“中國制造2025”和“新一代人工智能”為復雜產(chǎn)品非線性工藝多目標優(yōu)化帶來了機遇和指明了方向.智能制造[3]只有在充分融合非線性生產(chǎn)工藝的特點和多目標要求的約束下,將人工智能、云計算、建模仿真和優(yōu)化控制等信息處理技術與具體的生產(chǎn)資源相結合,開發(fā)出有效的智能優(yōu)化調(diào)度算法,才可能使制造業(yè)實現(xiàn)跨越式的發(fā)展,滿足時代的要求.科學工作流以其具備建模仿真能力強、資源參數(shù)量化準確、智能算法及優(yōu)化調(diào)度易開發(fā)等特點,使其在智能制造領域中具有獨特的優(yōu)勢.因此,研究如何利用科學工作流實現(xiàn)非線性制造工藝的多目標優(yōu)化調(diào)度具有非常重要的理論和現(xiàn)實意義.

近些年,將工作流技術應用在線性生產(chǎn)工藝的多目標優(yōu)化調(diào)度,國內(nèi)外學者進行了一定的研究.Arabnejad 等[4]面向服務計算,使用服務質(zhì)量(Quality of service,QoS)付費的量化約束,提出了一種異構預算約束調(diào)度算法,該算法可以保證在用戶指定的預算范圍內(nèi)執(zhí)行成本,并最大限度地縮短用戶應用程序的執(zhí)行時間,從而較好地完成了制造工藝異構系統(tǒng)的多目標任務優(yōu)化調(diào)度;Lv 等[5]在分析了產(chǎn)品制造工藝流程的制約關系后,提出了一種工作流優(yōu)化模型,該模型可進一步縮短制造工期,使工藝達到最優(yōu),從而提高了產(chǎn)品競爭力;Mollajafari 等[6]為解決云制造時間成本最優(yōu)問題,利用云計算和遺傳算法等技術提出了一種新的基因型到表型映射的工作流調(diào)度算法,該算法利用設定的資源調(diào)度代價函數(shù)有效地解決了限定時間下成本最優(yōu)的問題,隨后驗證了該算法的收斂速度等性能;Koch 等[7]為解決醫(yī)用模型制造工藝中的磨削精度和可靠性等問題,通過分析銑削的鑄造數(shù)據(jù)集與主參考數(shù)據(jù)集的映射變化規(guī)律,提出了一種數(shù)字工作流銑削模型,統(tǒng)計分析發(fā)現(xiàn)該模型可有效地解決醫(yī)用模型制造的多目標動態(tài)調(diào)度問題;Kianpisheh 等[8]將約束工作流與蟻群算法相結合,通過定義工期和成本因素變量完成了對云制造工藝的優(yōu)化調(diào)度;Chirkin 等[9]為解決工作流執(zhí)行時間估計中的常見問題,提出了一種考慮工作流組件及其運行復雜性和隨機方面的解決方案,該方案將制造工藝參數(shù)進行雙重隨機表示,并使用特性/分布函數(shù)簡化了工作流圖,提高了多目標平衡算法的性能和優(yōu)化效果;Roberts 等[10]為動態(tài)平衡危險復合無菌產(chǎn)品的生產(chǎn)時間、員工安全感和工作滿意度等參數(shù),提出一種基于質(zhì)量約束的輔助工作流系統(tǒng)模型,該模型限定生產(chǎn)質(zhì)量,并根據(jù)員工匿名的在線調(diào)查動態(tài)修改模型參數(shù)使其達到最優(yōu),從而有效地解決了生產(chǎn)工藝多目標平衡問題;Lucas 等[11]通過工序上下層之間的關系建立了基于事件的工藝工作流模型,通過所提出的相關公式完成了對制造系統(tǒng)的優(yōu)化調(diào)度問題;Stender 等[12]為解決不同條件下制造工藝質(zhì)量提升的問題,提出了一種有限元分析工作流模型,該模型可完成熱條件影響下制造工藝時間質(zhì)量的優(yōu)化調(diào)度問題;敬石開等[13]為解決云制造工藝多服務平衡可靠性等問題,提出了一種離散粒子群智能優(yōu)化工作流多目標調(diào)度算法,該算法通過不斷優(yōu)化云制造工藝參數(shù),并根據(jù)智能算法的語義分析實現(xiàn)多服務匹配,從而確保了云制造多服務選擇的可靠性問題;張璽等[14]采用人工智能理論提出了一種模糊Petri 網(wǎng)工作流模型,對制造車間在不確定環(huán)境下的制造工藝進行了資源重調(diào)度優(yōu)化,實現(xiàn)了時間和成本的動態(tài)平衡;張萌等[15]為更好地解決制造工藝服務級別優(yōu)選難的問題,提出了基于工作流的限定區(qū)間多目標優(yōu)化調(diào)度算法,該算法將制造工藝區(qū)分成若干個區(qū)間,根據(jù)各區(qū)間的特點使用非支配排序改進型遺傳算法對其進行局部優(yōu)化,通過處處選取局部最優(yōu)解完成整體優(yōu)化,從而實現(xiàn)多目標調(diào)度的目的.

上述研究成果對于優(yōu)化線性生產(chǎn)工藝的多目標動態(tài)平衡具有一定的先進性.然而,生產(chǎn)工藝錯綜復雜,尤其是某些工藝具有非線性特點,即反饋生產(chǎn)工藝.對于非線性工藝進行多目標多因素的優(yōu)化調(diào)度,現(xiàn)有的研究成果無法完成.另一方面,非線性制造工藝在生產(chǎn)企業(yè)中普遍存在,企業(yè)急需對這類工藝進行優(yōu)化調(diào)度.本文正是為解決非線性工藝優(yōu)化調(diào)度問題而展開研究的,并在以往研究[16-17]的基礎上,結合非線性制造工藝特點,考慮制造時間、質(zhì)量和費用成本這些參數(shù)的制約關系,采用虛擬技術提出一種三層虛擬工作流模型Three-VMG (Threevirtual model graph)及其優(yōu)化調(diào)度算法Three-OVMG(Three-optimal virtual model graph).該模型和算法的主要思想是首先建立非線性生產(chǎn)工藝的抽象結點層、虛擬工作流模型層和同構轉(zhuǎn)換層,其次采用分段優(yōu)化同構轉(zhuǎn)換層的工藝參數(shù),并由頂層向底層逐級傳遞優(yōu)化解,最終實現(xiàn)工藝資源的動態(tài)平衡,為制造企業(yè)提供科學的決策依據(jù)和改進方案.由于模型采用虛擬技術,將工藝中的反饋工序結點虛擬為單個結點,從而將非線性工藝改造為虛擬線性工藝,實現(xiàn)了其多目標的優(yōu)化調(diào)度.因此,該模型可用于解決非線性即反饋制造工藝的多目標優(yōu)化調(diào)度問題.此外,該模型的三層結構,即底層工藝資源抽象層、中層結點工藝偏序?qū)雍晚攲犹摂M組合層,每層分別代表制造企業(yè)的不同關注面,先由下而上進行抽象優(yōu)化形成決策,再由上而下傳達決策修改配置參數(shù).因此,這種三層模型較其他優(yōu)化模型更具有建模清晰、高效快捷和簡單明了等優(yōu)勢,值得推廣.

1 問題描述

1.1 非線性制造工藝優(yōu)化相關定義

非線性制造工藝虛擬工作流技術是根據(jù)非線性即反饋制約制造工藝特點將工作流與虛擬調(diào)度技術相結合為解決非線性制造工藝多目標動態(tài)平衡的一種綜合優(yōu)化調(diào)度技術.因此,其相關定義應體現(xiàn)虛擬、工作流和非線性制造工藝優(yōu)化調(diào)度等技術的特性.

定義 1.制造工藝原始工作流.該工作流可定義為M(Pet,H,C,W),式中,M為工作流名稱;Pet為其所繼承的原始Petri 網(wǎng)名稱,可定義為:Pet(B0,E0,P,T,L,Q),式中,B0為Petri 網(wǎng)開始狀態(tài)結點;E0為Petri 網(wǎng)終止狀態(tài)結點;P為工位結點抽象集,表示為P=(p0,p1,···,pn);T為遷移結點抽象集,表示為T=(t0,t1,···,tm);L為關系有向邊抽象集,表示為L=(l0,l1,···,ly);Q為Petri 網(wǎng)中各結點間變換條件的權重值抽象集,表示為Q=(q0,q1,···,qz);H為各結點被加工所消耗的時間抽象集,表示為H=(h1,h2,···,hi,···,hn);C為各結點被加工所需費用的抽象集,表示為C=(c1,c2,···,ci,···,cn);W為各結點所加工產(chǎn)品的質(zhì)量抽象集,表示為W=(w1,w2,···,wi,···,wn).

定義 2.虛擬結點s′.表示對多個結點進行組合,進而看作整體,成為一個虛擬結點,記為前者表示結點si至結點sj之間多結點的組合,后者表示結點si,sj兩結點的組合,由多個虛擬結點s′構成的集合稱為虛擬結點集合S′,其中,結點s可以是工位結點p也可以是遷移結點t,若結點s=p,則虛擬結點s′記為p′,若結點s=t,則虛擬結點s′記為t′.采用虛擬結點技術對非線性制造工藝進行處理,使其變?yōu)樘摂M線性制造工藝的過程稱之為虛擬技術.

定義 3.制造工藝虛擬工作流.該工作流可定義為VM(M,CP,P′,T′,Id,Od),式中,VM為虛擬工作流名稱;M為制造工藝虛擬化前的原始工作流;CP是非線性制造工藝中所設置質(zhì)量檢測結點抽象集,表示為CP=(cp1,cp2,···,cpi,···,cpk),k為檢測部門數(shù),cpi表示工作流VM變換到檢測部門i時,該部門對其直接前驅(qū)工位結點pj加工產(chǎn)品的累積生產(chǎn)質(zhì)量Fw(pj,hj)和累積加工費用Fc(pj,hj)進行檢測,當滿足Fw(pj,hj)≥此處要求的質(zhì)量δiw并且Fc(pj,hj)≤此處要求的費用δic時,工作流VM繼續(xù)進行變換,執(zhí)行該部門的直接后繼工位結點pq繼續(xù)加工,否則工位結點pj加工的產(chǎn)品未通過檢測,需反饋至結點pj的某個前驅(qū)工位結點pj-x處進行精修,直到工作流VM重新變換至工位結點pj且滿足檢測點cpi的檢測要求,整個過程的加工時間累積,因此檢測點cpi=(δiw,δic),δiw和δic的值由具體加工部門確定;P′為非線性工藝中進行虛擬重構后工位結點抽象集,表示為T′為工藝重構后的虛擬遷移結點抽象集,表示為Id為工作流VM中各結點入度值的抽象集,表示為Id=(id1,id2,···,idi,···,idz);Od為工作流VM中各結點出度值的抽象集,表示為Od=(od1,od2,···,odi,···,odz).

定義4.制造工藝虛擬工作流圖.該工作流圖可定義為VG(V M,E),式中,VG為名稱;VM為虛擬工作流名稱;E為圖中所有有向邊的抽象集,表示為E=(e1,e2,···,ei,···,en),集合E反映VM中所有結點的工序.

定義5.制造工藝三層虛擬工作流,是指由制造資源集合和模型VM及虛擬工作流圖VG所構成的決策優(yōu)化調(diào)度過程圖,可定義為Three-V MG(Re,Map,V M,V G),式中,Three-VMG是制造工藝三層虛擬工作流名稱;Re是制造資源集合由集合P和集合T構成;VM是制造工藝虛擬工作流模型;VG是制造工藝虛擬工作流圖;Map是制造資源集合向模型VM映射關系的集合,可表示為Map=(map1,map2,···,mapi,···,mapn+m).

定義6.合同矢量V,是指工藝所交付的產(chǎn)品應滿足所簽訂合同的各項指標,本文設定為V=(vh,vc,vw),式中,vh是時間限定,vc是費用限定,vw是質(zhì)量限定,要求交付產(chǎn)品的時間和費用不能超過vh和vc,質(zhì)量不能低于vw.

1.2 非線性制造工藝Three-VMG 模型優(yōu)化規(guī)則定義

由于三層虛擬工作流Three-VMG 模型具有一定的反饋制約等特性,為更好的識別其靜態(tài)數(shù)據(jù)關聯(lián)及生產(chǎn)過程中的動態(tài)轉(zhuǎn)換關系,為此本文設定了一系列Three-VMG 模型應遵循的優(yōu)化規(guī)則和約束條件,具體如下:

1)工作流VM的虛擬工位結點集P′識別重構.在工作流VM中,若多個工位結點構成一個完整的非線性即反饋制約關系,則這些結點可進行重構,記為虛擬工位結點,標記為表示由相鄰的工位結點pi和pj重構后的虛擬工位結點;表示由工位結點pi開始至工位結點pj結束所包含若干工位結點重構后的虛擬工位結點.由所有重構后的虛擬工位結點所構成的集合,記為虛擬工位結點集P′.

2)工作流圖VG的工位結點pi的優(yōu)選域識別.工位結點優(yōu)選域是指該結點可選擇最優(yōu)加工過程的時間范圍域,可定義為OSDi[SrTi,EdTi],式中,OSDi為優(yōu)選域名稱,SrTi為工位結點pi可選加工過程的最早開始時間,EdTi為工位結點pi可選加工過程的最遲開始時間,優(yōu)選域OSDi中的參數(shù)可由式(1)進行計算:

式(1)中,SrTpq和EdTpp為pi的直接前驅(qū)和后繼工位結點pq的最早和最遲開始時間.

3)工作流圖VG的加工域識別.重構后的工作流圖VG中,令集合N′是結點集N(N=P∪P′)的子集,則由集合N′中各結點所構成的局部工作流所確定的最小和最大合同矢量V.vhmin和V.vhmax值區(qū)間,識別為該結點集的加工域,記為τ=[V.vhmin,V.vhmax].集合N′加工域τ的參數(shù)可由式(2)進行計算:

4)工作流圖VG的虛擬歧途徑識別.虛擬歧途徑是指VG中,若存在某結點ni可與結點nj進行重構形成新的虛擬結點,但結點ni的部分出度邊又可與結點nk進行重構形成另外新的虛擬結點,則由結點ni和nk構成的途徑標記為歧途徑,用VWRni表示,其中,ni,nj和nk互不相同.例如:某虛擬工作流圖W,其結構如圖1 所示.經(jīng)分析,該工作流圖共有4 個加工域分別進行標注.在加工域1 中,工位結點n15和n16可進行重構形成新的虛擬結點.在加工域2 中,工位結點n18和n19可進行重構形成新的虛擬結點.由于結點n16存在2 條出度邊,其中一條可與n18進行重構虛擬,另外一條則不能進行重構虛擬,因此由結點n16,n18和n19所組成的途徑為虛擬歧途徑VWPn16.

圖1 虛擬歧途徑的識別過程Fig.1 The process of virtual wrong route recognition

5)工作流圖VG的生產(chǎn)參數(shù)標識規(guī)則.虛擬工作流圖VG中,令AHq,ACq和AW q為工作流圖進行到結點nq時的累積生產(chǎn)時間、累積生產(chǎn)費用和累積生產(chǎn)質(zhì)量,AHp和ACp為其直接前驅(qū)結點np的累積生產(chǎn)時間和累積生產(chǎn)費用,則AHq,ACq和AW q的值可通過式(3)進行計算.若nq=nE0,則AHE0,ACE0和AW E0表示工作流圖VG執(zhí)行完畢后所達到的最終生產(chǎn)時間、生產(chǎn)費用和生產(chǎn)質(zhì)量.

式(3) 中,lij表示工作流圖VG轉(zhuǎn)換至工位結點ni時,選用遷移結點tj來進行后續(xù)轉(zhuǎn)換,由于選擇具有互斥性,因此lij=0 或1;N′表示工作流VG換至工位結點nq時,已經(jīng)執(zhí)行完畢的工位結點集.

本文要求所建立的三層虛擬工作流Three-VMG 模型在滿足合同矢量V約束的前提下,利用規(guī)則1)～ 4)實現(xiàn)規(guī)則5)的各項參數(shù)最優(yōu).

1.3 非線性制造工藝三層虛擬工作流調(diào)度建模算法Three-MVMA

汲取部分以往研究成果并遵循第2.2 節(jié)中的相關規(guī)則和約束后,設計非線性制造工藝三層虛擬工作流調(diào)度建模算法Three-MVMA 如下:

步驟 1.分析非線性制造工藝,統(tǒng)計生產(chǎn)工位形成工位結點集P,分析各工位結點的轉(zhuǎn)換狀態(tài)形成遷移結點集T,將工藝中各檢測數(shù)據(jù)匯總形成檢測結點集CP;

步驟 2.結合工位結點集P和遷移結點集T的偏序關系構建原始工作流模型M;

步驟 3.根據(jù)非線性制造工藝,按序?qū)pi(cpi ∈CP,i=1,2,···,k)插入到原始工作流模型M中,調(diào)整有向邊集合L,形成新的偏序關系;

步驟 4.輸入合同矢量V,利用式(1)計算模型M各工位結點的優(yōu)選域OSD;

步驟 5.從工位結點B0開始廣度優(yōu)先遍歷模型M的工位結點集P,統(tǒng)計集合P中出度od和入度id不為1 的工位結點,將其插入至隊列List中,其中反饋前置結構中各工位結點不入隊;

步驟 6.出隊List中的隊首出度od不為1 的工位結點pj,尋找與其最近的反饋入度工位結點pi,重構結點pi流經(jīng)結點pj之間的所有工位結點,將其標注為虛擬工位結點將結點暫時保存至虛擬工位結點集P′中,將此過程中所涉及遷移結點重構為虛擬遷移結點并保存至虛擬遷移結點集T′中;

步驟 7.重復步驟6 直至隊列List為空;

步驟 8.按序移出集合P′和T′中的虛擬工位結點和虛擬遷移結點,使用規(guī)則4)進行判斷,檢查它們是否構成虛擬歧途徑,若不構成VWR則正式進行虛擬重構并修改模型M且更新模型VM,若構成VWR則不能進行重構,刪除該虛擬工位結點和虛擬遷移結點并恢復構成虛擬結點的工位結點和遷移結點;

步驟 9.若集合P′或T′不為空,則循環(huán)執(zhí)行步驟8,否則標記模型VM并輸出;

步驟 10.利用式(2)并遍歷虛擬工位結點集P′,計算各工位結點的加工域τ,將其標注至模型M中;

步驟 11.遍歷模型VM,統(tǒng)計相鄰工位結點pi至pj(pi≠pj)的全部途徑,將其建立有向邊ejk,其中k=1,2,···,idpj,計算有向邊ejk的參數(shù)hjk,cjk和wjk,標記這些參數(shù)形成虛擬工作流圖VG;

步驟 12.重復步驟11 直至工作流趨于穩(wěn)定,形成工作流圖VG;

步驟 13.將制造資源集合Re、映射集合Map、虛擬工作流模型VM和虛擬工作流圖VG進行組合,形成三層虛擬工作流Three-VMG,將其輸出.

根據(jù)上述策略,給出建模算法Three-MVMA的偽代碼如下:

算法1.Three -MVMA 算法

輸入.集合P,集合T,集合Q,集合H,集合C,集合W,集合Id,集合Od,集合CP,合同矢量V;

輸出.虛擬工作流模型VM,虛擬工作流圖VG,三層虛擬工作流Three-VMG;

1.4 非線性制造工藝三層虛擬工作流決策模型實例驗證

某公司汽車制造沖壓工藝質(zhì)量控制流程如圖2所示,經(jīng)分析該工藝流程呈現(xiàn)非線性的特點,可用三層虛擬工作流決策模型對其完工時間、生產(chǎn)質(zhì)量和費用等參數(shù)進行多目標優(yōu)化調(diào)度.

圖2 汽車制造沖壓加工工藝Fig.2 Stamping process of automobile manufacturing

根據(jù)一般統(tǒng)計發(fā)現(xiàn),該公司進行沖壓加工所需原材料常用供應商共計3 個,其供應號設定為:B1,B2和B3;采購部門共計設立2 個質(zhì)檢組,其編號設定為:C1和C2;沖壓工藝形成的中間件進行質(zhì)量抽查組共計有2 個,其編號設定為:S1和S2;沖壓件在進入庫存前的質(zhì)量檢測組共計有3 個,其編號設定為:D1,D2和D3.為便于研究,忽略該工藝流程的某些次要矛盾,將其主要矛盾進行非線性工作流分解,得出相應的結點記為:工位結點集合P和遷移結點集合T,各集合的情況如表1 所示.

表1 沖壓工藝質(zhì)量檢測結點集合P 和TTable 1 Node set P and T of stamping process quality inspection

將集合P和集合T的各元素輸入至Three-MVMG 算法后,形成非線性沖壓工藝質(zhì)量檢測的三層虛擬工作流如圖3 所示.

圖3 沖壓工藝質(zhì)量檢測三層虛擬工作流Fig.3 Three-tier virtual workflow for stamping process quality inspection

2 非線性制造工藝三層虛擬工作流調(diào)度模型優(yōu)化算法Three-OVMG

定義7.三層虛擬工作流調(diào)度輸出途徑VRoute.該途徑是指非線性制造工藝經(jīng)優(yōu)化調(diào)度算法處理后給出的最佳調(diào)度途徑,由相關虛擬結點、有向邊和生產(chǎn)參數(shù)組成,可定義為VRoute(P′,E,A),式中,VRoute是最優(yōu)輸出途徑名;P′是組成該途徑的虛擬工位結點集;E是偏序有向邊集合;A是該途徑各虛擬工位結點的累積參數(shù)集,表示為A=(a1,a2,···,ai,···,am),式中,ai為結點pi(pi ∈P′) 的累積參數(shù),表示為ai=(aiH,aiC,aiW),m為集合P′的結點數(shù).

假設函數(shù)?w(pi,hpi)和?c(pi,hpi)表示虛擬工作流Three-VMG在時刻hpi處,工位結點pi在其優(yōu)選域OSDpi[SrTpi,EdTpi]內(nèi)所選中的最高生產(chǎn)質(zhì)量和最低費用,則該時刻下可使用式(4)計算工位結點pi的?w(pi,hpi)和?c(pi,hpi):

虛擬工作流Three-VMG中,任意兩工位結點pi-1和pi(pi-1∈P′,pi ∈P′),若pi-1是pi的前驅(qū)結點,則可使用式(5)來計算結點pi-1的累積生產(chǎn)質(zhì)量和費用:

式(5)可由后向前完成對工作流Three-VMG的優(yōu)化求解,然后通過這些解完成非線性制造工藝資源的正向調(diào)度.由此,可設計三層虛擬工作流優(yōu)化算法Three-OVMG.

步驟1.調(diào)用建模算法Three-MVMG 處理非線性制造工藝各參數(shù),形成三層虛擬工作流Three-VMG 模型;

步驟2.結合合同矢量V由后向前將模型Three-VMG 分層,利用式(1)分析并計算每層形成各工位結點pi的優(yōu)選域OSDpi[SrTpi,EdTpi];

步驟3.利用式(4)計算并標記結束層的工位結點E0在其優(yōu)選域OSDE0內(nèi),各時刻的?w(E0,hE0)和?c(E0,hE0);

步驟4.全面處理模型Three-VMG,若工位結點不存在虛擬歧途徑VWR,則使用逆向串規(guī)約且利用式(4)計算并標記各工位結點pi在其優(yōu)選域OSDpi內(nèi),每個時刻的?w(pi,hpi)和?c(pi,hpi);

步驟5.若工位結點在虛擬歧途徑VWR中,則首先利用式(2)計算VWR的加工域τ,然后利用式(4)串行計算并標記該域τ下的各工位結點pi不同時刻的?w(pi,hpi)和?c(pi,hpi);

步驟6.利用式(3)并遵循合同矢量V的約束,全面處理標記后的模型Three-VMG 的工位結點P集合,確定并輸出最優(yōu)調(diào)度途徑VRoute.

算法Three-OVMG 其所對應的偽代碼如下:

算法2.Three -OVMG 算法

3 非線性制造工藝Three-VMG 模型優(yōu)化案例分析

為驗證上述建模及優(yōu)化調(diào)度算法,這里仍選用某公司汽車制造沖壓工藝質(zhì)量控制流程進行分析.實驗所用服務器操作系統(tǒng)為Windows Server2016,內(nèi)存配置至少8 GB,采用Java語言開發(fā)建模算法Three-MVMG 和優(yōu)化調(diào)度算法Three-OVMG 的代碼,設定合同矢量V為:V.h=111 天,V.w=0.98×100%,V.c=20 萬元.

3.1 非線性沖壓工藝Three-VMG 模型優(yōu)化過程

為驗證模型Three-VMG 的優(yōu)化調(diào)度過程,這里仍選用第2.4 節(jié)所述工藝,該工藝在忽略突發(fā)事件及其他附情況的前提下,加工某批工件的質(zhì)量控制數(shù)據(jù)如表2 所示.

將圖3 所示的該工藝模型輸入算法Three-OVMG 后,代入表2 中的數(shù)據(jù)并遵循合同矢量V的約束,形成最優(yōu)的虛擬調(diào)度途徑VRoute,其過程如圖4 所示.

根據(jù)該工藝特點將圖4 的調(diào)度過程分為兩個優(yōu)化段.由于合同矢量V.h=111 天,因此將第1 個優(yōu)化段的原材料采購質(zhì)量控制非線性工藝的合同約束時間定為V.h1=60 天,將第2 個優(yōu)化段的沖壓質(zhì)量控制非線性工藝的合同約束時間定為V.h2=51天.根據(jù)工藝要求,在第1 個段中,采購部質(zhì)檢抽查組設置的檢測點cp1=0.950,無費用約束,當工作流轉(zhuǎn)換到該檢測點時,若此時的fw(pi,hpi) ＜ 0.950時,則需要反饋至前向工位結點進行質(zhì)量缺陷修改,生產(chǎn)時間延誤5 天,費用增加5 萬;在第2 個段中,車間質(zhì)檢抽查組設置的檢測點cp2=0.975,無費用約束,當工作流轉(zhuǎn)換到該檢測點時,若此時的fw(pi,hpi)＜ 0.975時,則需要反饋至前向工位結點進行質(zhì)量缺陷修改,生產(chǎn)時間延誤3 天,費用增加1 萬.兩個段之間采用累積傳遞的策略進行銜接,利用式(1)～ (5)及表2 中的數(shù)據(jù),可完成對圖4 工藝各工位結點?w(pi,hpi) 和?c(pi,hpi) 的計算,過程如下:

圖4 工作流Three-VMG 的調(diào)度過程Fig.4 Process of workflow Three-VMG

表2 各部門服務的時間、質(zhì)量和費用Table 2 Time,quality and cost of departmental services

1)經(jīng)計算,工位結點p1,p2和p3的優(yōu)選域分別為:OSD1=[0,7],OSD2=[20,27]和OSD3=[35,42].它們符合虛擬重構要求且不存在VWR,故將其重構為虛擬工位結點的加工域:τ1=[35,35].

2)根據(jù)τ1和OSD1、OSD2、OSD3的值,計算第一階段各工位結點pi的?w及?c如下:

工位結點p3的計算過程為:

工位結點p2的計算過程:

工位結點p1的計算過程:

由上述過程可知,第1 階段由后至前累積到p1的?w(p1,0),?w(p1,1),?w(p1,2),?w(p1,3)和?w(p1,4)值所用生產(chǎn)時間分別為:60 天、59 天、58 天、57 天和56 天,但這些路徑的累積生產(chǎn)質(zhì)量fw＜ 0.950,不滿足檢測點cp1要求需返回前至修改.它們修改一次后的累積生產(chǎn)時間變?yōu)?65 天、64 天、63 天、62 天和61 天,這些生產(chǎn)時間不滿足合同矢量V.h1=60 天的要求,因此不能沿用這些路徑進行工藝的優(yōu)化調(diào)度,及時淘汰.

由累積到p1的?w(p1,5),?w(p1,6)和?w(p1,7)值所用生產(chǎn)時間分別為:55 天、54 天和53 天,同樣這些路徑的累積生產(chǎn)質(zhì)量fw＜ 0.950,不滿足檢測點cp1要求需返回前至修改.它們修改一次后的累積生產(chǎn)時間變?yōu)?60 天、59 天和58 天,這些生產(chǎn)時間小于合同矢量V.h1=60 天,滿足時間約束要求.因此,工藝修改正后它們的累積?w分別為:(p1,5)=0.912+(1 -0.912) × 0.912=0.992,(p1,6)=0.912+(1 -0.912) × 0.912=0.992,(p1,7)=0.912+(1 -0.912) × 0.912=0.992;修改后的累積?c分別為:(p1,5)=5+11.25=16.25 萬元,(p1,6)=5+11.25=16.25 萬元,(p1,7)=5+11.25=16.25 萬元.優(yōu)選生產(chǎn)時間最短且累積?w最高者,即(p1,7)=0.992.此段工藝將沿此途徑進行資源優(yōu)化,即:VRoute1=B0→p1/t1B3→p2/t2→p3/t3C2.

3)由于第2 階段為第1 階段的后續(xù)工藝且合同矢量V.h2=51 天,因此此階段的初始生產(chǎn)質(zhì)量?w=0.992.經(jīng)計算,工位結點p4、p5、p6和p7的優(yōu)選域分別為:OSD4=[0,4],OSD5=[1,5],OSD6=[21,25]和OSD7=[28,32].它們符合虛擬重構要求且不存在VWR,故將其重構為虛擬工位結點的加工域:τ2=[28,28].

4)根據(jù)τ2和OSD4、OSD5、OSD6、OSD7的值,計算第2 階段各工位結點pi的?w及?c如下:

a) 工位結點p7的計算過程為

b) 工位結點p6的計算過程為

c) 工位結點p5的計算過程為

d) 工位結點p4的計算過程為

e) 此段工藝被加工一次后工位結點p4的?w(p4,h0-4) 和?c(p4,h0-4) 為

由上述過程可知,第2 階段由后至前累積到p4的?w(p4,0),?w(p4,1)和?w(p4,2)值所用生產(chǎn)時間分別為:50 天、49 天和48 天,但這些路徑的累積生產(chǎn)質(zhì)量?w＜ 0.975,不滿足檢測點cp2要求需返回前至修改.它們修改一次后的累積生產(chǎn)時間變?yōu)?53 天、52 天和51 天.若沿此途徑繼續(xù)轉(zhuǎn)換至工位結點E0,則累積生產(chǎn)時間變?yōu)?54 天、53 天和52 天,均大于合同矢量V.h2=51 天,不滿足時間要求.因此,不能沿用這些路徑進行工藝的優(yōu)化調(diào)度,及時淘汰.

由累積到p4的?w(p4,3)和?w(p4,4) 值所用生產(chǎn)時間分別為:47 天和46 天,同樣這些路徑的累積生產(chǎn)質(zhì)量?w＜ 0.975,不滿足檢測點cp2要求需返回前至修改.它們修改一次后的累積生產(chǎn)時間變?yōu)?50天和49 天.若沿此途徑繼續(xù)轉(zhuǎn)換至工位結點E0,則累積生產(chǎn)時間分別為:51 天和50 天,均小于合同矢量V.h2=51 天,滿足時間要求.因此,工藝修改正后它們的累積?w分別為:(p4,3)=0.918+(1-0.918) × 0.925=0.994 和(p4,4)=0.910+(1-0.910) × 0.917=0.993;修改后的累積?c分別為:(p4,3)=1+17.81=18.81 萬元和(p4,4)=1+17.79=18.79 萬元.優(yōu)選累積?w最高者,即(p4,3)=0.994.此段工藝將沿此途徑進行資源優(yōu)化,即:VRoute2=p4/t4→p5/t5S1→p6/t6→p7/t7D3.

5)將第1 階段和第2 階段工藝采用段間累積的方法進行整合,整合后此工藝的最終累積?w=0.999 ×0.994=0.993,累積?c=0.04+18.81=18.85 萬元,累積?h=1+50+58=109 天.由于最終累積?h＜合同矢量V.h,滿足要求,因此最終輸出的優(yōu)化調(diào)度虛擬途徑VRoute=VRoute1+VRoute2=B0→p1/t1B3→p2/t2→p3/t3C2→p4/t4→p5/t5S1→p6/t6→p7/t7D3→E0.

3.2 Three-VMG 模型虛擬重構及算法比較

圖5 給出了模型Three-VMG 被算法Three-OVMG 處理后,各工位結點的虛擬重構歸約優(yōu)化過程.

圖5 虛擬結點重構過程Fig.5 Virtual node reconfiguration process

算法Three-OVMG 掃描模型Three-VMG 的工位結點集P,按規(guī)則將工位結點p1、p2、p3進行重構形成虛擬工位結點將工位結點p4、p5、p6、p7進行重構形成虛擬工位結點虛擬工位結點均不存在虛擬歧途徑VWR,因此整個工藝優(yōu)化后的最終?h2、?w2和?c2分別為:109 天、0.993 和18.85 萬元.

將該工藝和表1、表2 的數(shù)據(jù)分別輸入時間最小化優(yōu)化調(diào)度算法[18]和算法Three-OVMG 中,設定合同矢量V.h=111 天,得出兩條資源調(diào)度途徑VRoute,如圖6 所示.

圖6 調(diào)度途徑VRoute 輸出對比Fig.6 Comparison of scheduling routes Vroute output

圖6 所示工藝經(jīng)時間最小化優(yōu)化調(diào)度算法處理后被分為兩個優(yōu)化段,第一段被優(yōu)化后的累積?1h1,?1w1和?1c1分別為:58 天、0.990 和16.25 萬元;第二段被優(yōu)化后的累積?2h1,?2w1和?2c1分別為:47 天、0.992 和2.04 萬元.因此,整個工藝被優(yōu)化后最終的?h1,?w1和?c1分別為:106 天、0.991 和18.33 萬元.

比對最終的累積?w值發(fā)現(xiàn):相對于時間最小化優(yōu)化調(diào)度算法,算法Three-OVMG 最終優(yōu)化的生產(chǎn)質(zhì)量提升0.202%,即:Δ=(fw2-fw1)/fw1×100%.該結果表明:在有限范圍內(nèi)相同合同矢量V約束下,算法Three-OVMG 的優(yōu)化效果要好于時間最小化優(yōu)化調(diào)度算法.

3.3 算法Three-OVMG 的性能分析

影響算法Three-OVMG 執(zhí)行性能的因素眾多,本文只研究了算法在有限范圍內(nèi)不同合同矢量V.h和不同工位結點數(shù)集合P因素下執(zhí)行性能的受影響情況.

1) 有限范圍內(nèi)不同合同矢量V.h對算法的影響

限定工位結點集P中數(shù)目為10 和15 個,各工位結點pi的遷移結點集T中數(shù)目為集合{2,3,4,5}的隨機數(shù),按5%、10%、15%、20%、25%的比例增加合同矢量V.h,調(diào)用算法Three-OVMG 執(zhí)行,得出有限范圍內(nèi)不同合同矢量V.h對算法的影響,如圖7 所示.

圖7 合同矢量V 對性能的影響Fig.7 Effect of contract vector V on Performance

圖7 指出,在有限范圍內(nèi)合同矢量V.h的值跟算法Three-OVMG 優(yōu)化調(diào)度后工藝最終的?w值成正比關系.

2) 有限范圍內(nèi)不同工位結點數(shù)P集合對算法的影響

限定增加20%的合同矢量V.h后,將工藝的工位結點集P中數(shù)目分別設定為5、10、15 和20 后,各工位結點pi的遷移結點集T中數(shù)目為集合{2,3,4,5}的隨機數(shù),調(diào)用算法Three-OVMG 執(zhí)行,得出有限范圍內(nèi)不同工位結點數(shù)P集合對算法的影響,如圖8 所示.

圖8 指出,在有限范圍內(nèi)工位結點集P中數(shù)目跟算法Three-OVMG 優(yōu)化調(diào)度后工藝最終的?w值成反比關系.然而,同時間最小化調(diào)度算法相比,算法Three-OVMG 優(yōu)化調(diào)度后工藝最終的?w值有所增加,其增加比為:1.58%,3.68%,11.13%,15.45%.

圖8 工位結點數(shù)對性能的影響Fig.8 Effect of workplace node numbers on performance

4 結束語

制造工藝的多目標優(yōu)化調(diào)度具有一定的難度,尤其是當工藝呈現(xiàn)出非線性即反饋制約時,現(xiàn)有的研究成果無法實現(xiàn)優(yōu)化調(diào)度,本文針對這一不足提出了三層虛擬工作流決策模型及其優(yōu)化調(diào)度算法.該模型汲取了虛擬技術的部分思想,并根據(jù)反饋制約工藝建立反饋工作流.隨后,結合所提出的虛擬工作流調(diào)度模型識別規(guī)則對其掃描,重構工藝的虛擬結點,構建三層虛擬工作流模型.通過對模型進行逐級分段,段內(nèi)采用虛擬串歸約技術進行多目標動態(tài)優(yōu)化,段間采用多目標優(yōu)化結果累積傳遞和虛擬正向調(diào)度策略從而實現(xiàn)了對整個模型的優(yōu)化調(diào)度.經(jīng)驗證,這種三層虛擬工作流優(yōu)化調(diào)度方法具備虛擬特點,簡化了非線性制造工藝流程,增強了對這些反饋制約工藝的描述,有效地完成了多目標優(yōu)化調(diào)度.此外,該模型調(diào)度方法具備一定的啟發(fā)性,值得進一步研究.