基于聚類和區(qū)域?qū)?yōu)的零部件排版啟發(fā)式搜索算法研究.pdf

1、布局問題廣泛存在于多種生產(chǎn)實踐領(lǐng)域，諸如衛(wèi)星艙布置、服裝裁剪、板材下料和電子線路設(shè)計等領(lǐng)域，其研究具有理論價值和實際應(yīng)用價值。Pack ing和Nesting問題，又稱為裝填問題和排版問題，是兩類典型的布局問題。本文以課題來源單位大型起重機(jī)制造為背景，研究基于聚類和區(qū)域?qū)?yōu)的零部件排版問題。其特點是零部件種類繁多、形狀差異很大且多為不規(guī)則形狀。目前課題來源單位使用的是美國開發(fā)的排版軟件SigmaNest10，但對于批量板材的大規(guī)模多形狀

2、零部件排版本問題求解卻是不盡于人意，只好對其排版方案采用人工調(diào)整。為此，本文基于概率論、運籌學(xué)、計算機(jī)圖形學(xué)和人工智能理論，對該問題展開研究，提出了解決瓶頸問題和技術(shù)難點的方法，申請了發(fā)明專利1項。
　　本研究主要內(nèi)容包括：⑴提出了零部件CAD圖形的DXF文件編碼規(guī)則，開發(fā)了自動生成圖元數(shù)據(jù)文件的軟件。設(shè)計的編碼規(guī)則和開發(fā)的軟件適用于由線段、圓弧及圓圖元組成多形狀二維圖形，圖元數(shù)據(jù)文件包括其最小包絡(luò)矩形。設(shè)計的算法的計算復(fù)雜度低，

3、求解速度快。⑵提出了一種基于區(qū)域?qū)?yōu)的多形狀零部件包絡(luò)矩形排版的啟發(fā)式搜索算法?；趨^(qū)域?qū)?yōu)啟發(fā)式搜索算法的排版方案，多形狀二維零件間存在間隙。對此，本文進(jìn)一步提出一種基于La gra nge乘子和k uhn-Tucker條件的鄰界計算法，使得圖形之間盡量靠緊，得到進(jìn)一步優(yōu)化的布局方案。⑶在批量鋼板大規(guī)模多形狀零件排版問題中，針對前面排版利用率高，后面排版利用率低這一難點，提出了一種基于聚類的啟發(fā)式搜索算法，并且設(shè)計了排版流程步驟。通過