一維下料CAD 系統(tǒng)的測試與評價(jià)*

李好學(xué) 楊 柳 崔耀東

(①河南機(jī)電高等?？茖W(xué)校機(jī)電系，河南 新鄉(xiāng) 453003;②廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

制造業(yè)經(jīng)常需要將線材(型材、管材、棒材等)切成各種長度的毛坯，用于制造產(chǎn)品。采用一維下料CAD 系統(tǒng)確定下料方案，可以有效地降低產(chǎn)品成本。本文通過對一維下料過程與應(yīng)用軟件的分析，闡述CAD 系統(tǒng)應(yīng)該考慮的優(yōu)化目標(biāo)與工藝約束;以五種影響較大的CAD 系統(tǒng)為對象，通過示例說明如何對系統(tǒng)功能進(jìn)行測試與評價(jià)。目的是使通過閱讀本文，潛在的軟件設(shè)計(jì)者能夠根據(jù)所面向的用戶，確定CAD 系統(tǒng)應(yīng)該具有的功能;潛在的用戶能夠根據(jù)自身需求的特點(diǎn)，通過功能測試選擇CAD 系統(tǒng)。

1 一維下料問題及排樣方案的特點(diǎn)

在一維下料問題(1DCSP:1D Cutting Stock Problem)中，使用庫存M 種線材切割m 種毛坯。第i 種毛坯的長度和需求量分別為li和di，第k 種線材的長度、庫存量(根數(shù))和單價(jià)(每根價(jià)值)分別為Lk、Dk和Ck，i=1，…，m;k=1，…，M。1DCSP 的解是一個(gè)排樣方案，其中包括若干個(gè)排樣方式。排樣方案具有下列特點(diǎn):

(1)每個(gè)排樣方式所含毛坯總長度和切口損耗材料長度之和，不超過所用線材的長度。

(2)排樣方案所含每種毛坯的數(shù)量等于其需求量。

(3)排樣方案所使用的每種線材的根數(shù)不超過其庫存量。

為方便起見，以下敘述中將不考慮切口損耗。本文使用下料示例如下:使用8 種型材切割16 種毛坯;表1 所示為型材數(shù)據(jù)，假定每根型材的價(jià)格等于其長度;表2 所示為毛坯數(shù)據(jù)，毛坯總長度341 108 mm。圖1 所示為一個(gè)下料方案，每個(gè)排樣方式左側(cè)給出“序號* 線材長度* 線材根數(shù)”。例如，排樣方式1 使用長度為3 000 mm 的線材18 根，每根線材中含3 號、7 號和12 號毛坯各1 件。排樣方案含12 個(gè)排樣方式，共使用線材88 根，總長度為34 200 mm。排樣方案的材料利用率為99.74%(=341 108/342 000)。不難驗(yàn)證每種毛坯的需求都得到了滿足，每種線材的使用量不超過庫存量。例如對于7 號毛坯，按排樣方式1 切出18 件，按排樣方式9 和10 各切出1 件，切出的總數(shù)正好等于需求量20 件。

表1 示例的型材數(shù)據(jù)

表2 示例的毛坯數(shù)據(jù)(總長度341 108 mm)

2 一維下料CAD 系統(tǒng)的優(yōu)化目標(biāo)

1DCSP 通常是個(gè)多目標(biāo)優(yōu)化問題，主要目標(biāo)通常是線材成本最小。此外，尚需考慮減少排樣方式數(shù)、減少短材料庫存、集中余料等次要目標(biāo)。

減少排樣方式數(shù):下料機(jī)床通常有多把切割刀具。將按同一排樣方式切割的一根或多根線材裝夾好后，沿垂直于線材長度方向一次進(jìn)刀，就可以將這些線材切成毛坯。每更換一個(gè)排樣方式，就需要調(diào)整全部或部分刀具的位置，以保證切下的各種毛坯具有準(zhǔn)確的長度。減少排樣方案中所含排樣方式數(shù)，就可以減少刀具的調(diào)整次數(shù)，從而降低下料成本。

減少短材料庫存:短材料即長度較短的線材，可以是過去下料過程中產(chǎn)生的余料，也可以是從市場上購買來的。短材料通常較難有效利用，庫存管理也較麻煩。在不明顯提高線材成本的前提下，生成下料方案時(shí)應(yīng)盡量使用短材料。

集中余料:有時(shí)因庫存線材種數(shù)少或毛坯平均需求量小等原因，導(dǎo)致余料較長。這時(shí)應(yīng)盡量將余料集中到排樣方案的最后一根線材上，產(chǎn)生一根較長的余料，返回庫存供以后使用。

盡管1DCSP 可能涉及的目標(biāo)很多，但對于具體的生產(chǎn)環(huán)境，目標(biāo)數(shù)就不一定多，通常只考慮1～3 個(gè)目標(biāo)就夠了。常采用兩種方式處理1DCSP 的多目標(biāo):成本法和優(yōu)先級法。成本法的優(yōu)化目標(biāo)是總成本最小，要求將每個(gè)目標(biāo)都按金額折算。優(yōu)先級法按重要性排定目標(biāo)順序，優(yōu)先考慮高優(yōu)先級的目標(biāo)。

設(shè)計(jì)CAD 系統(tǒng)時(shí)，采用文獻(xiàn)［1］中的算法可以達(dá)到減少排樣方式數(shù)的目的，采用文獻(xiàn)［2］中的算法可以達(dá)到減少短材料庫存的目的，采用文獻(xiàn)［3］中的算法可以達(dá)到集中余料的目的。

3 一維下料的工藝約束

最大毛坯數(shù)約束和最大毛坯種數(shù)約束是兩個(gè)最為常見的工藝約束。

最大毛坯數(shù)約束:指一個(gè)排樣方式中所含毛坯數(shù)的上限。本約束通常取決于下料機(jī)床所具有的刀具數(shù)，因?yàn)橐笠淮芜M(jìn)刀切下一根線材中所含全部毛坯。

