在線排序是排序論的一個前沿研究方向,近二十年來得到人們廣泛的研究。文獻中有多種不同的在線排序模型,而本文的“在線排序”指的是“時間在線（onlinetime）排序”:工件是按時間到達,并且當(dāng)一個工件到達時,才知道這個工件的具體信息。對在線問題的研究中,決策者在當(dāng)前時刻需要在僅僅知道已經(jīng)到達的工件信息的前提下做出決策。因而,很多在線排序問題是沒有最優(yōu)算法的。人們通常用競爭比來衡量一個在線算法的好壞。我們以最小化目標(biāo)函數(shù)的排序問題為例。在線算法A的競爭比ρA定義為ρA=sup{A（I）/OPT（I）:I是任意一個實例且滿足OPT（I）>0},其中I是排序問題的任意一個實例,A（I）是執(zhí)行了在線算法A得到的實例I的目標(biāo)函數(shù)值,而OPT（I）則是由離線最優(yōu)排序所得到的實例I的目標(biāo)值。因而競爭比ρA≥1,而且ρA越趨近于1,在線算法的性能越好。如果不存在競爭比小于ρA的其他在線算法,我們就說在線算法A是最好可能的。在本文中我們研究了四類帶工件運輸時間的在線排序問題:在線折衷排序問題;工件具有不相容性并考慮工件運輸?shù)脑诰�排序問題;工件的加工時間有限制的在線排序問題;工件具有退化效應(yīng)的在線排序... 

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

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

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

【文章目錄】：
摘要
abstract
第1章 緒論
    1.1 排序問題
    1.2 排序的三參數(shù)表示法
    1.3 在線排序問題
    1.4 相關(guān)文獻
        1.4.1 多目標(biāo)排序
        1.4.2 平行分批排序
        1.4.3 工件帶有運輸時間的排序
        1.4.4 不相容工件組的排序
        1.4.5 工件具有退化效應(yīng)的排序
    1.5 本文的主要結(jié)果
第2章 最小化時間表長和最大運輸完工時間的在線折衷排序問題
    2.1 引言
    2.2 在線算法D-LDT(ρ)
    2.3 算法競爭比的分析
第3章 多個不相容工件組的無界平行批排序問題
    3.1 引言
    3.2 準(zhǔn)備工作
    3.3 算法及其競爭比分析
第4章 不相容工件組已確定的無界平行批排序問題
    4.1 引言
    4.2 準(zhǔn)備工作
    4.3 排序問題Dmax(online, pj= p, Ti= T )
    4.4 排序問題Dmax(online, f )
第5章 加工時間有限制的單機排序問題
    5.1 引言
    5.2 準(zhǔn)備工作
    5.3 問題的下界
    5.4 c = ∞ 的情形
    5.5 c < ∞ 的情形
第6章 單機上考慮運輸?shù)耐嘶ぜ脑诰�排序問題
    6.1 引言
    6.2 準(zhǔn)備工作
    6.3 車輛的容量充分大的情形
        6.3.1 問題的下界
        6.3.2 算法及競爭比分析
    6.4 容量有限制的情形
        6.4.1 問題的下界
        6.4.2 算法及競爭比分析
第7章 結(jié)論與展望
參考文獻
在學(xué)期間學(xué)術(shù)論文發(fā)表情況
致謝


【參考文獻】：
博士論文
[1]具有交貨期或友好釋放時間的在線排序研究[D]. 李文杰.鄭州大學(xué) 2014
[2]工件具有不相容性質(zhì)的機器排序問題[D]. 李士生.鄭州大學(xué) 2012
[3]關(guān)于一些在線分批排序問題的研究[D]. 方陽.華東理工大學(xué) 2011
[4]加工時間非常數(shù)的排序與調(diào)度模型研究[D]. 張新功.上海理工大學(xué) 2010
[5]平行批在線排序問題[D]. 付乳燕.鄭州大學(xué) 2009
[6]多臺平行批處理機在線排序和帶有運輸時間的在線排序[D]. 田記.鄭州大學(xué) 2009
[7]多目標(biāo)分批排序及其相關(guān)課題[D]. 何程.鄭州大學(xué) 2009
[8]工件加工時間可變的現(xiàn)代排序問題[D]. 王吉波.大連理工大學(xué) 2005



本文編號：3276516