基于滾動策略的不確定干擾下場橋調度問題研究

梁承姬，王典雪，徐德洪

(上海海事大學 科學研究院 物流研究中心，上海 201306)

?

基于滾動策略的不確定干擾下場橋調度問題研究

梁承姬，王典雪*，徐德洪

(上海海事大學 科學研究院 物流研究中心，上海 201306)

目前影響集裝箱港口裝卸效率的“瓶頸”從岸邊作業轉移到堆場作業.合理的場橋調度方案不僅可以提高堆場作業效率也可以配合集卡、岸橋，提高整個港口的裝卸效率.而在實施場橋調度方案時，總會出現各種不確定干擾因素使得原先的方案不能正常實行.針對這一問題 ，本文提出一種在滾動窗口策略下處理不確定干擾因素的場橋調度流程，即當出現干擾時，觸發窗口再調度機制，以減少干擾的影響.并且建立了以任務完成最大延遲量最小化為目標的混合整數規劃模型，采用改進遺傳算法對模型進行求解.通過案例分析對比，驗證了算法的有效性以及滾動窗口策略下場橋調度方案更優，更符合港口的實際運營.

滾動窗口策略； 不確定干擾因素； 場橋調度； 改進遺傳算法

集裝箱碼頭是陸地和海上運輸的連接點，并且作為多式聯運的轉運站和樞紐來進行服務[1].因此，對于任何一個集裝箱碼頭來說，堆存效率以及在碼頭區的大量集裝箱運輸都是至關重要的.目前影響集裝箱港口裝卸效率的“瓶頸”從岸邊作業轉移到堆場作業.合理的場橋調度方案可以提高堆場作業效率，因此場橋調度問題的研究對于集裝箱港口的作業管理具有重要意義[2].對于場橋調度工作，目前主要是依據場橋就近原則，工作量平衡原則，場橋調度員憑借經驗進行調度，缺乏系統性.場橋調度問題對于集裝箱碼頭的作業管理有著重要意義.本文將研究基于不確定因素下的場橋調度，為了達到優化調度方案，使得堆場作業效率提高從而提高碼頭作業效率的目的.

目前已有不少學者對場橋調度問題進行了研究.文獻[3]和文獻[4]討論了場橋的動態調度問題，在最小化剩余工作量的目標下，確定場橋在箱區間移動的次數和路線.文中建立了混合整數規劃模型，并采用啟發式算法進行求解.模型的基本假設中考慮了場橋之間的干涉約束，設定每個箱區中最多只能有兩臺場橋同時工作，有效避免了調度的不必要麻煩，通過算例分析，驗證了方法的有效性.文獻[5]研究多臺場橋的調度問題時，考慮了場橋間的干涉因素以及具有不同服務時間的任務集，并建立了整數規劃模型.由于場橋調度問題為NP-hard問題，文章最后采用基于動態規劃的啟發式算法求解模型.計算結果表明，啟發式算法能夠有效地解決調度問題.以上文獻在考慮場橋調度問題的時候，只考慮了場橋作業時的干涉因素(由于場橋體積大，多臺場橋同時作業會出現“干涉”情況)，并沒有考慮到實際作業中會出現的不確定干擾因素(比如，由于某船舶需要緊急離港，該船上的箱子需要緊急處理，這樣，原先的場橋任務分配情況會受到干擾)，而在實際港口碼頭作業中，不確定的干擾因素是大量存在的，因此，本文將把不確定干擾因素考慮到場橋調度中來，企圖得到更符合實際的調度方案.

