二維矩形切割問題的研究與實(shí)現(xiàn).pdf

1、二維矩形切割問題廣泛存在于各種工業(yè)部門中，如生產(chǎn)鋼鐵制品、紙張、木材、皮革、玻璃等行業(yè)。在所有這些應(yīng)用中，通常都是先生產(chǎn)出少數(shù)幾種標(biāo)準(zhǔn)規(guī)格的大件產(chǎn)品，然后再切割成用戶所要求規(guī)格的成品，這樣往往比直接生產(chǎn)用戶所需規(guī)格成品要經(jīng)濟(jì)的多。然而，切割過程對于生產(chǎn)過程乃至企業(yè)效益有著重要影響，特別是切割貴重材料時(shí)。同時(shí)，切割問題是一類組合問題和調(diào)度問題緊密結(jié)合的復(fù)雜問題。由于組合爆炸，這類問題往往描述成大規(guī)模整數(shù)規(guī)劃，已被證明為是NP-難問題。因此

2、，對于切割問題的研究無論是在理論價(jià)值上還是在實(shí)際生產(chǎn)當(dāng)中都具有重要意義。 本文研究的是矩形材料的切割問題，即二維矩形切割這一類問題。在對已有的二維切割問題分析的基礎(chǔ)上，考慮了幾種研究較少的特殊情形。 其一、考慮了現(xiàn)有文獻(xiàn)中極少考慮的1.5維切割問題，即待切割零件具有固定的維數(shù)和一個(gè)變量，這樣的切割是介于一維和二維之間的。本文針對1.5維切割的特殊性，提出一種兩階段求解方法，并采用混合粒子群算法進(jìn)行求解。實(shí)驗(yàn)結(jié)果表明，該兩

3、階段方法對解決1.5維切割問題是行之有效的。 其二、對于可進(jìn)一步減少切割損耗的切割路徑優(yōu)化問題進(jìn)行討論。通過對切割路徑優(yōu)化問題和旅行商問題的比較，發(fā)現(xiàn)二者有著很多相似點(diǎn)。采用解決旅行商問題的方法來解決一個(gè)路徑優(yōu)化問題，并采用遺傳算法求解。 其三、為了進(jìn)一步減少浪費(fèi)，對排樣切割所剩下的廢料進(jìn)行進(jìn)一步的優(yōu)化利用。由于所剩余的廢料大小、數(shù)量不等，針對此問題建立多目標(biāo)二維切割模型，并采用啟發(fā)式貪心算法求解。實(shí)驗(yàn)表明，該算法能夠在