張鵬程,孫亞紅,鄭榮杰

(1.河北工程技術(shù)高等專科學(xué)校,河北 滄州 061001;2.獻(xiàn)縣電力局,河北 滄州 062250)

在沖壓生產(chǎn)中,材料費(fèi)用是主要的生產(chǎn)成本,一般能夠占到總成本的 60%～80%,提高材料利用率是降低沖裁件成本的重要途徑,而材料利用率的高低取決于沖裁件的排樣方案。計(jì)算機(jī)優(yōu)化排樣[1](CAN)是計(jì)算機(jī)輔助設(shè)計(jì)與制造(CAD/CAM)技術(shù)的重要分支之一,它應(yīng)用范圍非常廣泛。在工程應(yīng)用領(lǐng)域中,沖裁件排樣、玻璃切割、報(bào)刊排版、家具下料、服裝裁剪、皮革裁剪、大規(guī)模集成電路設(shè)計(jì)中都存在大量的下料排樣問題[2]。排樣問題是將一系列形狀各異的零件在板材中按最優(yōu)方式進(jìn)行排布,要求零件排放在板材內(nèi),各個(gè)零件互不重疊,并滿足一定的工藝要求。

1 矩形自動(dòng)排樣系統(tǒng)的開發(fā)

1.1 功能需求

矩形排樣系統(tǒng)的處理對(duì)象主要為待排入的矩形及變化的排樣空間,其功能必須具備采集矩形相關(guān)數(shù)據(jù)及排樣參數(shù),自動(dòng)完成排樣操作,排樣完成后能夠輸出最優(yōu)排樣方案及排樣結(jié)果并能動(dòng)態(tài)模擬排樣過程。另外,如果用于指導(dǎo)工程實(shí)踐,系統(tǒng)還應(yīng)具有友好的操作界面,靈活的數(shù)據(jù)采集方式,方便進(jìn)行排樣流程控制;同時(shí)對(duì)于不同的排樣問題,應(yīng)具有很好的適應(yīng)性,能夠快速給出優(yōu)良的排樣方案。

1.2 可行域法的設(shè)計(jì)思想

在排樣求解過程中,一個(gè)最基本的要求就是放入的每一個(gè)矩形不能和已經(jīng)放入的矩形發(fā)生干涉,同時(shí),也不能和排樣空間發(fā)生干涉,否則排樣無效。判斷一個(gè)矩形放入排樣空間中是否發(fā)生干涉是非常繁瑣且計(jì)算量大的過程,而且隨排放矩形的增多,其復(fù)雜程度會(huì)不斷增加。為了避開此類復(fù)雜計(jì)算,本設(shè)計(jì)引入了矩形可行域的概念:首先確定排樣空間,根據(jù)矩形排樣問題的特點(diǎn)它可以被抽象成一個(gè)直角多邊形;當(dāng)排樣空間確定之后,計(jì)算待排矩形在當(dāng)前排樣空間中的可行域,即矩形能夠放入排樣空間中所有有效位置的集合(也是一個(gè)直角多邊形區(qū)域);最后利用定位策略選擇可行域內(nèi)矩形的最佳放置位置,將矩形排入并修改排樣空間。重復(fù)此過程,直至再無矩形可以被放入排樣空間,排樣完成。

1.3 算法流程

在求解矩形排樣問題時(shí),采用可行域確定排樣策略,則可避免一些啟發(fā)式算法對(duì)于不同排樣問題適應(yīng)性及求解效率較差的缺點(diǎn),使排樣問題的求解變得靈活而快速。利用可行域法求解矩形排樣問題可以充分利用矩形可行域所包含的有效信息,將其做為矩形在排樣過程中定序和定位的基礎(chǔ),最終獲得良好的排樣方案。本系統(tǒng)求解矩形排樣問題的算法流程如圖 1所示[3]。

2 矩形排樣系統(tǒng)的實(shí)現(xiàn)

2.1 系統(tǒng)總體結(jié)構(gòu)

矩形智能排樣系統(tǒng)的總體結(jié)構(gòu)如圖2所示。

2.2 系統(tǒng)設(shè)計(jì)

1)排樣空間的描述

排樣空間可以抽象為一個(gè)動(dòng)態(tài)直角多邊形,它隨著排樣過程的進(jìn)行不斷發(fā)生變化。本系統(tǒng)利用MFC中的CArray類定義數(shù)組并按順時(shí)針方向記錄排樣空間的頂點(diǎn)序列。對(duì)于排樣空間的處理主要涉及原始排樣空間的描述、排樣過程中排樣空間的更新以及排樣后期排樣空間的分割、提取、調(diào)整等一系列的內(nèi)容[4-5],這些功能分別由不同的函數(shù)實(shí)現(xiàn)。

2)可行域的計(jì)算

矩形可行域的計(jì)算[6-7]采用偏移多邊形法,由函數(shù)GetFeasibleRegion()來實(shí)現(xiàn)。首先將排樣空間多邊形按矩形的寬和高的 1/2向內(nèi)偏移,獲得其偏移多邊形;為了去掉偏移多邊形的自交部分(如排樣空間的某些區(qū)域矩形不能放入,偏移后必會(huì)發(fā)生自交),搜索偏移多邊形的邊界頂點(diǎn),獲得邊界多邊形;最后對(duì)邊界多邊形的頂點(diǎn)進(jìn)行處理,即可確定矩形的可行域,具體算法及詳細(xì)論述見文獻(xiàn)[7]。

