圓形件排樣優(yōu)化算法及其并行實(shí)現(xiàn)方法研究.pdf

1、排樣優(yōu)化問題廣泛存在于國民經(jīng)濟(jì)生產(chǎn)中的機(jī)械制造、木材服裝加工、印刷排版和交通運(yùn)輸?shù)刃袠I(yè)，采用排樣優(yōu)化技術(shù)實(shí)現(xiàn)對這些行業(yè)生產(chǎn)及運(yùn)營各環(huán)節(jié)資源的優(yōu)化利用，已成為企業(yè)降低生產(chǎn)運(yùn)營成本，提高經(jīng)濟(jì)效益的重要手段之一。排樣優(yōu)化問題是具有極高計(jì)算復(fù)雜度的NPC類問題，研究其求解方法，不僅可以滿足求解生產(chǎn)實(shí)踐中排樣優(yōu)化問題需要，同時也為其他NPC類問題求解方法研究提供了重要的理論依據(jù)。因此，開展排樣優(yōu)化問題求解方法的深入研究，對促進(jìn)實(shí)踐生產(chǎn)發(fā)展和推動計(jì)

2、算科學(xué)理論進(jìn)步都具有極其重要的價值和意義。
　　 圓形件排樣優(yōu)化問題普遍存在于工業(yè)生產(chǎn)和人們生活中，但相比于其他類型排樣優(yōu)化問題研究情況，其求解方法研究仍然較少，并且由于其排樣件形狀相對不規(guī)則，排樣規(guī)律難尋，更加大了問題求解難度。本文在總結(jié)分析國內(nèi)外研究現(xiàn)狀及發(fā)展趨勢基礎(chǔ)上，分別對矩形容器內(nèi)及圓形容器內(nèi)圓形件排樣，提出了一系列新的求解方法，主要工作及研究內(nèi)容有:
　　 (1)針對矩形容器內(nèi)圓形件排樣優(yōu)化問題求解，本文提出

3、一種以啟發(fā)式多策略布局為基礎(chǔ)，基于二分搜索和單親遺傳算法驅(qū)動的混合算法(PGA-BOFA)。算法基于一個嵌套雙重迭代過程實(shí)現(xiàn):內(nèi)核OFA算法，通過定義緊湊度、可行度等優(yōu)選參數(shù)，并引入優(yōu)先占項(xiàng)角、貼邊界等布局策略，能夠求得定長矩形容器內(nèi)圓形件排樣布局;在OFA基礎(chǔ)上，內(nèi)環(huán)BOFA算法利用二分搜索自適應(yīng)找到在指定布局策略下的矩形容器最小長度;外環(huán)通過單親遺傳算法迭代進(jìn)化，動態(tài)改變BOFA算法運(yùn)行的布局策略，驅(qū)動整個算法運(yùn)行，以擴(kuò)大搜索解空間

4、，提高求解質(zhì)量。
　　 (2)對于圓形容器內(nèi)圓形件排樣優(yōu)化問題，根據(jù)排入容器和排樣件特點(diǎn)，本文通過定義偽邊、偽頂角等概念，提出了對圓形容器進(jìn)行擬矩形劃分的設(shè)計(jì)思想，并設(shè)計(jì)了適用于問題求解的布局策略，使得PGA-BOFA算法同樣可以用于圓形容器內(nèi)圓形件排樣優(yōu)化問題求解。
　　 (3)根據(jù)PGA-BOFA算法隱含的并行性特點(diǎn)，并結(jié)合HPC系統(tǒng)高速并行性，基于并行分而治之思想，本文設(shè)計(jì)實(shí)現(xiàn)適用于求解圓形件排樣優(yōu)化問題的并行PG