矩形件二維剪切下料排樣算法研究.pdf

1、二維排樣問題是具有很高計算復(fù)雜度的NP難度問題，在機(jī)械、家具、船舶等制造行業(yè)中有著廣泛的應(yīng)用。本文研究了矩形件二維剪切下料排樣問題，優(yōu)化目標(biāo)是:尋找一個排樣方案，使得在矩形件毛坯需求量得到滿足的前提下，下料所耗費(fèi)的板材總面積最小。本文從優(yōu)化理論的數(shù)學(xué)模型和其對排樣問題的適應(yīng)性和有效性兩個方面研究了多毛坯排樣和單毛坯排樣，并根據(jù)實際生產(chǎn)中排樣問題的不同要求分別提出了相應(yīng)的排樣優(yōu)化算法。主要工作如下:
　　(1)針對多毛坯排樣問題，首

2、先采用動態(tài)規(guī)劃算法生成最優(yōu)四塊排樣方式。最優(yōu)四塊排樣方式將板材分為四個塊，同一塊中只包含方向和長度均相同的均勻條帶。算法通過求解背包模型生成塊中條帶的最優(yōu)布局，隱枚舉所有可能尺寸的塊，確定所有四塊組合的排樣價值，選擇排樣價值最大的一個組合作為最優(yōu)解。然后采用線性規(guī)劃算法，迭代調(diào)用四塊排樣方式生成算法，每次都根據(jù)生產(chǎn)成本最小的原則改善目標(biāo)函數(shù)并更新各種毛坯的當(dāng)前價值。再按照毛坯的當(dāng)前價值生成新的排樣方式。最后選擇最優(yōu)的一組排樣方式組成排樣

3、方案。實驗結(jié)果表明，該算法在提高材料利用率和簡化下料切割工藝兩方面都有效。
　　(2)針對單毛坯排樣問題，提出一種生成多板材單一矩形件排樣方案的優(yōu)化算法。該算法首先采用具有全容量特性的動態(tài)規(guī)劃方法，按最大板材生成排樣方式，一次性得到所有規(guī)格板材的排樣方式;然后建立整數(shù)規(guī)劃模型，求解下料方案中所用每種板材的張數(shù)，優(yōu)化目標(biāo)是在滿足毛坯需求的前提下使所用的板材總面積最小。實驗結(jié)果表明，對于板材張數(shù)無約束問題和有約束問題，多板材下料算法比