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

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

（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ī)則二維圖形（

【參考文獻(xiàn)】

相關(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];計(jì)算機(jī)工程;2010年15期

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

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

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

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

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

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

本文編號：2820000