求解矩形件排樣問(wèn)題的啟發(fā)式算法研究.pdf

1、排樣問(wèn)題是指在下料的過(guò)程中盡量減少材料的損失，使材料的利用率達(dá)到最高。它廣泛存在于加工生產(chǎn)中，如板材切割、集裝箱裝載、服裝和家具制造等。解決好這一問(wèn)題，不僅可以節(jié)省原材料，降低企業(yè)生產(chǎn)成本，而且還可提高企業(yè)生產(chǎn)效率。 矩形件排樣問(wèn)題是二維排樣問(wèn)題的一個(gè)分支。國(guó)內(nèi)外許多學(xué)者對(duì)其進(jìn)行過(guò)深入和廣泛地研究，理論上證明其屬于NP完全問(wèn)題。當(dāng)遇到較大規(guī)模時(shí)，勢(shì)必會(huì)帶來(lái)計(jì)算量的組合爆炸，因此很難在一定時(shí)間內(nèi)取得最優(yōu)解。針對(duì)上述問(wèn)題，目前解決的

2、方法多為啟發(fā)式方法。因此，研究矩形件排樣問(wèn)題既有實(shí)際應(yīng)用價(jià)值，又有理論意義。 啟發(fā)式方法的特點(diǎn)是解決問(wèn)題時(shí)，利用過(guò)去的經(jīng)驗(yàn)規(guī)則，選擇行之有效的方法。對(duì)于大規(guī)模問(wèn)題的優(yōu)化求解，其具有快速隨機(jī)的全局搜索能力，大大減少了計(jì)算量，表現(xiàn)出比其它方法更優(yōu)越的性能。除此以外，啟發(fā)式方法簡(jiǎn)單易行、易于理解，具有良好的可擴(kuò)展性，是解決排樣問(wèn)題的重要工具。 本文研究的是二維矩形件排樣問(wèn)題，即在多張規(guī)格相同的矩形板材上排放一定需求量的毛坯，使

3、得消耗板材的總面積達(dá)到最小?；谏鲜隹紤]，為了求解該問(wèn)題，本文以“最小浪費(fèi)優(yōu)先策略”為基礎(chǔ)，提出了一種分組搜索的啟發(fā)式算法。與其它文獻(xiàn)中報(bào)道的實(shí)例測(cè)試對(duì)比，板材利用率均有所改善，驗(yàn)證了本文算法的有效性。 本文所做的主要工作如下： 第一，認(rèn)真分析了中外學(xué)者提出的多種啟發(fā)式算法，經(jīng)過(guò)仔細(xì)比較，在總結(jié)其優(yōu)缺點(diǎn)的基礎(chǔ)上，對(duì)“最小浪費(fèi)優(yōu)先策略”進(jìn)行了改造?！白钚±速M(fèi)優(yōu)先策略”是從浪費(fèi)區(qū)域的角度考慮，即毛坯排入后是否產(chǎn)生浪費(fèi)區(qū)域以及

4、產(chǎn)生浪費(fèi)區(qū)域的大小。本文在其基礎(chǔ)上提出了兩種改造策略，第一，增加了一個(gè)限制條件，即毛坯排入后如果產(chǎn)生的浪費(fèi)區(qū)域大于某值，則取消其排入。修改后的策略避免了一些不良方案的出現(xiàn)。第二，是毛坯排入的方向。早期的策略使用“最左原則”排入毛坯，取得了很好的效果。本文在其基礎(chǔ)上進(jìn)行改造，增加了一個(gè)“最右原則”。改造后可能會(huì)增加毛坯擺放的多樣性，對(duì)提高板材的利用率或許起到幫助。 第二，考慮優(yōu)化計(jì)算時(shí)間過(guò)長(zhǎng)，以及排樣方案不均衡等問(wèn)題，本文提出了一

5、種分組策略，即把所有的毛坯按面積大小均分三組，每次生成當(dāng)前方式前，都從三組中各選擇適當(dāng)?shù)膲K數(shù)，用于生成當(dāng)前方式。在分組的過(guò)程中，有一些參數(shù)可以依據(jù)實(shí)際情況進(jìn)行調(diào)整。例如，為了確定適當(dāng)?shù)膲K數(shù)，從一組中挑選出的毛坯面積和應(yīng)該定為何值，本文規(guī)定其最大為1倍的板材面積，最小為0.3倍的板材面積。經(jīng)過(guò)分組操作后，選擇了一個(gè)毛坯集合的子集，從而縮短生成當(dāng)前方式所需時(shí)間。 第三，將改造的最小浪費(fèi)優(yōu)先和分組策略相結(jié)合，提出了一種啟發(fā)式算法——分

6、組搜索算法。算法中如何產(chǎn)生排樣序列是其關(guān)鍵步驟。在現(xiàn)有的啟發(fā)式算法中，有些學(xué)者應(yīng)用遺傳學(xué)的原理來(lái)生成排樣序列，已經(jīng)取得了較好的效果。本文引用隨機(jī)局部搜索，利用隨機(jī)交換兩個(gè)毛坯的相對(duì)順序，來(lái)生成新的排樣序列。在隨機(jī)操作中，需要使用一些技巧，當(dāng)隨機(jī)產(chǎn)生兩個(gè)小矩形件的位置時(shí)，如果產(chǎn)生的位置相同，或者兩個(gè)位置上小矩形件是同種，則把其中一個(gè)位置逐漸遞加，直到位置上的兩個(gè)小矩形件是不同種類為止，這樣盡量增加序列的多樣性，避免重復(fù)序列的生成。經(jīng)過(guò)整體

7、重復(fù)計(jì)算后，通過(guò)比較結(jié)果，保存較好的解，得到最終排樣方案。分組搜索算法是一個(gè)組合算法，文中給出了其詳細(xì)的偽碼描述。 第四，通過(guò)對(duì)矩形件優(yōu)化排樣系統(tǒng)框架的分析，分別實(shí)現(xiàn)了其四個(gè)主要模塊功能。包括數(shù)據(jù)輸入模塊、優(yōu)化排樣模塊、排樣結(jié)果顯示模塊、系統(tǒng)幫助模塊。其中算法模塊是整個(gè)框架的核心部分。本文選取了三組文獻(xiàn)中的測(cè)試實(shí)例，其均與本文研究問(wèn)題的排樣規(guī)則相似，因此本文的算法與其測(cè)試結(jié)果具有可比性。經(jīng)過(guò)測(cè)試后，并將實(shí)驗(yàn)結(jié)果與其進(jìn)行了比較和分