【摘要】：隨著經(jīng)濟(jì)全球化的發(fā)展,企業(yè)之間的競(jìng)爭(zhēng)越發(fā)激烈。在能源儲(chǔ)備不足日益凸顯的今天,高效分配和使用稀缺資源的技術(shù)優(yōu)勢(shì)無(wú)疑是企業(yè)的核心競(jìng)爭(zhēng)力之一。生產(chǎn)調(diào)度問(wèn)題是制造企業(yè)在日常運(yùn)作中面臨的主要問(wèn)題,單一機(jī)器是制造產(chǎn)業(yè)的基本生產(chǎn)單元,在機(jī)械科技水平的限制和購(gòu)入機(jī)器投入資金的限制下,如何通過(guò)排序和統(tǒng)籌調(diào)度方面的技術(shù)去提高機(jī)器產(chǎn)能是企業(yè)首要解決的問(wèn)題。打包裝箱方法是影響物流運(yùn)輸?shù)囊粋�(gè)關(guān)鍵技術(shù),跟物流運(yùn)輸?shù)淖詣?dòng)化水平、裝載效率和業(yè)務(wù)流程的規(guī)范都有著重要的關(guān)系。因此,本文針對(duì)生產(chǎn)調(diào)度和打包裝箱問(wèn)題展開(kāi)研究,基于列生成的思想為問(wèn)題設(shè)計(jì)有效的精確算法。首先,基于制造企業(yè)實(shí)際的生產(chǎn)場(chǎng)景,我們提出了一個(gè)考慮柔性周期維護(hù)和惡化效應(yīng)的單機(jī)調(diào)度問(wèn)題,并設(shè)計(jì)了有效的分支定價(jià)精確算法。通過(guò)推導(dǎo)問(wèn)題最優(yōu)解中所使用批次數(shù)目的上界,我們提出了該問(wèn)題的混合整數(shù)規(guī)劃模型,并將此模型通過(guò)Dantzig-Wolfe分解得到集合劃分問(wèn)題的整數(shù)規(guī)劃模型。由于集合劃分問(wèn)題所對(duì)應(yīng)的定價(jià)問(wèn)題是帶有資源約束的最短路問(wèn)題,我們?cè)O(shè)計(jì)了高效的標(biāo)簽設(shè)定算法來(lái)求解此問(wèn)題。在標(biāo)簽設(shè)定算法中,為了加速標(biāo)簽的搜索過(guò)程,我們針對(duì)定價(jià)問(wèn)題的特性和結(jié)構(gòu)設(shè)計(jì)了標(biāo)簽支配規(guī)則。同時(shí),考慮到最優(yōu)解的特性,我們還提出了一個(gè)能夠有效減少集合劃分模型中變量數(shù)目的批次支配規(guī)則。限制性主問(wèn)題的線性松弛求得的最優(yōu)解有可能不是整數(shù)。為了得到問(wèn)題的最優(yōu)整數(shù)解,我們?yōu)榫_算法設(shè)計(jì)了兩種分支策略:對(duì)批次的數(shù)目進(jìn)行分支和對(duì)最短路中的前向弧進(jìn)行分支。在分支定界樹(shù)中,全局上界的更新是通過(guò)構(gòu)造式的啟發(fā)式算法來(lái)實(shí)現(xiàn)的。在計(jì)算實(shí)驗(yàn)中,我們結(jié)合相關(guān)文獻(xiàn)隨機(jī)生成了 1440個(gè)算例,用來(lái)驗(yàn)證算法的求解性能。通過(guò)對(duì)分支定價(jià)算法的多個(gè)子模塊進(jìn)行對(duì)比實(shí)驗(yàn)和分析,實(shí)驗(yàn)結(jié)果表明我們所設(shè)計(jì)的分支定價(jià)算法是高效的。我們還給出了該問(wèn)題在線版本下的一個(gè)最優(yōu)策略。其次,我們以一個(gè)物流運(yùn)輸行業(yè)實(shí)際的打包裝箱收費(fèi)問(wèn)題為背景,提出了一個(gè)與體積重量相關(guān)的一般價(jià)格函數(shù)的二維向量裝箱問(wèn)題。我們?cè)谡撐闹薪榻B了知名物流企業(yè)對(duì)包裹的標(biāo)準(zhǔn)收費(fèi)流程,據(jù)我們所知,這是第一篇考慮體積重量的裝箱問(wèn)題的論文。由于價(jià)格函數(shù)的原因,我們所考慮的問(wèn)題要比經(jīng)典的二維向量裝箱問(wèn)題復(fù)雜很多。為了求解這一問(wèn)題,我們?cè)诜种Ф▋r(jià)算法的基礎(chǔ)上往限制性主問(wèn)題里面加入兩種有效不等式,因此我們所設(shè)計(jì)的算法是一個(gè)分支定價(jià)切割精確算法。用于加速全局下界的提升速度和減少結(jié)點(diǎn)的求解個(gè)數(shù)的兩種有效不等式分別為:取整不等式和Subset-row不等式。因?yàn)镾ubset-row不等式會(huì)改變定價(jià)問(wèn)題的結(jié)構(gòu)使得定價(jià)問(wèn)題的復(fù)雜性增加,我們僅在根結(jié)點(diǎn)添加Subset-row不等式。為了求解定價(jià)問(wèn)題,我們?cè)O(shè)計(jì)了標(biāo)簽設(shè)定算法,同時(shí)推導(dǎo)出了考慮Subset-row不等式下的標(biāo)簽支配規(guī)則。為了求得問(wèn)題的最優(yōu)整數(shù)解,我們采用了兩種分支策略:對(duì)使用的箱子的數(shù)目進(jìn)行分支和對(duì)成對(duì)的物品進(jìn)行分支。我們基于一種最短路解碼算法來(lái)更新分支定界樹(shù)中每個(gè)結(jié)點(diǎn)的上界。我們隨機(jī)生成了 360個(gè)算例來(lái)測(cè)試我們所設(shè)計(jì)算法的性能。我們將原問(wèn)題的混合整數(shù)規(guī)劃模型帶入CPLEX求解器求解,所得到的結(jié)果與分支定價(jià)切割算法的實(shí)驗(yàn)結(jié)果進(jìn)行了比較,結(jié)果顯示我們的算法遠(yuǎn)比CPLEX求解高效。另外,我們還對(duì)算法的幾個(gè)關(guān)鍵子模塊做了測(cè)評(píng)實(shí)驗(yàn)和分析。最后,我們?yōu)橐粋�(gè)抗癌靜脈注射針劑的運(yùn)輸存儲(chǔ)問(wèn)題設(shè)計(jì)了一個(gè)分支定價(jià)切割精確算法。此問(wèn)題實(shí)際上是一個(gè)不確定尺寸的二維向量裝箱問(wèn)題,我們將存儲(chǔ)抗癌靜脈注射針劑的容器看成是具有體積維度和加工時(shí)長(zhǎng)維度的箱子,那么在體積維度上箱子的體積是確定的,但是在加工時(shí)長(zhǎng)這一維度上箱子的大小是不確定的。在加工時(shí)長(zhǎng)維度上,我們只需考慮的問(wèn)題是針劑的延遲時(shí)長(zhǎng)不超過(guò)給定的時(shí)間限制即可。為了減少求解分支定界樹(shù)中結(jié)點(diǎn)的數(shù)目,我們?cè)谙拗菩灾鲉?wèn)題里面添加了取整不等式。為了求解定價(jià)問(wèn)題,我們?cè)O(shè)計(jì)了標(biāo)簽設(shè)定算法和標(biāo)簽支配規(guī)則。另外,我們還設(shè)計(jì)了對(duì)定價(jià)問(wèn)題中的前向弧進(jìn)行分支的分支策略。通過(guò)隨機(jī)生成420個(gè)算例來(lái)測(cè)試我們算法的性能。我們用CPLEX求解器來(lái)求解原問(wèn)題的0,1整數(shù)規(guī)劃模型,將得到的結(jié)果與分支定價(jià)切割算法的實(shí)驗(yàn)結(jié)果進(jìn)行比較,結(jié)果顯示我們的算法遠(yuǎn)比CPLEX求解高效。另外,我們還對(duì)加入取整不等式的BPC算法與不加取整不等式的BP算法做了比較實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果顯示取整不等式能夠極大地提升我們算法的性能。
【圖文】：