最大毛坯種數(shù)約束:指一個(gè)排樣方式中所含毛坯種數(shù)的上限。按一個(gè)排樣方式切割時(shí)，切下的各種毛坯需要分開存放(例如，一種毛坯占用一個(gè)容器)。毛坯種數(shù)多，需要的容器數(shù)多，占據(jù)的工作場地面積大。因此，本約束取決于可供使用的容器數(shù)或工作場地面積。采用文獻(xiàn)［4］中的算法，可以達(dá)到約束毛坯種數(shù)的目的。

盡管1DCSP 可能涉及的工藝約束很多，但對于具體的生產(chǎn)環(huán)境和下料數(shù)據(jù)，約束數(shù)就不一定多。

4 一維下料CAD 系統(tǒng)的比較分析

筆者從網(wǎng)上下載了五種CAD 系統(tǒng)［A -E］，其中前四種系統(tǒng)(系統(tǒng)A［5］、B［6］、C［7］和D［8］)為國外開發(fā)的商業(yè)CAD 系統(tǒng)的試用版，系統(tǒng)E［9］是國內(nèi)開發(fā)的免費(fèi)軟件。在Google 搜索引擎下，這些系統(tǒng)通過關(guān)鍵詞“Stock Cutting Software”可以找到;系統(tǒng)E 也可通過關(guān)鍵詞“下料軟件”或“排樣軟件”找到。選擇系統(tǒng)E 的原因有二:一是筆者從網(wǎng)上沒有下載到可與前四種系統(tǒng)性能匹敵的國產(chǎn)軟件;二是用前述關(guān)鍵詞搜索時(shí)，系統(tǒng)E 總是出現(xiàn)在搜索結(jié)果的最前面幾條，也許說明其有一定影響。各系統(tǒng)考慮的優(yōu)化目標(biāo)見表3，其中“降低線材成本”是主要目標(biāo)，其它為次要目標(biāo)。下面使用本文示例，說明系統(tǒng)的優(yōu)化功能測試方法。

表3 各種CAD 系統(tǒng)考慮的優(yōu)化目標(biāo)

4.1 降低線材成本的實(shí)驗(yàn)

令各次要目標(biāo)取盡可能小的權(quán)值，表4 總結(jié)出各系統(tǒng)輸出的解的特性?？梢钥闯龀到y(tǒng)A 的線材成本較高外，其他4 種系統(tǒng)的線材成本接近，所耗線材總長度的差別在0.5 m 以內(nèi)。系統(tǒng)E 的排樣方式數(shù)最少，系統(tǒng)C 使用的線材根數(shù)最多(平均長度小)。也即在次要目標(biāo)中，系統(tǒng)E 的解有利于“減少排樣方式數(shù)”，系統(tǒng)C 的解有利于“減少短材料庫存”。

表4 降低線材成本的實(shí)驗(yàn)結(jié)果

后面關(guān)于各次要目標(biāo)的實(shí)驗(yàn)中，只考慮系統(tǒng)C、D和E，因?yàn)橄到y(tǒng)A 和B 不考慮這些目標(biāo)。