文獻[6]考慮了一種動態滾動策略的場橋調度決策方案，建立了最小化箱區內所有任務的延遲量以及場橋轉場距離的整數規劃模型，提出了一種結合仿真模型的啟發式算法，并建立仿真模型以推進計劃周期，對任務組的延誤進行評估.同時，采用遺傳算法對啟發式算法得到的初始解進行優化.通過算例驗證，提出的動態滾動策略更貼近于碼頭實際作業情況，比靜態滾動方法得出更精確的調度方案.文獻[7]進行了基于時間窗的場橋調度研究，利用干涉管理思想，解決場橋實際調度中產生的操作困難，得出相應的模型函數求得最優調度策略；其次，引入時間窗概念，通過設置理性的時間窗，構造帶有時間窗的場橋調度函數模型，使整個場橋調度中存取箱作業盡量滿足集裝箱計劃到達時刻表，減少存取箱作業的提前或延遲，以達到集卡等待時間最小化，最大化場橋利用效率.以上兩篇文獻，從設計滾動時段的角度，針對場橋調度，進行周期性的滾動更新，這比以往的靜態調度得到更優良的調度方案；文獻[6]采用遺傳算法對啟發式算法的初始解進行優化，驗證該方法的有效性，而戴開梅則加入時間窗，運用啟發式算法求解，雖然都取得有效成果，但兩篇文獻仍然沒有將不確定干擾因素考慮進來，此外，兩篇文獻提出的是離散時間下的場橋調度問題，而場橋調度是實時調度，并且實時調度問題會經常出現new arrival moves handling，因此，本文將從連續時間角度考慮場橋實時調度問題.

文獻[8]考慮了基于遺傳算法的車間動態調度研究，考慮了車間作業在不確定因素影響下，進行滾動優化機制，利用改進遺傳算法求解.實例證明，采用該方法可以使得車間作業效率大大提高.文獻[9]對動態泊位調度引入滾動窗口技術，并采用Memetic算法進行計算求解得出較優的泊位調度方案，文中的Memetic算法結合了禁忌搜索和遺傳算法求解，禁忌搜索用于局部搜索，遺傳算法用于全局優化，算例證明了該算法在解決此問題時的有效性.文獻[10]針對連續泊位與橋吊集成調度求解的困難，引入一種基于滾動策略的優化方法，將動態抵泊的船舶按照順序分成若干連續的調度窗口，設計滾動窗口的滾動機制，采用啟發式算法求解，通過算例分析說明利用滾動調度方法能有效解決大規模的調度問題.以上3篇文獻都將滾動窗口策略引用到動態調度問題里面來，并得到較優的調度方案.滾動調度方法的主要思想在于，通過反復求解小規模優化問題來取代求解大規模調度問題，這樣，將問題簡化，同時得到更優解決方案.但是，這些思想目前還沒有在場橋調度中得到運用；因此，本文將從連續時間角度考慮場橋實時調度問題，根據集裝箱動態到達的順序，將調度過程分為連續的調度窗口，將大規模的調度分解，引用滾動窗口策略方法，通過此方法解決場橋作業中的不確定干擾因素.基于前面有學者采用遺傳算法求解驗證了該算法在求解此類問題的有效性，因此，本文將繼續用遺傳算法求解.

1 問題描述

在場橋調度中，存在場橋來不及處理任務，集卡等待的情況，這造成了集卡資源的浪費，作業分配不合理也影響了集裝箱碼頭的作業效率，從而降低了貨物吞吐量.在實際集裝箱碼頭作業中，存在許多不確定因素，比如：船舶到港時間的不確定會影響集裝箱是否能按時被處理；場橋可能出現機械故障，不能及時對集裝箱服務；集裝箱延遲到達，但又急需處理等等因素.為了更好達到客戶需求，本文引用“滾動窗口策略”來解決動態調度問題，當發生不確定干擾因素時立即重調度，如果未發生干擾因素，則進行之前設定的周期滾動調度.這樣做目的是實現場橋實時調度，從而節省時間，使服務水平得到提高.場橋調度的流程如圖1.

圖1 場橋調度流程圖Fig.1 The process of YC schedule