別對(duì)這三個(gè)問(wèn)題建立了混合整數(shù)規(guī)劃或整數(shù)規(guī)劃模型，，然后基于列生成方法設(shè)計(jì)逡逑了不同的精確算法，最后通過(guò)大量的數(shù)值實(shí)驗(yàn)對(duì)所設(shè)計(jì)的算法的性能進(jìn)行評(píng)估和逡逑問(wèn)題本身的性質(zhì)進(jìn)行分析探討。本文具體的技術(shù)路線圖在圖１－２中給出。逡逑１６逡逑

南京大學(xué)博士學(xué)位論文邐逡逑可以表示成ｌ｜ｐｙ邋＝邋ｐ＿／邋＋邋ｏｃ／Ｓｙ；邋ｄ邋－邋／ｐｍ｜Ｃｍａｘ，這里的ｄ邋－邋／ｐｍ表示惡化效應(yīng)逡逑（Ｄｅｔｅｒｉｏｒａｔｉｏｎ邋Ｅｆｆｅｃｔ）和／ｐｍ表示柔性周其月維護(hù)活動(dòng)（Ｆｌｅｘｉｂｌｅ邋Ｐｅｒｉｏｄｉｃ邋Ａｃｔｉｖｉｔｙ邋）。目逡逑標(biāo)函數(shù)Ｃｍａｘ指的是最后一個(gè)工件的完工時(shí)刻。逡逑
【學(xué)位授予單位】：南京大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2018
【分類(lèi)號(hào)】：F274

