排序論是運(yùn)籌學(xué)與組合最優(yōu)化的重要分支.分批排序是人們十分關(guān)注的現(xiàn)代排序模型;其特點(diǎn)是可將工件分批進(jìn)行加工,每一批工件具有相同的開工時(shí)間和相同的完工時(shí)間.在本文研究的平行分批排序模型中,每一批的加工時(shí)間等于該批中工件的最長(zhǎng)加工時(shí)間.按照每一批可以加工的工件數(shù)目b的限制（稱為批容量）,平行分批排序又可分為批容量有限（b<∞）和批容量無(wú)限（b=∞）兩種情形.在線排序問題是近年來排序論研究的熱點(diǎn)方向;其特點(diǎn)是工件的信息事先并不確定,決策者在沒有獲得所有工件信息之前就必須對(duì)已有工件進(jìn)行排序.本文所研究的在線排序是工件實(shí)時(shí)到達(dá)（over time）的情形,即工件是隨著時(shí)間逐漸到達(dá)的.工件的所有信息在其到達(dá)時(shí)刻才能獲知.針對(duì)在線優(yōu)化問題設(shè)計(jì)的算法稱為在線算法.人們常用競(jìng)爭(zhēng)比來衡量在線算法性能的好壞.對(duì)于一個(gè)極小化目標(biāo)函數(shù)的優(yōu)化問題,我們稱一個(gè)在線算法是ρ-競(jìng)爭(zhēng)的,如果對(duì)于該問題的任意實(shí)例,算法所產(chǎn)生的目標(biāo)函數(shù)值不大于最優(yōu)離線算法所產(chǎn)生的目標(biāo)函數(shù)值的ρ倍.在線算法A的競(jìng)爭(zhēng)比定義為ρA=inf{ρ:A是ρ-競(jìng)爭(zhēng)的}.不難看出,ρA總是大于等于1的.由于信息的缺乏,ρA=1的情形只有在很特殊的問題上... 

【文章來源】：鄭州大學(xué)河南省 211工程院校

【文章頁(yè)數(shù)】：91 頁(yè)

【學(xué)位級(jí)別】：博士

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 排序理論簡(jiǎn)介
    1.2 算法和計(jì)算復(fù)雜性
    1.3 排序的相關(guān)知識(shí)及進(jìn)展
    1.4 本文結(jié)果
第2章 允許有限重啟的多臺(tái)平行批處理機(jī)上的排序問題
    2.1 引言
    2.2 算法A（α）及相應(yīng)排序的性質(zhì)
    2.3 問題的下界
    2.4 在線算法
第3章 允許有限重啟的單臺(tái)平行批處理機(jī)上的排序問題
    3.1 引言
    3.2 批容量為2時(shí)問題的下界
    3.3 批容量為2時(shí)的最好可能的在線算法及競(jìng)爭(zhēng)比分析
    3.4 批容量大于2時(shí)問題的下界
    3.5 批容量大于2時(shí)最好可能的在線算法及競(jìng)爭(zhēng)比分析
第4章 允許重啟的單臺(tái)平行批處理機(jī)上的排序問題
    4.1 引言
    4.2 批容量為3時(shí)問題的下界
    4.3 批容量為3時(shí)的最好可能的在線算法及競(jìng)爭(zhēng)比分析
    4.4 批容量大于3時(shí)問題的下界
    4.5 批容量大于3時(shí)的最好可能的在線算法及競(jìng)爭(zhēng)比分析
    4.6 允許κ-有限重啟（κ≥2）時(shí)的問題
第5章 允許有限重啟且?guī)в羞\(yùn)輸?shù)钠叫信幚頇C(jī)上的排序問題
    5.1 引言
    5.2 批容量為2時(shí)問題的下界
    5.3 批容量為2時(shí)的最好可能的在線算法及競(jìng)爭(zhēng)比分析
    5.4 批容量大于2時(shí)問題的下界
    5.5 批容量大于2時(shí)的最好可能的在線算法及競(jìng)爭(zhēng)比分析
結(jié)論與展望
參考文獻(xiàn)
個(gè)人簡(jiǎn)歷、在學(xué)期間發(fā)表的學(xué)術(shù)論文與研究成果
致謝



本文編號(hào)：2895870