羅智勇 王靜遠(yuǎn) 謝志強(qiáng) 孫廣路 楊 旭

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

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

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

1 問題描述

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

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

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

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

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

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

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

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

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

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

1)工作流VM的虛擬工位結(jié)點(diǎn)集P′識(shí)別重構(gòu).在工作流VM中,若多個(gè)工位結(jié)點(diǎn)構(gòu)成一個(gè)完整的非線性即反饋制約關(guān)系,則這些結(jié)點(diǎn)可進(jìn)行重構(gòu),記為虛擬工位結(jié)點(diǎn),標(biāo)記為表示由相鄰的工位結(jié)點(diǎn)pi和pj重構(gòu)后的虛擬工位結(jié)點(diǎn);表示由工位結(jié)點(diǎn)pi開始至工位結(jié)點(diǎn)pj結(jié)束所包含若干工位結(jié)點(diǎn)重構(gòu)后的虛擬工位結(jié)點(diǎn).由所有重構(gòu)后的虛擬工位結(jié)點(diǎn)所構(gòu)成的集合,記為虛擬工位結(jié)點(diǎn)集P′.

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

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

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

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

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

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

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

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

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

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

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

步驟 2.結(jié)合工位結(jié)點(diǎn)集P和遷移結(jié)點(diǎn)集T的偏序關(guān)系構(gòu)建原始工作流模型M;

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

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

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

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

步驟 7.重復(fù)步驟6 直至隊(duì)列List為空;

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

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

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

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

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

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

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

算法1.Three -MVMA 算法

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

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

1.4 非線性制造工藝三層虛擬工作流決策模型實(shí)例驗(yàn)證

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

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

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

表1 沖壓工藝質(zhì)量檢測結(jié)點(diǎn)集合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)度途徑,由相關(guān)虛擬結(jié)點(diǎn)、有向邊和生產(chǎn)參數(shù)組成,可定義為VRoute(P′,E,A),式中,VRoute是最優(yōu)輸出途徑名;P′是組成該途徑的虛擬工位結(jié)點(diǎn)集;E是偏序有向邊集合;A是該途徑各虛擬工位結(jié)點(diǎn)的累積參數(shù)集,表示為A=(a1,a2,···,ai,···,am),式中,ai為結(jié)點(diǎn)pi(pi ∈P′) 的累積參數(shù),表示為ai=(aiH,aiC,aiW),m為集合P′的結(jié)點(diǎn)數(shù).

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

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

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

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

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

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

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

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

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

算法Three-OVMG 其所對應(yīng)的偽代碼如下:

算法2.Three -OVMG 算法

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

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

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

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

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

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

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

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

工位結(jié)點(diǎn)p3的計(jì)算過程為:

工位結(jié)點(diǎn)p2的計(jì)算過程:

工位結(jié)點(diǎn)p1的計(jì)算過程:

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

由累積到p1的?w(p1,5),?w(p1,6)和?w(p1,7)值所用生產(chǎn)時(shí)間分別為:55 天、54 天和53 天,同樣這些路徑的累積生產(chǎn)質(zhì)量fw＜ 0.950,不滿足檢測點(diǎn)cp1要求需返回前至修改.它們修改一次后的累積生產(chǎn)時(shí)間變?yōu)?60 天、59 天和58 天,這些生產(chǎn)時(shí)間小于合同矢量V.h1=60 天,滿足時(shí)間約束要求.因此,工藝修改正后它們的累積?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)時(shí)間最短且累積?w最高者,即(p1,7)=0.992.此段工藝將沿此途徑進(jìn)行資源優(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)計(jì)算,工位結(jié)點(diǎn)p4、p5、p6和p7的優(yōu)選域分別為:OSD4=[0,4],OSD5=[1,5],OSD6=[21,25]和OSD7=[28,32].它們符合虛擬重構(gòu)要求且不存在VWR,故將其重構(gòu)為虛擬工位結(jié)點(diǎn)的加工域:τ2=[28,28].

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

a) 工位結(jié)點(diǎn)p7的計(jì)算過程為

b) 工位結(jié)點(diǎn)p6的計(jì)算過程為

c) 工位結(jié)點(diǎn)p5的計(jì)算過程為

d) 工位結(jié)點(diǎn)p4的計(jì)算過程為

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

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

由累積到p4的?w(p4,3)和?w(p4,4) 值所用生產(chǎn)時(shí)間分別為:47 天和46 天,同樣這些路徑的累積生產(chǎn)質(zhì)量?w＜ 0.975,不滿足檢測點(diǎn)cp2要求需返回前至修改.它們修改一次后的累積生產(chǎn)時(shí)間變?yōu)?50天和49 天.若沿此途徑繼續(xù)轉(zhuǎn)換至工位結(jié)點(diǎn)E0,則累積生產(chǎn)時(shí)間分別為:51 天和50 天,均小于合同矢量V.h2=51 天,滿足時(shí)間要求.因此,工藝修改正后它們的累積?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.此段工藝將沿此途徑進(jìn)行資源優(yōu)化,即:VRoute2=p4/t4→p5/t5S1→p6/t6→p7/t7D3.

5)將第1 階段和第2 階段工藝采用段間累積的方法進(jìn)行整合,整合后此工藝的最終累積?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 模型虛擬重構(gòu)及算法比較

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

圖5 虛擬結(jié)點(diǎn)重構(gòu)過程Fig.5 Virtual node reconfiguration process

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

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

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

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

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

3.3 算法Three-OVMG 的性能分析

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

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

限定工位結(jié)點(diǎn)集P中數(shù)目為10 和15 個(gè),各工位結(jié)點(diǎn)pi的遷移結(jié)點(diǎn)集T中數(shù)目為集合{2,3,4,5}的隨機(jī)數(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值成正比關(guān)系.

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

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

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

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

4 結(jié)束語

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