動態(tài)規(guī)則在矩形毛坯單一排樣.pdf

1、矩形件排樣優(yōu)化通常是指在一定數(shù)量的長和寬給定的板材上,盡可能多地排放所需要的矩形件,從而使得所需要的板材盡可能地少,以達到節(jié)省材料的目的。這項工作廣泛用于機械制造、輕工、家具以及玻璃切割等行業(yè)。
　　對于非矩形件的不規(guī)則裝配件排樣問題,也可以通過計算機的圖形處理技術(shù)轉(zhuǎn)化為矩形件的排樣問題。矩形件排樣優(yōu)化問題實際上是一個十分困難的問題,從數(shù)學(xué)計算復(fù)雜性理論看,它屬于具有最高計算復(fù)雜性的一類問題:NP完全問題。按是否允許在同一張板材中

2、排入多種尺寸的毛坯,把相應(yīng)的排樣方式稱為套裁排樣方式或單一排樣方式。套裁排樣方式有利于提高材料利用率,但由于單一排樣方式的切割工藝簡單、排樣過程易于管理,往往更容易為用戶所接受。目前,矩形毛坯單一排樣的常用算法主要有動態(tài)規(guī)劃算法、分支定界算法、連分數(shù)算法、多項式時間算法。算法的實現(xiàn)難易程度由動態(tài)規(guī)劃算法到多項式算法依次提高。動態(tài)規(guī)劃算法以其簡單容易實現(xiàn)而經(jīng)常使用,而且在計算中比其它的算法具有一定的優(yōu)勢。在生產(chǎn)實踐中,企業(yè)所購入的板材長度

3、可能超過剪床所能切割的最大長度,排樣時必須先將長板用平行于寬邊方向的切割線分割成多張子板,每張子板的長度均小于等于刀刃長度;然后,在各張子板上切出毛坯。在這里我們把這個問題稱為刀刃長度受限問題。已經(jīng)提出的動態(tài)規(guī)劃算法要求刀刃長度不小于板材長度,否則就有可能生成不能切割的排樣方式,因而不能有效地解決上述問題。
　　本文致力于從實現(xiàn)的角度改進動態(tài)規(guī)劃算法來解決刀刃長度受限的問題。另外已經(jīng)提出的動態(tài)規(guī)劃算法實際上解決的是無約束排樣問題,

4、即如何在單張板材上生成盡可能多的毛坯。在實際生產(chǎn)中,毛坯需求總是有限的。因此,有必要進行有約束排樣。即在滿足毛坯需求量的情況下所使用的板材面積最少。本文從實現(xiàn)的角度闡述了如何對動態(tài)規(guī)劃算法進行改進以進行有約束排樣。另外,本文還討論了如何把單一排樣優(yōu)化算法應(yīng)用于庫存優(yōu)化決策中。市面上有多種尺寸的板材可供選擇,本文討論了如何把采用了動態(tài)規(guī)劃算法與庫存成本計算相結(jié)合來提高庫存決策的科學(xué)性。當企業(yè)從市場上購買不到合適尺寸的板材時,可以考慮在向板