科學(xué)技術(shù)正在迅速發(fā)展,計算機(jī)已經(jīng)融入到國民生產(chǎn)的各個領(lǐng)域中,軟件產(chǎn)品正在逐漸成為社會生產(chǎn)中不可缺少的輔助工具。排樣問題廣泛存在于工業(yè)制造、交通運輸和日常生活管理等重要領(lǐng)域,本文的工作就是推廣和改進(jìn)優(yōu)化方法在板材切割問題中的解決方案。排樣問題常見于工業(yè)生產(chǎn)中,例如玻璃切割、鋼材切割、產(chǎn)品包裝、集裝箱裝載、車廂裝載、托盤組裝,還有文本排版、衣料裁剪以及物品擺放等等。為了降低成本消耗、提高生產(chǎn)效率以及節(jié)約社會生產(chǎn)資源,一個好的排樣方案將帶來巨大的社會生產(chǎn)效益并提高生活與生產(chǎn)質(zhì)量。切割最優(yōu)化問題是排樣問題的一種具體形式。給定一個二維板材和一定數(shù)量的待排樣物品,將待排樣的物品在符合一定約束條件的前提下合理地擺放在空間內(nèi),使得空間利用效率達(dá)到某種最優(yōu)目標(biāo)。排樣的優(yōu)劣將直接或間接影響相關(guān)行業(yè)的生產(chǎn)、傳輸及銷售,繼而影響其經(jīng)濟(jì)收益。切割問題也是一個組合優(yōu)化問題,其最大的挑戰(zhàn)就是組合爆炸,尤其是當(dāng)計算規(guī)模增加時,其組合的規(guī)模將呈現(xiàn)指數(shù)增長。國內(nèi)外專家學(xué)者在這方面進(jìn)行了很多探索提出了很多算法,本文就是在這些算法的基礎(chǔ)上通過分析比較,設(shè)計了一種針對切割問題的擬人算法。討論了在帶有多個缺陷的二維矩形板材上切割... 

【文章來源】：江西財經(jīng)大學(xué)江西省

【文章頁數(shù)】：62 頁

【學(xué)位級別】：碩士

【部分圖文】：

板材一刀切（（a）一刀切

2問題描述9表示：=∑;∈+=1(2.1)其中，F(xiàn)為目標(biāo)函數(shù)，是非負(fù)數(shù)，表示第類目標(biāo)塊的數(shù)量，是正整數(shù)，表示第類目標(biāo)塊塊的面積。其次，建立二維歐式坐標(biāo)系，將矩形原板材的左下角置于坐標(biāo)原點，原板材水平方向跟坐標(biāo)系軸指向，原板材豎直方向為軸指向。這樣，我們可以用四元組=(0,0,,)來表示原板材基本信息，其中(0,0)表示原板材左下角的橫縱坐標(biāo)，表示原板材水平方向的寬，表示原板材豎直方向的高。再次，矩形原板材上不能用于切割出目標(biāo)矩形塊的區(qū)域稱為缺陷區(qū)域。原板材上存在數(shù)量為的缺陷區(qū)域，每個區(qū)域是不規(guī)則形狀的，為了更好地描述缺陷區(qū)域的位置和尺寸信息，我們用一個恰好完全覆蓋缺陷的矩形塊來表示缺陷區(qū)域，并且缺陷的各個邊均平行或垂直于坐標(biāo)軸。因此，缺陷可以用四元組表示為=(,,,)，其中，缺陷區(qū)域左下角坐標(biāo)為(,)，寬為，高為，其中∈。缺陷區(qū)域在坐標(biāo)系中表示如圖2.2。圖2.2缺陷區(qū)域在坐標(biāo)系中的表示最后，為了后續(xù)算法描述方便，我們還要定義兩個常量，它們是和，分別表示所有目標(biāo)塊中最小的寬度和最小的高度，其公式表示如下：=();=1,2,…,=();=1,2,…,2.2問題解法本文作為一種優(yōu)化問題，最大的挑戰(zhàn)就是具有組合爆炸[38]。人們在已掌握的技術(shù)下無法在能接受的時間范圍內(nèi)找到最優(yōu)解，尤其是隨著問題規(guī)模的增加，其