4.2 減少排樣方式數(shù)的實(shí)驗(yàn)

設(shè)置后三種系統(tǒng)的次要目標(biāo)權(quán)值，使之優(yōu)先考慮“減少排樣方式數(shù)”。實(shí)驗(yàn)結(jié)果如表5 所示。三個(gè)系統(tǒng)輸出的排樣方式數(shù)相近，平均值比表4 中大為減少。除系統(tǒng)C 外，系統(tǒng)D 和E 的線材成本稍有上升。三個(gè)系統(tǒng)消耗線材總長度的差別在0.9 m 以內(nèi)。系統(tǒng)D和E 的解有利于“減少短材料庫存”，因?yàn)樗鼈兪褂玫木€材根數(shù)較大。

表5 減少排樣方式數(shù)的實(shí)驗(yàn)結(jié)果

4.3 減少短材料庫存的實(shí)驗(yàn)

設(shè)置后三種系統(tǒng)的次要目標(biāo)權(quán)值，使之優(yōu)先考慮“減少短材料庫存”。實(shí)驗(yàn)結(jié)果如表6 所示。系統(tǒng)D使用102 根線材，最有利于“減少短材料庫存”，但其線材成本上升較為明顯。很難評價(jià)系統(tǒng)C 和E 排樣方案的優(yōu)劣，因?yàn)榍罢呦木€材的總長度比后者少0.6 m，但其排樣方式數(shù)多出4 個(gè)，使用的線材少13根，不利于“減少排樣方式數(shù)”和“減少短材料庫存”。系統(tǒng)E 輸出的排樣方案如前面圖1 所示。

表6 減少短材料庫存的實(shí)驗(yàn)結(jié)果

4.4 集中余料的實(shí)驗(yàn)

本文示例由于線材種數(shù)多，材料利用比較充分。將示例修正為:16 種毛坯的需求量均為2(毛坯總長度成為38 584 mm)，只能使用長6 000 mm 的一種線材，以說明集中余料的效果。

設(shè)置后三種系統(tǒng)的次要目標(biāo)權(quán)值，使之優(yōu)先考慮“集中余料”。實(shí)驗(yàn)結(jié)果如表7 所示。三個(gè)系統(tǒng)的線材成本相同，材料利用率均為91.87%，系統(tǒng)E 的最后一根余料長度最長。圖2 所示為系統(tǒng)E 輸出的排樣方案，圖中文字意義和圖1 中相同。

表7 集中余料的實(shí)驗(yàn)結(jié)果

5 結(jié)語

本文根據(jù)一維下料的生產(chǎn)實(shí)踐和對各CAD 系統(tǒng)的分析，闡述了CAD 系統(tǒng)設(shè)計(jì)與選購時(shí)應(yīng)該考慮的優(yōu)化目標(biāo)與工藝約束，供CAD 系統(tǒng)設(shè)計(jì)者和用戶參考。設(shè)計(jì)者可以根據(jù)用戶需求，確定系統(tǒng)要考慮的優(yōu)化目標(biāo)與工藝約束;用戶可以根據(jù)自己的生產(chǎn)特點(diǎn)，提取部分有代表性的下料實(shí)例數(shù)據(jù)，通過實(shí)驗(yàn)計(jì)算，選擇最適合的CAD 系統(tǒng)。

［1］Cui Y，Zhao X，Yang Y，et al.A heuristic for the one dimensional cutting stock problem with pattern reduction［J］.Journal of Engineering Manufacture，2008，222:677 -685.

［2］Cherri A C，Arenales M N，Yanasse H H.The one-dimensional cutting stock problem with usable leftover -a heuristic approach［J］.European Journal of Operational Research，2009，196:897 -908.

［3］Cui Y，Yang Y.A heuristic for the one-dimensional cutting stock problem with usable leftover［J］.European Journal of Operational Research，2010，204:245 -250.

［4］鄭文，崔耀東，周密.一種基于遞歸技術(shù)的一結(jié)下料算法［J］.廣西科學(xué)院學(xué)報(bào)，2010，26(4):415 -417.

［5］Pipe Cutting Suite v5.29［OL］.http://www.optimizecutter.com

［6］1D Cutting Optimizerv1.2［OL］.http://www.optimumcut.com

［7］CutLogic 1D v4.4［OL］.http://www.tmachines.com

［8］1D Stock Cutter 2.94［OL］.http://www.astrokettle.com

［9］BarCutE［OL］.http://www.gxnu.edu.cn/Personal/ydcui/html/Soft-Down.htm