【摘要】：排樣優(yōu)化問題廣泛存在于現(xiàn)代工業(yè)生產(chǎn)加工行業(yè)中,如鋼筋切割,布料裁剪,印刷排版以及機械制造等,是制造業(yè)自動化從設(shè)計到下料過程的關(guān)鍵環(huán)節(jié)。排樣優(yōu)化問題的研究旨在通過尋找一種合理有效的算法,以節(jié)省原材料的消耗,降低生產(chǎn)成本,提高企業(yè)經(jīng)濟效益。本文研究矩形件排樣問題:在寬度固定長度不限的板材上,按照某種策略排入一定規(guī)格數(shù)量的矩形件,以充分利用原材料。該類問題在數(shù)學(xué)上屬于NP完全問題,不能確保在有限的計算時間內(nèi)得到最優(yōu)解。因此,如何設(shè)計一種高效的求解算法用于矩形件排樣問題,具有重要的研究意義與價值。本文提出一種自適應(yīng)遺傳模擬退火算法,將遺傳算法和模擬退火算法相結(jié)合以確定矩形件的排放順序,并改進一種定位算法以確定矩形件在板材中的擺放位置。本文的主要工作如下:1.提出基于匹配度的最低水平線啟發(fā)式搜索算法。在排入過程中引入旋轉(zhuǎn)和啟發(fā)式判斷,對無法排入最低水平線的矩形件進行旋轉(zhuǎn)重排。若仍無法排入,則在后續(xù)待排矩形件序列中,通過匹配度函數(shù)中的主影響因子和次影響因子從全局優(yōu)化上共同指導(dǎo)最優(yōu)矩形件的選擇,搜索出與最低水平線匹配度最高的矩形件并排入。改進后的算法可以有效利用空閑區(qū)域,減少板材的浪費。2.在遺傳模擬退火算法中引入動態(tài)調(diào)整策略,根據(jù)當(dāng)前個體適應(yīng)值的大小自動調(diào)節(jié)交叉和變異概率,動態(tài)地控制收斂速度和搜索解的能力。同時采用環(huán)形交叉算子,交叉過程環(huán)繞染色體兩端進行,以保證基因被選中的概率相等。對遺傳操作后的所有個體按照狀態(tài)產(chǎn)生函數(shù)生成新個體,并計算適應(yīng)值,若滿足接受概率,用新個體替換舊個體;否則,進行降溫操作,并更新最優(yōu)個體,直到達到最大迭代次數(shù),完成模擬退火過程。多組算例的對比結(jié)果表明,本文提出的自適應(yīng)遺傳模擬退火算法在保證算法性能的同時具有較快的求解速度,可以有效提高板材的利用率。
【圖文】：

一維排樣問題通常只考慮原料為一個維度的條形材料，相比材料的長度而言，寬度逡逑往往可以忽略，比如線材切割、鋼管切割。依照所需產(chǎn)品的種類，可以將其分為單一原逡逑材料排樣和多種原材料排樣。圖１－１所示為一維線材排樣示例圖，其中陰影部分為需要逡逑在原材料上排放的線形毛坯。逡逑ｆｉｌｌ邋W逡逑Ｉ邋｜邐］［．邐．逡逑（ａ）邐（ｂ）逡逑１邋．邐邐１邐ｉ—逡逑（ｃ）逡逑圖Ｍ邋—維線材排樣示例（ａ）原材料（ｂ）所需毛坯（ｃ）排樣方案逡逑Ｆｉｇ．邋１－１邋Ｅｘａｍｐｌｅ邋ｏｆ邋ｏｎｅ－ｄｉｍｅｎｓｉｏｎａｌ邋ｗｉｒｅ邋ｌａｙｏｕｔ邋（ａ）Ｍａｔｅｒｉａｌｓ邋（ｂ）Ｒｅｑｕｉｒｅｄ邋ｐａｒｔｓ邋（ｃ）Ｌａｙｏｕｔ邋Ｓｃｈｅｍｅ逡逑二維排樣問題考慮毛坯在水平原材料上的布局，依據(jù)所需毛坯的屬性，可以將其分逡逑為規(guī)則毛坯排樣優(yōu)化問題和不規(guī)則毛坯排樣優(yōu)化問題［３］。圖１－２所示為二維矩形件排樣逡逑示例圖，其中排入的毛坯必須互不重疊，且正交排放。逡逑圖１－２二維矩形件排樣示例逡逑Ｆｉｇ．邋１－２邋Ｅｘａｍｐｌｅ邋ｏｆ邋ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌ邋ｒｅｃｔａｎｇｌｅｓ邋ｌａｙｏｕｔ逡逑三維排樣問題需要考慮毛坯在長、寬、高三個方位的布局，其中原材料和毛坯同為逡逑三維物體，需要將一定體積和重量的毛坯裝入固定體積的原材料箱體中，且須同時滿足逡逑體積和重量相關(guān)約束條件，在滿足毛坯需求的同時，使得所使用箱體的總數(shù)最少或箱體逡逑空間利用率最大

