滿足“一刀切”約束的卷型材矩形件排樣方法研究.pdf

1、卷型材矩形件排樣問(wèn)題是一類經(jīng)典的NP完全問(wèn)題，主要研究如何將矩形工件排放在長(zhǎng)度可變的矩形原材料上，以獲得高的材料利用率。受某些制造過(guò)程和工藝的影響，卷型材矩形件排樣方案必須滿足“一刀切”約束——“從矩形板材的一端，沿直線方向切割到另一端，將其分割成兩個(gè)獨(dú)立的矩形件”;受生產(chǎn)過(guò)程的約束，某些工件之間有配對(duì)要求，需要盡可能排放在一起。這些工藝約束和生產(chǎn)約束給卷型材矩形件排樣問(wèn)題的求解帶來(lái)新的要求。卷型材矩形件排樣問(wèn)題在制造業(yè)中廣泛存在，諸如

2、造紙、薄鋼板的加工或切割。對(duì)這一問(wèn)題的有效求解方法直接影響企業(yè)的原料成本。
　　本文重點(diǎn)研究工件可旋轉(zhuǎn)的“一刀切”卷型材矩形件排樣問(wèn)題。提出了一種基于組塊策略的啟發(fā)式排樣搜索算法GBHSA(Group-Based Heuristic SearchApproach)。算法將二維矩形件排樣問(wèn)題分解成工件定位問(wèn)題和工件組合問(wèn)題，將多個(gè)工件的組合工件組當(dāng)成一個(gè)整體作為排樣的基本單元;進(jìn)而，提出一種構(gòu)造性的排樣遞歸搜索方法:利用“左下優(yōu)先”

3、原則解決工件的定位問(wèn)題，將排樣過(guò)程轉(zhuǎn)化為“排放→切割”基本步驟的組合，并以利用率閾值作為回溯條件進(jìn)行回溯。算法同時(shí)在切割方案的選擇、排放工件的選擇上運(yùn)用了一系列的啟發(fā)式規(guī)則。組塊策略、啟發(fā)式規(guī)則的使用有效縮減了搜索的解空間，提升了算法的速度，構(gòu)造性的遞歸搜索在一定程度上保證了算法的全局尋優(yōu)能力。通過(guò)使用國(guó)際上通用的一批標(biāo)準(zhǔn)測(cè)試案例進(jìn)行測(cè)試，算法具有一定的先進(jìn)性。
　　同時(shí)，論文還研究了滿足“一刀切”約束的矩形件交互式排樣系統(tǒng)，開(kāi)發(fā)