基于貪嚼算法的快速可重組制造系統(tǒng)布局規(guī)劃研究

基于貪嚼算法的快速可重組制造系統(tǒng)布局規(guī)劃研究

在可繁殖于制造系統(tǒng)的布局計劃中，通常有許多優(yōu)化方法，如極值法、數(shù)學(xué)規(guī)劃法、多目標(biāo)優(yōu)化法、網(wǎng)絡(luò)理論、最大原則函數(shù)分析、隨機優(yōu)化法等。采用基于擬陣的貪婪算法,則可以針對不同的生產(chǎn)情況,快速、準(zhǔn)確地響應(yīng)市場不斷變化的規(guī)劃目標(biāo),優(yōu)化可重組制造系統(tǒng)的布局規(guī)劃。1優(yōu)化數(shù)學(xué)模型在快速可重組制造系統(tǒng)布局規(guī)劃的研究內(nèi)容中,系統(tǒng)布置(組態(tài))是一個重要的概念。由于可能的組態(tài)方案很多,如6臺機床組成的制造系統(tǒng)可能有54種組合可能,即:串行、平行和52種混聯(lián)(串并行)可能,因此要采用仿真軟件和產(chǎn)品的產(chǎn)出分析軟件來分析評定。為了建立布局的數(shù)學(xué)模型,要確定最優(yōu)準(zhǔn)則并從抽象和簡化某車間的生產(chǎn)情況開始。在訂貨條件下,車間采用基于成本的測度,即在滿足客戶質(zhì)量要求和其它要求的前提下,盡量降低成本;如果訂單產(chǎn)量變化大而快時,應(yīng)主要采用基于完成時間的測度;此外,還要考慮基于加工中心故障率的測度,最優(yōu)性準(zhǔn)則可建立在以下3個測度和它們不同的組合度基礎(chǔ)上:基于成本的測度、基于完成時間的測度、基于故障率懲罰的測度。通常,要根據(jù)不同的最優(yōu)準(zhǔn)則來進(jìn)行不同的規(guī)劃布置。以江蘇某計算機組件廠為應(yīng)用實例。其車間實際生產(chǎn)情況為:所加工零件為一族零件,具有較高的相似性;在一定時期內(nèi),一個制造系統(tǒng)只生產(chǎn)一種特定的零件;零件加工總數(shù)由訂單和周生產(chǎn)計劃預(yù)先指定;機床能力與每種零件的加工參數(shù)(加工時間、平均加工成本等)為已知,但每種零件加工工序不相同,最大工序數(shù)為m,每道工序可選用的機床有多種加工方案。現(xiàn)對車間的生產(chǎn)情況作一些必要的假設(shè):只考慮CNC加工中心的串行和并行安排;任何CNC機床均可以用于固定的幾種工序;機器Mj(j=1,2…,m)上加工工序Si(i=1,2,…,n)的參數(shù)(時間、成本、故障率)是預(yù)先測定的。在上述已知條件和假設(shè)下,將車間的生產(chǎn)情況簡化為圖1,假設(shè)某零件有3道工序S1,S2,S3,每道工序有幾臺加工中心(方框中為加工中心序號)可以選擇,圖中表示了實際可行的加工方案。這些加工方案組成了一個有向網(wǎng)絡(luò)圖。在每條連線上,定義一個權(quán)ωi,代表連線終端加工中心的主要參數(shù),如加工時間、故障率、成本等等。我們所要研究的就是選擇一條路線,使其具有最小(大)權(quán)基(權(quán)基定義為所有選擇中的權(quán)ωi的總和,最小或最大應(yīng)視參數(shù)性質(zhì)而定),而對于權(quán)ωi所代表的不同參數(shù),則分別求出最小(大)權(quán)基,即為完成不同目標(biāo)的優(yōu)化設(shè)計。假設(shè)ωi代表加工時間,若ω1+ω4+ω6=min(t),則按照時間最短的優(yōu)化判據(jù),應(yīng)選擇如圖1中粗線所示路線。以上問題可以轉(zhuǎn)化為這樣一個矩陣:A=???ω1ω20ω3ω4ω5ω6ω70???A=[ω1ω20ω3ω4ω5ω6ω70]其中每一行代表一道工序,每行中的元素為可選擇的加工中心的權(quán)。這樣,目標(biāo)為求A中元素的一個子集S,使得S中均為非零元素且任何兩個元素不在A的同一行里,以使S中的元素之和最小(大)。由擬陣?yán)碚摽芍?這個矩陣屬于劃分?jǐn)M陣,而此問題的求解是擬陣中的一類典型問題,即求最大(小)權(quán)基的問題。如上所述,將生產(chǎn)實踐中的問題通過簡化、抽象以后,建立了以擬陣為中心的數(shù)學(xué)模型。應(yīng)用擬陣的數(shù)學(xué)模型,其突出的優(yōu)點是算法的通用性,即對于不同的零件和不同的規(guī)劃目標(biāo),只要改變矩陣A的容量和權(quán)ωi,就可用同一種算法完成多種優(yōu)化設(shè)計。2使用一個擬陣的推動方法在各種優(yōu)化算法中,常見的有遺傳算法、單純形法、貪婪算法等等。要選擇一個合適的算法,首先要明確此處優(yōu)化內(nèi)容的特點:屬于中小規(guī)模優(yōu)化問題;數(shù)學(xué)模型比較簡單;對運算的快速性能無特別要求;雖然是單目標(biāo)規(guī)劃,但目標(biāo)具有可變性。本文選用的擬陣的貪婪算法,由于其直觀性和通用性,可以用同一個算法來實現(xiàn)不同的規(guī)劃目標(biāo)。選用這一方法使優(yōu)化問題簡化為由不同的數(shù)據(jù)源得出不同的擬陣。貪婪算法的主要思想是:按元素的權(quán)由大到小的順序,每次找一個最大權(quán)的未檢查過的元素進(jìn)行檢查,若該元素與已選取的元素構(gòu)成獨立集(即不在同一行里),則選取它,否則丟掉它。在剩下的未檢查元素中重復(fù)上述過程,直到選取k個元素為止,最后被選取的元素所構(gòu)成的集合即為所求。對于上節(jié)所得到的矩陣A,其中的獨立集就是不在同一行的元素的集合。或者所有剩下的元素都已檢查完了,此時說明M中不存在k-獨立集。3原型法的開發(fā)和調(diào)試本課題所要求的應(yīng)用軟件應(yīng)體現(xiàn)4個特點:開發(fā)周期短,開發(fā)人員少,系統(tǒng)規(guī)模小、簡單,可以在使用過程中進(jìn)行調(diào)整修改,不要求高度的正確率。為了提高效率,選用原型法進(jìn)行軟件的開發(fā)和調(diào)試工作。開發(fā)工具主要采用MicrosoftVisualC++6.0。其它輔助的開發(fā)工具有MicrosoftVisualFoxpro,為應(yīng)用程序提供數(shù)據(jù)庫支持,同時應(yīng)用VisualC++的ODBC類創(chuàng)建數(shù)據(jù)庫訪問。開發(fā)平臺為Windows98。3.1加工信息表的建立考慮到本系統(tǒng)中所用數(shù)據(jù)具有數(shù)據(jù)量小、邏輯關(guān)系較簡單的特點,不采用數(shù)據(jù)庫格式,而采用自由表的格式,在程序體中通過編程完成查詢、修改等功能。車間數(shù)據(jù)庫主要由5張自由表組成:零件基本信息表、加工工序基本信息表、加工中心及其加工成本信息表、加工中心的加工時間信息表、加工中心的故障率信息表。從零件信息表中,可以得到零件的名稱、包括哪些加工工序及其它相關(guān)信息;從加工工序基本信息表中,可以得到每道工序的名稱及可以用哪些加工中心來進(jìn)行加工;從加工中心及其加工成本信息表中,可以得到每臺加工中心的名稱及其相應(yīng)工序的成本;從加工中心及其加工時間信息表中,可以得到每臺加工中心的名稱及其相應(yīng)工序所用時間;從加工中心及其故障率信息表中,可以得到每臺加工中心的名稱及其相應(yīng)工序的故障率。這5張自由表之間通過獲取表中的邏輯值,可以在程序中完成相應(yīng)的檢索修改功能。3.2生成報告文件系統(tǒng)程序的主要流程為:首先由用戶輸入必要的數(shù)據(jù),包括輸入目標(biāo)產(chǎn)量,選擇所加工零件和規(guī)劃目標(biāo)(最優(yōu)準(zhǔn)則)。數(shù)據(jù)準(zhǔn)備好以后,就可以把這些數(shù)據(jù)作為輸入,應(yīng)用貪婪算法,計算出最優(yōu)化結(jié)果,生成報告文檔。用戶可以根據(jù)這個報告文檔,進(jìn)行下一步的車間布局規(guī)劃。在每一步中,由不同的數(shù)據(jù)表來提供數(shù)據(jù)支持。如在選擇規(guī)劃目標(biāo)以后,需要根據(jù)所選的規(guī)劃目標(biāo)來選擇對應(yīng)的數(shù)據(jù)表。3.3生成報告命令此軟件包括以下幾個用戶界面:(1)數(shù)據(jù)初始化。包括輸入目標(biāo)函數(shù),選擇規(guī)劃目標(biāo),選擇零件。(2)生成規(guī)劃報告文檔。點擊菜單中生成報告命令,可以生成一個文本文件。此文檔的內(nèi)容包括:基本數(shù)據(jù)信息(每天目標(biāo)產(chǎn)量,規(guī)劃目標(biāo),所加工零件ID、名稱及備注);零件加工信息(零件的工序名稱、每道工序可用的數(shù)控機床的名稱);生成的矩陣;運算結(jié)果(每道工序選擇的數(shù)控機床、所需數(shù)控機床數(shù)量、加工參數(shù))。(3)數(shù)據(jù)修改。選擇菜單項中數(shù)據(jù)表選項,用戶可以修改各個參數(shù),同時結(jié)果保存到原數(shù)據(jù)庫中。4制造系統(tǒng)的重組江蘇某計算機組件廠是外資獨資企業(yè),有兩個主要加工車間,主要生產(chǎn)計算機硬盤的磁頭支架,共有9種規(guī)格,1999年的總產(chǎn)量達(dá)到4千萬件。由于客戶訂單的不確定性和多變性,需要定期變換生產(chǎn)計劃(一般為根據(jù)客戶訂單制訂周生產(chǎn)計劃),經(jīng)常需要對制造系統(tǒng)進(jìn)行重組,其中,最長的周期為幾個月,最短的重組周期為8小時。如此頻繁的重組,除了依據(jù)訂單對車間和加工中心進(jìn)行重新布置外,更重要的是考慮加工成本的降低,加工時間的縮短等等一系列因素。在調(diào)研過程中,我們發(fā)現(xiàn),該廠生產(chǎn)車間重組的規(guī)劃,基本上都是采用手工計算的方式來完成的,因此,需要開發(fā)一個規(guī)劃軟件來輔助完成車間的重組規(guī)劃,以代替手工計算部分,達(dá)到快速優(yōu)化重組布置,縮短單件時間、降低成本和提高質(zhì)量與重組準(zhǔn)備周期的目的。4.1各目標(biāo)優(yōu)化下的最優(yōu)化準(zhǔn)則選擇不同的規(guī)劃目標(biāo),運行上面的應(yīng)用程序,選擇名為CONNER的零件,日產(chǎn)量為15000件,在此初始條件下生成3個項目及相應(yīng)結(jié)果,如表1所示。結(jié)果分析:(1)對于擬陣模型A=???ω1ω20ω3ω4ω5ω6ω70???A=[ω1ω20ω3ω4ω5ω6ω70]將不同的參數(shù)代替其中的ωi,則可以得到不同的擬陣,這些擬陣可以通過同一個貪婪算法來得到最優(yōu)解。(2)由表1可以看出,選擇不同的規(guī)劃目標(biāo)即最優(yōu)化準(zhǔn)則,可以得到不同的優(yōu)化結(jié)果。(3)比較各個優(yōu)化結(jié)果,它們之間具有較大差別。至于用戶采用何種最優(yōu)化準(zhǔn)則來進(jìn)行重組規(guī)劃,需要根據(jù)不同的生產(chǎn)情況而定。(4)此軟件只能實現(xiàn)單目標(biāo)規(guī)劃,暫時不能實現(xiàn)多目標(biāo)規(guī)劃。4.2結(jié)果分析表2為江蘇某計算機組件廠115#車間的某日生產(chǎn)任務(wù),以及實際的手工優(yōu)化結(jié)果與使用此軟件得到的優(yōu)化結(jié)果的比較。結(jié)果分析:(1)對比兩組數(shù)據(jù)可見,選擇的數(shù)控機床類型幾乎全同,數(shù)量也大致相同,說明計算結(jié)果與實際情況基本相符,說明此軟件有一定的實用價值。(2)程序優(yōu)化結(jié)果與手工優(yōu)化結(jié)果的機器數(shù)量絕對誤差在1臺到4臺之間,在允許誤差范圍之內(nèi)。(3)誤差源于建模過程中對生產(chǎn)條件和生產(chǎn)過程所作的假設(shè)。因此,要消除誤差,需要建立更加精確的模型。5在多目標(biāo)規(guī)劃時的應(yīng)用(1)隨著RRMS研究的深入,對其系統(tǒng)的規(guī)劃與運作管理的研究將會成為重要的課題?；跀M陣的