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

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

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