具有無交叉約束的碼頭起重機(jī)調(diào)度問題.pdf

1、現(xiàn)代物流行業(yè)中，海洋運(yùn)輸是國際物流行業(yè)的主要運(yùn)輸方式，海運(yùn)已成為國際貿(mào)易的支柱和推動(dòng)貿(mào)易全球化的關(guān)鍵動(dòng)力。來自中國產(chǎn)業(yè)信息網(wǎng)消息，國際貿(mào)易總運(yùn)輸量的2/3、中國貿(mào)易貨運(yùn)量的約90％均來自海運(yùn)。隨著中國經(jīng)濟(jì)的不斷快速發(fā)展及影響力不斷擴(kuò)大，中國海港的集裝箱吞吐量已經(jīng)位居世界第一。港口之間為了增強(qiáng)自身競(jìng)爭力，就如何提高港口運(yùn)行效率，尤其是如何減少碼頭起重機(jī)的裝載或卸載耗時(shí)，就顯得至關(guān)重要。本文主要研究一類具有無交叉約束的碼頭起重機(jī)調(diào)度問題，即

2、通過對(duì)集裝箱港口的碼頭起重機(jī)調(diào)度，使其裝載或卸載一艘集裝箱貨輪的時(shí)間盡可能小。對(duì)此問題，本文給出了近似算法和相應(yīng)的最壞情況分析。
　　本研究分為四個(gè)部分：第一章首先給出調(diào)度問題的定義，接著介紹近似算法、時(shí)間復(fù)雜度，最壞情況界等概念，最后介紹了本文所研究的碼頭起重機(jī)調(diào)度問題及其數(shù)學(xué)規(guī)劃模型。第二章，研究了具有無交叉約束的m臺(tái)碼頭起重機(jī)調(diào)度問題。對(duì)此問題，我們不僅給出了關(guān)于最優(yōu)解的一個(gè)新的下界，而且給出了求解該問題的一種最壞情況界為2

3、?2/m+1的”分割”調(diào)度算法，此最壞情況界是應(yīng)用”分割”思想的最好可能界。最后，我們從時(shí)間復(fù)雜度和最壞情況界角度比較了幾種應(yīng)用”分割”思想的近似算法，并通過數(shù)值實(shí)驗(yàn)驗(yàn)證已有算法的平均性能。第三章，研究了兩臺(tái)不同速率的碼頭起重機(jī)調(diào)度問題。首先對(duì)文獻(xiàn)中的已有算法進(jìn)行了改進(jìn)的分析，得到最壞情況緊界為min{s+1s,(s+1)2/2s+1}，其中s(≥1)是兩臺(tái)起重機(jī)的速率之比；接著設(shè)計(jì)了改進(jìn)算法，并證明其最壞情況界為(1+s)2/1+s+