生成矩形毛坯最優(yōu)四塊排樣方式的精確算法.pdf

1、計算機輔助排樣，又稱為CAN(Computer Aided Nesting)，是廣泛應(yīng)用的計算機輔助技術(shù)之一。CAN廣泛的應(yīng)用于電氣機械制造業(yè)、服裝制造業(yè)、家具制造業(yè)、交通運輸設(shè)備制造業(yè)等行業(yè)。CAN的目的在于尋求某種優(yōu)化的布局方式使平面區(qū)域的面積利用率較高、減少排樣工作量和化簡切割工藝，達(dá)到降低產(chǎn)品成本的目地，最終增強企業(yè)在同行業(yè)的竟?fàn)幜Α?矩形排樣問題是計算機輔助排樣的一個重要分支。由于矩形毛坯優(yōu)化下料方案不僅通過提高材料利

2、用率節(jié)約生產(chǎn)成本，而且可以通過簡化切割工藝、縮短計算時間，提高生產(chǎn)效率，所以對矩形毛坯優(yōu)化排樣問題的研究具有深遠(yuǎn)的理論和實際意義。并且對于不規(guī)則零件的排樣問題，可通過計算機的圖形處理技術(shù)將一個或幾個零件套排在一個包容矩形中，然后對包容矩形進行排樣，從而轉(zhuǎn)化為矩形件排樣問題。 由于排樣問題要考慮到的因素有三個方面：材料利用率、切割工藝和計算時間。在提高材料利用率方面，本文采用四塊排樣方式和線性規(guī)劃相結(jié)合，保證了較高的材料利用率。

3、 另外，由于排樣問題是NP難度問題，如果不對排樣方式加以必要的限制，不僅計算時間難以接受，排樣方式也十分復(fù)雜。本文采用了四塊排樣方式：先用一條豎直或水平剪切線把板材分為左右或上下兩塊，然后每塊分別用垂直于剪切線的兩條直線將其分為兩塊。每個區(qū)域中包含一個由同尺寸毛坯組成的均質(zhì)塊，板材中最多含四種毛坯。實現(xiàn)了四塊排樣方式生成算法FBPFRB，它基于背包問題和動態(tài)規(guī)劃算法，可以求解矩形毛坯無約束二維剪切排樣問題。并且用二十道例題做了對比

4、實驗。然后本文根據(jù)線性規(guī)劃的原理把四塊排樣方式生成算法FBPFRB和線性規(guī)劃結(jié)合后的算法稱為四塊排樣方案生成算法FBPFRBLP，用來求解矩形毛坯下料問題。并且用一道例題做了對比實驗。由于四塊排樣方式由條帶組成，適合剪沖下料工藝的需要；可以單獨應(yīng)用勻質(zhì)塊排樣方式，簡化下料過程的管理，縮短生產(chǎn)周期；和線性規(guī)劃結(jié)合，在求解最優(yōu)排樣方案時，時間效率較高，生成每種排樣方案中的毛坯種數(shù)最多不超過四種，排樣方式簡單，能在一定程度上簡化切割工藝，提高

5、下料效率，有實際應(yīng)用價值。 本文算法分為兩部分： 第一部分為四塊排樣方式生成算法FBPFRB，其步驟如下： 第一步：求解規(guī)范尺寸； 第二步：用動態(tài)規(guī)劃算法確定各種尺寸的勻質(zhì)塊中含每種毛坯的最大數(shù)量值； 第三步：確定四塊排樣方式的最大價值V 并生成排樣方式。 第二部分將FBPFRB和線性規(guī)劃算法LP結(jié)合形成四塊排樣方案生成算法FBPFRBLP，其主要步驟如下： 第一步：給出一個初始基

6、可行解； 第二步：根據(jù)用單純形法求解線性規(guī)劃問題所得到的當(dāng)前基對應(yīng)的檢驗數(shù)，確定每種毛坯當(dāng)前價值系數(shù)； 第三步：調(diào)用FBPFRB算法，根據(jù)毛坯的當(dāng)前價值系數(shù)，生成一個四塊排樣方式； 第四步：如果能夠使解改善，就將生成的四塊排樣方式引入當(dāng)前基并轉(zhuǎn)第二步；否則轉(zhuǎn)第五步； 第五步：輸出排樣方案。 采用文獻(xiàn)中報道的兩組例題進行對比實驗。第一組是矩形毛坯無約束二維剪切排樣實驗，即確定毛坯在一張板材上的排列方

7、式，使板材總價值達(dá)到最大，并且對每種毛坯在板材中出現(xiàn)的次數(shù)沒有約束。采用算法FBPFRB生成了每道例題的最優(yōu)四塊排樣方式，并與二階段方式和三塊排樣方式進行比較，結(jié)果表明四塊排樣方式的平均材料利用較高。第二組是矩形毛坯下料實驗，要求切出全部所需毛坯，使所使用的板材總成本最小。實驗結(jié)果表明：當(dāng)只允許使用均質(zhì)條帶時，使用四塊排樣方式，可以比三塊、二階段、T形和三階段等排樣方式取得較高或相當(dāng)?shù)牟牧侠寐剩划?dāng)允許使用普通條帶時，雖然采用四塊排樣方