基于工藝相似性理論的虛擬制造單元生成研究

0制造單元生成方法現有的制造系統基本上沒有可重建性。如果市場需求發生變化，大量設備將減少、報廢并浪費。可重構制造系統(ReconfigurableManufacturingSystem,RMS)的實施是解決這一問題的根本途徑。可重構的本質是在制造系統全生命周期內通過邏輯或物理構形變化而獲得最大生產柔性。發達國家從20世紀90年代中期開展了有關研究,但目前還沒有成熟完善的RMS實現方法,因此,研究RMS的實現方法有重要意義。RMS的實現可通過改變可重構機床的模塊化構件,或通過移動、更換和添加可移動性設備,或以邏輯重構方式生成虛擬制造單元(VirtualManufacturingCell,VMC)來進行。目前可重構機床的研制正處于初級階段,而且現有制造系統的設備一般為普通設備,設備物理位置大部分被永久固定,因此用改變物理構形的方式實現RMS還有困難;但若以生成VMC的方式實現RMS的邏輯重構,最終將能起到物理重構的效果。這是因為VMC的設備在物理位置上可以不相鄰而且不可移動,在邏輯和概念上卻可以相互關聯構成虛擬動態實體,這種關聯可通過物流系統,如自動導引小車(AutomatedGuidedVehicle,AGV)的路徑網絡來實現,而無需改變現有系統物理布局來完成。制造單元生成方法大多基于成組技術,VMC生成方法一般沒有考慮多工件族間單元共享和單元間設備共享的問題,而且在單元生成前還需預先設置一些參數。例如,Babu等基于不同秩聚類(RankOrderClustering,ROC)提出可生成多種單元構形的單元生成算法,但沒有考慮系統的單元共享,而且還需主觀設置一些參數;Sarker等開發出基于工藝路線和調度而不是單元共享的VMC生成方法,用以在多工件和多機床調度系統中尋找最短生產路線;Ratchev提出基于資源元的類能力模式的制造單元生成方法,將工藝需求動態地與制造系統加工能力相匹配;Ko等基于機床模式的概念給出可實現機床共享的VMC生成算法。目前對制造單元的研究主要集中在單元生成及計劃上,很少有人將其應用到RMS中。本文應用相似性理論提出設備集合模式的概念,并給出在某些假設時的VMC生成方法,以實現RMS的邏輯重構。1虛擬世界的引入VMC是C.R.McLean等人于1982年在對傳統制造單元擴展的基礎上提出的。它是從已有物理資源中抽取出的某個整體或片段,是針對當前生產任務從共享資源庫中選出的合適資源集合,本質上并未改變原有資源物理布局,而僅是在邏輯上進行重構。它是一種基于針對某一生產任務的多工藝路線,通過計算機動態地聚合制造資源庫中的設備而生成的概念性設備組合,即邏輯實體,是一種對物理資源及其之間關系的信息描述,與物理制造單元的根本區別在于它并不消耗真實的物質和能源,需要輸入的是物理資源的信息模型。VMC總是和特定的生產任務聯系在一起,隨任務的改變而構建,隨任務的完成而解散,完成某一任務可能需要多個VMC協同工作。從VMC設備布局形式看,虛擬生產線可視作VMC的一種特殊形態。VMC最為顯著的特點是具有共享性,即在不改變重構對象物理布局的情況下,同一設備可以屬于不同VMC,多種工件的部分工序可由同一VMC來完成。筆者把引入VMC和工件路徑網絡的RMS稱為虛擬RMS。圖1為基于原有車間布局重構出的3個VMC,分別由車床1、銑床、車床2、鉆床,車床1、銑床、鉆床、車床7等,車床7、銑床、焊機等構成,其中,車床1為VMC1和VMC2共享,車床7為VMC2和VMC3共享。虛擬RMS具有以下兩方面優勢:(1)單元內設備物理布局不變在傳統單元制造系統中,對現有單元進行革新時需對設備布局進行物理重構,把屬于同一單元的設備固定在固定物理區域,以最大程度地減少物流運送時間(或距離),但這種布局只有在面向一個單元的工件族不隨時間變化且加工量充足的情況下才是合理的;而在虛擬RMS中,沒有因設備重新布置而產生的成本。(2)單元間設備共享在傳統單元制造系統中,單元通常是針對工件族設計的,不期望存在跨單元加工同一工件和跨單元物流路徑,這樣將造成設備重復設置,設備閑置和設備利用率降低;而在虛擬RMS中,不同單元可以共享相同設備,避免了設備重復設置,提高了設備利用率,節約了生產成本。2rm多工藝路徑的相似性分析2.1系統相似特性及相似要素自然界的一切事物均可視為是由一定要素構成的系統,不同類型和層次的系統間可能存在某些有差異的共有特性,這種有差異的共有特性稱為相似特性。當系統間存在相似特性時,可認為系統間存在相似性。相同和相異是相似的兩個極端,若用相似度Q表示相似性程度,則Q=1表示兩系統特性相同,Q=0表示兩系統特性相異,0<Q<1表示兩系統特性介于相異和相同之間。在系統要素間存在相似特性的要素稱為相似要素,相似要素的存在使系統間具有相似性。相似性本質源于系統間客觀特性的相似性,不依賴于人的感性認識而存在。2.2相同工藝路線相同序結構的相似度RMS多工藝路線表現為由當前生產任務決定的工件工藝信息,將每種工件的這種信息整體視為一個系統Wi,將工件類別pi、工藝路線ri和加工量ni視為系統的構成要素(i為工件種類數),則多工藝路線可表示為一個如下三元組:Wi=[pi?ri?ni]。(1)Wi=[pi?ri?ni]。(1)將設備序號作為ri的要素(即Wi的子要素,可視作ri的特征值),以圖2所示的多工藝路線為例,則有r1=[1,2,…,9],r2=[11,12,…,13],r3=[1,2,…,13]。r1,r2和r3間存在一些相同要素,即相同設備序號,可表示為:uri～rj=ri∩rj(i,j=1,2,3?且i≠j)。(2)uri～rj=ri∩rj(i,j=1,2,3?且i≠j)。(2)r1,r2,r3中的元素數量分別為11,9,9,r1和r2,r1和r3,r2和r3間相同元素的數量分別為7,7,5,按相似度計算公式可得r1和r2,r1和r3,r2和r3間的相似度分別為54%,54%,38%。可見,ri間共有設備越多,則ri間的相似程度越大。系統要素有多種排列組合方式,每種排列順序都代表一種系統序結構特性,當要素排列組合方式有共性時,系統序結構就出現相似性。如果要素中特征元素數量相同,排列順序也相同,則要素序結構特性相同;如果要素中特征元素數量不完全相同,或元素數量相同但排列順序不同,則要素的序結構特性相似。分析以上多工藝路線子要素中存在的相同序結構可以發現,、,、,、分別是r1和r2,r1和r3,r2和r3間的相同設備序列。按相似性理論有以下結論:①在要素中元素數量及排序一定時,相同設備序列越多,則序結構特性相似度越大;②在相同設備序列數量一定時,要素中元素數量越多,則序結構特性相似度越小;③在要素間元素沒有相同設備序列時,則序結構特性相似度為最小;④在要素中元素和設備序列均相同時,則序結構特性相似度為最大。2.3設置相應單元設備集合模式是指在RMS多工藝路線中間存在的至少由兩臺邏輯上連續的設備所構成的相同設備序列。由與設備集合模式相對應的設備構成的制造資源集合稱為候選制造單元(簡稱候選單元)。候選單元只能由候選首末設備各一臺和若干臺其他設備構成,特殊情況下只由候選首末兩臺設備構成。本文中候選單元是運算中間結果,并不是最終生成的VMC,但在特殊情況下一些候選單元可能成為VMC,即候選單元間運算結果中某一(些)VMC可能正好等于某一(些)候選單元。該單元有以下優點:①加工種類較多,可避免設備重復設置;②規模較小,可減少單元內工件移動數量(或物流運動距離);③單元間通過工藝路線關聯,可避免加工過程中出現的工藝路線連接不暢;④具有成組制造單元的所有優點;⑤具有可重構性,制造資源可分布在一個離散、變化的范圍內。由若干候選單元按順序構成的單元序列與一列火車相似,單元相當于車廂,單元序列相當于火車,火車可以根據旅客情況隨時調配各車廂,而單元序列則可以根據生產需求臨時生成各單元。一種工件工藝的完成可能需要多個單元按順序進行,加工過程可看作是將一個傳統制造單元分解為若干有序單元。3vmc生成的相關定義(1)假設備是一種置于每種工件工藝路線的開始和結尾位置的虛假設備標志,其序號用0表示。本文中將序號為0的設備統稱為偽設備。(2)特殊設備是在某條由設備序列表示的已被候選單元更新的工藝路線中,其前趨、后繼設備均為偽設備的設備。(3)作業順序和工藝路線順序排列是一種將多工藝路線以設備對形式,按設備作業順序和不同工藝路線順序排列,來全面表示設備間關系的表,包括序號、工件序號、從設備序號、到設備序號和流量5個字段。(4)設備合并、加速度的計算是一種基于從到表,通過將相同設備對(由偽設備構成的設備對除外)進行合并、累加,并按從設備序號以遞增順序重新排列形成的表,包括序號、工件序號、從設備序號、到設備序號和累加流量5個字段。(5)設備進入to表該表的生成過程同設備從表一樣,不同的是按到設備序號以遞增順序進行排列的。(6)設備入度及出度指表示設備入出度差的表。設備入出度差指設備入度與出度的差,設備入度指到表中所有該設備的前趨設備的數量,設備出度指從表中所有該設備的后繼設備的數量。(7)節點序列重建指在多工藝路線中尋找所有以某設備為起始設備、另一設備為結尾設備且不能包含重復節點的節點序列。例如,兩條工藝路線r1=,r2=,若要尋找的開始、結尾設備為7和9,則從r1和r2中識別出的設備集合模式為。(8)作為篩選單元的確定指用所生成的候選單元取代多工藝路線中與之匹配的設備序列,被取代的設備序列用0表示。如在(7)中,將作為候選單元更新r1和r2,則r1=,r2=,可見r1中的和r2中的被取代了;再如r1=,r2=,r3=,r4=,…,假設生成的候選單元有C1=,C2=,C3=,…,則r1和r2均可由C2和C3來更新,r3可由C1和C3來更新,r4可由C3來更新。4vmc生成算法規則4.1結果規則的合理性(1)如果一臺設備的入出度差dio≥1,且其后繼設備全不是偽設備,則該設備為候選首設備。(2)如果一臺設備的入出度差dio≤-1,且其前趨設備是偽設備,則該設備為候選首設備。(3)如果一臺設備的入出度差dio≥1,且其后繼設備是偽設備,則該設備為候選末設備。(4)如果一臺設備的入出度差dio≤-1,且其前趨設備不是偽設備,則該設備為候選末設備。(5)如果用以上規則(1)和(2)不能生成任何候選首設備,則所有工藝路線中的首設備(偽設備除外)為候選首設備。(6)如果用以上規則(3)和(4)不能生成任何候選末設備,則所有工藝路線中的末設備(偽設備除外)為候選末設備。以上規則的合理性是基于工藝路線中設備間的關聯關系,設備入度和出度能夠表明設備在工藝路線中的相對位置。例如,若設備j的入出度差dj≥1,則表明j的前趨設備要多于后繼設備。若j的后繼設備全不為偽設備時,則可推斷出j為候選首設備,符合上述規則1,這時的候選首設備肯定不是工藝路線中的第一臺設備。若j的后繼設備是偽設備時,則可推斷出j為候選末設備,符合上述規則3,這時的候選末設備并不一定是工藝路線中的最后一臺設備:當j的后繼設備全部為偽設備(即其后沒有其他真實的設備時),則它一定是工藝路線中的最后一臺設備;當j的后繼設備不全為偽設備時,則它不是工藝路線中的最后一臺設備。其他規則的情況可以類推,在此從略。4.2規則2候選人處理規則(1)集合規則如果有幾個候選單元,其中幾個單元(子單元)是另一個單元(父單元)的子集,則可用父單元作為候選單元取代原候選單元。(2)集合規則如果幾個候選單元在起始或結尾兩個位置有兩臺相同設備,則可用這兩臺設備構成的新單元作為候選單元,取代原候選單元。(3)合并成新單元的組合如果幾個候選單元有相同規模,包含的設備臺數大于或等于3,且僅有一臺設備不相同,則可將這幾個單元合并成新單元;如果有三個兩臺設備的候選單元,其中兩個單元共享一臺設備而另一臺設備不相同,第三個單元恰由前兩個單元中不相同的兩臺設備構成,則可將這三個單元合并成新單元。如果一個候選單元總是另一個候選單元的前趨,而后者又總是前者的后繼,則可將這兩單元合并成新單元。(4)單元分解和設備匹配如果工藝路線中沒有設備序列能夠和任何新生成的候選單元相匹配,這種情況下工藝路線中有無法被單元更新的設備(因為沒有生成這樣的單元),則可將已生成的單元分解為幾個兩設備的單元,但需保證分解后至少有一個單元能夠用來與工藝路線中的某一設備序列匹配。以上規則的合理性基于數學中的集合論。5vmc生成結構模型本文建立的VMC生成框架模型如圖3所示。(1)多工藝路線的定義基于制造資源庫,把原始多工藝路線轉換為由設備序號表示(以下將這種轉換后的原始多工藝路線稱為多工藝路線)。基于圖論把多工藝路線轉換為加權有向圖(簡稱多工藝路線圖),將設備表示為節點,設備間的先后工藝關系用弧表示,加工量用弧上權值表示,直接表現形式是設備從到表、從表、到表及設備入出度差表等。(2)設備啟動前件件基于多工藝路線圖,用候選首末設備生成規則生成候選首末設備,候選首末設備一定是屬于多工藝路線圖節點集的元素。(3)選取末設備為結置設備的集合在多工藝路線中,識別所有以候選首設備為起始設備、候選末設備為結尾設備的設備集合模式,將結果表示為候選單元集合,該集合是多工藝路線圖節點集的子集,其元素排列順序與多工藝路線中相應的某一設備序列精確匹配。(4)設備序列精確匹配是試驗集未一定能與工藝路線匹配的一基于集合論和候選單元處理規則,通過單元間集合運算生成VMC。VMC是多工藝路線圖中節點集的子集,但不一定能與工藝路線中相應的某一設備序列精確匹配。在用候選單元更新工藝路線時,工藝路線中凡等于(或包含)候選單元且元素數量大于(或等于)2的設備序列均可用相應候選單元更新(這里將設備序列集合中序號相同的設備視為同一元素),VMC內設備排列順序與工藝路線中設備順序可以不相同。6制造資源集合VMC生成算法的假設條件如下:①重構對象為由有固定物理位置的設備構成的制造資源集合。②生產任務是動態變化的。③某一生產任務(如工件種類、工藝路線及加工量)是確定的。④同一工件可在不同時段內多次“訪問”同一設備。⑤工件運送由AGV(或人)來實現。⑥不考慮重構內因。6.1該算法VMC生成算法的流程圖如圖4所示。6.2創建多工藝路線(1)獲取原始多工藝路線數據;(2)將原始多工藝路線轉換為多工藝路線;(3)基于圖論和多工藝路線創建多工藝路線圖;(4)計算設備的入度、出度及入出度差。6.3設mc+k(1)生成所有候選首末設備并遞增排序,設J和K分別等于候選首末設備數,j=1,Nc=0。(2)設k=1。(3)將所有可用設備的序號存儲在Mu中。(4)將Mu中除第j個候選首設備、第k個候選末設備以外的所有候選首末設備去掉。(5)設置Mt=?,F=0;將第j個候選首設備儲存在Mt中;將Mu中第j個候選首設備去掉;設Mp={0},Mc=?;將第j個候選首設備存儲在Mc中。(6)選取Mu中屬于Mc的所有可用后繼設備。(7)將(6)中所選設備的前趨設備存儲在Mp中;所選設備存儲在Mt和Mc中,設備在Mt中的位置要與其前趨設備在Mp中的位置對應;設Mc=?;從Mu中將(6)中所選設備去掉。(8)對Mc中的每臺設備進行評估。①如果Mc中有1臺設備正好是第k個候選末設備,則設置F=1,轉(9)。②如果Mc中沒有任何設備,則設置F=0,轉(13)。③如果①和②均不滿足,則轉(6)。(9)設Cc=?,Nm=0;從Mt中抽取并去除第k個候選末設備,并將其賦給i。(10)將設備i存儲在Cc中,設Nm=Nm+1。(11)在Mp中查找設備i的前趨設備。①如果查出的設備是偽設備,則輸出Cc及Nm,轉(12)。②如果查出的設備不是偽設備,則從Mt中去掉所查出設備,將該設備序號賦給i,轉(10)。(12)設Nc=Nc+1。(13)若k≠K,則k=k+1,轉向(3);否則轉向(14)。(14)若j≠J,則j=j+1,轉(2);否則轉(15)。(15)輸出Nc。以上算法用到的參數如表1所示。6.4計算工件的偽設備更新的加工量(1)設J和K分別等于新創建候選單元數和工件種類數;按單元大小以遞減順序對所有已創建候選單元重新排序和編號;設m=0,j=1。(2)設k=1。(3)如果工件k的工藝路線中有某一設備序列與候選單元j匹配,則用偽設備替換該設備序列;更新候選單元j的加工量;設m=m+1