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

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

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

【學位級別】：博士

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



本文編號：2895870