滾動窗口策略的工作原理為：在初始時刻，從所有待處理任務中選取一定數目的任務，加入任務窗口進行調度并產生初始調度方案，這是靜態調度問題；但在初始方案的執行過程中，由于作業環境情況的變化，需要進行再調度，也就是動態調度；這時將已完工的任務從任務窗口中移去，再加入一批待處理任務到任務窗口中，重新對任務窗口內的任務進行靜態調度.這樣的過程重復進行，直到所有任務都完成，這就是滾動窗口調度策略.

滾動調度方法的主要思想是滾動優化，把不確定性調度問題分解成一系列動態但確定的調度問題，通過將動態調度過程分解成連續靜態調度窗口，然后在線優化每個滾動窗口，使系統在此窗口內達到最優，再平移窗口并更新窗口中優化問題的參數，以此循環，直到所有任務完成.首先建立一個動態調度裝卸任務窗口，窗口任務數量的選取根據集裝箱碼頭實際的作業情況來確定，一般按照先到先服務的原則選取一定數量的任務加入到場橋調度窗口，對當前窗口下的任務建立數學優化模型，求解得出當前的場橋調度方案，并設定周期的滾動時間；當觸發再調度機制的突發事件出現時，實施再調度.將已完成的任務從滾動窗口移除，并把需要緊急處理的任務移入滾動窗口，使當前窗口中的裝卸任務數量保持一定的平衡，場橋進行任務再分配，不斷的重復上述過程，直到所有的裝卸任務全部完成.

假設設定周期性的再調度每間隔30 min調度一次，從0時刻開始，根據已到達場區任務以及任務處理優先權等原則，進行初始調度計劃，各場橋進行任務安排，開始作業；隨著任務的進行，到達的任務會發生變化，任務處理順序也會發生相應變化，假設在時刻20 min時出現某緊急任務需要處理，時刻50 min該任務處理完成，那么，該系統調度時刻為20 min、30 min、50 min、60 min，以此類推，直到所有任務完成.圖2即為任務受到干擾時的處理情況.

圖2 處理干擾的調度示意圖Fig.2 The dealing of the interference

當突發因素出現時，場橋應該優先處理干擾因素，此時應該暫時“封存”原先任務，進行重調度，當干擾因素處理結束，進行場橋重調度，直到任務完成.以需要緊急處理的集裝箱為例.

由于船舶需要緊急離港，該船上的箱子需要及時處理.定義p1為正在作業的任務，p2為待入場任務，其具體步驟如下：

Step1：將需要緊急處理的任務安插到p1之后，同時暫時“封存”p2中的所有待處理的任務；

Step2：計算p1中所有任務的完工時間以及場橋的釋放時間；

Step3：運用遺傳算法進行調度，得到對于緊急處理任務的優化結果；

Step4：當緊急處理的任務被處理完畢后，p2中待處理任務的預期處理順序和服務場橋已經不同.計算緊急處理的任務被安排之后所有場橋的可釋放時刻；

Step5：運用遺傳算法進行再調度，生成新的調度方案.

例如，圖2中從上到下是場橋處理任務的順序，每個圈代表一個任務，圈中的數字代表任務編號，其中，灰色為發生擾動計劃的任務，圖中虛線指任務的擾動計劃.任務初始安排如圖2(a)所示，由于任務進行到100 min時，任務15，16，18，19需要緊急處理，因此，應優先安排，此時，調用GA進行場橋重調度，以在規定時間完成緊急任務的前提下最小化任務延遲量為目標.原來任務11由YC2服務，重調度后置于任務15之后，由YC3處理；任務18，19則安插在YC2處理的任務8和任務13之間，任務13和10也相繼往后移動.即重調度后YC2發生變化的任務處理順序依次為18、19、13、10，而YC3處理完任務16后的任務處理順序由原來的18、 15 、19變為15、11.得到的新調度方案，如圖2中圖(b)所示.其作業流程圖如圖3所示：

圖3 滾動策略調用GA作業流程圖Fig.3 The progress of rolling-horizon decision strategy using GA

2 模型建立

