【摘要】：二維排樣問(wèn)題在許多工業(yè)領(lǐng)域均有應(yīng)用,比如:沖裁件加工、造船、服裝、皮革切割等。排樣效率的微小提升可為這些行業(yè)帶來(lái)巨大的經(jīng)濟(jì)效益。另外排樣算法屬于一類(lèi)組合優(yōu)化問(wèn)題,具有極高的計(jì)算復(fù)雜度,國(guó)內(nèi)外學(xué)者對(duì)此進(jìn)行了幾十年持續(xù)不斷的研究。二維不規(guī)則零件排樣問(wèn)題存在兩大瓶頸:臨界多邊形(NFP)和計(jì)算機(jī)速度。多數(shù)排樣算法都是基于NFP的,但其計(jì)算時(shí)間與零件類(lèi)型數(shù)(N)和轉(zhuǎn)角個(gè)數(shù)(RN)成平方關(guān)系,因此當(dāng)零件數(shù)量很大或旋轉(zhuǎn)角數(shù)目很多時(shí),NFP的計(jì)算時(shí)間將成為一個(gè)巨大障礙。另外排樣優(yōu)化算法歷來(lái)是一個(gè)需要多次迭代的耗時(shí)算法,排樣優(yōu)化問(wèn)題為了得到一個(gè)較為理想的結(jié)果,往往需要幾個(gè)小時(shí)的時(shí)間。針對(duì)以上問(wèn)題,本文主要做了如下幾個(gè)方面的工作。 (1)提出了一種基于矢量格式的零件靠接算法,突破了“矢量圖形靠接速度慢”的論斷。該靠接算法包含兩部分內(nèi)容:多邊形分離判據(jù)和進(jìn)退法。多邊形分離判據(jù)將多邊形之間的相對(duì)關(guān)系歸結(jié)為點(diǎn)與多邊形的包含關(guān)系以及直線段之間相交關(guān)系。至于進(jìn)退法,其思路如下:如果零件分離,則進(jìn);如果零件重疊,則退;直至靠接誤差滿足精度要求。本文通過(guò)一個(gè)算例證明了該算法的高效性。 (2)提出了基于最小勢(shì)能原理的不規(guī)則零件排樣算法(HAPE),揭示了零件排樣問(wèn)題的物理意義:零件總是試圖通過(guò)平移和旋轉(zhuǎn)運(yùn)動(dòng)盡量降低零件的重心高度,從而得到更加緊密的排列。為了尋找最優(yōu)排樣姿態(tài)使零件重心最低,需要在母材上均勻布置一些點(diǎn),讓零件在每個(gè)點(diǎn)間隔一定的角度進(jìn)行旋轉(zhuǎn)。算例表明HAPE是可靠的,且物理意義明確,不需要計(jì)算臨界多邊形,可以處理任意不規(guī)則形狀零件。 (3)將HAPE與爬山算法(HC)和模擬退火算法(SA)結(jié)合產(chǎn)生了兩種混合排樣算法。通過(guò)大量測(cè)試和對(duì)比分析,研究了這兩種混合算法的性能,尤其是RN以及PPD (排樣點(diǎn)間距)對(duì)于排樣密度的影響。對(duì)混合算法表現(xiàn)出來(lái)的“甜蜜”RN現(xiàn)象進(jìn)行了初步的研究。 (4)排樣問(wèn)題并行化在國(guó)內(nèi)外尚處于前沿研究階段。本文成功地將并行計(jì)算應(yīng)用于不規(guī)則排樣算法。測(cè)試結(jié)果表明并行技術(shù)能夠大幅度提高排樣的計(jì)算速度,但考慮到通信開(kāi)銷(xiāo),并行計(jì)算更適合求解大規(guī)模排樣問(wèn)題。
【學(xué)位授予單位】：華南理工大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2011
【分類(lèi)號(hào)】：TH13;TP391.7

【引證文獻(xiàn)】

相關(guān)期刊論文 前1條

1 鐘相強(qiáng);;基于成組原理的船舶件排樣系統(tǒng)研究[J];計(jì)算機(jī)工程與應(yīng)用;2014年15期

相關(guān)碩士學(xué)位論文 前1條

1 劉月明;二維不規(guī)則零件排樣算法及系統(tǒng)的研究[D];華南理工大學(xué);2012年

，

本文編號(hào)：2660210