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

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

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

【相似文獻】

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

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

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

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

4 張玉棟;孔德豐;;一種尺寸可變的裝箱問題的在線近似算法[J];許昌學院學報;2010年05期

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

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

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

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

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

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

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

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

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

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

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

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

6 陳s

本文編號：2621712