一維排樣問題通常只考慮原料為一個維度的條形材料，相比材料的長度而言，寬度逡逑往往可以忽略，比如線材切割、鋼管切割。依照所需產(chǎn)品的種類，可以將其分為單一原逡逑材料排樣和多種原材料排樣。圖１－１所示為一維線材排樣示例圖，其中陰影部分為需要逡逑在原材料上排放的線形毛坯。逡逑ｆｉｌｌ邋W逡逑Ｉ邋｜邐］［．邐．逡逑（ａ）邐（ｂ）逡逑１邋．邐邐１邐ｉ—逡逑（ｃ）逡逑圖Ｍ邋—維線材排樣示例（ａ）原材料（ｂ）所需毛坯（ｃ）排樣方案逡逑Ｆｉｇ．邋１－１邋Ｅｘａｍｐｌｅ邋ｏｆ邋ｏｎｅ－ｄｉｍｅｎｓｉｏｎａｌ邋ｗｉｒｅ邋ｌａｙｏｕｔ邋（ａ）Ｍａｔｅｒｉａｌｓ邋（ｂ）Ｒｅｑｕｉｒｅｄ邋ｐａｒｔｓ邋（ｃ）Ｌａｙｏｕｔ邋Ｓｃｈｅｍｅ逡逑二維排樣問題考慮毛坯在水平原材料上的布局，依據(jù)所需毛坯的屬性，可以將其分逡逑為規(guī)則毛坯排樣優(yōu)化問題和不規(guī)則毛坯排樣優(yōu)化問題［３］。圖１－２所示為二維矩形件排樣逡逑示例圖，其中排入的毛坯必須互不重疊，，且正交排放。逡逑圖１－２二維矩形件排樣示例逡逑Ｆｉｇ．邋１－２邋Ｅｘａｍｐｌｅ邋ｏｆ邋ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌ邋ｒｅｃｔａｎｇｌｅｓ邋ｌａｙｏｕｔ逡逑三維排樣問題需要考慮毛坯在長、寬、高三個方位的布局，其中原材料和毛坯同為逡逑三維物體，需要將一定體積和重量的毛坯裝入固定體積的原材料箱體中，且須同時滿足逡逑體積和重量相關(guān)約束條件，在滿足毛坯需求的同時，使得所使用箱體的總數(shù)最少或箱體逡逑空間利用率最大
【學(xué)位授予單位】：廣西大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：TP18

【相似文獻】

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

1 張瑞友;潘衛(wèi)平;劉士新;;基于勻質(zhì)塊五塊模式的矩形件非剪切排樣算法[J];東北大學(xué)學(xué)報(自然科學(xué)版);2018年06期

2 董功云;陳進;王鴻超;;矩形件排樣的流程和算法設(shè)計[J];輕工機械;2016年06期

3 易向陽;潘衛(wèi)平;張俊暉;;基于五塊模式的單一矩形件排樣算法[J];圖學(xué)學(xué)報;2015年04期

4 宋雪楓;陳江義;張明偉;;基于遺傳算法的矩形件排樣問題求解[J];煤礦機械;2011年05期

5 陳仕軍;曹炬;;矩形件優(yōu)化排樣的一種啟發(fā)式算法[J];計算機工程與應(yīng)用;2010年12期

6 彭文;;一種快速的有約束矩形件優(yōu)化排樣模型[J];計算機工程與應(yīng)用;2010年27期

7 鄧冬梅;周來水;安魯陵;王桂賓;;矩形件優(yōu)化排樣的研究[J];宇航材料工藝;2007年04期

8 馬炫;張亞龍;;基于遺傳算法的大規(guī)模矩形件優(yōu)化排樣[J];智能系統(tǒng)學(xué)報;2007年05期

9 宋連超;朱建良;張彤;;矩形件排樣優(yōu)化貪婪算法及系統(tǒng)開發(fā)[J];哈爾濱理工大學(xué)學(xué)報;2007年01期

10 黃紅兵;一個矩形件排樣的較優(yōu)算法[J];東華理工學(xué)院學(xué)報;2005年03期

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

1 岳琪;基于遺傳退火算法板式家具大規(guī)模矩形件優(yōu)化下料研究[D];東北林業(yè)大學(xué);2005年

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

1 夏以沖;矩形件排樣問題的遺傳模擬退火算法研究[D];廣西大學(xué);2018年

2 宋仁坤;基于遺傳算法的矩形件排樣問題研究[D];廣西大學(xué);2017年

3 陸敏;多約束條件下的矩形件優(yōu)化排樣研究[D];浙江大學(xué);2006年

4 陳仕軍;矩形件下料優(yōu)化算法研究[D];華中科技大學(xué);2009年

5 趙曉東;矩形件優(yōu)化排樣算法的研究與實現(xiàn)[D];大連交通大學(xué);2008年

6 李捷;基于遺傳算法與螞蟻算法的矩形件布局問題的研究與應(yīng)用[D];南昌大學(xué);2008年

7 龔志輝;基于遺傳算法的矩形件優(yōu)化排樣系統(tǒng)研究[D];湖南大學(xué);2003年

8 趙新芳;解決矩形件帶排樣問題的一種遺傳算法[D];廣西師范大學(xué);2008年

9 任海;鞍鋼中厚板矩形件自動排板系統(tǒng)的研究與應(yīng)用[D];哈爾濱工業(yè)大學(xué);2017年

10 張偉;矩形件排樣與切割路徑優(yōu)化技術(shù)研究[D];南京航空航天大學(xué);2010年

本文編號：2694482