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

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

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

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

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