【相似文獻(xiàn)】

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

1 元野;李一軍;王延青;王曉博;;基于圖著色模型的沖突裝箱問(wèn)題啟發(fā)式算法[J];運(yùn)籌與管理;2013年05期

2 羅建軍;吳東輝;羅細(xì)飛;;三維裝箱問(wèn)題的啟發(fā)式算法[J];物流技術(shù);2012年03期

3 賈向權(quán);;模擬退火算法在裝箱問(wèn)題中的應(yīng)用[J];電腦知識(shí)與技術(shù);2010年05期

4 張玉棟;孔德豐;;一種尺寸可變的裝箱問(wèn)題的在線近似算法[J];許昌學(xué)院學(xué)報(bào);2010年05期

5 周春良;;基于遺傳算法的港口裝箱問(wèn)題的研究[J];電腦知識(shí)與技術(shù);2009年36期

6 丁丹軍;;一種尺寸可變的裝箱問(wèn)題的在線近似算法[J];科技創(chuàng)新導(dǎo)報(bào);2008年04期

7 張玉棟;蔡靜;郝自軍;何尚錄;;尺寸可變的裝箱問(wèn)題的近似算法的研究[J];蘭州交通大學(xué)學(xué)報(bào);2007年01期

8 孫春玲;染色裝箱問(wèn)題及其啟發(fā)式算法[J];云南民族大學(xué)學(xué)報(bào)(自然科學(xué)版);2005年04期

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

10 孫春玲,陳智斌,李建平;裝箱問(wèn)題的一種新的近似算法[J];云南大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年05期

相關(guān)會(huì)議論文 前8條

1 陳鋒;邢文訓(xùn);;在線塔狀裝箱問(wèn)題(英文)[A];中國(guó)運(yùn)籌學(xué)會(huì)第六屆學(xué)術(shù)交流會(huì)論文集（上卷）[C];2000年

2 張國(guó)川;;組合優(yōu)化算法研究-從裝箱問(wèn)題說(shuō)起[A];2006年中國(guó)運(yùn)籌學(xué)會(huì)數(shù)學(xué)規(guī)劃分會(huì)代表會(huì)議暨第六屆學(xué)術(shù)會(huì)議論文集[C];2006年

3 那日薩;崔雪蓮;韓琪瑋;;帶角件約束的三維裝箱問(wèn)題優(yōu)化算法及其可視化[A];中國(guó)系統(tǒng)工程學(xué)會(huì)第十八屆學(xué)術(shù)年會(huì)論文集——A05系統(tǒng)工程理論應(yīng)用與創(chuàng)新[C];2014年

4 ;Voronoi Diagram Approximate the Extreme Packing and Its Applications[A];中國(guó)運(yùn)籌學(xué)會(huì)第六屆學(xué)術(shù)交流會(huì)論文集（上卷）[C];2000年

5 董杰方;張漢欣;李安平;;冷卷入庫(kù)的數(shù)學(xué)模型及算法[A];2001中國(guó)鋼鐵年會(huì)論文集（下卷）[C];2001年

6 陳s

本文編號(hào)：2621712