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

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

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

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