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

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

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

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