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

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

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

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

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

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

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

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