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

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

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

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