圖1 可行域法求解矩形排樣問題的算法流程圖

3)排樣策略的確定

矩形排樣問題屬于NP完全問題,其求解一般依賴于啟發(fā)式算法。在設(shè)計(jì)時(shí)將矩形的排樣過程分解為兩個(gè)步驟,即定序和定位。對(duì)于定序操作,借鑒人們對(duì)排樣問題傳統(tǒng)直觀的認(rèn)知經(jīng)驗(yàn),采用按待排矩形的面積降序排列,先將面積最大的矩形放入,然后依次在剩余矩形中選擇面積最大的重復(fù)上述操作,即先放大的,再放小的。對(duì)于定位操作,采用文獻(xiàn)[8]中提出的定位函數(shù)法,根據(jù)不同的定位點(diǎn)對(duì)應(yīng)的不同的定位函數(shù)值,結(jié)合評(píng)價(jià)函數(shù)從可行域中選擇最佳的放置位置。

4)排樣過程的實(shí)現(xiàn)

排樣過程的流程如圖1所示。該過程由函數(shù)Layout()實(shí)現(xiàn),首先讀入排樣矩形數(shù)據(jù),并按矩形的面積做降序排列,計(jì)算當(dāng)前矩形在排樣空間中的可行域,然后將可行域多邊形的頂點(diǎn)帶入定位函數(shù)f(x,y)計(jì)算,根據(jù)評(píng)價(jià)函數(shù)minf(xi,yi),選定矩形的合理放置位置(xi,yi)。重復(fù)上述過程,直到矩形數(shù)為0或再無矩形可以放入剩余排樣空間中,排樣完成。

圖2 二維矩形自動(dòng)排樣系統(tǒng)總體結(jié)構(gòu)圖

3 排樣系統(tǒng)的測試及應(yīng)用

運(yùn)行矩形智能排樣系統(tǒng) MyLayout Sys,打開所示參數(shù)設(shè)置對(duì)話框,以文本文件方式輸入排樣數(shù)據(jù),并根據(jù)需要設(shè)定定位函數(shù)的參數(shù)。如圖3所示。

以用開放的矩形排樣數(shù)據(jù)集 http://people.brunel.ac.uk/～mastjjb/jeb/orlib/files/strip3.xls中的矩形數(shù)據(jù)對(duì)該系統(tǒng)進(jìn)行測試。以T7和N7中兩組矩形數(shù)據(jù)為例,矩形數(shù)量分別為197個(gè)和199個(gè),排樣空間為200×200。測試計(jì)算機(jī)配置為Intel PentiumD 925,1G內(nèi)存,矩形按面積降序排入,排樣子空間選取按可行域面積優(yōu)先。定位函數(shù)參數(shù)采用圖 3中數(shù)據(jù),吸引子的位置選在排樣空

間的四個(gè)角上。排樣系統(tǒng)輸出排樣結(jié)果如圖4、圖 5所示。

圖3 定位函數(shù)參數(shù)設(shè)計(jì)輸入對(duì)話框

4 結(jié)論

以基于可行域的矩形排樣問題的求解理論為依據(jù),結(jié)合各類相關(guān)算法,利用VC++6.0作為編程工具,完成了矩形智能排樣系統(tǒng)的設(shè)計(jì)與開發(fā)。在開發(fā)過程中,綜合考慮了不同形式、不同規(guī)模的矩形排樣問題的特點(diǎn),以及工程實(shí)踐中對(duì)于排樣問題的具體要求,從而使得該系統(tǒng)具有簡捷的實(shí)用性,廣泛的適應(yīng)性和較高的穩(wěn)定性。對(duì)于算法及程序本身的優(yōu)化,在一定程度上提高了該問題的求解效率,縮短了獲得優(yōu)異排樣方案的運(yùn)算時(shí)間。實(shí)例證明采用可行域方法求解矩形排樣問題是一個(gè)非常好的思路,它使得整個(gè)求解過程變得簡潔、高效且富于彈性。

[1]崔耀東.計(jì)算機(jī)排樣技術(shù)及應(yīng)用 [M].北京:機(jī)械工業(yè)出版社,2004.

[2]賈志欣.排樣問題的研究現(xiàn)狀及趨勢 [J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2004,16(7):890-897.

[3]Zhang Pengcheng,WangJinmin,Zhu Yanhua.Rectangle Packing Problems Solved by Using Feasible Region Method[C].ICADAM 2008,2008:591-600.

[4]張鵬程,郗艷梅,李國順,等.利用可行域的矩形布局求解方法[J].現(xiàn)代制造工程,2010,354(3):90-93.

[5]Pengcheng Zhang,Hongxia Ren,Yanmei Xi,ect.Calculation and Optimization of Packing Space in Rectangle’s Packing Design[C].ICMS2010,2010:71-74.

[6]張鵬程,王金敏,朱艷華.凹點(diǎn)法求解矩形可行域研究 [J].天津工程師范學(xué)院學(xué)報(bào),2007,(4):40-44.

[7]王金敏,張鵬程,朱艷華.矩形布局可行域的確定 [J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2008,20(2):246-252.

[8]王金敏,楊維嘉.動(dòng)態(tài)吸引子在布局求解中的應(yīng)用[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2005,17(8):1725-1730.