在每個時間窗內建立以任務完成最大延遲量最小化為目標的混合整數規劃模型.本文研究的案例來自一個有4個箱區的堆場，集裝箱均為20英尺，考慮4小時作業時段，數據來自于某港口碼頭實際業務數據.為避免場橋作業中出現干涉，假設單個箱區內同時作業的場橋數不超過兩臺；滾動策略為每小時滾動一次，突發干擾因素只考慮緊急任務情況；每個時段場橋的任務數量不應該超過場橋從當前時間到計劃完成時間的工作能力.前期未完成的任務仍然被視為一個新的任務，該任務的到達時間即為當前滾動周期的開始時間.假設場橋在平行場區間的移動距離按箱區長度計算，在垂直區間的移動設定所有轉彎以及垂直行駛時間固定為3*3.5 min；假設場橋完成一次move(一次存箱或取箱任務)的時間是3 min；無突發干擾因素發生時，每臺場橋在一個時段內只能在某一箱區服務，且場橋必須處理完當前任務才能處理下一個任務.

2.1 基本假設

1) 堆場內用于卸裝作業的場橋型號、司機水平等相同，確保場橋作業效率一致；

2) 集卡運行速度，場橋作業效率均一致；

3) 一個任務組的集裝箱放到同一箱區，來自于同一船舶；

4) 場橋在完成集裝箱任務過程中，集卡的配置數目是充足的；

5) 所有場橋在同一計劃時間段，同時開始和結束該時段的作業.

2.2 參數設計

NP：計劃時間域內計劃時間段總數；

NTt：t計劃時段內集裝箱任務組數量；

NTit：t計劃時間段內集裝箱任務組中包含的集裝箱任務數量i；

Bit：t計劃時間段內集裝箱任務組所在的箱區；

Nc：當前計劃時間段內的新任務組數量；

j： 新的集裝箱任務組；

S： 箱區s的可用容量；

M：需要作業的集裝箱集M={1，2，…，m}；

NC：場區中可用的場橋總數；

k： 場橋k編號；

NTj：當前計劃時間段內新任務組j里的任務數量；

TPit：t計劃時間段內集裝箱任務組i的計劃完成時間；

TRit：t計劃時間段內集裝箱任務組i的實際完成時間；

TPj：當前時段新任務組j的計劃完成時間；

TRj：當前時段新任務組j的實際完成時間；

v： 場橋作業效率；

2.3 決策變量

如果場橋k在t時段內分配給集裝箱任務i，xikt=1；否則，xikt=0.

如果集裝箱任務i放到箱區s，yis=1；否則，yis=0.

2.4 約束條件

j=(1，2，…，NC)，

(1)

i=(1，2，…，NTt)，

(2)

Tli-Tai>0，

(3)

(4)

(5)

i∈(1，2，…，NTt)， t=(1，2，…，NP)，

(6)

(7)

(8)

xikt=0 or 1， t=(1，2，…，NP)，

i=(1，2，…，NTt);k=(1，2，…，NC)，

(9)

TBiot=0 or 1， t=(1，2，…，NP)，

i=(1，2，…，NTt); o=(1，2，…，NTt)，i≠0.

(10)

約束條件(1)表示任意時段內，一臺場橋只能同時服務一個集裝箱任務組；(2)表示任意時段內，一個集裝箱任務組有且只有一臺場橋服務；(3)表示每個集裝箱任務組必須在集卡到達箱區后才開始被服務；(4)表示需要存放的集裝箱總數不大于堆場容量；(5)表示當前時段內總的任務數量等于每個時段內任務數量和；(6)表示任意時段，同一場區同時作業的場橋數不超過兩臺 ；(7)表示任何時段內被分配作業的場橋數量不大于總的場橋數量；(8)表示場橋工作能力不超過集裝箱任務數量；(9)、(10)均是二進制表示.

2.5 目標函數

(NTi(t-1)-NTit)v，

(11)

(12)

(13)

