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

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

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

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