基于同形塊的剪切下料布局算法研究.pdf

1、布局問題屬于高復雜度的典型NP難度問題，對機械、船舶和汽車等制造行業(yè)有重要意義。本文研究了二維剪切下料布局問題，優(yōu)化目標是:尋求一個毛坯布局方案，使板材利用率最高?；趧討B(tài)規(guī)劃算法和背包問題精確算法，本文提出了兩類基于同形塊布局方式的精確布局算法。結合列生成的線性規(guī)劃求解算法，提出了基于同形塊的布局方案精確算法。實驗結果比國際上針對同類問題的常用有效算法在時間價值比方面有明顯改善，并化簡了下料切割工藝。
　　本研究主要內容包括：⑴

2、根據(jù)實際生產中允許毛坯轉向的要求，提出了生成三種新型同形塊布局方式的精確算法:同形塊兩階段布局方式算法、同形塊兩段布局方式算法和同形塊三階段布局方式算法。⑵針對某些行業(yè)存在毛坯方向固定的要求，本文將同形塊轉換為一種特殊結構—單毛坯條帶，提出了生成三種新型單毛坯條帶布局方式的精確算法:單毛坯條帶兩階段算法、單毛坯條帶兩段算法和單毛坯條帶三階段算法。⑶將上述六種布局方式算法與列生成的線性規(guī)劃方法結合生成解決生產中大規(guī)模二維剪切下料布局問題的

3、布局方案精確算法。⑷將本文的新型布局方式與目前常用的布局方式進行分析對比，得出各種布局方式優(yōu)化效果的大小關系，并分析得出本文布局方式的四個特性:板材利用率高、切割工藝簡單、生產周期短和布局方式易擴展性。⑸在以上布局方式算法和布局方案算法的基礎上，本文設計了解決大規(guī)模二維無約束剪切布局問題和二維剪切下料布局問題的運行環(huán)境GCSRE，在GCSRE上運行共120例算例，將本文算法與目前多種常用有效算法進行比較，通過大量的對比實驗來驗證本文算法