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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文編號(hào)：2694482