32D_SLOPP的求解算法15子問題_=(0,0+,,)。切割線僅對當(dāng)前中間板而言，換言之，切割線是一個相對值，如果是豎直切割，c表示中間板的左邊界和切割位置橫坐標(biāo)的相對距離，如果是水平切割，表示中間板的下邊界和切割位置的縱坐標(biāo)的相對距離。切割線示意圖如圖3.1。圖3.1切割線的表示3.2離散集在待切割的中間板上我們把同一方向獲得的所有的切割線組成一個離散化的集合稱之為離散集。把這些切割線所在位置信息記錄下來并挨個進(jìn)行分解計算，將一個大問題分解成若干個小問題然后將所得小問題的解反饋，小問題分解成更小的問題，依次類推，將會得到原板材的解，這樣一來即是在原板材上排樣了所有可能的切割模式，選取其中最大的一個值即是原板材的最優(yōu)目標(biāo)值。在中間板上記錄水平和豎直兩個方向的所有切割線，將會形成寬為高為的網(wǎng)格，最終將從眾多的切割線中尋找出一條作為最優(yōu)的切割方式進(jìn)行切割。那么，如果可選的切割線越多就意味著有跟多的可能獲得更大的目標(biāo)值，于是文獻(xiàn)[8]考慮了豎直和水平方向所有的位置作為切割線進(jìn)行計算，將其稱之為完全離散集。用()表示水平方向完全離散集，()表示豎直方向的完全離散集，則有：{()={|∈+,1≤≤1}()={|∈+,1≤≤1}(3.1)嘗試計算中間板上所有的整數(shù)切割位置，意味著枚舉所有的可行解，其優(yōu)點是能夠獲得最優(yōu)解，但是缺點是可行解的基數(shù)大使得計算量增多，另一方面，相鄰的兩個切割線計算得到的結(jié)果可能對切割質(zhì)量沒影響，只是改變了目標(biāo)塊的擺放位置。使用完全離散集做切割的代價是極大的，隨之基礎(chǔ)離散集被構(gòu)造。Herz[16]通過限制離散集的大小，在不損失最優(yōu)解的情況下可以取代完全離散

【參考文獻(xiàn)】：
期刊論文
[1]求解二維矩形Packing問題的一種優(yōu)美度枚舉算法[J]. 王磊,尹愛華.  中國科學(xué):信息科學(xué). 2015(09)
[2]生成矩形毛坯最優(yōu)兩段排樣方式的遞歸算法[J]. 崔耀東,季君,曾窕俊.  南京航空航天大學(xué)學(xué)報. 2006(01)
[3]生成矩形毛坯最優(yōu)T形排樣方式的遞歸算法[J]. 崔耀東.  計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報. 2006(01)
[4]矩形件排樣的模擬退火算法求解[J]. 賈志欣,殷國富,羅陽,徐雷.  四川大學(xué)學(xué)報(工程科學(xué)版). 2001(05)
[5]利用混沌人工神經(jīng)元網(wǎng)絡(luò)進(jìn)行布局優(yōu)化計算[J]. 李建勇,鄂明成,曹月東.  制造業(yè)自動化. 2000(01)
[6]矩形件排樣問題的遺傳算法求解[J]. 劉德全,滕弘飛.  小型微型計算機(jī)系統(tǒng). 1998(12)
[7]矩形件排樣優(yōu)化的一種近似算法[J]. 曹炬,周濟(jì).  計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報. 1995(03)

碩士論文
[1]板材切割問題的求解與應(yīng)用[D]. 饒昊.江西財經(jīng)大學(xué) 2019
[2]全局優(yōu)化問題的確定性算法研究[D]. 欒世超.曲阜師范大學(xué) 2009
[3]矩形件下料優(yōu)化排樣的遺傳算法[D]. 黃紅兵.廣西師范大學(xué) 2005



本文編號：3140831