二維矩形條帶裝箱問題(2DR-SPP)是典型的組合優(yōu)化問題,也是NP-Hard問題,求解的難度較大,有重要的研究意義。該問題在計算機輔助設(shè)計、圖像處理、大規(guī)模集成電路邏輯布線設(shè)計等領(lǐng)域有廣泛應(yīng)用,有較高的實際應(yīng)用價值。構(gòu)建2DR-SPP的簡單數(shù)學(xué)模型,既可實現(xiàn)對中小規(guī)模問題的有效求解,又可為研究求解大規(guī)模問題的快速高精度的數(shù)學(xué)規(guī)劃啟發(fā)式算法奠定基礎(chǔ),有重要的研究價值。對2DR-SPP,為構(gòu)建其準確、有效、簡單的數(shù)學(xué)模型,本文主要做了以下兩個方面的工作:(1)針對不旋轉(zhuǎn)置于條帶箱中的任意兩個矩形物體,提出并理論論證這兩個物體被重疊放置時,其左下角單元坐標應(yīng)滿足的充要條件,基于此充要條件構(gòu)建兩矩形互不重疊放置的約束模型;然后針對問題的其它要求和目標構(gòu)建問題的其它約束模型和目標函數(shù),得到不旋轉(zhuǎn)問題的線性整數(shù)規(guī)劃模型;最后引入輔助變量,將不旋轉(zhuǎn)模型拓展得可旋轉(zhuǎn)情況下問題的數(shù)學(xué)模型。實驗結(jié)果驗證了模型的準確性和較已有模型的更有效性。(2)將基于任意兩矩形左下角單元坐標的內(nèi)在關(guān)系構(gòu)建約束模型的建模思想進行改進,利用矩形左下角單元坐標和條帶箱單元坐標的內(nèi)在關(guān)系構(gòu)建禁止矩形重疊放置的約束模型,得到問題的改進左下角定位模型;然后根據(jù)矩形放置方式選擇的特性,將可旋轉(zhuǎn)情形轉(zhuǎn)化為不旋轉(zhuǎn)情形,并構(gòu)建其模型。可旋轉(zhuǎn)2DR-SPP的改進模型在決策變量個數(shù)和約束條件個數(shù)兩方面都較已有模型有較大幅度的減少,所以模型更為簡單、有效。對12個標桿算例的求解結(jié)果進一步驗證了所建改進模型的準確性和更有效性。
【學(xué)位單位】：武漢科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2018
【中圖分類】：O157
【文章目錄】：
摘要
ABSTRACT
第1章 緒論
    1.1 問題背景
    1.2 國內(nèi)外研究現(xiàn)狀
    1.3 選題意義
    1.4 論文結(jié)構(gòu)安排
第2章 2DR-SPP的左下角定位模型
    2.1 問題離散化描述
    2.2 符號設(shè)定
    2.3 左下角定位模型
        2.3.1 不旋轉(zhuǎn)模型
        2.3.2 可旋轉(zhuǎn)模型
    2.4 小結(jié)
第3章 2DR-SPP的改進左下角定位模型
    3.1 符號說明
    3.2 改進左下角定位模型
        3.2.1 改進不旋轉(zhuǎn)左下角定位模型
        3.2.2 改進可旋轉(zhuǎn)左下角定位模型
    3.3 小結(jié)
第4章 實驗算例
    4.1 模型準確性檢驗
        4.1.1 左下角定位模型檢驗
        4.1.2 改進左下角定位模型檢驗
    4.2 模型復(fù)雜性檢驗
        4.2.1 不旋轉(zhuǎn)模型檢驗
        4.2.2 可旋轉(zhuǎn)情況下的模型驗證
    4.3 小結(jié)
第5章 總結(jié)與展望
    5.1 總結(jié)
    5.2 創(chuàng)新點
    5.3 展望
致謝
參考文獻
附錄1 攻讀碩士學(xué)位期間發(fā)表的論文
附錄2 攻讀碩士學(xué)位期間參加的科研項目

【參考文獻】

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

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

2 孔令熠;陳秋蓮;;二維多階段矩形剪切排樣算法[J];計算機應(yīng)用與軟件;2015年05期

3 田大肥;申喜;周巍;;二維裝箱問題的遺傳算法求解[J];艦船電子工程;2014年01期

4 彭碧濤;周永務(wù);;求解2D條帶矩形Packing問題的迭代啟發(fā)式算法[J];軟件學(xué)報;2012年10期

5 黃嵐;齊季;譚穎;楊濱;;一種求解矩形排樣問題的遺傳-離散粒子群優(yōu)化算法[J];電子學(xué)報;2012年06期

6 蔣興波;呂肖慶;劉成城;;二維矩形條帶裝箱問題的底部左齊擇優(yōu)匹配算法[J];軟件學(xué)報;2009年06期

7 于洪霞;張紹武;張立衛(wèi);;二維裝箱問題非線性規(guī)劃模型和算法[J];大連理工大學(xué)學(xué)報;2008年02期

8 張德富;韓水華;葉衛(wèi)國;;求解矩形Packing問題的砌墻式啟發(fā)式算法[J];計算機學(xué)報;2008年03期

9 湯巖;胡俊敏;武立豐;;一種改進的二維裝箱問題的混合遺傳算法[J];集美大學(xué)學(xué)報(自然科學(xué)版);2006年03期

10 趙中凱,梅國建,沈洪,趙戰(zhàn)彪;基于混合螞蟻算法的二維裝箱問題求解[J];計算機應(yīng)用;2004年S1期

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

1 姚怡;二維裝箱問題的啟發(fā)式算法研究[D];華南理工大學(xué);2016年

本文編號：2870935