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

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

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

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

【部分圖文】：

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

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

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

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

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



本文編號(hào)：3140831