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

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

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

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

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


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



本文編號(hào)：3276516