程方啟 葉飛帆
1.浙江工商職業(yè)技術(shù)學(xué)院,寧波,315012 2.寧波大學(xué),寧波,315211
在網(wǎng)絡(luò)化制造環(huán)境下,產(chǎn)品制造的各個(gè)環(huán)節(jié)可能分布在不同的區(qū)域、企業(yè),為保證產(chǎn)品制造的高效、低成本,獲得制造任務(wù)的企業(yè)需要尋求能滿足需求的協(xié)作企業(yè)的協(xié)同。這種跨地域、跨企業(yè)的協(xié)作,需要一種能夠快速建立協(xié)同制造過(guò)程鏈的途徑。網(wǎng)絡(luò)環(huán)境下建立協(xié)同制造過(guò)程鏈的方法,大多是根據(jù)制造任務(wù)選擇所需的資源[1],分析制造資源所在企業(yè)的信譽(yù)、生產(chǎn)負(fù)荷等狀況。制造任務(wù)的結(jié)構(gòu)一旦確定,較少考慮通過(guò)調(diào)整改變制造任務(wù)的參數(shù)來(lái)適應(yīng)市場(chǎng)上的制造資源情況,而主要關(guān)注承擔(dān)制造任務(wù)的制造資源能夠完成協(xié)同任務(wù)的完成時(shí)間、完成質(zhì)量、完成成本等[2]。虛擬企業(yè)或虛擬聯(lián)盟作為21世紀(jì)重要的生產(chǎn)經(jīng)營(yíng)與市場(chǎng)競(jìng)爭(zhēng)的企業(yè)組織形式,將地理上和組織上分散的企業(yè)組織起來(lái),通過(guò)企業(yè)間的有效協(xié)作而實(shí)現(xiàn)“共贏”的目標(biāo),以實(shí)現(xiàn)企業(yè)間制造資源的共享與優(yōu)化配置[3]。Fischer等[4]提出了一種基于“能力單元”的虛擬企業(yè)模型——水平型區(qū)域制造網(wǎng)絡(luò),以改善并提高中小企業(yè)的競(jìng)爭(zhēng)力,并根據(jù)制造任務(wù)尋找可適用的制造資源。Yao等[5]針對(duì)網(wǎng)絡(luò)環(huán)境中復(fù)雜零件的制造問(wèn)題,提出了物理制造單元與邏輯制造單元的概念,在制造任務(wù)與制造資源確定后應(yīng)用遺傳算法計(jì)算最優(yōu)可執(zhí)行加工路徑。吉峰等[6]提出了一種應(yīng)用UML建模語(yǔ)言描述的網(wǎng)絡(luò)制造服務(wù)模式——協(xié)同制造鏈,利用蟻群算法對(duì)其優(yōu)化問(wèn)題進(jìn)行求解??梢?jiàn),協(xié)同制造過(guò)程的快速構(gòu)建需要解決制造任務(wù)與制造資源的規(guī)劃、過(guò)程優(yōu)化模型的構(gòu)建及優(yōu)化方法的選擇等問(wèn)題。
構(gòu)建虛擬企業(yè)或協(xié)作聯(lián)盟是制造任務(wù)與制造資源之間相互協(xié)調(diào)、不斷調(diào)整優(yōu)化的演化過(guò)程。筆者在以上研究的基礎(chǔ)上,從協(xié)同制造過(guò)程鏈的角度出發(fā),提出了協(xié)同制造單元(collaborative manufacturing unit,CMU)、制造任務(wù)單元(manufacturing task unit,MTU)及協(xié)同制造鏈(collaborative manufacturing chain,CMC)的概念,從制造任務(wù)參數(shù)優(yōu)化角度出發(fā),基于制造任務(wù)參數(shù)距離建立了協(xié)同制造鏈的優(yōu)化模型,應(yīng)用自適應(yīng)遺傳算法進(jìn)行優(yōu)化計(jì)算,并對(duì)實(shí)例的結(jié)果進(jìn)行了分析。
(1)協(xié)同制造單元。CMU是由同一個(gè)企業(yè)內(nèi)的制造設(shè)備、工裝附件以及相關(guān)軟資源組成的、具有一定核心能力的制造單元,具有高度專業(yè)化及對(duì)外協(xié)作能力,在法律及經(jīng)濟(jì)上自治。一個(gè)CMU屬于一個(gè)企業(yè);而一個(gè)企業(yè)可以組建一個(gè)或多個(gè)CMU,處于網(wǎng)絡(luò)中的所有CMU構(gòu)成了一個(gè)制造能力庫(kù)。
(2)制造任務(wù)單元。根據(jù)復(fù)雜零件的制造加工任務(wù)的制造特性及工藝規(guī)劃可將其分解為多個(gè)MTU。一個(gè)MTU可以包含一個(gè)或多個(gè)制造加工工序,是對(duì)外協(xié)作任務(wù)的基本單位。由于制造工藝路線的多樣性,因此一個(gè)MTU可以由不同的CMU來(lái)承擔(dān),這些CMU可以是不同類型的,也可以是同一類型的;一個(gè)CMU也可以承擔(dān)一個(gè)或多個(gè)MTU。
(3)協(xié)同制造鏈。針對(duì)復(fù)雜零件制造任務(wù)分解得到的MTU分別由網(wǎng)絡(luò)中合適的CMU所提供的制造服務(wù)完成,各MTU之間按照約束關(guān)系組合成一條整體的制造服務(wù)鏈,稱之為CMC,可描述為
式中,Si為CMC中的第i個(gè)制造服務(wù);Ni為制造服務(wù)Si的ID;tBi為制造服務(wù)Si的開(kāi)工時(shí)間;tEi為制造服務(wù)Si的完工時(shí)間;Rij描述制造服務(wù)Si與下一個(gè)制造服務(wù)Sj的時(shí)序關(guān)系;n為制造服務(wù)的數(shù)量。
圖1為CMC示意圖。
圖1 CMC示意圖
CMC的優(yōu)化過(guò)程涉及的影響因素較多,為深入研究其優(yōu)化過(guò)程,對(duì)制造任務(wù)性能參數(shù)進(jìn)行形式化的描述。
制造任務(wù)性能參數(shù)(parameters of manufacturing task,PMT)描述制造任務(wù)屬性,反映制造任務(wù)的性能指標(biāo),主要包括制造時(shí)間、執(zhí)行成本、成品率等。如果CMC包括n個(gè)制造子任務(wù),則制造任務(wù)性能參數(shù)可表示為
式中,Pj為制造任務(wù)的第j個(gè)參數(shù);m為參數(shù)的數(shù)量;Pij為第i個(gè)制造任務(wù)的第j個(gè)參數(shù);PRLij、PRUij分別為第i個(gè)制造任務(wù)的第j個(gè)參數(shù)取值區(qū)間PRij的下限和上限。
在CMC的構(gòu)建過(guò)程中,針對(duì)制造任務(wù),盟主CMU經(jīng)過(guò)市場(chǎng)調(diào)研,初步預(yù)先確定能夠完成制造任務(wù)的參數(shù)指標(biāo),稱之為制造任務(wù)預(yù)期參數(shù)(prospective PMT),它可表示為
式中,Ppij為第i個(gè)制造任務(wù)的第j預(yù)期參數(shù)。
在CMC的構(gòu)建過(guò)程中,針對(duì) MTU,候選CMU針對(duì)具體的制造子任務(wù),結(jié)合自身制造資源的屬性特征,提出的任務(wù)完成性能指標(biāo)稱為制造任務(wù)完成參數(shù)(completed PMT),它可表示為
式中,Pcij(k)為第k個(gè)候選CMU的第i個(gè)制造任務(wù)的第j個(gè)完成參數(shù),k=1,2,…,mi。
在CMC的構(gòu)建過(guò)程中,針對(duì)制造任務(wù),結(jié)合制造任務(wù)完成參數(shù)與預(yù)期制造任務(wù)參數(shù),優(yōu)化任務(wù)參數(shù)的最優(yōu)解為最優(yōu)制造任務(wù)參數(shù)(optimal PMT),它可表示為
式中,Poij為第i個(gè)制造任務(wù)的第j個(gè)最優(yōu)參數(shù)。
在構(gòu)建CMC的過(guò)程中,盟主CMU在市場(chǎng)上尋求協(xié)作CMU來(lái)完成制造任務(wù),并致力于CMC整體運(yùn)行的最優(yōu)化。盟主CMU根據(jù)產(chǎn)品制造任務(wù)的具體特性,考慮到自身制造資源的不足,尋找協(xié)作CMU來(lái)共同完成制造任務(wù)。盟主CMU對(duì)制造任務(wù)進(jìn)行分解進(jìn)而形成n個(gè)制造子任務(wù),針對(duì)制造子任務(wù)i,盟主CMU提出完成制造子任務(wù)i的預(yù)期參數(shù)Ppij;市場(chǎng)中有mi個(gè)候選CMU對(duì)制造子任務(wù)i進(jìn)行響應(yīng)時(shí),每個(gè)候選CMUk提出自己的制造任務(wù)完成參數(shù)Pcij(k)。CMC任務(wù)參數(shù)優(yōu)化的目標(biāo)就是根據(jù)盟主CMU與候選CMU雙方的參數(shù),建立適當(dāng)?shù)膬?yōu)化數(shù)學(xué)模型,得到適當(dāng)?shù)闹圃烊蝿?wù)參數(shù)。CMC優(yōu)化構(gòu)建過(guò)程分析見(jiàn)圖2。
在CMC的構(gòu)建過(guò)程中,當(dāng)盟主CMU提出制造任務(wù)完成參數(shù)Pc時(shí),針對(duì)第k個(gè)候選協(xié)作CMU所提出的Pci,我們可以考察任一制造任務(wù)參數(shù)P與Pci之間的參數(shù)距離。參數(shù)距離描述兩個(gè)多維參數(shù)指標(biāo)的平均偏差。對(duì)所有候選協(xié)作CMU,計(jì)算P與Pc中每個(gè)Pc(k)的平均參數(shù)偏差。平均參數(shù)偏差表示制造任務(wù)完成參數(shù)Pc相對(duì)于任一制造任務(wù)參數(shù)P的分布情況,即Pc整體所表現(xiàn)出來(lái)的穩(wěn)定與波動(dòng)、集中與離散的程度。顯然,該值越小,說(shuō)明Pc相對(duì)于P的分布越集中,P所代表的制造任務(wù)參數(shù)值越接近于市場(chǎng)中實(shí)際制造資源的供給情況。
圖2 CMC優(yōu)化過(guò)程分析
為了便于CMC參數(shù)優(yōu)化建模,這里引入向量、向量范數(shù)的概念。衡量?jī)蓚€(gè)多維向量之間的距離有多種方法,如街區(qū)距離、歐氏距離、明考夫斯基距離等。由于歐氏距離的概念清晰、簡(jiǎn)單,因此,本文應(yīng)用歐氏距離來(lái)度量多維向量之間的距離。
3.2.1 制造任務(wù)參數(shù)向量的歐氏距離
在CMC的構(gòu)建過(guò)程中,對(duì)于任一制造任務(wù)的參數(shù)Pi與第k個(gè)候選協(xié)作CMU所提出的制造任務(wù)完成參數(shù)Pc(k),如果將它們基于制造任務(wù)的序數(shù)展開(kāi)為向量形式,那么可得到這兩個(gè)向量之間的加權(quán)向量歐氏距離,記為di(P)。
令λj為第j個(gè)任務(wù)性能參數(shù)的權(quán)重系數(shù),
則得到
3.2.2 制造任務(wù)參數(shù)優(yōu)化目標(biāo)
在CMC的構(gòu)建過(guò)程中,對(duì)于所有n個(gè)制造子任務(wù)的參數(shù)P與對(duì)應(yīng)的每一個(gè)Pci中的di(P)的總和,設(shè)為制造任務(wù)參數(shù)優(yōu)化目標(biāo),記為f(P)。根據(jù)制造任務(wù)參數(shù)、制造任務(wù)完成參數(shù)以及歐氏距離的概念,令wi表示第i個(gè)制造子任務(wù)的權(quán)重系數(shù),則得到
相對(duì)于二進(jìn)制編碼,實(shí)數(shù)編碼直觀性好,避免了位編碼與實(shí)參數(shù)間的轉(zhuǎn)換操作,以及由此引起的量化誤差,并在理論上能以任意精度取得結(jié)果;同時(shí)實(shí)數(shù)編碼形式可以使編碼和問(wèn)題的解具有明顯的對(duì)應(yīng)關(guān)系。因此,本文采用實(shí)數(shù)編碼機(jī)制(見(jiàn)表1)。
表1 編碼機(jī)制
對(duì)于包含n個(gè)MTU的制造任務(wù),將從1到n所有MTU所對(duì)應(yīng)的PMT按照升序展開(kāi),形成一條染色體。每條染色體就代表一種選擇,可以表示如下:
則在約束條件(式(3))下,目標(biāo)函數(shù)(式(2))可表述為優(yōu)化函數(shù):
通過(guò)模型轉(zhuǎn)換,得到的式(4)與式(5)比原來(lái)的式(2)與式(3)更清晰、更具體。對(duì)于較大規(guī)模的組合優(yōu)化問(wèn)題,傳統(tǒng)的數(shù)學(xué)方法難以獲得優(yōu)化解,但是應(yīng)用遺傳算法卻相對(duì)容易。
標(biāo)準(zhǔn)遺傳算法采用固定的交叉算子與變異算子,這嚴(yán)重影響了算法的收斂性,易陷入局部最優(yōu)。為了提高算法的收斂速度。本文采用根據(jù)適應(yīng)度值自適應(yīng)改變交叉算子與變異算子的機(jī)制。進(jìn)行選擇操作時(shí),按適應(yīng)度值大小,保留本代最優(yōu)個(gè)體進(jìn)入下一步操作(交叉或變異),而不是直接進(jìn)入下一代,其余個(gè)體按輪盤賭進(jìn)行隨機(jī)選擇。
遺傳算法解的搜索是在適應(yīng)度值的引導(dǎo)下進(jìn)行的,所以應(yīng)該根據(jù)適應(yīng)度值的大小動(dòng)態(tài)調(diào)整交叉與變異算子,加快收斂速度。交叉概率pc越大,產(chǎn)生新個(gè)體的速度就越快;然而,pc過(guò)大時(shí)遺傳模式容易被破壞,適應(yīng)值高的個(gè)體不容易保持,但是pc過(guò)小,搜索速度會(huì)變慢。如果變異概率pm過(guò)小,就不容易產(chǎn)生新個(gè)體;過(guò)大則搜索過(guò)程成了純粹的隨機(jī)搜索。如果用固定的交叉與遺傳算子,對(duì)于給定的優(yōu)化問(wèn)題,需要不斷調(diào)整來(lái)確定其值?;诖?,本文提出自適應(yīng)動(dòng)態(tài)調(diào)整交叉與變異算子的機(jī)制。pc與pm按以下公式進(jìn)行自適應(yīng)調(diào)整:
式中,fmin為種群中最小的適應(yīng)度值;f為每代種群的平均適應(yīng)度值;f′為要交叉的2個(gè)個(gè)體中較小的適應(yīng)度值;f為要變異個(gè)體的適應(yīng)度值;k1,k2,k3,k4∈ [0,1]。
本文采用的自適應(yīng)遺傳算法在群體收斂至局部極值附近時(shí),增大變異概率,從而增加群體多樣性,跳出局部解;當(dāng)群體在解空間分散時(shí),則增大交叉概率,加快收斂速度,這樣既保證了向全局最優(yōu)解逼近,又保證了一定的收斂速度。
優(yōu)化仿真試驗(yàn)以某金屬制品公司一種產(chǎn)品的制造為應(yīng)用實(shí)例進(jìn)行分析,該產(chǎn)品為金屬密封圈,試驗(yàn)中的數(shù)據(jù)來(lái)源于該企業(yè)的生產(chǎn)計(jì)劃部門。盟主CMU分析產(chǎn)品制造過(guò)程,結(jié)合自身制造資源狀況,需要尋找其他CMU構(gòu)建CMC進(jìn)行協(xié)作制造。
針對(duì)該產(chǎn)品CMC構(gòu)建過(guò)程,盟主CMU將該制造任務(wù)分解為5個(gè)可以獨(dú)立進(jìn)行市場(chǎng)運(yùn)作的MTU,它們分別是開(kāi)模、精密鑄造、熱處理、精加工與檢驗(yàn),記為 (T1,T2,T3,T4,T5)。每 一 項(xiàng)MTU有3個(gè)性能參數(shù):制造周期MT、制造費(fèi)用MC、成品率MQ。
盟主CMU經(jīng)過(guò)市場(chǎng)前期調(diào)研,分別就各MTU與有協(xié)作意向的CMU建立了聯(lián)系。盟主CMU根據(jù)自身制造資源的綜合條件,結(jié)合制造任務(wù)自身特性及需求,提出了對(duì)各MTU的完成指標(biāo)參數(shù)。所有MTU對(duì)應(yīng)的候選協(xié)作CMU及其完成參數(shù)Pc見(jiàn)表2。
盟主CMU根據(jù)制造任務(wù)的特性及需求,提出了制造任務(wù)參數(shù)值域(表3)和預(yù)期制造任務(wù)參數(shù)(表4)。
PMT的權(quán)重可以根據(jù)對(duì)CMC運(yùn)行的風(fēng)險(xiǎn)及其影響來(lái)評(píng)價(jià)。MTU的權(quán)重應(yīng)該根據(jù)具體的市場(chǎng)環(huán)境、任務(wù)的結(jié)構(gòu)及參數(shù)來(lái)確定。本例中,制造協(xié)作CMU的權(quán)重與MTU的權(quán)重取值見(jiàn)表5。
表2 候選協(xié)作CMU及完成參數(shù)Pc
表3 PMT的取值區(qū)間值域
表4 預(yù)期PMT Pp
表5 權(quán)重值
根據(jù)遺傳算法的染色體編碼機(jī)制,確定
則由5個(gè)MTU構(gòu)成的制造任務(wù)參數(shù)序列為
那么,染色體可以表示為
遺傳算法的相關(guān)參數(shù)取值具體見(jiàn)表6。
表6 遺傳算法參數(shù)取值
計(jì)算條件如下:Pentium 4主頻2.66GHz的CPU、512MB內(nèi)存、WinXP操作系統(tǒng)、MATLAB 7.0軟件。采用實(shí)數(shù)編碼的自適應(yīng)遺傳算法進(jìn)行CMC性能參數(shù)優(yōu)化,得到目標(biāo)函數(shù)的最優(yōu)值,即min f(P)=4.5616。得到的最優(yōu)解為
其CMC參數(shù)優(yōu)化仿真曲線在迭代次數(shù)接近300時(shí)趨于穩(wěn)定,見(jiàn)圖3。
圖3 自適應(yīng)遺傳算法迭代過(guò)程
預(yù)期制造任務(wù)參數(shù)Pp與獲得的最優(yōu)制造任務(wù)參數(shù)P*的對(duì)比見(jiàn)表7。根據(jù)理想解(PIS)與負(fù)理想解(NIS)所確定的PMT的取值范圍如圖4中陰影所示,用折線連接的點(diǎn)表示最優(yōu)解P*。
表7 PMT Pp與P*的對(duì)比
分析遺傳算法計(jì)算過(guò)程的搜索空間,并與應(yīng)用TOPSIS方法[7]的搜索空間相比較。TOPSIS法是一種常用的有限方案多目標(biāo)(屬性)決策分析法。然而,TOPSIS法有不容忽視的不足之處:與“理想解”歐氏距離更近的方案可能與“負(fù)理想解”的歐氏距離也更近,按相對(duì)歐氏距離對(duì)方案作排序的結(jié)果并不能完全反映出各方案的優(yōu)劣性。
應(yīng)用TOPSIS于本例中,理想解(PIS)表示
圖4 TOPSIS中值域與P*的對(duì)比
從而,根據(jù)理想解與負(fù)理想解所確定的PMT的取值范圍如圖4中陰影所示。用折線連接的散點(diǎn)表示最優(yōu)解P*,可以看出,基因位3與7處的取值并不在陰影區(qū)間內(nèi)。表明CMC的協(xié)作雙方可以通過(guò)協(xié)商,調(diào)整響應(yīng)制造子任務(wù)的制造成本與制造周期。同時(shí)也表明自適應(yīng)遺傳算法擴(kuò)大搜索區(qū)間的方法優(yōu)于TOPSIS方法。
針對(duì)優(yōu)化仿真結(jié)果,進(jìn)行分析如下:
(1)對(duì)比表3與獲得的最優(yōu)解P*,可以發(fā)現(xiàn)
(2)從表7可以看出,MTU1、MTU3與MTU4狀況相似。最優(yōu)解P*的制造成本MC均高于對(duì)應(yīng)的預(yù)期制造任務(wù)參數(shù)Pp的制造成本MC,而制造周期與成品率均低于預(yù)期制造任務(wù)參數(shù)Pp的對(duì)應(yīng)參數(shù)值。這表明上述3個(gè)MTU可以在較短的制造周期內(nèi)完成,但是制造成本較高。
(3)MTU2的狀況與 MTU5相似。最優(yōu)解P*的制造周期MT均長(zhǎng)于預(yù)期制造任務(wù)參數(shù)Pp對(duì)應(yīng)的參數(shù),但制造成本MC與成品率MQ卻低于對(duì)應(yīng)的預(yù)期制造任務(wù)參數(shù)Pp對(duì)應(yīng)的參數(shù)。說(shuō)明制造子任務(wù)MTU2與MTU5的完成技術(shù)難度較高,需要花費(fèi)較長(zhǎng)的制造時(shí)間。
(4)預(yù)期制造任務(wù)參數(shù)Pp與最優(yōu)解P*之間存在著差距,表明盟主CMU對(duì)制造任務(wù)的屬性估計(jì)不準(zhǔn)確,對(duì)市場(chǎng)調(diào)研不夠深入,應(yīng)該結(jié)合具體的市場(chǎng)協(xié)作制造資源環(huán)境,針對(duì)制造任務(wù)的參數(shù)需求進(jìn)行重新調(diào)整。
本文提出了網(wǎng)絡(luò)環(huán)境下協(xié)同制造鏈的概念,對(duì)制造任務(wù)參數(shù)進(jìn)行形式化描述。詳細(xì)論述了協(xié)同制造鏈的優(yōu)化構(gòu)建過(guò)程、基于制造任務(wù)參數(shù)歐氏距離的優(yōu)化模型以及基于自適應(yīng)遺傳算法的制造任務(wù)與資源的優(yōu)化配置?;谥圃烊蝿?wù)參數(shù)距離模型構(gòu)建的協(xié)同制造鏈,能夠有效地?cái)U(kuò)大搜索區(qū)間,便于獲得最優(yōu)解。對(duì)優(yōu)化結(jié)果的分析表明,協(xié)同制造鏈構(gòu)建過(guò)程是一個(gè)制造任務(wù)與制造資源相互協(xié)調(diào)演進(jìn)的過(guò)程,應(yīng)該結(jié)合具體的制造任務(wù)參數(shù)和市場(chǎng)協(xié)作制造資源環(huán)境,不斷調(diào)整才能獲得最佳的任務(wù)與資源的匹配,快速、及時(shí)地響應(yīng)市場(chǎng)的需求變化。
[1]倪中華,江勇.面向網(wǎng)絡(luò)化制造的動(dòng)態(tài)自組織制造資源模型的研究[J].中國(guó)機(jī)械工程,2004,15(20):1823-1826.
[2]王景峰,王剛,呂民,等.基于產(chǎn)品結(jié)構(gòu)的制造服務(wù)鏈構(gòu)建研究[J].計(jì)算機(jī)集成制造系統(tǒng),2009,15(6):1222-1230.
[3]Davulcu H,Kifer M,Pokorny O,et al.Modelling and Analysis of Interactions in Virtual Enterprises[C]//Proceedings of the Ninth International Workshop on Research Issues on Data Engineering.Information Technology for Virtual Enterprises.Sydney,Australia,1999:12-18.
[4]Fischer M,Jahn H,Teich T.Optimizing the Selection of Partners in Production Networks[J].Robotics and Computer-Integrated Manufacturing,2004,20:593-601.
[5]Yao C F,Zhang D H,Peng W L,et al.Research on Resources Optimization Deployment Model and Algorithm for Collaborative Manufacturing Process[J].International Journal of Production Research,2006,44(16):3279-3301.
[6]吉鋒,何衛(wèi)平,王東成,等.網(wǎng)絡(luò)制造環(huán)境下面向復(fù)雜零件的協(xié)同制造鏈研究[J].計(jì)算機(jī)集成制造系統(tǒng)-CIMS,2006,12(1):71-76.
[7]Hwang C L,Yoon K.Multiple Attribute Decision Making[M].Berlin:Springer-Verlag,1981.