解一維下料問題的一種改進(jìn)的啟發(fā)式算法.pdf

1、在國民經(jīng)濟生產(chǎn)中，存在著大量的切割下料問題。一維下料問題是指原材料和所需坯料維數(shù)都為一維時，在供應(yīng)條件已知的情況下考慮如何優(yōu)化切割下料，使得坯料需求滿足，并且最大限度的提高材料利用率、減少切割損失。一維下料問題在工程技術(shù)和工業(yè)生產(chǎn)中有著重要和廣泛的應(yīng)用，討論該問題是研究二維、三維等多維下料問題的基礎(chǔ)。伴隨著信息化產(chǎn)業(yè)和計算機技術(shù)的快速發(fā)展，先進(jìn)的計算機輔助設(shè)計技術(shù)也越來越多地應(yīng)用于下料過程中。因此，對該問題求解方法的研究在實際應(yīng)用中和理

2、論上都具有重要的意義。 本篇論文討論的是多種長度線材上的下料問題，在對啟發(fā)式算法進(jìn)行分析和研究的基礎(chǔ)上，使用一種改進(jìn)的順序啟發(fā)式算法進(jìn)行一維下料問題的求解。根據(jù)實際生產(chǎn)環(huán)境的需要，通過一系列的改進(jìn)策略，對算法進(jìn)行進(jìn)一步優(yōu)化，在保證較高材料利用率的同時考慮減少排樣方式、增加最后一根材料上余料長度、優(yōu)先使用短材料等多個優(yōu)化目標(biāo)。通過大量的實例測試，證實了本文算法的有效性。本文的主要工作和創(chuàng)新點如下： 首先，針對所研究的問題，

3、給出求解當(dāng)前最優(yōu)排樣方式的數(shù)學(xué)模型，在該模型的基礎(chǔ)上介紹算法的基本思想以及實現(xiàn)流程。本文使用的是一種基于順序價值修正的啟發(fā)式算法。順序價值修正是指每生成一個新的排樣方式前，都利用以前的信息，修正各種毛坯的價值，并多次重復(fù)該過程，最終使其價值系數(shù)達(dá)到較為合理的狀態(tài)。通過適當(dāng)調(diào)整毛坯價值，將他們的相對受歡迎程度體現(xiàn)出來，對不好排的毛坯賦予較高的優(yōu)先權(quán)，使之優(yōu)先被選擇。這樣做有助于生成較好的排樣方式，并利用前面方式的信息，指導(dǎo)后面的排樣過程，

4、從而有效的提高原材料的利用率。 基于當(dāng)前最優(yōu)排樣方式的計算模型，求解背包問題，生成總價值最大的排樣方式?？紤]增加有效排樣方式的數(shù)量，加大選擇空間。因此，在已經(jīng)獲得的排樣方式中，選擇影響其重復(fù)次數(shù)的毛坯進(jìn)行替換，得到更多效果較好的排樣方式。進(jìn)行判斷，依次選取合適的排樣方式組成當(dāng)前排樣方案。多次迭代執(zhí)行該過程，保存較好的排樣結(jié)果。 進(jìn)一步完善和改進(jìn)本文算法。通過采用多種啟發(fā)式策略和參數(shù)優(yōu)化的方法，提高材料利用率、減少排樣方式

5、數(shù)以簡化生產(chǎn)工藝。對待排毛坯進(jìn)行預(yù)分組，每次使用候選組中的坯料生成當(dāng)前排樣方式，坯料子集的選取可有效的減少排樣方式的數(shù)目；設(shè)計排樣方式的選擇標(biāo)準(zhǔn)，優(yōu)先使用較短的原材料，以減少庫存容量；記錄每個排樣方案中最后一個排樣方式的余料長度，算法反復(fù)執(zhí)行多次，較好的一部分排樣方案進(jìn)行保存，優(yōu)先選用余料較長的方案來實現(xiàn)，達(dá)到方便余料回收并再次利用、降低生產(chǎn)成本的目的。考慮到問題的多樣性，對算法涉及的參數(shù)采用循環(huán)方式控制計算。對應(yīng)每一組參數(shù)值，算法迭代