(11)是目標函數，旨在求滾動計劃時段內的任務完成時間的延遲量最小.(12)指當前滾動時段內總的計劃任務量；(13)指當前滾動時段總的任務完成量.

3 算例分析

3.1 遺傳算法

場橋調度問題是一個NP難的問題，計算復雜度很高，很難用現有的研究技術在合理時間內獲得滿意的解.在解決場橋調度問題時，以往的研究中有采用模擬退火算法，禁忌搜索算法以及啟發式算法等方法求解的，而對于滾動策略來說，使用啟發式算法計算量太大，根據參考文獻有學者采用遺傳算法求解并得到較好結果，因此，本文考慮使用改進的遺傳算法來解決該問題.下面是對遺傳算法的具體解決方案解釋.

3.1.1 染色體編碼 本文采用的是二維編碼，分別表示場橋作業順序，以及場橋的任務組作業量.染色體采用整數形式編碼.具體形式如下.

圖4 染色體編碼Fig.4 The chromosome encoding

染色體編碼可理解為：若場橋j在任務i的作業順序是0，表示場橋j不服務任務組i；此時，該基因處的作業量即為0.每條場橋染色體的長度為NT1+Nc.該染色體表示：場橋1給任務組3服務，作業量為20個move(move為場橋作業量的單位，表示場橋經過一次起重和落重，完成一次裝卸任務)，場橋2先為任務組1完成24個move，再給任務組2完成35個move.

3.1.2 種群初始化 種群初始化方法如下流程圖所示，假設種群規模為n，也就是說，要形成完整的種群，需要將該方法重復n次.

圖5 種群初始化Fig.5 The population initialization

3.1.3 適應度函數 適應度函數的公式如下：

(14)

目標函數值越小，適應度函數值越小，個體適應度越高.

3.1.4 父代選擇 父代選擇的步驟為

Step3：計算個體的累計概率.

Step4：產生n個0到1之間的隨機數.

Step5：如果隨機數落在兩個個體的累積概率之間，則選擇累積概率較高的那個個體.

3.1.5 遺傳算子設計 遺傳算子設計步驟如下.

1) 選擇

為了減少整個程序運行時間，本文考慮選擇算子采用較簡單的隨機遍歷選擇策略.具體操作像輪盤賭一樣計算選擇概率ps，只是隨機遍歷選擇法中等距離的選擇體，如圖6所示，設newpoint 為需要選擇的個體數目，進行等距離的選擇個體，選擇指針的距離是1/newpoint ，第一個指針的位置由[0，1/newpoint ]的均勻隨機數決定.

圖6 隨機遍歷選擇法Fig.6 The method of random traversal selection

本文采用整數編碼，一般整數編碼采用普通的單點交叉或者多點交叉方式.為了更好地控制修正發生的概率和修正幅度，本文設計一種基于滑動窗口的兩點交叉算子，其具體思想如下.

Step1： 選取兩個個體作為父代，在選取的父代中按設定的滑動窗口大小內隨機確定兩個交叉點，形成一個交叉的基因片段窗口，基因片段為不超過設定的滑動窗口大小的連續基因組成，如圖7所示.

交換后發現有重復基因(圖中陰影部分標出)；

圖7 根據設定窗口大小選擇基因片段Fig.7 According to the setted window size selecting gene

圖8 交換基因后的染色體Fig.8 The chromosome after exchanging gene

圖9 重復基因修正流程圖Fig.9 The progress of gene repair

圖10 修正過后的子染色體Fig.10 The repaired chromosome

2) 變異

為了避免算法陷入局部最優，設計合理的變異算子使得增加后代多樣性.本文設計了一種非線性變異算子進行染色體變異，表達式為

Offspring=

上式中，A和B分別是變異的上限和下限，r是0到1之間的一個隨機數，N為種群當前的迭代次數，M為種群的最大迭代次數，c為變異的調節參數.場橋作業順序的變異范圍是[0，NT1+Nc].計劃周期開始時已有任務組的作業量變異范圍為[0，NTi1]而周期內新出現任務組的作業量變異范圍為[0，NTk].此外，若染色體某基因的作業順序維為0，則其任務組作業量維也必須為0.

