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

1、矩形毛坯優(yōu)化排樣問題廣泛用于機械制造業(yè)、家具制造業(yè)以及皮革制造業(yè)等行業(yè)。隨著制造行業(yè)市場面臨的競爭日益激烈，有效提高材料的利用率，降低生產(chǎn)成本，是增加企業(yè)效益的有效途徑之一。由于矩形毛坯優(yōu)化下料方案不僅可以提高材料利用率，節(jié)約生產(chǎn)成本，而且可以簡化切割工藝，提高生產(chǎn)效率，所以對矩形毛坯優(yōu)化排樣問題的研究具有深遠的理論和實際意義。 矩形毛坯無約束兩維剪切問題通常是指在一定數(shù)量的長和寬給定的板材上，盡可能多地排放所需要的矩形毛坯，從

2、而使得所消耗的板材盡可能地少，以達到節(jié)省材料的目的。 它屬于典型的組合優(yōu)化問題，己被證明是NP 完全問題，即由于存在計算上的復雜性，在一定時間內(nèi)求其精確全局最優(yōu)解相當困難。國內(nèi)外學者對于該問題的研究給予了足夠的重視，并提出了許多算法。通?？梢圆捎镁_算法和提示算法解決此問題，精確算法只能用于解決規(guī)模較小的排樣問題，實踐中的排樣問題，一般屬于中大規(guī)模，常采用提示算法求解。與矩形毛坯無約束兩維剪切問題緊密相關的矩形毛坯優(yōu)化排樣問題通

3、常是指在滿足對毛坯需求量的前提下，使得板材利用率最高，最大限度地減少廢料，以達到節(jié)省材料的目的。通常采用線性規(guī)劃求解矩形毛坯優(yōu)化排樣問題。線性規(guī)劃是通過反復迭代求解，在每一次迭代過程中，都需要調用矩形毛坯無約束排樣算法，生成一個排樣方式。按是否允許在同一張板材中排入多種尺寸的毛坯，把相應的排樣方式稱為單一排樣方式或套裁排樣方式。和單一排樣相比，套裁排樣雖然切割工藝比較復雜，但能明顯提高材料利用率。本文研究的是矩形毛坯套裁排樣問題。

4、 矩形毛坯優(yōu)化排樣問題是一個多目標優(yōu)化問題，一方面要考慮到板材的利用率，由于國內(nèi)的許多企業(yè)仍處于手工下料階段，下料利用率較低，造成原材料的浪費，提高板材利用率可以節(jié)約生產(chǎn)成本，減少環(huán)境污染，提高企業(yè)效益；另一方面要考慮到生產(chǎn)時的下料效率，生產(chǎn)中常采用剪沖下料工藝分兩階段將金屬板材分割成毛坯，第一階段稱為剪切階段，用平剪床將板材切成條帶，第二階段稱為沖裁階段，用沖床從條帶上分離出毛坯，為了提高下料效率，在設計排樣算法時，通常在保證利用率

5、的前提下，要求生成的排樣方式中所含的毛坯種類數(shù)盡可能的少，以便提高下料利用率。綜合考慮這些因素，本文采用了三塊排樣方式生成算法，它基于背包問題和動態(tài)規(guī)劃算法，可以生成無約束排樣方式-最優(yōu)三塊排樣方式，這種排樣方式是用兩條成T 形的剪切線將板材分成三個矩形區(qū)域，每個區(qū)域中包含一個由同尺寸毛坯組成的均質塊。在此基礎上，通過對解的分析，采用三種策略縮小解的搜索范圍，以縮短求解時間。 將三塊排樣方式生成算法和線性規(guī)劃結合后的算法稱為三塊

6、排樣方案生成算法，它可以生成最優(yōu)三塊排樣方案，用于解決大規(guī)模的矩形毛坯排樣問題。在具體求解過程中，采用單純形法迭代求解線性規(guī)劃，在每次迭代循環(huán)中，都調用最優(yōu)三塊排樣方式生成算法，根據(jù)當前的毛坯單價，生成一個排樣方式。在滿足約束條件的情況下，得出最優(yōu)三塊排樣方案。 采用文獻中報道的基準排樣例題和生產(chǎn)實例對本文的算法進行實驗。對文獻中例題的計算結果表明，與經(jīng)典二階段排樣方式相比，三塊排樣方式生成算法生成的最優(yōu)三塊排樣方式在板材利用率

7、和簡化切割工藝兩個方面都有比較好的效果；與典型排樣算法（二階段、T 形、兩段、三階段排樣算法）相比，三塊排樣方案生成算法在解決大規(guī)模矩形毛坯排樣問題時，雖然板材利用率稍低，但生成的最優(yōu)三塊排樣方案簡單，每種排樣方式中的毛坯種數(shù)最多不超過三種，能夠簡化切割工藝。對生產(chǎn)實例的計算結果表明，三塊排樣方案生成算法的計算時間可以滿足實際應用的要求，生成的最優(yōu)三塊排樣方案的板材利用率較高，排樣方式較簡單，能夠簡化切割工藝。因此，三塊排樣方案生成算法