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

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

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

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