3.1.6 基因修復 在交叉與變異完成后，有可能產生不可行后代，此時需要進行用基因修復.本文設計的基因修復具體規則如下：

規則1 如果場橋j被分配給任務組i，但此時另外一臺場橋正在對任務組i服務，那么場橋j應該被分配給其他沒有場橋作業的任務組.

規則2 如果場橋j被分配給任務組i，但此時已經有兩臺場橋在任務組i所在的箱區作業，那么場橋j應該被分配到另一個任務組，且該任務組所在箱區正在工作的場橋數不大于1.

3.1.7 子代接收策略 在交叉、變異和基因修復完成后，將所有的后代按照適應值排列，并將序號大于種群規模數的后代舍棄.

3.1.8 終止條件設定 當算法的迭代次數達到最大迭代次數時，算法終止.算法的最大迭代次數由實驗決定.

3.2 算例分析—以突發緊急任務為例

本文算例基于一個在4個箱區具有4臺場橋對27個任務組的作業的情景，算例在可作業時間為240 min的時段內進行，在MATLAB上用遺傳算法進行求解.算例輸入數據見表1所示.

表1 算例初始數據

表1中，TN指任務組編號，Slot指任務目標堆存位置，PT指任務組準備時間，V指每個任務組包含任務量.首先，進行無干擾情況下的周期驅動的滾動窗口策略的算例，在MALAB上用遺傳算法求解得到的任務分配方案如圖11所示.

圖11 無干擾情況下場橋調度方案Fig.11 YC schedule without interference

由上圖，可直觀看到，在無干擾情況下，實施周期驅動的滾動策略調度方案，對任務進行合理安排，使得每個滾動窗口內的目標函數最優，使每個窗口內延遲量最小，該方案下，所有任務完成時間為228 min，圖中M指任務組，M右邊第一個數字指所在箱區，后兩位數字代表箱子存放位置，圖中從左向右即為場橋服務的順序.

本文考慮一種基于急件插入情況的突發干擾因素，某時刻由于船舶急需離港，該船上的集裝箱急需處理，此時，應該將屬于該船上的任務作為緊急任務插入，調整場橋分配，重新安排任務.算例設定滾動計劃為60 min進行一次周期滾動，同時，突發任務出現時進行重新調度，定義同一個箱區內的可以集中裝卸的多個任務為一個任務組，任務組作為場橋作業的最小化單位，場橋一次作業叫做一個move.下面進行有干擾情況的算例分析.

由于在任務進行到第100 min時，來自箱區3的任務組15，16，18，19需要在一個小時后處理完，因此進行緊急處理，此時發生重調度計劃，因此，第二次滾動的調度方案受到干擾，進行重調度后的調度方案和無干擾情況進行對比可知，場橋2和場橋3發生重調度，場橋2和場橋3作業路徑分別為：

M207?M217?M201?M314?

M316?M220?M210；

M311?M318?M303?M309?

M305?M212.

而在無干擾情況下，場橋2和場橋3的作業路徑分別為：

M209?M212?M208?M211?

M213?M210；

M317?M320?M314?M316?

M318?M315?M319.

在滿足緊急任務按時完成并使得所有任務完成時間最短，任務延遲量最小的情況下，得到如圖12所示的場橋調度方案，該方案下所有任務完成最短時間為213 min.

圖12 有干擾情況下場橋調度方案Fig.12 YC schedule with interference

4 結論

本文針對場橋動態調度中，由于不確定干擾因素的影響，導致原先的調度方案發生變化這一問題進行研究，提出滾動窗口策略來解決該問題，當突發因素發生時，及時調整調度方案，算例證明，滾動策略能有效解決該問題，由于滾動策略進行的是每個滾動窗口中的優化，從而來實現全局的優化，這種方案能夠節約計算時間，適用于大規模的問題.本文采用改進的遺傳算法，利用MATLAB來求解場橋調度模型.

