航空貨運碼頭裝卸平臺預定問題及算法研究.pdf

1、本文研究了以現(xiàn)代服務業(yè)預訂系統(tǒng)中的實際問題——航空貨運碼頭裝卸平臺預定問題為背景的具有預約到達時間的在線排序問題，不僅考慮了單一任務裝卸平臺的在線預定問題（1|on-line，oj，rj，pj|Cmax），特別地，考慮了其中的特殊情形（1|on-line，oj，rj，pj=p|Cmax），還考慮了多任務裝卸平臺在線預定問題中流水作業(yè)任務的在線預定問題（F2| on-line，oj，rj，pj|Cmax）和開放作業(yè)任務的在線預定問題（O2

2、| on-line，oj，rj，pj|Cmax）。對這些問題，提出了在線貪婪算法:包含任務信息的訂單到達系統(tǒng)后，馬上對任務的加工作出安排，然后再接收下一個訂單。然后分析了在線貪婪算法對各個問題的競爭比，得到了下面的結論:
　　(1)在線貪婪算法對單一任務裝卸平臺的在線預定問題模型化為的1|on-line，oj，rj，pj|Cmax問題的競爭比為2，特別地，當限制條件pj=p時，即對問題1|on-line，oj，rj，pj=p|Cm

3、ax，算法的競爭比達到了3/2;
　　(2)在線貪婪算法對流水作業(yè)任務的在線預定問題模型化為的F2| on-line，oj，rj，pj|Cmax問題的競爭比為2;
　　(3)通過分析任務在機器1，機器2上面的加工情況，得到了機器1和機器2上面空閑加工區(qū)間的一些性質。然后，以此為切入點，分3類情形證明了在線貪婪算法對開放作業(yè)任務的在線預定問題模型化為的O2| on-line，oj，rj，pj|Cmax問題的競爭比為2。