帶運(yùn)輸時(shí)間的若干批處理排序問題的研究.pdf

1、本文主要研究帶運(yùn)輸時(shí)間的單機(jī)在線批處理排序問題的算法設(shè)計(jì)及其競爭比分析.每個工件帶有到達(dá)時(shí)間rj,加工時(shí)間乃和運(yùn)輸時(shí)間qj.給定一臺批處理機(jī),它一次可以同時(shí)加工多個工件(稱為一批),每批工件有相同的開工和完工時(shí)間,并且開工后不允許中斷,也不允許插入其他工件,加工時(shí)間等于其中最長工件的加工時(shí)間.工件一旦加工完畢須立即運(yùn)往目的地,目標(biāo)是極小化所有工件最遲到達(dá)目的地的時(shí)間.本文主要考慮兩種情況;運(yùn)輸時(shí)間與加工時(shí)間相關(guān)的批處理在線排序問題和帶運(yùn)

2、輸時(shí)間的工件分類批處理排序問題.
　　 全文共分四章,第一章介紹了與排序問題相關(guān)的一些概念,并概括了本文研究的背景及目前國內(nèi)外關(guān)于批處理排序的研究現(xiàn)狀.
　　 第二章研究運(yùn)輸時(shí)間與加工時(shí)間相關(guān)的在線批處理排序問題.當(dāng)pj≥βqj(β≥0.4472)時(shí),給出了最優(yōu)算法,競爭比為√5+1/2;當(dāng)qj=βpj(β≥0)時(shí),給出算法的競爭比為√β2+2β+4-β+1/2,下界為√β+5/β+1+1/2.
　　 第三章研究