[1] LI W，WU Y，PETERING M E H，et al. Discrete time model and algorithms for container yard crane scheduling [J]. European Journal of Operational Research，2009，198(1): 165-172.

[2] STAHLBOCK R，VOΒ S. Operations research at container terminals: a literature update[J]. OR Spectrum，2008，30(1):1-52.

[3] ZHANG C Q，WAN Y W，LIU J Y, et al. Dynamic crane deploymention container storage yards[J]. Transportation Research Part B，2002，36(6):537-555

[4] RICHARD J, LIN N, ZHANG C Q. A heuristic for dynamic yard crane deployment in a container terminal[J]. IIE Transactions，2003，35: 161-174

[5] HG W C. Crane scheduling in container yards with inter-crane interference[J]. European Journal of Operational Research，2005，164: 64-78

[6] CHANG D F，WEI Y ，JIANG Z H ，et al. Developing a dynamic rolling-horizon decision strategy for yard crane scheduling[J]. Advanced Engineering Informatics，2011，25: 485-494．

[7] 梁承姬，戴開梅. 基于集裝箱任務組時間窗的堆場場橋調度模型建立與求解[J].河南科學，2013，31(4): 477-483．

[8] 張富生，劉長安. 基于遺傳算法的車間動態調度研究[D].山東：山東大學，2013．

[9] 林志國，王 諾. 基于滾動窗口的集裝箱碼頭泊位動態調度研究[D].遼寧：大連海事大學，2010．

[10] 肖 玲，胡志華. 基于滾動策略的集裝箱碼頭連續泊位與橋吊集成調度[J].計算機應用，2013，33(10)：2969-2973．

[11] HE J L，CHANG D F，WEI J, et al. A hybrid parallel genetic algorithm for yard crane scheduling[J]. Transportation Research Part E，2010，46: 136-155．

[12] 嚴 偉，宓為建，萇道方，等. 一種基于最佳優先搜素算法的集裝箱堆場場橋調度策略[J].中國工程機械學報，2008，6(1):95-100．

[13] KIM H K，LEE M，WANG H H.Sequencing delivery and receiving operations for yard cranes in port container terminals[J]. International Journal of Production Economics，2003，84(3):283-292．

[14] LI W K，WU Y，PETERING M, et al.A continuous time model for multiple yard crane scheduling with last minute job arrivals[J]. Int J Production Economics，2012，136: 332-343．

[15] 劉文君. Memetic算法研究與工程應用[D]. 武漢：華中科技大學，2007．

Research of the yard crane schedule with uncertain interference that based on the rolling-horizon decision strategy

LIANG Chengji，WANG Dianxue，XU Dehong

(Logistics Research Center，Scientific Research Academy，Shanghai Maritime University，Shanghai 201306)

Currently，the “bottleneck” affecting the efficiency of container port handling was transferred from the berth to the yard. A reasonable yard crane schedule can improve the efficiency of yard work，so the research of yard crane schedule has an important effect on the management of container ports. Based on the uncertain interference factors in the yard crane operation，a dynamic rolling-horizon decision strategy was proposed to deal with the problem that how to reduce the uncertain interference factors and thus improve efficiency of yard crane. A mixed integer programming model was established to minimize the maximum delaying time at blocks and the improved Genetic algorithm was used to solve the model. According to the analysis of examples，this algorithm is useful and the dynamic rolling-horizon decision strategy is effective in scheduling the yard crane under uncertain interference factors．

rolling-horizon decision strategy; uncertain disturb factors; yard crane schedule; improved genetic algorithm

2016-04-22.

國家自然科學基金項目(71471110,71301101);上海市科委項目(14170501500).

1000-1190(2016)05-0695-09

F512.5

A

*通訊聯系人. E-mail: wangdianxue519@519.com.