在板材切割的過程中,一個優(yōu)秀的切割方案可以將原料的使用率大大提高,從而減少板材的浪費,節(jié)約經(jīng)濟成本,為廠商帶來更大的經(jīng)濟效應(yīng)。因此,研究出一種高效的板材切割算法具有重要的理論價值和實際應(yīng)用價值。板材切割問題在理論上是NP難問題,同時在工業(yè)上也是一個長期需要解決的重要問題。板材切割問題是一種經(jīng)典的NP難問題,不斷地在時間和優(yōu)度上做出均衡。論文所研究的切割問題全稱為cutting optimization problem,即‘切割優(yōu)化問題’,是2018年法國運營(OR)和決策支持協(xié)會(ROADEF)共同組織的一次ROADEF/EURO挑戰(zhàn)賽的挑戰(zhàn)題目。問題的主要內(nèi)容是要將多塊板材原料按順序切割成所需要的目標(biāo)方塊。在該問題中,板材將使用流水線切割的形式進行切割,并且板材原料存在defect(雜質(zhì))。由于切割機器及相關(guān)硬件的原因,給該切割問題產(chǎn)生了許多的限制約束,大大增加了切割方案設(shè)計的難度。論文中使用動態(tài)切割與集束搜索相結(jié)合的方式,對問題進行分化求解。總體思路是將問題從尋找整體近似最優(yōu)切割方案拆分成以1_cut切割線為分界線的尋找局部近似最優(yōu)切割方案。將問題拆開成多個求解局部近似最優(yōu)解的問題后,再使用集束搜索的方式來尋找這些局部近似最優(yōu)解。這樣就將一個原本巨大的搜索樹拆分成了眾多的小搜索樹,使得搜索的過程更加高效且迅速。當(dāng)所有的局部近似最優(yōu)解找出后,組合起來作為總體的近似最優(yōu)解。方法中定義名為貼邊度的指標(biāo)作為局部搜索時動作的選擇因素。將每個1_cut區(qū)域的第一個目標(biāo)方塊作為分支節(jié)點,按照逐層切割的理念進行切割,將搜索樹的分支發(fā)展下去,直到該1_cut區(qū)域沒有多余的空間繼續(xù)切割出目標(biāo)方塊或所有的目標(biāo)方塊都已有切割線將其切出為止,作為一個局部的終止格局。從所有的局部終止格局中選擇當(dāng)前利用率最大的分支路線進行切割,作為局部近似最優(yōu)解。同理后續(xù)的1_cut區(qū)域重復(fù)此操作,直到所有1_cut區(qū)域切割完畢為止。在集束搜索的過程中,我們還使用動態(tài)切割的方式,對每次局部搜索的結(jié)果進行調(diào)整。在每個局部切割方案計算完成前,所有的切割線都是動態(tài)的,不會將該1_cut區(qū)域內(nèi)的切割線位置真正確定下來,而是根據(jù)動作選擇策略的結(jié)果,將某條暫時定下位置的切割線進行向上或向右的浮動平移,以求得更高的局部利用效率。也就是說每一個1_cut區(qū)域的寬度不會因為第一個目標(biāo)方塊的放置而被確定,而是會出現(xiàn)一個預(yù)1_cut線作為參考線,后面的目標(biāo)方塊若是判定放置位置會壓住這條1_cut線,預(yù)1_cut線將會向右平移,與超出的部分剛好相切為止。同理橫向的2_cut切割線也會因需要進行向上浮動平移。直到整個1_cut區(qū)域被切割線分割完畢,才會將這個局部區(qū)域內(nèi)的所有切割線位置確定下來,不再改變。該創(chuàng)新點會為算法提供一定的柔性化,使得在運算過程中切割線存在一定的柔性,來避免某些目標(biāo)方塊只差一點,卻由于切割線無法浮動的原因,而無法放置的結(jié)果。實驗通過計算2018年ROADEF/EURO挑戰(zhàn)賽官方所提供的A組算例,來驗證該原創(chuàng)算法的優(yōu)點與不足之處。實驗結(jié)果通過大賽官方所提供的檢測代碼進行結(jié)果測試,從而保證結(jié)果的正確性,并與官方所給出的單例最優(yōu)解進行比較。單例最優(yōu)解是官方對每一個實例公布的所有算法最優(yōu)解。通過分析計算結(jié)果得出結(jié)論:算法在處理目標(biāo)方塊與板材原料之間的尺寸差距較大的算例時,切割效果較好,算例板材利用率可在80%以上。
【學(xué)位單位】：江西財經(jīng)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2019
【中圖分類】：O224
【部分圖文】：

（a）一刀切模式 （b）非一刀切模式圖 1-1 按切割工藝劃分的兩種切割方式（3）根據(jù)目標(biāo)方塊種類數(shù)劃分根據(jù)目標(biāo)方塊的種類，可將二維板材切割問題劃分為單一切割方式和套裁割方式[1]。其中前者單一切割方式的目標(biāo)方塊只含有一種尺寸，雖然會降低板

（a）單一切割方式 （b）套裁切割方式圖 1-2 按目標(biāo)方塊的種類劃分的兩種切割方式（4）根據(jù)目標(biāo)方塊方向劃分根據(jù)目標(biāo)方塊方向是否允許轉(zhuǎn)向，可以分成兩種切割方式，如圖 1-3 求中的目標(biāo)方塊給定長寬參數(shù)，若約束條件不允許目標(biāo)方塊轉(zhuǎn)向，則在

（a）目標(biāo)方塊方向固定 （b）目標(biāo)方塊允許轉(zhuǎn)向圖 1-3 按目標(biāo)方塊是否允許轉(zhuǎn)向劃分的兩種切割方式（5）根據(jù)目標(biāo)方塊類型劃分根據(jù)目標(biāo)方塊的形狀是否是規(guī)則形狀，可將板材切割問題劃分為規(guī)則件切不規(guī)則件切割。規(guī)則件切割如圖 1-4（a）所示，目標(biāo)方塊都是規(guī)則二維圖形（

【參考文獻】

相關(guān)期刊論文 前7條

1 王磊;尹愛華;;求解二維矩形Packing問題的一種優(yōu)美度枚舉算法[J];中國科學(xué):信息科學(xué);2015年09期

2 易向陽;仝青山;潘衛(wèi)平;;矩形件二維下料問題的一種求解方法[J];鍛壓技術(shù);2015年06期

3 何琨;黃文奇;;三維矩形Packing問題的擬人求解算法[J];中國科學(xué):信息科學(xué);2010年12期

4 毛力;童科;沈明明;董洪偉;;基于群智能算法的玻璃切割問題求解研究[J];計算機工程;2010年15期

5 吳振翔;魏曉東;張廣明;;自動玻璃切割機排樣優(yōu)化算法設(shè)計與實現(xiàn)[J];機械設(shè)計與制造;2009年09期

6 陳仕軍;曹炬;;一種“一刀切”式矩形件優(yōu)化排樣混合算法[J];鍛壓技術(shù);2009年04期

7 崔耀東,周儒榮;單一尺寸矩形毛坯排樣時長板的最優(yōu)分割[J];計算機輔助設(shè)計與圖形學(xué)學(xué)報;2001年05期

相關(guān)碩士學(xué)位論文 前2條

1 孔令熠;基于普通條帶的二維多階段排樣算法[D];廣西大學(xué);2014年

2 鄭瑩;面向玻璃切割機的排樣優(yōu)化算法設(shè)計與實現(xiàn)[D];武漢理工大學(xué);2012年

本文編號：2820000