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

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

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

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

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

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

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

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